A
签到,竟然还WA了一次,我忏悔(
#include<bits/stdc++.h> using namespace std; const int N = 130; int a[N]; int main(){ int n,k; cin>>n>>k; for(int i = 1; i <= k; i++){ int x; cin>>x; } for(int i = 1; i <= n - k; i++){ cin>>a[i]; } for(int i = 1; i <= n; i++){ cout<<a[i]<<" "; } }
B
模拟,没啥难度
#include<bits/stdc++.h> using namespace std; const int N = 130; int a[N]; int main(){ int H,M; cin>>H>>M; int lt = H / 10, ld = H % 10, rt = M / 10, rd = M % 10; while(1){ if(lt * 10 + rt < 24 && ld * 10 + rd < 60){ if(lt != 0){ cout<<lt; } cout<<ld<<" "; if(rt != 0){ cout<<rt; } cout<<rd; break; } else { rd++; if(rd >= 10){ rt++; rd = 0; } if(rt >= 6){ ld++; rt = 0; } if(ld >= 4 && lt == 2){ ld = 0; lt = 0; } else { if(ld >= 10){ lt++; ld = 0; } } } } }
C
大概意思就是有一堆Follow关系,然后1操作A Follow B,2操作B 取消Follow A,3操作查询AB是否互关。
用Map存一下关系就行了,查询就是确认是否{A, B}和{B, A}都被标记过。
#include<bits/stdc++.h> using namespace std; const int N = 130; map<pair<int, int>, bool> mp; int main(){ int n,q; cin>>n>>q; for(int i = 1; i <= q; i++){ int op,a,b; cin>>op>>a>>b; if(op == 1){ mp[{a ,b}] = true; } if(op == 2){ mp[{a ,b}] = false; } if(op == 3){ if(mp[{a ,b}]&&mp[{b, a}]){ cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } } }
D
感觉和上一题一样,用Map存一下就完事了
但是Map如果用clear来清空会超时(O(N)),直接重新赋值就能过了
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 10; unordered_map<int, int> py; int fg = 0; signed main(){ int n; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; py[i] = x; } int q; cin>>q; for(int i = 1; i <= q; i++){ int op; cin>>op; if(op == 1){ int x; cin>>x; fg = x; py = unordered_map<int, int>(); } if(op == 2){ int i,x; cin>>i>>x; py[i] += x; } if(op == 3){ int x; cin>>x; cout<<fg + py[x]<<endl; } } }
E
类似队列,对于每一行(指可以放下黑框的行),每次移动框的时候前面的加进来后面的退出去,统计出来的就是答案了
#include<bits/stdc++.h> using namespace std; int H,W,n,h,w,ans; const int N=310; int a[N][N],tong[N]; void jia(int x){ans+=(tong[x]==0);++tong[x];} void jian(int x){--tong[x];ans-=(tong[x]==0);} int main() { cin>>H>>W>>n>>h>>w; for(int i=1;i<=H;++i) for(int j=1;j<=W;++j)scanf("%d",&a[i][j]); for(int i=1;i<=H-h+1;++i) { for(int j=0;j<=n;++j)tong[j]=0;ans=0; for(int j=1;j<=H;++j) for(int k=1;k<=W;++k) if(i<=j&&j<=i+h-1&&1<=k&&k<=w)continue; else jia(a[j][k]); for(int j=1;j<=W-w+1;++j) { if(j==W-w+1) { printf("%d\n",ans); } else { printf("%d ",ans); for(int k=1;k<=h;++k)jia(a[i+k-1][j]),jian(a[i+k-1][j+w]); } } } return 0; }
F
状压DP+博弈论性质
对于一种局面,如果接下来的所有局面有先手必败,那么先手必胜,如果接下来所有局面都先手必胜,那么先手必败。
因为先手的人可以选第一次开始的局面...所以先手的要求就是有下一手必败就行了,而对后手来说,则需要所有的局面都满足条件才行。
那么很明显所有的局面就可以递推出来了
剩下就是一个状压DP,16这个范围还是很关键的,下次应该想到状压的。。。
贴个Editorial的代码,写得很好(https://atcoder.jp/contests/abc278/editorial/5250)
#include<bits/stdc++.h> using namespace std; #define int long long int const N=16; int f[1<<N][27],n; string s[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for (int i=0;i<n;++i) cin>>s[i]; for (int i=(1<<n)-1;~i;--i) for (int k=0;k<26;++k){ int flg=1; for (int l=0;l<n;++l){ if ((1<<l)&i) continue; if (s[l][0]!='a'+k) continue; if (f[i|(1<<l)][s[l][s[l].length()-1]-'a']){flg=0;break;} } f[i][k]=flg; } for (int i=0;i<n;++i) if (f[1<<i][s[i][s[i].length()-1]-'a']){ cout<<"First\n"; return 0; } cout<<"Second\n"; return 0; }