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;
}
View Code
思路：交互题，提问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;
}
View Code
思路：并查集维护每个集合，统计集合里元素个数
#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;
}
View Code
思路：用栈找出每一对括号，同一深度的括号染一个色即可
#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;
}
View Code
思路：
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;
}
View Code
标签：Summer,typedef,const,Contest,int,SMU,long,solve,ll From： https://www.cnblogs.com/bible-/p/17561058.html