C. Double Lexicographically Minimum

題意

字符串$s$，你可以把它按任意順序組合，保留的是你組合的字符串和它的倒序之間大的那一個(gè)，問(wèn)你在滿(mǎn)足上面條件的前提下字典序最小的字符串。

思路

分析不難發(fā)現(xiàn)在沒(méi)達(dá)到一個(gè)關(guān)鍵的點(diǎn)的時(shí)候肯定是對(duì)稱(chēng)是最好的，這樣肯定能保證得到的字符串是最小的，而關(guān)鍵點(diǎn)到了之后就不需要平分了，全部放前面就好了。那關(guān)鍵點(diǎn)要怎么看，其實(shí)也很明顯，因?yàn)榕袛嘧址笮≈饕吹谝粋€(gè)不同的字符，所以只要把第一個(gè)奇數(shù)個(gè)數(shù)的字符的最后一個(gè)放到后面就行了。那為什么是奇數(shù)呢？因?yàn)槿绻桥紨?shù)那要滿(mǎn)足題目要求，后面就必須要比前面多放兩個(gè)，但這樣就比正常情況下大了（這里可以畫(huà)圖模擬一下就行）。
最后就是如果關(guān)鍵點(diǎn)后面只有一種類(lèi)型的字符那就需要特判一下，才能滿(mǎn)足題目要求，這里就看一下代碼畫(huà)圖模擬一下把，也好理解。

代碼

#include <bits/stdc++.h>using namespace std; const int N = 105;int st[30];void solve()
{string s;cin >> s;memset(st, 0, sizeof(st)); // 記錄a, b, ..., z各有多少個(gè)for (int i = 0; i < s.size(); i ++ ) st[s[i] - 'a'] ++;string l = "", r = "";for (int i = 0; i < 26; i ++ ) // 不到關(guān)鍵點(diǎn)就前后分開(kāi){while (st[i] > 1) {l += (char)('a' + i);r += (char)('a' + i);st[i] -= 2;}if(st[i]) break; // 奇數(shù)就代表找到了，可以中斷了}int cc = 0;for(int i = 0; i < 26; i ++) if(st[i]) cc ++; // 判斷一下關(guān)鍵點(diǎn)后面有幾個(gè)字符if(cc <= 2) {for (int i = 25; i >= 0; i -- ) // 把大的放前面{while (st[i] > 1) {l += (char)('a' + i);r += (char)('a' + i);st[i] -= 2;}if(st[i]) l += (char)('a' + i);}}else {int flag = true;for(int i = 0; i < 26; i ++) {while(st[i]) {if(flag) // 把關(guān)鍵點(diǎn)放到后面r += (char)('a' + i), st[i] --, flag = 0; else // 剩下的全放前面l += (char)('a' + i), st[i] --;}}}reverse(r.begin(), r.end()); // 翻轉(zhuǎn)一下cout << l << r << '\n';
}int main() 
{int T = 1;cin >> T;while (T --) {solve();    }return 0;
}

---

D1. Hot Start Up (easy version)

題意

$n$個(gè)數(shù)，大小為$k$的數(shù)組$cold$，$hot$，你有兩個(gè)CPU，如果你選擇的CPU的上一個(gè)進(jìn)程和當(dāng)前的進(jìn)程一樣，所用時(shí)間就是$hot$，否則$cold$。問(wèn)你完成所有的進(jìn)程的最短時(shí)間。

思路

很明顯是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，關(guān)鍵是動(dòng)態(tài)規(guī)劃數(shù)組代表的含義，這里是$dp(i,j,k)$，代表走到 $i$ 的時(shí)候CPU1最后處理的進(jìn)程是 $j$, CPU2最后處理的進(jìn)程是 $k$。但這樣肯定是要超時(shí)的，然后通過(guò)題目可以得到要去進(jìn)行 $i$，$i?1$ 必須要完成，所以可以?xún)?yōu)化一維，這樣就可以了。
$dp[i][j]$就代表進(jìn)程處理到第 $i$ 個(gè)位置的時(shí)候，CPU1最后處理的進(jìn)程是 $j$（CPU2默認(rèn)為 $a[i?1]$）這樣就題目要求得到了轉(zhuǎn)換方程：

$dp[i][j]=min(dp[i][j],dp[i?1][j]+(a[i]==a[i?1]?hot[i]:cold[i]))$ 和
$dp[i][a[i?1]]=min(dp[i][a[i?1]],dp[i?1][j]+(a[i]==j?hot[i]:cold[i]))$

代碼

#include <bits/stdc++.h>using namespace std;#define int long long  // 開(kāi)一下 long long
typedef long long LL;
const int N = 5e5 + 10, mod = 998244353;void solve()
{int n, k;cin >> n >> k;vector<int> a(n + 1), cold(k + 1), hot(k + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= k; i ++ ) cin >> cold[i];for (int i = 1; i <= k; i ++ ) cin >> hot[i];vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1e18)); // 初始化dp[1][0] = cold[a[1]];for (int i = 2; i <= n; i ++ ){for (int j = 0; j <= k; j ++ ){int x = cold[a[i]];if (a[i - 1] == a[i]) x = hot[a[i]];// 轉(zhuǎn)化方程dp[i][j] = min(dp[i][j], dp[i - 1][j] + x);dp[i][a[i - 1]] = min(dp[i][a[i - 1]], dp[i - 1][j] + (a[i] == j ? hot[a[i]] : cold[a[i]]));}}int ans = 1e18;for (int i = 0; i <= k; i ++ ) ans = min(ans, dp[n][i]);cout << ans << '\n';
}signed main()
{int T = 1;cin >> T;while (T -- ){solve();}return 0;
}

反思

做 C 題的時(shí)候把自己繞暈了，之間明白是這樣做的，但是做起來(lái)不是這里不行就哪里不行，做題之前需要把自己的思路邏輯理清楚，然后再去寫(xiě)。
D 題就是自己動(dòng)態(tài)規(guī)劃做題經(jīng)驗(yàn)不足了，狀態(tài)表示沒(méi)有想到，還需要繼續(xù)做題。