QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#673472 | #9430. Left Shifting 2 | yxfql | AC ✓ | 7ms | 12204kb | C++20 | 1.2kb | 2024-10-24 22:38:59 | 2024-10-24 22:38:59 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
const int M=5e5+10;
int l[M<<1],r[M<<1];
void solve() {
std::string s;
std::cin >> s;
int n = s.length();
s = " " + s;
s.resize((n << 1) + 1);
for(int i = 1; i <= n; ++i) s[i + n] = s[i];
for(int i = 1; i < (n << 1); ++i)
{
if (s[i] == s[i - 1]) l[i] = l[i - 1];
else l[i] = i;
}
l[n << 1] = 0;
for(int i = (n << 1) - 1; i; --i)
{
if (l[i] == l[i + 1]) r[i] = r[i + 1];
else r[i] = i;
}
int cnt = 0;
int minn = n + 1, ans = 0;
for(int i = 1; i <= n; ++i)
{
if (l[i] == i) cnt += (std::min(r[i], n) - i + 1) >> 1;
}//cout << n << '\n';
for(int i = 1; i <= n; ++i)
{
if (cnt < minn)
{
minn = cnt;
ans = i - 1;
}
//cout << i << " " << cnt << '\n';
if (s[i] == s[i + 1] && ((r[i] - i + 1) & 1) == 0) --cnt;
if (s[i + n - 1] == s[i + n] && ((i + n - l[i + n] + 1) & 1) == 0) ++cnt;
}
std::cout << minn << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin>>t;
while(t--){
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5820kb
input:
3 abccbbbbd abcde x
output:
2 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 5584kb
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: 0ms
memory: 12204kb
input:
1 cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...
output:
18631
result:
ok single line: '18631'
Test #4:
score: 0
Accepted
time: 5ms
memory: 12052kb
input:
1 qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 3ms
memory: 11900kb
input:
1 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
246800
result:
ok single line: '246800'
Test #6:
score: 0
Accepted
time: 7ms
memory: 12108kb
input:
1 yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...
output:
242729
result:
ok single line: '242729'
Extra Test:
score: 0
Extra Test Passed