QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610688#9430. Left Shifting 2huangzihao123AC ✓12ms12296kbC++202.6kb2024-10-04 16:58:412024-10-04 16:58:44

Judging History

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

  • [2024-10-04 16:58:44]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:12296kb
  • [2024-10-04 16:58:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(a) a.begin(),a.end()
typedef pair<int,int> PII;
typedef long long LL;
const int N = 1e6;
const int mod = 998244353;
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
int dx[8] = { 1,0,0,-1,-1,-1,1,1 };
int dy[8] = { 0,-1,1,0,-1,1,-1,1};
inline int gcd(int a, int b)
{
   if (b) while ((a %= b) && (b %= a));
   return a + b;
}
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    s = s + s;
    vector<int>suf(n),pre(n);
    for(int i = 0;i < n;i++) suf[i] = pre[i] = i;
    int sum = 0;
    set<int>st;
    for(int i = 0;i < n;){
        int j = i;
        while(j < n && s[j] == s[i]){
            j++;
        }
        sum += (j - i) / 2;
        for(int k = i;k < j;k++){
            suf[k] = j - 1;
            pre[k] = i;
        }
        i = j;
        st.insert(s[i] - 'a');
    }
    if(st.size() == 1){
        cout << sum << endl;
        return;
    }
    int ans = sum;
    for(int i = 0;i <= suf[0];i++){
        int res = sum;
        int cnt = suf[0] + 1;
        res -= cnt / 2;
        res += (suf[i] - i) / 2;
        if(s[0] == s[n - 1]){
            int r = n - pre[n - 1];
            res -= r / 2;
            res += (i + 1 + r) / 2;
        }
        else res += (i + 1) / 2;
        // cerr << i << ' ' << res << endl;
        ans = min(ans,res);
    }
    int tmp = 0;
    if(s[0] == s[n - 1]){
        int l = suf[0] + 1;
        int r = n - pre[n - 1];
        tmp += (l + r) / 2 - l / 2 - r / 2;
    }
    for(int i = suf[0] + 1;i < pre[n - 1];i++){
        int res = sum;
        int cnt = (suf[i] - pre[i] + 1);
        res -= cnt / 2;
        res += (i - pre[i] + 1) / 2 + (suf[i] - i) / 2;
        if(s[0] == s[n - 1]) res += tmp;
        // cerr << i << ' ' << res << endl;
        ans = min(res,ans);
    }
    for(int i = pre[n - 1];i < n - 1;i++){
        int res = sum;
        int cnt = n - pre[n - 1];
        res -= cnt / 2;
        res += (i - pre[i] + 1) / 2;
        if(s[0] == s[n - 1]){
            int l = suf[0] + 1;
            res -= l / 2;
            res += (n - 1 - i + l) / 2;
            // cerr << l << ' ' << n - i << ' ';
        }
        else res += (n - i - 1) / 2;
        // cerr << i << ' ' << res << endl;
        ans = min(ans,res);
    }
    cout << ans << endl;
}
signed main()
{
    io;
    int tt = 1;
    cin >> tt;
    while(tt--)
    {
        solve();
    }
	return 0;
}
/*
 3
 abccbbbbd
 abcde
 x
*/

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

詳細信息

Test #1:

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

input:

3
abccbbbbd
abcde
x

output:

2
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 9ms
memory: 3860kb

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

input:

1
cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...

output:

18631

result:

ok single line: '18631'

Test #4:

score: 0
Accepted
time: 12ms
memory: 11908kb

input:

1
qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 5ms
memory: 12172kb

input:

1
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

246800

result:

ok single line: '246800'

Test #6:

score: 0
Accepted
time: 0ms
memory: 12144kb

input:

1
yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...

output:

242729

result:

ok single line: '242729'

Extra Test:

score: 0
Extra Test Passed