Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

CF2069Dsol

发布于：2025年2月19日

更不好的阅读体验

题目链接

CF2069D(*1900) Palindrome Shuffle(luogu)

CF2069D(*1900) Palindrome Shuffle(codeforces)

解题思路

本文 VV 代表 2626，即字符集大小。

这题是史，大家一起吃。

首先根据题中定义这题显然长度为 i(i<n)i(i < n) 合法，则长度为 i+1i + 1 合法，因为你可以任意交换，不影响。

因此此题可以二分答案。

那么容易得出 check 一个长度 lenlen 是否合法只需要判断是否有至少一个长度为 lenlen 的区间合法即可，那么我们考虑如何进行 check 一个任意交换区间 [l,r][l,r] 是否合法，首先通过提前预处理判断掉不能任意交换且字母本应该相同的位置是否合法，处理完这个之后此时我们可以考虑分讨以下几种情况：

  • r≤n2r \le \displaystyle \frac{n}{2}，此时整个可交换的区间都在左边，只需要前缀和即可 O(V)O(V) 判断一个区间是否合法。

  • l>n2l > \displaystyle \frac{n}{2}，此时整个可交换的区间都在右边，只需要前缀和即可 O(V)O(V) 判断一个区间是否合法。

  • l≤n2<rl \le \displaystyle \frac{n}{2} < r，则此时可交换区间包含左右两边，此时我们继续分讨：

    • n2−l<r−n2\displaystyle\frac{n}{2} - l < r - \displaystyle\frac{n}{2}，此时我们只需要判断左边是否能暴力匹配右边的字母即可。

    • n2−l≥r−n2\displaystyle\frac{n}{2} - l \ge r - \displaystyle\frac{n}{2}，此时我们只需要判断右边是否能暴力匹配左边的字母即可。

那么 check 就做完了，那么整题也就做完了，最后是一个二分板子，不赘述。

时间复杂度 O(nVlog⁡n)O(nV \log n)，可以通过本题。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
string s;
ll n;
ll pre[200010];
ll sum[200010][30];
ll now[30];
bool PRE(ll len){
    return pre[len]==len;
}
bool ck(ll l,ll r)
{
    if(l==1 && r==n)
        return 1;
    ll l1,l2,r1,r2;
    l1=1,r1=l-1;
    l2=r+1,r2=n;
    ll len=min(r1,n-l2+1);
    if(!PRE(len))
        return 0;
    if(l+r==n+1)
        return 1;
    forl(i,0,25)
        now[i]=sum[r][i]-sum[l-1][i];
    if(l<=n/2 && r<=n/2)
    {
        if(r!=n/2 && pre[n/2]-pre[r]!=n/2-r)
            return 0;
        forl(i,0,25)
            if(now[i]!=sum[n+1-l][i]-sum[n+1-r-1][i])
                return 0;
        return 1;
    }
    else if(l>n/2 && r>n/2)
    {
        if(l!=n/2+1 && pre[n/2]-pre[n+1-l]!=n/2-(n+1-l))
            return 0;
        forl(i,0,25)
            if(now[i]!=sum[n+1-l][i]-sum[n+1-r-1][i])
                return 0;
        return 1;
    }
    else
    {
        if(n/2-l<r-n/2)
        {
       //   bug2;
            forl(i,0,25)
            {
                now[i]-=sum[n+1-(n+1-l)-1][i]-sum[n+1-r-1][i];
                if(now[i]<0)
                    return 0;
            }
            /*
            r,r-1,n-l
            */
            ///////
            // while(l+r>n+1)
            // {
            //     //r--;
            //  //   cout<<s[n+1-r]<<endl;
            //     if(!now[s[n+1-r]-'a']--)
            //         return 0;
            //     r--;
            // }
        //    bug3;
            forl(i,0,25)
                if(now[i]&1)
                    return 0;
            return 1;
        }
        else
        {
            forl(i,0,25)
            {
                now[i]-=sum[n+1-l][i]-sum[n+1-(n+1-r)][i];
                if(now[i]<0)
                    return 0;
            }
       //  bug1;
            // while(l+r<n+1)
            // {
            //     //l++;
            //     if(!now[s[n+1-l]-'a']--)
            //         return 0;
            //     l++;
            // }
         // bug4;
            forl(i,0,25)
                if(now[i]&1)
                    return 0;
            return 1;
        }
    }
}
bool check(ll Mid)
{
    forl(i,1,n-Mid+1)
        if(ck(i,i+Mid-1))   
            return 1;
    return 0;
}
ll L,R;
/*
ababa babababab
ababa babb ababa
*/
void _clear(){}
void solve()
{
    _clear();
    cin>>s;
    n=s.size();
    s=' '+s;
    forl(i,1,n)
    {
        forl(j,0,25)
            sum[i][j]=sum[i-1][j];
        sum[i][s[i]-'a']++;
    }
    forl(i,1,n)
        pre[i]=0;
    forl(i,1,n/2)
        pre[i]=(s[i]==s[n-i+1]);
    forl(i,1,n/2)
        pre[i]+=pre[i-1];
    if(pre[n/2]==n/2)
    {
        cout<<0<<endl;
        return ;
    }
   // cout<<ck(5,10)<<endl;
   // return ;
    L=1,R=n;
    while(L<R)
    {
        ll Mid=(L+R)/2;
        if(check(Mid))
            R=Mid;
        else
            L=Mid+1;
    }
    cout<<L<<endl;
}

更新于：2025年2月20日

评论