QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693198#9430. Left Shifting 2Nana7#AC ✓6ms12560kbC++141.1kb2024-10-31 15:41:532024-10-31 15:41:58

Judging History

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

  • [2024-10-31 15:41:58]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:12560kb
  • [2024-10-31 15:41:53]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#define I inline
using namespace std;

const int N = 1000100;
char s[N];
int lc[N],rc[N];
int n,ans;


I void solve() {
	scanf("%s",s+1); n=strlen(s+1); ans=0;
	for(int i=n+1;i<=n*2;++i) s[i]=s[i-n];
	int nr=n*2,nl=1;
	for(int i=n*2;i>=1;--i) {
		if(i!=n*2&&s[i]!=s[i+1]) {
			nr=i;
		}
		rc[i]=nr;
	}
	for(int i=1;i<=n*2;++i) {
		if(i!=1&&s[i]!=s[i-1]) {
			nl=i; 
		}
		lc[i]=nl;
	}
	//for(int i=1;i<=n*2;++i) cout<<lc[i]<<' '<<' '<<rc[i]<<endl;
	int r=0,l=1;
	for(int i=1;i<n;++i) {
		r++;
		if(lc[r]!=r) {
			ans-=(r-lc[r])/2;
			ans+=(r-lc[r]+1)/2;
		}
	}
	int fi=n;
	for(int i=1;i<=n;++i) {
		r++;
		int v=max(lc[r],i-1);
		if(v!=r) {
			ans-=(r-v)/2;
			ans+=(r-v+1)/2;
		}
		if(i!=1) {
			int nv=min(rc[i-1],r);
			if(nv!=i-1) {
				ans-=(nv-(i-1)+1)/2;
				ans+=(nv-(i-1))/2;
			} 
		}
		
		fi=min(fi,ans);
	}
	cout<<fi<<endl;
} 
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0); cout.tie(0);
	int T; cin>>T;
	while(T--) {
		solve();
	} 
} 

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5692kb

input:

3
abccbbbbd
abcde
x

output:

2
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 5820kb

input:

5000
lfpbavjsmppdppkfwnyfmbdhptdswsoulrbhyjh
cfliuqnynejgnxolzbdoztclzbozqomvioszk
eiivcoqoymonrqgrjdtkts
mdcvservaxcbioopfungsgkiftchwlmtbzqgaraovjknsgiegkvdbolmeunvrxrpscnf
ujeqtidwtoikkqtygo
llma
qjfvgwrdhaazejsfgilnpmmhkefndzvyon
kzwwpdpbrudqmwmjscllnnjyoepxophcoopvfepikouinuxx
vftculoorxskpkxoz...

output:

1
0
0
0
0
0
1
4
0
0
1
1
1
1
1
3
1
0
5
6
0
0
5
2
0
1
3
2
0
3
0
1
0
1
1
0
1
4
1
3
1
0
1
5
3
0
3
0
0
1
8
1
0
6
1
2
0
1
0
0
4
1
2
4
3
1
3
2
3
1
2
1
0
0
2
0
2
2
0
4
0
5
5
0
3
0
4
1
0
2
1
0
2
0
1
6
1
2
1
3
3
3
5
2
3
0
3
5
1
3
0
0
3
0
4
5
3
2
1
1
0
0
2
0
1
1
3
3
3
1
2
0
1
1
4
3
1
3
1
1
1
2
0
1
2
0
4
0
1
1
...

result:

ok 5000 lines

Test #3:

score: 0
Accepted
time: 6ms
memory: 12560kb

input:

1
cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...

output:

18631

result:

ok single line: '18631'

Test #4:

score: 0
Accepted
time: 5ms
memory: 12556kb

input:

1
qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 12364kb

input:

1
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

246800

result:

ok single line: '246800'

Test #6:

score: 0
Accepted
time: 3ms
memory: 12408kb

input:

1
yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...

output:

242729

result:

ok single line: '242729'

Extra Test:

score: 0
Extra Test Passed