A题
对于两个分别求解到每一位的时间，看看是否有相等的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int d1[N],d2[N]; int main(){ ios::sync_with_stdio(false); int n,a,x,b,y; cin>>n>>a>>x>>b>>y; int i; int cnt=0; while(a!=x){ d1[a]=cnt; cnt++; a++; if(a==n+1){ a=1; } } d1[a]=cnt; cnt=0; while(b!=y){ d2[b]=cnt; cnt++; b--; if(b==0){ b=n; } } d2[b]=cnt; int flag=0; for(i=1;i<=n;i++){ if(d1[i]&&d2[i]&&(d1[i]==d2[i])){ flag=1; break; } } if(flag){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } return 0; }
B题
找出两对，他们的数各不相同，如果找不出，那么一定成立，因为我们只要取一对中的两个数就成功了
如果找出来了，那么答案一定是他们的组合，如果组合完还是没有答案，那么无解，我们只要枚举第一个pair找另一个pair即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=3e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int a[N][2]; int n,m; bool chk(int x,int y){ int i; for(i=1;i<=m;i++){ if(a[i][0]!=x&&a[i][1]!=x&&a[i][0]!=y&&a[i][1]!=y) return false; } return true; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; int i; int p=0; for(i=1;i<=m;i++){ cin>>a[i][0]>>a[i][1]; if(a[i][0]!=a[1][0] && a[i][0]!=a[1][1] && a[i][1]!=a[1][0] && a[i][1]!=a[1][1]) p=i; } if(!p){ cout<<"YES"<<endl; return 0; } if(chk(a[1][0],a[1][1]) || chk(a[1][0],a[p][0]) || chk(a[1][0],a[p][1]) || chk(a[1][1],a[p][0]) || chk(a[1][1],a[p][1])) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }
C题
因为每次取的个数没有限制，所以存在二分性，因此二分答案
check函数里，从第一位开始，如果他大于前面的，那最好能变成前面一样的，否则不变
如果小于前面的，那变成和前面一样是最优的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=3e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int a[N],lst[N]; int b[N]; int n,m; bool check(int x){ int i; for(i=1;i<=n;i++) b[i]=a[i]; for(i=1;i<=n;i++){ if(b[i]>b[i-1]){ if(m-b[i]+b[i-1]<=x){ b[i]=b[i-1]; } } else{ if(b[i-1]-b[i]>x) return false; b[i]=b[i-1]; } } return true; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; int i; for(i=1;i<=n;i++){ cin>>a[i]; } int l=0,r=1e9; while(l<r){ int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<l<<endl; return 0; }
D题
爆搜猜测当串变长时一定有答案，因此暴力就行，复杂度时O（N）的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=3e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int main(){ ios::sync_with_stdio(false); string s; cin>>s; int i; int n=s.size(); s=" "+s; int l,r; r=n+1; ll ans=0; for(i=n;i>=1;i--){ for(int len=1;i+2*len<=n;len++){ if(s[i]==s[i+len]&&s[i]==s[i+2*len]){ r=min(r,i+2*len); break; } } ans+=max(0ll,n+1-1ll*r); } cout<<ans<<endl; return 0; }
E题
这个套路比较经典，容易被看出来，首先我们观察到是与，因此可以想到按位维护
又因为中间的个数不限，所以可以想到状态为f[i][j]，表示在i位之前的第j位为1并且能更新到i这个位置的最大值
对于这个我们需要维护对于每个j位为1的最大位置在哪
之后跑出所有状态更新即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=3e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int n; int g[N][28],a[N]; int f[N][28]; int main(){ ios::sync_with_stdio(false); int n,q; cin>>n>>q; int i,j,k; for(i=1;i<=n;i++){ cin>>a[i]; } for(i=1;i<=n;i++){ for(j=0;j<26;j++){ if(a[i-1]>>j&1){ g[i][j]=i-1; } else{ g[i][j]=g[i-1][j]; } } } for(i=1;i<=n;i++){ for(j=0;j<26;j++){ for(k=0;k<26;k++){ if(a[i]>>k&1){ int pre=g[i][k]; f[i][j]=max(f[i][j],f[pre][j]); if(a[pre]>>j&1){ f[i][j]=max(f[i][j],pre); } } } } } while(q--){ int l,r; cin>>l>>r; int flag=0; for(i=0;i<26;i++){ if(a[l]>>i&1){ if(f[r][i]>=l){ flag=1; break; } } } if(flag){ cout<<"Shi"<<endl; } else{ cout<<"Fou"<<endl; } } return 0; }