T3 回文

!!!這是一道極好的枚舉題目

小 C 有一個長度為 \(n\) 且由小寫字母構成的字符串 \(S\)。

小 C 現在可以對 \(S\) 做一些變換，但變換是需要代價的，將字母 \(c_1\) 變成 \(c_2(c_1\ne c_2)\) 的代價為 \(v_{c_2}\)，其中 \(v\) 是一個長度為 \(26\) 的數組。（為了方便理解，規定字母 a 對應數字 \(1\)，字母 b 對應數字 \(2\)，以此類推）

小 C 在做上述變換前可以先選擇兩個位置并交換兩個位置上的字母（該操作最多做一次且代價為 \(0\)），然后再將字母隨意變換。

小 C 想要知道將 \(S\) 變成回文串的最小代價，保證 \(2|n\)。

include<bits/stdc++.h>

using namespace std;

define endl '\n'

define ll long long

define dbug(x) (void)(cerr << #x << " = " << x << endl)

ll n, v[30];
string s;
ll minn = INT_MAX;
ll cost[27][27];
ll freq[27][27]; // 添加頻率數組記錄字符對出現次數

inline ll oside(ll x) {
return n - x + 1;
}

inline ll f(string s){
ll ans = 0;
for (ll i = 1; i <= n / 2; i++) {
if (s[i] != s[oside(i)]){
int c1 = s[i] - 'a' + 1;
int c2 = s[oside(i)] - 'a' + 1;
ll current_cost = min({2 * minn, v[c1], v[c2]});
ans += current_cost;
int minC = min(c1, c2);// 標準化為有序對，確保第一個索引不大于第二個索引
int maxC = max(c1, c2);
freq[minC][maxC]++; // 記錄出現次數
}
}
return ans;
}

int cs(int x, int y){
if(x == y) return 0;
return min({2*minn, v[y], v[x]});
}

int main() {
freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (ll i = 1; i <= 26; i++) {
cin >> v[i];
minn = min(minn, v[i]);
for(ll j = 1; j <= 26; j++){
freq[i][j] = 0; // 初始化頻率數組
}
}
cin >> s;
s = " " + s;
ll ans, sum, temp;
temp = ans = sum = f(s);

if (sum == 0) {// 如果已經是回文，直接輸出0
    cout << 0 << endl; return 0;
}

// 26^4枚舉交換可能性,ac一對，bd一對，然后ab進行交換 
for(ll a = 1; a <= 26; a++){
    for(ll b = a+1; b <= 26; b++){
        for(ll c = 1; c <= 26; c++){
            for(ll d = 1; d <= 26; d++){
                int min_ac = min(a, c);// 標準化字符對為有序對
                int max_ac = max(a, c);
                int min_bd = min(b, d);
                int max_bd = max(b, d);
                
                if (freq[min_ac][max_ac] == 0 || freq[min_bd][max_bd] == 0) continue;// 檢查字符對是否存在
                
                if (min_ac == min_bd && max_ac == max_bd) {//x:本質上zhiyou 是同一對，比如a   ....  b  ，a要和b交換，這是不行的 
                    if (freq[min_ac][max_ac] == 1) continue;
                }    
                // 計算舊代價和新代價
                ll old_cost = cs(a, c) + cs(b, d);
                ll new_cost = cs(b, c) + cs(a, d); //如果像 x那樣交換，則c,c一對，a,a一對，所以很多測試點過不去 
                ans = min(ans, temp - old_cost + new_cost);
                
            }
        }
    }
}

cout << ans << endl;
return 0;

}

T4 CodeForces 1670F Jee, You See?

小 C 喜歡序列，某一天他隨手寫下了一個長度為 \(n\) 的序列 \(A\)，其中 \(\forall 1\le i\le n\)，\(A_i \ge 0\)。

可惜小 C 不小心弄丟了這個序列，但是他保存下了序列 \(A\) 的一些特征。

• \(l\le \sum_{i=1}^n A_i\le r\)。
• \(\bigoplus_{i=1}^n A_i=z\)。

其中 \(\bigoplus\) 為二進制下的異或運算符號，\(l,r,z\) 都為常數。

現在小 C 想要知道多少種可能的序列 \(A\) 滿足他所給出的特征，由于答案可能很大，你只需要告訴小 C 答案對 \(10^9+7\) 取模后的值。

• 對于 \(20\%\) 的數據，保證 \(r\le 30\)。
• 對于 \(40\%\) 的數據，保證 \(n\le 20\)，\(r\le 500\)。
• 對于另 \(20\%\) 的數據，保證 \(n=2\)。
• 對于另 \(20\%\) 的數據，保證 \(n\le 50\)。
• 對于 \(100\%\) 的數據，保證 \(1\le n\le 10^{3}\)，\(1\le l\le r\le 10^{18}\)，\(1\le z\le 10^{18}\)。

1.40分dp
狀態：前i個數，枚舉每個數，異或之后的值，總和。答案dp[n][s+x][p^x] += dp[n-1][s][p];
2.滿分處理，非常的數位dp。異或的操作一般都是拆位，通過枚舉每一位，如果z的這意味是1，則需要從n個數中選擇奇數個當前這一位是1的數字。

dfs中當前這一位，如果為1，則枚舉選擇奇數個數字是幾。
那么如何處理是否比r大？傳一個變量b。如果比r的當前位小，則前面位都大也可以，比如
r的每一位是11011,前面的位枚舉出來是xxx00,如果當前倒數第三位是1,1>r的這一位，成為xx100，則它一定比r大。反之，如果比r這一位小，即使前面都大，則也比r小。如果相等，則原來大還是大，原來小還是小。

int dfs(int pos,int c,int b) { //第pos位， 進位，是否比當前數字大了
	if(pos>len) {
		if(!c&&!b) return 1;
		return 0;
	}
	if(~dp[pos][c][b]) return dp[pos][c][b];
	int ret=0;
	for(int i=0; i<=n; i++) { //枚舉有幾個數當前pos位是1
		if((i&1)!=zz[pos]) continue;//與z的第pos位奇偶相同
		int now=(i+c)&1; //當前pos位是幾(0或者1)
		bool bb=(now<num[pos])?0:(now==num[pos])?b:1; //x的pos位是num[pos] 
		ret=(ret+dfs(pos+1,(i+c)/2ll,bb)*C[n][i]);
	}
	return dp[pos][c][b]=ret;
}