Posted by 目录
T1
http://codeforces.com/contest/1200/problem/A
题意
略。
题解
按题意模拟即可；
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <cstdio> inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=1e5+10; int n; char a[MAXN]; bool vis[10]; int main() { n=read(); scanf("%s",a+1); for(int i=1;i<=n;++i) { if(a[i]=='L') { for(int j=0;j<=9;++j) if(!vis[j]) { vis[j]=true; break; } } else if(a[i]=='R') { for(int j=9;~j;--j) if(!vis[j]) { vis[j]=true; break; } } else vis[a[i]-'0']=false; } for(int i=0;i<=9;++i)printf("%d",vis[i]); puts(""); return 0; } |
T2
http://codeforces.com/contest/1200/problem/B
题意
有$n$个柱子，每个柱子由高度相同的块组成，从第一个柱子开始往后跳，能跳到下一个柱子的条件是$|h_i-h_{i+1}|\leq k$，有一个无限大的背包，每次可以从柱子上取一块下来或者从背包里取一块放到柱子上以改变柱子的高度；
求最后能不能跳到第$n$个柱子。
题解
贪心，每次尽量从柱子上取块，注意柱子取空了就不能再取了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <cstdio> #include <cmath> #include <algorithm> typedef long long LL; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=110; int n,k,a[MAXN]; LL m; int main() { int T=read(); while(T--) { n=read();m=read();k=read(); bool flag=true; for(int i=1;i<=n;++i) { a[i]=read(); if(!flag||i==1)continue; if(a[i]-k-a[i-1]>m)flag=false; if(a[i]-k-a[i-1]>0)m-=a[i]-k-a[i-1]; else m+=std::min(a[i-1],a[i-1]-a[i]+k); } flag?puts("YES"):puts("NO"); } return 0; } |
T3
http://codeforces.com/contest/1200/problem/C
题意
由内外两层构成的环，内外层之间没有墙，但是内层和外层分别被墙等分成$n,m$块，$12$点方向一定有一堵墙，现在把块编号，问能否从某一块走到另一块。
题解
观察样例，发现两块之间不能到达的条件是内外层的墙在某一处重合使得路径被隔断；
那么隔断的位置在哪呢？容易想到是$gcd(n,m)$的整数倍；
于是可以想到重合的墙将这个环分为几个大块，只需要判断询问的两块是不是在同一个大块里即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <cstdio> #include <iostream> typedef long long LL; inline LL read() { char ch=getchar(); LL x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } LL n,m,q; LL gcd(LL a,LL b) { return b?gcd(b,a%b):a; } int main() { n=read();m=read();q=read(); LL t=gcd(n,m); n/=t;m/=t; for(int i=1;i<=q;++i) { LL sx=read(),sy=read()-1,ex=read(),ey=read()-1; LL t1=sx==1?sy/n:sy/m,t2=ex==1?ey/n:ey/m; if(t1==t2)puts("YES"); else puts("NO"); } return 0; } |
T4
http://codeforces.com/contest/1200/problem/D
题意
一个画布上只有黑白两种像素块，能通过一个边长为$k$的橡皮把一块全变成白色；
求问只用一次橡皮的条件下，最多能产生多少个白像素条？（全为白的行和全为白的列）。
题解
可以通过$O(1)$判断在某个位置用一次橡皮能否将某一个行或者列变成白像素条（这行或者列的最边缘的两个黑像素块都能被橡皮覆盖）；
计算列的答案：从$(1,1)$开始，先$O(k)$计算结果，然后每次向右移动一格橡皮，判断左右两列答案是否更新；
到下一行，重复上述操作；
特别注意本来就是白的像素条；
计算行的答案同理，复杂度$O(n^2)$。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <cstdio> #include <algorithm> typedef long long LL; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=2010; int n,k,lx[MAXN],rx[MAXN],ly[MAXN],ry[MAXN],ansx[MAXN][MAXN],ansy[MAXN][MAXN],ans,blkx,blky; char a[MAXN][MAXN]; bool isbx[MAXN],isby[MAXN]; int main() { n=read();k=read(); for(int i=1;i<=n;++i) { scanf("%s",a[i]+1); for(int j=1;j<=n;++j) { if(a[i][j]=='W')continue; if(!lx[i])lx[i]=j; rx[i]=j; } if(!lx[i])++blkx; } for(int j=1;j<=n;++j) { for(int i=1;i<=n;++i) { if(a[i][j]=='W')continue; if(!ly[j])ly[j]=i; ry[j]=i; } if(!ly[j])++blky; } for(int i=1;i<=n-k+1;++i) { int cnt=blkx; for(int j=1;j<=k;++j) { if(ly[j]>=i&&ry[j]<=i+k-1) { ++cnt; isby[j]=true; } } ansx[i][1]=cnt; for(int j=2;j<=n-k+1;++j) { if(isby[j-1]) { isby[j-1]=false; --cnt; } if(ly[j+k-1]>=i&&ry[j+k-1]<=i+k-1) { isby[j+k-1]=true; ++cnt; } ansx[i][j]=cnt; } for(int j=n-k+1;j<=n;++j)isby[j]=false; } for(int j=1;j<=n-k+1;++j) { int cnt=blky; for(int i=1;i<=k;++i) { if(lx[i]>=j&&rx[i]<=j+k-1) { ++cnt; isbx[i]=true; } } ansy[1][j]=cnt; for(int i=2;i<=n-k+1;++i) { if(isbx[i-1]) { isbx[i-1]=false; --cnt; } if(lx[i+k-1]>=j&&rx[i+k-1]<=j+k-1) { isbx[i+k-1]=true; ++cnt; } ansy[i][j]=cnt; } for(int i=n-k+1;i<=n;++i)isbx[i]=false; } for(int i=1;i<=n-k+1;++i) for(int j=1;j<=n-k+1;++j) ans=std::max(ans,ansx[i][j]+ansy[i][j]); printf("%d\n",ans); return 0; } |
T5
题意
如果前单词的后缀和后单词的前缀相同，那么可以将这两个单词合并（要求最长的相同前后缀）；
给出一句话，求合并的结果，区分大小写。
题解
字符串哈希，暴力。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <cstdio> #include <algorithm> #include <cstring> typedef long long LL; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=1e6+10,MOD=998244353; int n,suml,len,hash[MAXN],hash1[MAXN],mi[MAXN],invmi[MAXN],lenb; char a[MAXN],b[MAXN]; int main() { n=read()-1; scanf("%s",a+1); lenb=len=strlen(a+1); strcpy(b+1,a+1); for(int i=1;i<=len;++i) hash[i]=( (LL)hash[i-1]*126+a[i] )%MOD; mi[0]=1; for(int i=1;i<=1000000;++i) mi[i]=(LL)mi[i-1]*126%MOD; while(n--) { scanf("%s",a+1); len=strlen(a+1); for(int i=1;i<=len;++i) hash1[i]=( (LL)hash1[i-1]*126+a[i] )%MOD; int i; for(i=len;i;--i) if(hash1[i]==(hash[lenb]-(LL)hash[lenb-i]*mi[i]%MOD+MOD)%MOD)break; for(int j=1;j<=len-i;++j) { b[lenb+j]=a[i+j]; hash[lenb+j]=( (LL)hash[lenb+j-1]*126+b[lenb+j] )%MOD; } lenb+=len-i; } printf("%s\n",b+1); return 0; } |
T6
题意
有向图，每个点有点权，一个点连向$m_i$个点，分别是$e_0,e_1,\dots e_{m_i-1}$，初始手上有个权值$x$，每次到一个点之后把点权加到手上这个权值里，之后走向$e_{x}$。
会陷入死循环里，问从某一个点走到的死循环的大小是多少。
题解
首先对于一个点来说，手上权值的有效状态最多有$lcm(1,2,\dots,10)=2520$个，于是对于每一个状态建立一个点，总共有$2520n$个点；
之后就可以dfs判断循环了，注意原始图中的一个可能在环中出现多次，需要去重。
PS:set去重会RE。
加记忆化搜索，复杂度$O(2520n+q)$。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <cstdio> #include <vector> #include <cstring> #define pii pair<int,int> inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=1010,MOD=2520; int n,k[MAXN],a[MAXN][3000],e[MAXN][11],cnt[MAXN]; bool vis[MAXN][3000]; std::pii pre[MAXN][3000]; int dfs(int u,int val) { if(a[u][val])return a[u][val]; vis[u][val]=true; int vval=(val+k[u])%MOD,v=e[u][vval%e[u][0]+1]; if(a[v][vval])return a[u][val]=a[v][vval]; if(!vis[v][vval]) { pre[v][vval]=std::make_pair(u,val); return a[u][val]=dfs(v,vval); } std::pii tmp=std::make_pair(u,val); memset(cnt,0,sizeof(cnt)); while(tmp!=std::make_pair(v,vval)) { if(!cnt[tmp.first]) { cnt[tmp.first]=true; ++a[u][val]; } tmp=pre[tmp.first][tmp.second]; } if(!cnt[tmp.first]) { cnt[tmp.first]=true; ++a[u][val]; } return a[u][val]; } int main() { n=read(); for(int i=1;i<=n;++i) k[i]=(read()%MOD+MOD)%MOD; for(int i=1;i<=n;++i) { int m=read(); for(int j=1;j<=m;++j) e[i][j]=read(); e[i][0]=m; } int q=read(); while(q--) { int x=read(),y=(read()%MOD+MOD)%MOD; printf("%d\n",dfs(x,y)); } return 0; } |