QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#510232 | #6505. CCPC String | Leizijin | TL | 0ms | 11656kb | C++14 | 1.2kb | 2024-08-09 00:14:42 | 2024-08-09 00:14:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<ll,ll>
#define il inline
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// 我们注意到匹配串的格式是c^2t p c^t
// p的出现次数只有1,所以我们显然可以考虑枚举p的位置,再考虑每一个p的位置的贡献
// 所以显然的,对于每一个'p' / '?',我们考虑两侧最长不含p的距离
// 然后左边长度/2,右边长度/t,取个min,就是结果
//
const int N = 1e6+5;
int lft[N],rgt[N],idx;
string s;
inline void work(){ // 正反各扫一遍数组,然后再扫一遍找答案
idx=0;
memset(lft,0,sizeof(lft));
memset(rgt,0,sizeof(rgt));
cin >> s;
int n = s.size();
int l=0,r=0, ans = 0;
for(int i=0;i<n;i++){
lft[i]=l;
if(s[i]=='p') l=0;
else l++;
}
for(int i=n-1;i>1;i--){
rgt[i]=r;
if(s[i]=='p') r=0;
else r++;
}
for(int i=0;i<n;i++){
if(s[i]=='c') continue;
ans += min(lft[i]/2, rgt[i]);
}
printf("%d\n", ans);
return ;
}
signed main(){
fastio;
int T;
cin >> T;
while(T--) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11656kb
input:
5 ?cpc ccp?? ???c??? ?c???cp?? ?c?????cccp????
output:
1 1 4 5 14
result:
ok 5 number(s): "1 1 4 5 14"
Test #2:
score: -100
Time Limit Exceeded
input:
100000 c?cp?pp?c? ppp????pcc c?ppppcc?p ?p?cc?ccpc pc?ppc?cp? ?pp?p?c?cp p???pcccpp cpcccpcc?? ????c?cc?p pcp?pppcp? cc?pccc?pp cpc??c?p?c ??c??cpppc cpcp?pc??c pcc??ppccp ?p?p?cpcpp c?ccpcpp?? ppc?cccccp cp?pcccppp cccc???ccc c?pcc?pp?p pcc?p??cp? ?cc??ppp?p ?ppp??p?pp ??pccc??p? ???cccpp?? c???c?p...
output:
1 3 0 2 1 1 1 2 4 0 1 3 2 1 1 1 1 0 0 7 1 2 1 1 3 1 3 1 2 2 2 3 0 2 1 8 0 3 2 0 1 1 1 1 1 0 3 0 3 3 2 1 4 0 1 1 1 1 2 1 6 4 3 1 4 1 2 1 1 0 1 2 5 1 1 3 2 1 1 2 1 5 0 0 2 1 3 1 2 0 4 0 0 1 5 2 0 1 0 1 0 0 1 0 1 2 0 0 0 0 3 0 0 2 1 3 2 4 2 0 1 3 1 3 1 3 2 1 2 0 1 2 0 0 5 0 4 4 0 0 2 3 0 1 1 0 1 0 1 1 ...