QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#683285#9430. Left Shifting 2jimmyywangAC ✓8ms19928kbC++141.3kb2024-10-27 19:52:542024-10-27 19:52:54

Judging History

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

  • [2024-10-27 19:52:54]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:19928kb
  • [2024-10-27 19:52:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
ll rd(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}return x*f;
}
#define d rd()
ll T,n;
char c[500010];
ll f[2][500010];
ll g[2][500010];
int main(){
    T=d;while(T--){
        scanf("%s",c+1);
        n=strlen(c+1);
        f[0][1]=0,f[1][1]=1;
        ll t=1;f(i,2,n){
            f[0][i]=f[0][i-1];
            if(c[i]==c[i-1])t++;else t=1;
            if(t%2==0)f[0][i]++;
        }t=0;f(i,2,n){
            f[1][i]=f[1][i-1];
            if(c[i]==c[i-1])t++;else t=1;
            if(t%2==0)f[1][i]++;
        }reverse(c+1,c+n+1);
        g[0][1]=0,g[1][1]=1;
        t=1;f(i,2,n){
            g[0][i]=g[0][i-1];
            if(c[i]==c[i-1])t++;else t=1;
            if(t%2==0)g[0][i]++;
        }t=0;f(i,2,n){
            g[1][i]=g[1][i-1];
            if(c[i]==c[i-1])t++;else t=1;
            if(t%2==0)g[1][i]++;
        }ll res=f[0][n];
        f(i,1,n){
            if(c[1]!=c[n])res=min(res,min(f[0][n-i],f[1][n-i])+min(g[0][i],g[1][i]));
            else res=min(res,min(f[0][n-i]+g[1][i],f[1][n-i]+g[0][i]));
        }cout<<res<<endl;
    }
	return 0;
}

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

详细

Test #1:

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

input:

3
abccbbbbd
abcde
x

output:

2
0
0

result:

ok 3 lines

Test #2:

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

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: 7ms
memory: 19928kb

input:

1
cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...

output:

18631

result:

ok single line: '18631'

Test #4:

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

input:

1
qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 8ms
memory: 19872kb

input:

1
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

246800

result:

ok single line: '246800'

Test #6:

score: 0
Accepted
time: 8ms
memory: 19812kb

input:

1
yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...

output:

242729

result:

ok single line: '242729'

Extra Test:

score: 0
Extra Test Passed