QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#510229 | #6505. CCPC String | Leizijin | TL | 0ms | 11560kb | C++14 | 1.3kb | 2024-08-09 00:09:19 | 2024-08-09 00:09:19 |
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,就是结果
//
// 我们考虑一下这个算法的时间复杂度
// 设序列长度n,共m个p
// 那么最劣情况下,距离为n/m
// O( m * 2 * n/m ) = O(n)
// 这是一个线性算法,十分优雅
const int N = 1e6+5;
int lft[N],rgt[N],idx;
string s;
void work(){
idx=0;
memset(lft,0,sizeof(lft));
memset(rgt,0,sizeof(rgt));
cin >> s;
int n = s.size();
s = '#'+s; // 懒得改下标了
for(int i=1;i<=n;i++){
if(s[i] == 'c') continue;
++idx;
for(int j=i+1;j<=n;j++,rgt[idx]++) if(s[j]=='p') break;
for(int j=i-1;j>=1;j--,lft[idx]++) if(s[j]=='p') break;
}
int ans = 0;
for(int i=1;i<=idx;i++) ans += min(lft[i]/2, rgt[i]);
printf("%lld\n", ans);
}
signed main(){
fastio;
int T;
cin >> T;
while(T--) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11560kb
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 ...