题解：AT_cf17_final_e Combination Lock

· · 题解

困难题，但是场切了。

首先先把字符串处理成若干个数。然后回文串就是要求第一个数和最后一个数相等，以此类推。

首先这个区间加显然很不可做，一个经典套路就是转成差分。考虑回文串在差分上怎么刻画。显然，差分上，第一个位置应该和最后一个位置是相反数，以此类推（这里差分数组最后要加一个零）。

然后这个操作在差分数组上显然就是一个位置单点加，一个位置单点减对吧。这个过程很像权值的“传递”。我们不妨使用边 u \rightarrow v 表示存在操作，可以操作 [u,v-1]，使得 u 权值减少一，v 权值增加一。

然后整个题显然都是在模 26 的同余系上对吧。所以这个边其实是双向的，我们可以通过做 25 次操作使得 u 权值加一，v 权值减一。

然后因为你发现，一个联通块内，只要保证和不变，你可以随意钦定每个数的值。所以我们肯定往这方面去想。

设一开始那个数组长度为 sz，不妨钦定 sz 是偶数，如果不是你在中间再填一个数即可。我们定义原数组前半部分为下标在 [1,\frac{sz}{2}] 的部分，后半部分就是其他部分。

你发现如果一个操作横跨前后两边不太方便。于是可以这么处理：

你发现红色的操作和紫色的操作等价。

你发现紫色操作和绿色操作是等价的。

因此我们可以把任何一个操作转换到前半部分。

现在问题就变成了你要使前半部分和后半部分相等。然后有若干联通块，你可以对联通块内数任意赋值，但要满足和为一个定值。

那做法就显然了，联通块内和与后半部分对应的和相等就可以，反之就不行。

AC Code

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 1e5 + 7 ;
char s[MAXN] ;
int val[MAXN] ;
int d[MAXN] ;
int sz ;
vector<int> dir[MAXN] ;
bool vis[MAXN] ;
int cnt1 , cnt2 ;

void dfs(int u) {
    cnt1 += d[u] ;
    if (u != (sz + 2) / 2)
        cnt2 += d[sz + 1 - u + 1] ;
    vis[u] = 1 ;

    for (auto v : dir[u]) {
        if (vis[v]) continue ;
        dfs(v) ;
    }
    return ;
}

void solve() {
    cin >> s + 1 ;

    for (sz = 1 ; s[sz] != 0 ; sz ++) ; sz -- ;

    for (int i = 1 ; i <= sz + 2 ; i ++) {
        dir[i].clear() ;
        vis[i] = 0 ;
    }

    for (int i = 1 ; i <= sz ; i ++) {
        val[i] = s[i] - 'a' ;
        d[i] = (val[i] - val[i - 1] + 26) % 26 ;
    }
    d[sz + 1] = (26 - val[sz]) % 26 ;

    bool flag = 0 ;
    if (sz & 1) {
        for (int i = sz + 2 ; i >= (sz + 1) / 2 + 2 ; i --) {
            d[i] = d[i - 1] ;
        }
        d[(sz + 1) / 2 + 1] = 0 ;
        sz ++ ;
        flag = 1 ;
    }

    int n ;
    cin >> n ;
    for (int i = 1 ; i <= n ; i ++) {
        int l , r ;
        cin >> l >> r ;

        if (flag) {
            if (l > sz / 2) l ++ ;
            if (r >= sz / 2)    r ++ ;
        }

        if (sz / 2 - l + 1 < r - sz / 2) {
            //翻转过去 
            int dl = sz - r + 1 ;
            int dr = sz - l + 1 ;
            l = dl ;
            r = dr ;
        }

        if (r > sz / 2) {
            r = sz / 2 - (r - sz / 2) ;
        }

        dir[l].push_back(r + 1) ;
        dir[r + 1].push_back(l) ;
    }

    for (int i = 1 ; i <= sz / 2 + 1 ; i ++) {
        if (!vis[i]) {
            cnt1 = cnt2 = 0 ;
            dfs(i) ;

            if ((cnt1 + cnt2) % 26 != 0) {
                cout << "NO\n" ;
                return ;
            }
        }
    }

    cout << "YES\n" ;
    return ;
}

signed main() {
//  freopen("string.in" , "r" , stdin) ;
//  freopen("string.out" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

//  int t ;
//  cin >> t ;
//  while (t--) {
//      if (t == 52) {
//          t ++ ;
//          t -- ;
//      }
        solve() ;
//  }

    return 0 ;
}
/*
1
fefjkookjkja
3
1 3
6 7
4 11
*/