公司设计网站建设合同,自己注册公司网站,展厅内部设计,wordpress多功能博客C. Double Lexicographically Minimum
题意
字符串sss#xff0c;你可以把它按任意顺序组合#xff0c;保留的是你组合的字符串和它的倒序之间大的那一个#xff0c;问你在满足上面条件的前提下字典序最小的字符串。
思路
分析不难发现在没达到一个关键的点的时候肯定是…C. Double Lexicographically Minimum
题意
字符串sss你可以把它按任意顺序组合保留的是你组合的字符串和它的倒序之间大的那一个问你在满足上面条件的前提下字典序最小的字符串。
思路
分析不难发现在没达到一个关键的点的时候肯定是对称是最好的这样肯定能保证得到的字符串是最小的而关键点到了之后就不需要平分了全部放前面就好了。那关键点要怎么看其实也很明显因为判断字符串大小主要看第一个不同的字符所以只要把第一个奇数个数的字符的最后一个放到后面就行了。那为什么是奇数呢因为如果是偶数那要满足题目要求后面就必须要比前面多放两个但这样就比正常情况下大了这里可以画图模拟一下就行。 最后就是如果关键点后面只有一种类型的字符那就需要特判一下才能满足题目要求这里就看一下代码画图模拟一下把也好理解。
代码
#include bits/stdc.husing 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)
题意
nnn个数大小为kkk的数组coldcoldcoldhothothot你有两个CPU如果你选择的CPU的上一个进程和当前的进程一样所用时间就是hothothot否则coldcoldcold。问你完成所有的进程的最短时间。
思路
很明显是一个动态规划问题关键是动态规划数组代表的含义这里是dp(i,j,k)dp(i, j, k)dp(i,j,k)代表走到 iii 的时候CPU1最后处理的进程是 jjj, CPU2最后处理的进程是 kkk。但这样肯定是要超时的然后通过题目可以得到要去进行 iiii−1i - 1i−1 必须要完成所以可以优化一维这样就可以了。 dp[i][j]dp[i][j]dp[i][j]就代表进程处理到第 iii 个位置的时候CPU1最后处理的进程是 jjjCPU2默认为 a[i−1]a[i - 1]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][j] min(dp[i][j], dp[i - 1][j] (a[i] a[i - 1] ? hot[i] : cold[i]))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]))dp[i][a[i - 1]] min(dp[i][a[i - 1]], dp[i - 1][j] (a[i] j ? 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.husing 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;vectorint 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];vectorvectorint dp(n 1, vectorint(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 题就是自己动态规划做题经验不足了状态表示没有想到还需要继续做题。
