QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#748887 | #9430. Left Shifting 2 | Yuu# | AC ✓ | 783ms | 410616kb | C++23 | 1.8kb | 2024-11-14 21:50:16 | 2024-11-14 21:50:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
// The 2024 ICPC Kunming Invitational Contest
void sol(){
std::string s;
std::cin>>s;
int n = s.length();
if(std::count(s.begin(), s.end(), s[0]) == n){
std::cout<<n / 2<<"\n";
return ;
}
s.insert(s.end(), s.begin(), s.end());
s = ' ' + s + ' ';
int N = 2 * n;
std::vector<int>pre(N + 2), suf(N + 2);
std::iota(pre.begin(), pre.end(), 0);
std::iota(suf.begin(), suf.end(), 0);
for(int i = 1;i <= N;i++){
if(s[i] == s[i - 1]){
pre[i] = pre[i - 1];
}
}
for(int i = N;i >= 1;i--){
if(s[i] == s[i + 1]){
suf[i] = suf[i + 1];
}
}
const int M = 20;
std::vector<std::vector<int>>cost(N + 2, std::vector<int>(M));
std::vector<std::vector<int>>nxt(N + 2, std::vector<int>(M, N + 1));
for(int i = N;i>=1;i--){
cost[i][0] = (suf[i] - i + 1) / 2;
nxt[i][0] = suf[i] + 1;
}
for(int j = 1;j < M;j++){
for(int i = 1;i <= N;i++){
if(nxt[i][j - 1] != N + 1){
cost[i][j] = cost[i][j - 1] + cost[nxt[i][j - 1]][j - 1];
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
}
int ans = N;
for(int i = 1;i <= n;i++){
int now = i, cur = 0, ed = i + n - 1;
for(int j = M - 1;j >= 0;j--){
if(nxt[now][j] <= ed){
cur += cost[now][j];
now = nxt[now][j];
}
}
if(now <= ed){
cur += (ed - now + 1) / 2;
}
ans = std::min(ans, cur);
}
std::cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; std::cin>>t;
while(t--) sol();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
3 abccbbbbd abcde x
output:
2 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 52ms
memory: 3980kb
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: 729ms
memory: 410616kb
input:
1 cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...
output:
18631
result:
ok single line: '18631'
Test #4:
score: 0
Accepted
time: 783ms
memory: 410336kb
input:
1 qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 593ms
memory: 410392kb
input:
1 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
246800
result:
ok single line: '246800'
Test #6:
score: 0
Accepted
time: 707ms
memory: 410496kb
input:
1 yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...
output:
242729
result:
ok single line: '242729'
Extra Test:
score: 0
Extra Test Passed