QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#748887#9430. Left Shifting 2Yuu#AC ✓783ms410616kbC++231.8kb2024-11-14 21:50:162024-11-14 21:50:16

Judging History

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

  • [2024-11-14 21:50:16]
  • 评测
  • 测评结果:AC
  • 用时:783ms
  • 内存:410616kb
  • [2024-11-14 21:50:16]
  • 提交

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