Codeforces Round 854 by cybercats (Div. 1 + Div. 2) C、D1

C. Double Lexicographically Minimum

题意

字符串$s$，你可以把它按任意顺序组合，保留的是你组合的字符串和它的倒序之间大的那一个，问你在满足上面条件的前提下字典序最小的字符串。

思路

分析不难发现在没达到一个关键的点的时候肯定是对称是最好的，这样肯定能保证得到的字符串是最小的，而关键点到了之后就不需要平分了，全部放前面就好了。那关键点要怎么看，其实也很明显，因为判断字符串大小主要看第一个不同的字符，所以只要把第一个奇数个数的字符的最后一个放到后面就行了。那为什么是奇数呢？因为如果是偶数那要满足题目要求，后面就必须要比前面多放两个，但这样就比正常情况下大了（这里可以画图模拟一下就行）。
最后就是如果关键点后面只有一种类型的字符那就需要特判一下，才能满足题目要求，这里就看一下代码画图模拟一下把，也好理解。

代码

#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各有多少个for (int i = 0; i < s.size(); i ++ ) st[s[i] - 'a'] ++;string l = "", r = "";for (int i = 0; i < 26; i ++ ) // 不到关键点就前后分开{while (st[i] > 1) {l += (char)('a' + i);r += (char)('a' + i);st[i] -= 2;}if(st[i]) break; // 奇数就代表找到了，可以中断了}int cc = 0;for(int i = 0; i < 26; i ++) if(st[i]) cc ++; // 判断一下关键点后面有几个字符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) // 把关键点放到后面r += (char)('a' + i), st[i] --, flag = 0; else // 剩下的全放前面l += (char)('a' + i), st[i] --;}}}reverse(r.begin(), r.end()); // 翻转一下cout << l << r << '\n';
}int main() 
{int T = 1;cin >> T;while (T --) {solve();    }return 0;
}

---

D1. Hot Start Up (easy version)

题意

$n$个数，大小为$k$的数组$cold$，$hot$，你有两个CPU，如果你选择的CPU的上一个进程和当前的进程一样，所用时间就是$hot$，否则$cold$。问你完成所有的进程的最短时间。

思路

很明显是一个动态规划问题，关键是动态规划数组代表的含义，这里是$dp(i,j,k)$，代表走到 $i$ 的时候CPU1最后处理的进程是 $j$, CPU2最后处理的进程是 $k$。但这样肯定是要超时的，然后通过题目可以得到要去进行 $i$，$i-1$ 必须要完成，所以可以优化一维，这样就可以了。
$dp[i][j]$就代表进程处理到第 $i$ 个位置的时候，CPU1最后处理的进程是 $j$（CPU2默认为 $a[i-1]$）这样就题目要求得到了转换方程：

$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  // 开一下 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]];// 转化方程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 题的时候把自己绕晕了，之间明白是这样做的，但是做起来不是这里不行就哪里不行，做题之前需要把自己的思路逻辑理清楚，然后再去写。
D 题就是自己动态规划做题经验不足了，状态表示没有想到，还需要继续做题。