SMU Summer 2023 Contest Round 4
思路：满足有8，且8后有大于等于11个数
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<char,int>PCI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ int n;cin>>n; string s;cin>>s; for(int i=0;i<s.size()&&(n-i)>=11;++i){ if(s[i]=='8'){ cout<<"YES\n";return ; } } cout<<"NO\n"; return ; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }
思路：交互题，提问4个问题：（i，j），给出ai*aj，求原序列。提问（1，2）（2，3）可知a1，a2，a3，提问（4，5）（5，6）可知a4，a5，a6。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<char,int>PCI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ vector<int>ve(4),ans; int h[6]={4,8,15,16,23,42}; vector<PII>g; int idx=0; for(int i=1;i<=4;++i){ if(i<=2){ cout<<"? "<<i<<" "<<i+1<<endl; } else cout<<"? "<<i+1<<" "<<i+2<<endl; fflush(stdout); cin>>ve[idx++]; } for(int i=0;i<4;++i){ bool ok=false; for(int x=0;x<6;++x){ for(int y=0;y<6;++y){ if(h[x]*h[y]==ve[i]){ g.push_back({h[x],h[y]});ok=true;break; } }if(ok)break; } } int c; if(g[0].first==g[1].first||g[0].first==g[1].second)c=g[0].first; else c=g[0].second; if(g[0].first==c)ans.push_back(g[0].second); else ans.push_back(g[0].first); ans.push_back(c); if(g[1].first==c)ans.push_back(g[1].second); else ans.push_back(g[1].first); if(g[2].first==g[3].first||g[2].first==g[3].second)c=g[2].first; else c=g[2].second; if(g[2].first==c)ans.push_back(g[2].second); else ans.push_back(g[2].first); ans.push_back(c); if(g[3].first==c)ans.push_back(g[3].second); else ans.push_back(g[3].first); cout<<"! "; for(int i=0;i<ans.size();++i){ cout<<ans[i]; if(i!=ans.size()-1)cout<<" "; else cout<<endl; } return ; } signed main(){ //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; }
思路：并查集维护每个集合，统计集合里元素个数
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<char,int>PCI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; vector<int>fa; int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } void solve(){ int n,m;cin>>n>>m; fa=vector<int>(n+1); for(int i=1;i<=n;++i)fa[i]=i; for(int i=1;i<=m;++i){ int k;cin>>k; for(int j=0,x,pre;j<k;++j){ cin>>x; if(j){ int a=find(x),b=find(pre); if(a!=b)fa[a]=b; } pre=x; } } map<int,int>mp; for(int i=1;i<=n;++i){ int a=find(i); mp[a]++; } for(int i=1;i<=n;++i){ int a=find(i); cout<<mp[a]<<' '; } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; }
思路：用栈找出每一对括号，同一深度的括号染一个色即可
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<char,int>PCI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; int n; string s; vector<int>clo; vector<int>r; void dfs(int L,int R,int c){ if((R-L)<=1)return ; for(int i=L+1;i<=R;++i){ if(r[i]){ clo[i]=c;clo[r[i]]=c; dfs(i,r[i],!c); i=r[i]; } } } void solve(){ cin>>n; cin>>s; clo=vector<int>(n); r=vector<int>(n,0); stack<int>st; for(int i=0;i<n;++i){ if(s[i]=='('){ st.push(i); }else{ r[st.top()]=i; st.pop(); } } for(int i=0;i<n;++i){ if(r[i]){ clo[i]=1;clo[r[i]]=1; dfs(i,r[i],0); i=r[i]; } } /*for(int i=0;i<n;++i){ if(r[i])clo[r[i]]=clo[i]; }*/ for(int i=0;i<n;++i)cout<<clo[i]; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; }
思路：
f（i，j）表示删去值在[i，j]的所有数后的序列为不递减的序列，问一共有多少个这种序列。
单调性：若f（i，j）满足条件，则f（x，y）也满足。（x<=i，y>=j）
若f（i，j）满足条件，则值在[1，i-1]和[j+1，x]的数的序列一定为不递减序列；找出最大的pl和最小的pr，使得值在[1，pl-1]和[pr+1，x]的序列一定为不递减序列；那么i的范围即为[1，pl]，j的范围即为[pr，x]；
枚举i，由单调性找出最小的j，每次答案增加x-j+1；
由于i递增，j也是递增的，用双指针维护i，j；
判定序列不递减条件：值在[1，i-1]的数的最大下标 小于 值在[j+1，x]的数的最小下标
维护每个数出现的最大和最小位置，进而维护值在[1，i]的数中的最大下标，和值在[j+1，x]的数中的最小下标
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n,x;cin>>n>>x; vector<int>a(n+1); for(int i=1;i<=n;++i)cin>>a[i]; vector<int>l(x+2,INF),r(x+2,-1),ll(x+2,INF),rr(x+2,-1); for(int i=1;i<=n;++i){ r[a[i]]=max(r[a[i]],i); l[a[i]]=min(l[a[i]],i); } for(int i=1;i<=x;++i){ rr[i]=max(r[i],rr[i-1]); } for(int i=x;i>=1;--i){ ll[i]=min(l[i],ll[i+1]); } int pl=1,pr=x,ans=0; while(pl<=x&&rr[pl-1]<=l[pl])pl++; while(pr>=1&&r[pr]<=ll[pr+1])pr--; for(int i=1,j=pr;i<=pl;++i){ while(j<=x&&(j<i||rr[i-1]>ll[j+1]))j++; ans+=(x-j+1); } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }