QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#510232#6505. CCPC StringLeizijinTL 0ms11656kbC++141.2kb2024-08-09 00:14:422024-08-09 00:14:42

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 00:14:42]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:11656kb
  • [2024-08-09 00:14:42]
  • 提交

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
...

result: