话说这几天怎么光考试啊aaa
T1 Jelly的难题1
这题是一个纯纯的BFS（其实与马的遍历十分相像【其实改改就行】）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<iomanip> #include<string> #include<algorithm> #include<cstdlib> #include<queue> #include<stack> //一堆头文件 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<node> 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 %lld",maxn,sum%19260817); //不能忘记取模 return 0; }
T2【音乐会】二重变革
首先我们看到数据范围，发现如果就按照程序这么跑肯定会T成狗
所以我们进行一波分析
如果最后停止（按照所给的程序），则所有数在最后都会相等
那么我们那n为2的情况来模拟一下，发现这tm就是更相减损术啊
那么这题就好做了。
#include<bits/stdc++.h> 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; } 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【音乐会】道路千万条
这题我看到说明的时候就不想做了，后来发现好像可以线段树
#include<bits/stdc++.h> 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; } inline char gc() { char c; do { c=getchar(); } while(c==' '||c==' '||c==' '||c==' '||c==' '); } int n; char s[501],ops[501]; long long t[501][501],f[501][501]; const int mod=998244353; pair<long long,long long>exgcd(long long a,long long b) { if(b==0) { return make_pair<long long,long long>(1,0); } pair<long long,long long>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<j;k++) { if(ops[k]=='&') { t[i][j]=(t[i][j]+(t[i][k]*t[k+1][j])%mod)%mod; f[i][j]=(f[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod+(f[i][k]*f[k+1][j])%mod)%mod; } if(ops[k]=='|') { t[i][j]=(t[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod+(t[i][k]*t[k+1][j])%mod)%mod; f[i][j]=(f[i][j]+(f[i][k]*f[k+1][j])%mod)%mod; } if(ops[k]=='^') { t[i][j]=(t[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod)%mod; f[i][j]=(f[i][j]+(f[i][k]*f[k+1][j])%mod+(t[i][k]*t[k+1][j])%mod)%mod; } } } } cout<<(t[1][n]*((exgcd(t[1][n]+f[1][n]%mod,mod).first%mod+mod)%mod))%mod; return 0; }
最后才只有205分。。。（第三题的大骗分竟然才5分）