QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#510225#6505. CCPC StringLeizijinTL 0ms11820kbC++141.3kb2024-08-08 23:51:172024-08-08 23:51:17

Judging History

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

  • [2024-08-08 23:51:17]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:11820kb
  • [2024-08-08 23:51:17]
  • 提交

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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11820kb

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: