话说这几天怎么光考试啊aaa
T1 Jelly的难题1
这题是一个纯纯的BFS（其实与马的遍历十分相像【其实改改就行】）
#include#include #include #include #include #include #include #include #include #include //一堆头文件 using namespace std;inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+c-'0'; c=getchar(); } return X*w;}//快读struct node{ int x,y,step; node(int x,int y,int step):x(x),y(y),step(step){};};//表示当前(x,y)以及当前所花的步数 int n,m,sx,sy;long long sum,maxn;queue q;char s[600][600],a;int st[600][600];int used[600][600];int mx[5]={ 0,0,0,1,-1};//x的移动 int my[5]={ 0,1,-1,0,0}; //y的移动 bool check(int x,int y){ return ((1<=x&&x<=n)&&(1<=y&&y<=m)&&s[x][y]!='o');}//判断是否出界 void bfs(){ used[sx][sy]=1; //标记已走 q.push(node(sx,sy,0)); //第一个入队(即开始 BFS) st[sx][sy]=0; //起点肯定为 0啊 while(!q.empty()) { node u=q.front(); //取队首,对队列进行操作 q.pop(); //弹出队首 for(int i=1;i<=4;i++) //四个方向 { int nx=u.x+mx[i]; int ny=u.y+my[i]; if(check(nx,ny)&&!used[nx][ny]) //表示未走过且满足不出界 { used[nx][ny]=1; //标记走过 st[nx][ny]=u.step+1; //步数加 1 q.push(node(nx,ny,u.step+1)); //继续入队 } } }}//就是 BFS,无他,唯手熟尔 int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a=getchar(); while(a!='*'&&a!='o'&&a!='#') { a=getchar(); } s[i][j]=a; if(s[i][j]=='*') { sx=i; sy=j; } } } //读入(可能有点麻烦) bfs(); //进行 BFS for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(st[i][j]>maxn) { maxn=st[i][j]; } } } //找出最大时间 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(st[i][j]!=0) { st[i][j ]=maxn+1-st[i][j]; sum+=st[i][j]; } } } //通过操作计算总卷数 printf("%lld\n%lld",maxn,sum%19260817); //不能忘记取模 return 0;}
T2【音乐会】二重变革
首先我们看到数据范围，发现如果就按照程序这么跑肯定会T成狗
所以我们进行一波分析
如果最后停止（按照所给的程序），则所有数在最后都会相等
那么我们那n为2的情况来模拟一下，发现这tm就是更相减损术啊
那么这题就好做了。
#includeusing namespace std;inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+c-'0'; c=getchar(); } return X*w;}int gcd(int a,int b){ if(b==0) { return a; } else { return gcd(b,a%b); }}int n;int x[2];int ans;int main(){ n=read(); x[0]=read(); ans=x[0]; for(int i=2;i<=n;i++) { x[1]=read(); ans=gcd(ans,x[1]); } ans*=n; printf("%d",ans); return 0;}
边算边gcd就行啊。
T3【音乐会】道路千万条
这题我看到说明的时候就不想做了，后来发现好像可以线段树
#includeusing namespace std;inline int read(){ int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+c-'0'; c=getchar(); } return X*w;}inline char gc(){ char c; do { c=getchar(); } while(c==' '||c=='\n'||c=='\r'||c=='\0'||c=='\t');}int n;char s[501],ops[501];long long t[501][501],f[501][501];const int mod=998244353;pair exgcd(long long a,long long b){ if(b==0) { return make_pair (1,0); } pair rtn=exgcd(b,a%b); rtn.first^=rtn.second^=rtn.first^=rtn.second; rtn.second-=a/b*rtn.first; return rtn;}int main(){ n=read(); for(int i=1;i<=n-1;i++) { s[i]=gc(); ops[i]=gc(); } s[n]=gc(); for(int i=1;i<=n;i++) { if(s[i]=='t') { t[i][i]=1,f[i][i]=0; } else { f[i][i]=1,t[i][i]=0; } } for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=i;k
最后才只有205分。。。（第三题的大骗分竟然才5分）