目录
<一>Acwing 4791. 死或生
一、题目
1、原题链接
2、题目描述
某国正在以投票的方式决定 2 名死刑犯(编号 1∼2)的生死。
共有 n组人员(编号 1∼n)参与投票,每组 10 人。
每组成员只参与一名死刑犯的投票,其中第 i 组人员的投票对象是死刑犯 ti,其中 xi人认为他无罪,yi 人认为他有罪。
在所有人员投票结束后,将对投票结果进行统计。
对于每名死刑犯,如果投他无罪的总票数大于或等于投他有罪的总票数,则他得以生还,否则他将被处死。
请你判断每名死刑犯的生死。
输入格式
第一行包含一个整数 n。
接下来 n 行,每行包含三个整数 ti,xi,yi。
保证两名犯人都会被投票。
输出格式
如果第一位死刑犯生还,则在第一行输出
LIVE
,否则在第一行输出DEAD
。如果第二位死刑犯生还,则在第二行输出
LIVE
,否则在第二行输出DEAD
。数据范围
前 3 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤1000,1≤ti≤2,0≤xi,yi≤10,xi+yi=10。输入样例1:
2 1 5 5 2 6 4输出样例1:
LIVE LIVE输入样例2:
3 1 0 10 2 0 10 1 10 0输出样例2:
LIVE DEAD
二、解题报告
1、思路分析
1)根据题意直接模拟,根据输入的t,来依次统计两名死刑犯的有罪和无罪票数。
2)对投票结果进行判断,针对每名死刑犯输出对应的结果。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
- #include
- using namespace std;
- int main()
- { int n;
- cin>>n;
- int t,x,y;
- int sumx1=0,sumx2=0;
- int sumy1=0,sumy2=0;
- for(int i=0;i
- cin>>t>>x>>y;
- if(t==1){
- sumx1+=x;
- sumy1+=y;
- }
- if(t==2){
- sumx2+=x;
- sumy2+=y;
- }
- }
- if(sumx1
- cout<<"DEAD"<
- }
- else{
- cout<<"LIVE"<
- }
- if(sumx2
- cout<<"DEAD";
- }
- else{
- cout<<"LIVE";
- }
- return 0;
- }
<二>Acwing 4792. 最大价值
一、题目
1、原题链接
2、题目描述
已知,小写字母 a∼z的价值分别为 wa,wb,…,wz。
对于一个由小写字母构成的长度为 l 的字符串 S=s1s2…sl,其价值为 ws1×1+ws2×2+…+wsl×l。
现在,给定一个由小写字母构成的字符串 S,请你在这个字符串中插入 k 个小写字母,要求最终得到的字符串的价值尽可能大。
注意:
- 插入的位置可以随意选。
- 插入的字母也可以随意选,可以插入不同字母。
输出最大可能价值。
输入格式
第一行包含一个字符串 S。
第二行包含一个整数 k。
第三行包含 26 个整数 wa,wb,…,wz。
输出格式
一个整数,表示最大可能价值。
数据范围
前 3 个测试点满足,S的长度范围 [1,5]。
所有测试点满足,SS 的长度范围 [1,1000],0≤k≤10^3,wa∼wz 的取值范围 [0,1000]。输入样例:
abc 3 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1输出样例:
41
二、解题报告:
思路来源:AcWing 4792. 最大价值(AcWing杯 - 周赛) - AcWing
y总yyds
1、思路分析
1)首先,我们要确定插入的字母为哪一个,根据对问题的简单分析,如果我们插入的不是价值最大的,一定不是最优解,所以我们必须插入价值最大的字母。
2)其次,我们要确定插入的位置是哪里?由1)可知我们插入的需要是价值最大的字母,所以,每次插入字母的价值是相同的而且是最大的,我们又可以知道,插入的位置有,字符串前k个位置,字符串每个字母间的位置,还有字符串后k个位置,而这些位置的l(与价值相乘的那个数)是依次增大的,由排序不等式的知识可知,两数列“顺序”相乘和最大,因为可插入位置的l是有序的,所以我们要保证插入的字母的位置的l与原字符串字母的位置的l,尽可能有序,如果我们把字母连续插入,或者说是一起插入到最后,我们就可以保证字符串的最后k个位置的l至少是有序的,而且这至少的k个数的位置l的值也是最大的,而插入字母的价值又是相等的,所以我们只需要让最大的l,次大的l,...依次来乘插入字母的价值,插入字母的总价值一定是最大的。综上,我们需要把字母全部插在字符串的后k个位置,也就是说,需要把插入的字母拼接在字符串后,这样得到的插入字母的总价值最大,同时,也能保证字符串总价值最大。
3)最后,我们模拟上述过程:先找出价值最大的字母,然后将k个该字母全部插到字符串后面,计算原字符串价值和插入字母的价值,最后相加得到字符串最大可能价值,输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
- #include
- #include
- using namespace std;
- int w[26];
- int main()
- { string s;
- cin>>s;
- int ans=0;
- int k;
- cin>>k;
- int max=0;
- for(int i=0;i<26;i++){
- cin>>w[i];
- if(w[i]>max){
- max=w[i];
- }
- }
- int ls=s.size();
- for(int i=0;i
- ans+=w[s[i]-'a']*(i+1);
- }
- for(int i=ls;i
- ans+=max*(i+1);
- }
- cout<
- return 0;
- }
<三>Acwing 4793. 危险程度
一、题目
1、原题链接
2、题目描述
有 n 种化学物质,编号 1∼n。
其中,有 m对物质之间会发生反应。
现在,要将这些化学物质逐个倒入同一个试管之中,具体倒入顺序不限。
我们需要计算一下试管的危险值。
已知,空试管的危险值为 1,每倒入一种化学物质,如果该物质能够与之前倒入试管中的一种或多种物质发生反应,则试管的危险值将乘以 2。
请你计算并输出,通过合理安排所有化学物质的倒入顺序,能够得到的试管的最大危险值。
输入格式
第一行包含两个整数 n,m。
接下来 m行,每行包含两个整数 x,y,表示化学物质 x 和化学物质 y 之间会发生反应。保证同一对化学物质在输入中最多出现一次。
输出格式
一个整数,表示最大危险值。
数据范围
前 4 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤50,0≤m≤n(n−1)/2,1≤x输入样例1:
1 0
输出样例1:
1
输入样例2:
2 1 1 2输出样例2:
2
输入样例3:
3 2 1 2 2 3输出样例3:
4
二、解题报告
思路来源:AcWing 4793. 危险程度(AcWing杯 - 周赛) - AcWing
y总yyds
1、思路分析
1)我们可以利用贪心的思想,尽量使每次加入的物质都能与试管中的物质反应。
2)我们将可以反应的物质看成一个连通块,所以不同的连通块中的物质之间是不能反应的,分析可知,如果有k个物质是可以相互反应的,我们加入这k个物质后危险值最大乘2^(k-1)。我们可以一个连通块,一个连通块地加入,也就是说把可以把一组可以互相反应的物质加入试管,然后再加另一组,这样可以保证除了每组第一种物质加入不反应,其他都要反应,如果假设总共的连通块的数量为q,也就是要反应2^(n-q)次,也就是说危险值要乘2^(n-q),此时危险值为最大。
3)模拟上述过程:利用并查集,将能相互反应的物质组成一个连通块,记录连通块的个数,最后利用2^(n-连通块数)求出最大危险值,输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
- #include
- #include
- using namespace std;
- int s[55];
- void init(int num){
- for(int i=0;i
- s[i]=i;
- }
- }
- int find(int w){
- if(s[w]==w){
- return w;
- }
- else{
- s[w]=find(s[w]);
- return s[w];
- }
- }
- int main()
- { int n,m;
- cin>>n>>m;
- init(n);
- int x,y;
- int cnt=n;//初始没有边,连通块数量为n
- for(int i=0;i
- cin>>x>>y;
- x=find(x),y=find(y);
- //如果x和y能反应,而且x,y的祖宗节点不同,合并x,y,连通块数量减1
- if(x!=y){
- s[x]=y;
- cnt--;
- }
- }
- long long ans=1; //根据数据范围可知,ans为2^49超int,用long long类型
- for(int i=0;i
- ans*=2;
- }
- cout<
- return 0;
- }
<四> 知识风暴
1、排序不等式
内容:两个等长数列每项相乘再相加的和,“顺序”相乘(大数乘大数、次大乘次大、直到最小乘最小)该和最大,“逆序”相乘(最大乘最小、次大乘次小、...)该和最小,其他情况位于两者之间。
2、贪心法
贪心法用于解决最优化问题,这类问题有两种性质:
1)最优子结构:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构。
2)贪心选择性质:指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到。
3、数据范围
1)short:[-2^15,2^15-1]
2)int:[-2^31,2^31-1]
3)long:[-2^31,2^31-1](32位编译器)/ [-2^63,2^63-1](64位编译器)
4)long long:[-2^63,2^63-1]
(注:数据超过10^9左右,使用long long类型,不能继续使用int类型)
4、并查集
并查集主要用于处理一些不相交集合的合并问题
基本操作
初始化
int f[10001]; void init(int N){ for(int i=0;i f[i]=i; } }查找
int find(int x){ if(f[x]==x){ return x; } f[x]=find(f[x]); return f[x]; }合并
void un(int x,int y){ int xf=find(x); int yf=find(y); f[xf]=yf; }
评论记录:
回复评论: