ABC题总结:
- 可以用geiline读取一行
- cctype中有很多字符处理函数,比如isupper(c),判断c是不是一个字母
string s; getline(cin,s); for(auto &c:s) if(isupper(c)) c=mp[c];
D题描述:
CodeForces - 1138A
东东和他的女朋友(幻想的)去寿司店吃晚餐(在梦中),他发现了一个有趣的事情,这家餐厅提供的 n 个的寿司被连续的放置在桌子上 (有序),东东可以选择一段连续的寿司来吃
东东想吃鳗鱼,但是东妹想吃金枪鱼。核 平 起 见,他们想选择一段连续的寿司(这段寿司必须满足金枪鱼的数量等于鳗鱼的数量,且前一半全是一种,后一半全是另外一种)我们用1代表鳗鱼,2代表金枪鱼。
比如,[2,2,2,1,1,1]这段序列是合法的,[1,2,1,2,1,2]是非法的。因为它不满足第二个要求。
东东希望你能帮助他找到最长的一段合法寿司,以便自己能吃饱。
D题思路:
因为序列都是12交替,所以把序列抽象成整数交替即可(把连续的一段1看成一个整数),比如 111221222111可以抽象成3 2 1 3 3,然后处理相邻的每一对数,最后取max即可
D题代码:
#include <cstdio> #include <iostream> using namespace std; const int MAXN=1e5+5; int seg[MAXN]; int main() { int N; cin>>N; int last=0,tot=0; for(int i=1;i<=N;i++) { int t; scanf("%d",&t); if(t==last) seg[tot]++; else tot++,seg[tot]=1,last=t; } int ans=0; for(int i=2;i<=tot;i++) ans=max(ans,(seg[i]<=seg[i-1]) ? (seg[i]*2) : (seg[i-1]*2)); cout<<ans<<endl; return 0; }