目录
<一>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：
输出样例1：
输入样例2：
输出样例2：
二、解题报告
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;
- }
注：本文转载自blog.csdn.net的负重奋进，笃行求实的文章"https://blog.csdn.net/dzk666123/article/details/128603905"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
评论记录：
回复评论：