codeforces round 149 div2(a,b,c,d)

本文主要是介绍codeforces round 149 div2(a,b,c,d)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

手速场，可惜我傻逼卡$c$了
题目链接

A

#include<bits/stdc++.h>using namespace std;#define int long long
#define PII pair<int,int>void solve()
{int n,k;cin>>n>>k;if(n<k){cout<<1<<'\n';cout<<n<<'\n';}if(n==k){cout<<2<<'\n';cout<<n-1<<' '<<1<<'\n';}if(n>k){if(n%k!=0){cout<<1<<'\n';cout<<n<<'\n';return;}cout<<2<<'\n';cout<<n-1<<' '<<1<<'\n';}
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

B

#include<bits/stdc++.h>using namespace std;#define int long long
#define PII pair<int,int>void solve()
{int n;cin>>n;string str;cin>>str;int cnt=0;str=' '+str;int ans=INT_MIN;for(int i=1;i<=str.size();i++){cnt=1;while(str[i]==str[i+1]&&i+1<=n)cnt++,i++;ans=max(ans,cnt);}cout<<ans+1<<'\n';
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

C

题目大意

给定仅包含$1,0,?$的字符串$s$，允许把$?$变为$1$或$0$。定义操作为翻转任意连续字串。定义字符串代价为，令整个串呈非降序的操作数量

思路

结论：当$?$在首位，则变为$0$，若在后面，则等于前面的字符
证明：考虑$?$的位置，当在首位的时候，令其为$0$对总操作数没有贡献
在后面的时候，若$?$前面是$1$，则令其为$1$对总操作数没有贡献，前面是$0$则$1$同理

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{string str;cin>>str;if(str[0]=='?')str[0]='0';for(int i=1;i<str.size();i++){if(str[i]=='?')str[i]=str[i-1];}cout<<str<<'\n';
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

D

题目大意

如果一个括号序列符合以下两个条件中的一个，那么它是优美的：

1、序列的任意一个前缀中，左括号的个数不少于右括号的个数，且整个序列中，左括号的个数等于右括号的个数。

2、序列的任意一个前缀中，右括号的个数不少于左括号的个数，且整个序列中，左括号的个数等于右括号的个数。

给定一个括号序列，你需要把它分成若干组，使得每一组的括号构成的序列都是优美的。求最少需要分成多少组，并输出分组方案。如果无解，则输出$-1$
——翻译来自洛谷Bracket Coloring

思路

括号匹配
把$0,1$赋给$),($，统计前缀和

所有绿色是一种，所有红色是一种
再特判一下括号数量不同和分成一组即可

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n;cin>>n;string str;cin>>str;if(n&1){cout<<-1<<'\n';return;}if(str[0]==')')for(int i=0;i<n;i++)if(str[i]=='(')str[i]=')';else str[i]='(';vector<int>ou(n,2);bool ok=1;bool pos=1;int c=0;for(int i=0;i<n;i++){if(str[i]=='(')c++;else c--;if(c>0)pos=1,ou[i]=1;if(c==0)if(pos)ou[i]=1;if(c<0)pos=0,ok=0;}if(c){cout<<-1<<'\n';return;}if(ok){cout<<1<<'\n';for(int i=0;i<n;i++)cout<<1<<' ';cout<<'\n';return;		}cout<<2<<'\n';for(int i=0;i<n;i++)cout<<ou[i]<<' ';cout<<'\n';
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

这篇关于codeforces round 149 div2(a,b,c,d)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---