<一>Acwing 4791. 死或生
一、题目
1、原题链接
4791. 死或生 - AcWing题库
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、原题链接
4792. 最大价值 - AcWing题库
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杯 - 周赛） - AcWingy总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、原题链接
4793. 危险程度 - AcWing题库
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杯 - 周赛） - AcWingy总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;
}
