阳新网站建设,整合营销网络推广,镇江网站建设优化案例分析,培训机构软件开发目录 引言一、平均二、三国游戏三、松散子序列 引言
今天做了三道新题#xff0c;类型是贪心、枚举、DP#xff0c;不是特别难#xff0c;但是努力一下刚好能够够得上#xff0c;还是不错的#xff0c;只要能够一直坚持下去#xff0c;不断刷题不断总结#xff0c;就是… 目录 引言一、平均二、三国游戏三、松散子序列 引言
今天做了三道新题类型是贪心、枚举、DP不是特别难但是努力一下刚好能够够得上还是不错的只要能够一直坚持下去不断刷题不断总结就是记忆力和毅力了加油 一、平均
标签贪心
思路贪心这种题目只能是见过类似的然后去变种一般比赛中是不太可能去现推出来的这里只讲一下解题思路。这个变数只有四种情况多变多、多变少、少变多、少变少。 1.多变多多的给多的那么一个变少了一个变多了变多了的肯定又要变成少的所以相当于第一步就多余了反而代价多了 2.少变多少的变多的那么肯定会有一个多的变成少的那么就要多变相当于第一步也就多余了 3.少变少其中的一个少的变少了肯定会有一个多的变成这个少的所以第一步也多余了 所以说只能是多的变少的由于n的数量刚好所以多余的部分肯定是会变的要求又得是代价最少那么就把多余的代价少的那部分变了就行了。
题目描述
有一个长度为 n 的数组n 是 10 的倍数每个数 ai都是区间 [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均而更改第 i 个数的代价为 bi他想更改若干个数的值使得这 10 种数出现的次数相等
都等于 n10)请问代价和最少为多少。输入格式
输入的第一行包含一个正整数 n。接下来 n 行第 i 行包含两个整数 ai,bi用一个空格分隔。输出格式
输出一行包含一个正整数表示答案。数据范围
对于 20% 的评测用例n≤1000
对于所有评测用例n≤1050bi≤2×105。输入样例
10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10
输出样例
27
样例解释
只更改第 1,2,4,5,7,8 个数需要花费代价 12457827。示例代码
#include cstdio
#include iostream
#include algorithm
#include vectorusing namespace std;typedef long long LL;const int N 1e510;int n;
vectorint 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;
}二、三国游戏
标签枚举
思路这道题只有三种情况胜出然后在这其中 x i y i z i , i ∈ ( 1 , n ) 当中任选多个 x_iy_iz_i,i\in(1,n)当中任选多个 xiyizi,i∈(1,n)当中任选多个即 x i − y i − z i 0 , i ∈ ( 1 , n ) 当中任选多个 x_i-y_i-z_i0,i\in(1,n)当中任选多个 xi−yi−zi0,i∈(1,n)当中任选多个可以规定一个 w i w_i wi来表示左半边也就是有多个 w i w_i wi问最多能选多少个使得它们的和大于0我们可以把这些 w i w_i wi由大到小排序然后到了边界条件判断一下就可以了。最后结果从三个国家胜出的最大结果中选最大的就行了。
题目描述
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z一开始可以认为都为 0。游戏有 n 个可能会发生的事件每个事件之间相互独立且最多只会发生一次当第 i 个事件发生时会分别让 X,Y,Z
增加 Ai,Bi,Ci。当游戏结束时 (所有事件的发生与否已经确定)如果 X,Y,Z 的其中一个大于另外两个之和我们认为其获胜。例如当 XYZ 时我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜最多发生了多少个事件?如果不存在任何能让某国获胜的情况请输出 −1。输入格式
输入的第一行包含一个整数 n。第二行包含 n 个整数表示 Ai相邻整数之间使用一个空格分隔。第三行包含 n 个整数表示 Bi相邻整数之间使用一个空格分隔。第四行包含 n 个整数表示 Ci相邻整数之间使用一个空格分隔。输出格式
输出一行包含一个整数表示答案。数据范围
对于 40% 的评测用例n≤500对于 70% 的评测用例n≤5000
对于所有评测用例1≤n≤1050≤Ai,Bi,Ci≤109。
注意蓝桥杯官方给出的关于 Ai,Bi,Ci 的数据范围是 1≤Ai,Bi,Ci≤109但是这与给出的输入样例相矛盾因此予以纠正。输入样例
3
1 2 2
2 3 2
1 0 7
输出样例
2
样例解释
发生两个事件时有两种不同的情况会出现获胜方。
发生 1,2 事件时蜀国获胜。
发生 1,3 事件时吴国获胜。示例代码
#include cstdio
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 1e510;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, wn, greaterint());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 ] f[i][2] f[i][2]中分别表示前 i i i个字母中不选、选第 i i i个字母的最大价值可以推导出方程来 f [ i ] [ 0 ] m a x ( f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] ) , f[i][0]max(f[i-1][0],f[i-1][1]), f[i][0]max(f[i−1][0],f[i−1][1]), f [ i ] [ 1 ] f [ i − 1 ] [ 0 ] s t r [ i ] − ′ a ′ 1 f[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][0] f[n][0]和 f [ n ] [ 1 ] f[n][1] f[n][1]中选一个最大的出来就行了。
题目描述
给定一个仅含小写字母的字符串 s假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi个字符。我们定义 s 的一个松散子序列为对于 i1 总是有 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 cstdio
#include cstring
#include iostreamusing namespace std;const int N 1e610;int n;
char str[N];
int f[N][2];int main()
{scanf(%s, str1);n strlen(str1);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;
}
