QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693198 | #9430. Left Shifting 2 | Nana7# | AC ✓ | 6ms | 12560kb | C++14 | 1.1kb | 2024-10-31 15:41:53 | 2024-10-31 15:41:58 |
Judging History
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