算法刷题day14

目录

• 引言
• 一、平均
• 二、三国游戏
• 三、松散子序列

引言

今天做了三道新题，类型是贪心、枚举、DP，不是特别难，但是努力一下刚好能够够得上，还是不错的，只要能够一直坚持下去，不断刷题不断总结，就是记忆力和毅力了，加油！

一、平均

标签：贪心

思路：贪心这种题目只能是见过类似的，然后去变种，一般比赛中是不太可能去现推出来的，这里只讲一下解题思路。这个变数只有四种情况，多变多、多变少、少变多、少变少。
1.多变多：多的给多的，那么一个变少了一个变多了，变多了的肯定又要变成少的，所以相当于第一步就多余了，反而代价多了
2.少变多：少的变多的，那么肯定会有一个多的变成少的，那么就要多变，相当于第一步也就多余了
3.少变少：其中的一个少的变少了，肯定会有一个多的变成这个少的，所以第一步也多余了
所以说只能是多的变少的，由于n的数量刚好，所以多余的部分肯定是会变的，要求又得是代价最少，那么就把多余的代价少的那部分变了就行了。

题目描述：

有一个长度为 n 的数组（n 是 10 的倍数），每个数 ai都是区间 [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为 bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 n10)，请问代价和最少为多少。输入格式输入的第一行包含一个正整数 n。接下来 n 行，第 i 行包含两个整数 ai,bi，用一个空格分隔。输出格式输出一行包含一个正整数表示答案。数据范围对于 20% 的评测用例，n≤1000；对于所有评测用例，n≤105，0<bi≤2×105。输入样例：101 11 21 32 42 52 63 73 83 94 10输出样例：27样例解释只更改第 1,2,4,5,7,8 个数，需要花费代价 1＋2＋4＋5＋7＋8=27。

示例代码：

#include #include #include #include using namespace std;typedef long long LL;const int N = 1e5+10;int n;vector<int> arr[10];int main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i){int a, b;cin >> a >> b;arr[a].push_back(b);}LL res = 0, ave = n / 10;for(int i = 0; i < 10; ++i){if(arr[i].size() > ave){sort(arr[i].begin(), arr[i].end());for(int j = 0; j < arr[i].size() - ave; ++j) res += arr[i][j];}}cout << res << endl;return 0;}

二、三国游戏

标签：枚举

思路：这道题只有三种情况胜出，然后在这其中， xi> yi+ zi, i ∈ ( 1 , n ) 当中任选多个x_i>y_i+z_i,i\in(1,n)当中任选多个xi​>yi​+zi​,i∈(1,n)当中任选多个，即 xi− yi− zi> 0 , i ∈ ( 1 , n ) 当中任选多个x_i-y_i-z_i>0,i\in(1,n)当中任选多个xi​−yi​−zi​>0,i∈(1,n)当中任选多个，可以规定一个 wi w_iwi​来表示左半边，也就是有多个 wi w_iwi​问最多能选多少个使得它们的和大于0，我们可以把这些 wi w_iwi​由大到小排序，然后到了边界条件判断一下就可以了。最后结果从三个国家胜出的最大结果中选最大的就行了。

题目描述：

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 0）。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X,Y,Z 增加 Ai,Bi,Ci。当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X>Y+Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?如果不存在任何能让某国获胜的情况，请输出 −1。输入格式输入的第一行包含一个整数 n。第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。输出格式输出一行包含一个整数表示答案。数据范围对于 40% 的评测用例，n≤500；对于 70% 的评测用例，n≤5000；对于所有评测用例，1≤n≤105，0≤Ai,Bi,Ci≤109。注意，蓝桥杯官方给出的关于 Ai,Bi,Ci 的数据范围是 1≤Ai,Bi,Ci≤109，但是这与给出的输入样例相矛盾，因此予以纠正。输入样例：31 2 22 3 21 0 7输出样例：2样例解释发生两个事件时，有两种不同的情况会出现获胜方。发生 1,2 事件时蜀国获胜。发生 1,3 事件时吴国获胜。

示例代码：

#include #include #include using namespace std;typedef long long LL;const int N = 1e5+10;int n;int a[N], b[N], c[N], w[N];LL work(int x[], int y[], int z[])//x国家胜出{for(int i = 0; i < n; ++i) w[i] = x[i] - y[i] - z[i];sort(w, w+n, greater<int>());LL sum = 0, res = -1;for(int i = 0; i < n; ++i){sum += w[i];if(sum > 0) res = i + 1;else break;}return res;}int main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];for(int i = 0; i < n; ++i) cin >> b[i];for(int i = 0; i < n; ++i) cin >> c[i];LL res = max({work(a, b, c), work(b, a, c), work(c, a, b)});cout << res << endl;return 0;}

三、松散子序列

标签：状态机DP

思路：这个题目的意思就是从一个字符串中选一段子序列，然后不能选相邻的，然后使得这个子序列的价值最大。这个跟那个小偷偷盗差不多，不能选相邻一家的。然后就是每个字符串有两个状态，选或者不选，$f[i][2]$中分别表示前$i$个字母中不选、选第$i$个字母的最大价值，可以推导出方程来$$f[i][0]=max(f[i-1][0],f[i-1][1]),$$f[i][1]=f[i−1][0]+str[i]−′ a ′+1f[i][1]=f[i-1][0]+str[i]-\ ‘a’\ +1 f[i][1]=f[i−1][0]+str[i]−′a′+1最后的结果就是从$f[n][0]$和$f[n][1]$中选一个最大的出来就行了。

题目描述：

给定一个仅含小写字母的字符串 s，假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi个字符。我们定义 s 的一个松散子序列为：对于 i>1 总是有 pi−pi−1≥2。设一个子序列的价值为其包含的每个字符的价值之和（a∼z 分别为 1∼26）。求 s 的松散子序列中的最大价值。输入格式输入一行包含一个字符串 s。输出格式输出一行包含一个整数表示答案。数据范围对于 20% 的评测用例，|s|≤10；对于 40% 的评测用例，|s|≤300；对于70%的评测用例，|s|≤5000；对于所有评测用例，1≤|s|≤106，字符串中仅包含小写字母。输入样例：azaazaz输出样例：78

示例代码：

#include #include #include using namespace std;const int N = 1e6+10;int n;char str[N];int f[N][2];int main(){scanf("%s", str+1);n = strlen(str+1);for(int i = 1; i <= n; ++i){f[i][0] = max(f[i-1][0], f[i-1][1]);f[i][1] = f[i-1][0] + str[i] - 'a' + 1;}cout << max(f[n][0], f[n][1]) << endl;return 0;}