AcWing第85场周赛 - 勇敢龙龙
source link: https://www.cnblogs.com/sdnu-dfl/p/17035357.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
这场周赛是手速局hh
死或生
某国正在以投票的方式决定 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：
简单的枚举即可，借助哈希表记录无罪票数和有罪票数
最大价值
已知，小写字母 a∼z 的价值分别为wa,wb,…,wz。
对于一个由小写字母构成的长度为 l 的字符串 ，其价值为S=s1,s2…sl，其价值为ws1×1+ws2×2+…+wsl×l。
现在，给定一个由小写字母构成的字符串 S，请你在这个字符串中插入 k 个小写字母，要求最终得到的字符串的价值尽可能大。
注意：
- 插入的位置可以随意选。
- 插入的字母也可以随意选，可以插入不同字母。
输出最大可能价值。
输入格式
第一行包含一个字符串 S。
第二行包含一个整数 k。
第三行包含 26 个整数 wa,wb,…,wz。
输出格式
一个整数，表示最大可能价值。
数据范围
前 3 个测试点满足，S 的长度范围 [1,5]。
所有测试点满足，S 的长度范围 [1,1000]，0≤k≤103，wa∼wz 的取值范围 [0,1000]。
输入样例：
输出样例：
贪心即可，经过证明（很好证）要得到最大价值，插入方法即在尾部插入k个单个价值的最大的字母
危险程度
有 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<y≤n。
输入样例1：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
题意中几个很重要的性质抓出来
- 第一个放入的物品无法和其他物质反映，因为此时试管中没有其他物品
- 不能相互反应的物品一定严格独立，没有交集
- 假设同一个反应体系中的物品数为k个，则该反应体系对危险程度的贡献度为2k−1，因此我们可以看出，每一个反应体系实际就是一个连通块，即每一个连通块中的物品数量为ki，则该连通块的作用即可为2ki−1
现在共有t个独立的连通块，则总的贡献度为2k1−1 * 2k2−1 * ... * 2ki−1 = 2k1+k2+...+ki−t
我们注意到共有n件物品，因此结果为2n−t，题目瞬间转化为求解独立的连通块的数量
1. 法一：并查集求解独立连通块数量
#include <bits/stdc++.h> using namespace std; const int N = 55; int p[N]; int n,m; typedef long long LL; int find(int x) { if (p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>n>>m; for (int i=1;i<=n;i++) p[i]=i; int cnt=n; // cnt为独立集合的数量，即连通块的数量 while (m--) { int a,b; cin>>a>>b; int pa = find(a); int pb = find(b); if (pa!=pb) { cnt--; p[pa]=pb; } } printf("%lld\n",1ll<<n-cnt); return 0;
}
2. 建图，图的遍历求解连通块的数量
dfs写法一
dfs写法二
#include <bits/stdc++.h> using namespace std; const int N = 55 ,M = N*N; // 无向图注意边数 int e[M],h[N],ne[M],idx; int n,m; typedef long long LL; bool st[N]; void add(int a,int b) // 经典邻接表建图add { e[idx]=b,ne[idx]=h[a],h[a]=idx++; }
void dfs(int x) // dfs遍历无向图 { st[x]=true; for (int i=h[x];~i;i=ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } } int main() { cin>>n>>m; memset(h,-1,sizeof h); // 不初始化的后果就是TLE while (m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); // 无向图即为特殊的有向图 } int cnt=0; // 求解连通块的数量 for (int i=1;i<=n;i++) { if (!st[i]) { dfs(i); cnt++; } } cout<<(1ll<<n-cnt)<<endl; // 答案为2^{n-cnt} return 0; }
bfs写法
#include <bits/stdc++.h> using namespace std; const int N = 55 ,M = N*N; // 无向图注意边数 int e[M],h[N],ne[M],idx; int n,m; typedef long long LL; bool st[N]; queue<int>q; void add(int a,int b) // 经典邻接表建图add { e[idx]=b,ne[idx]=h[a],h[a]=idx++; }
void bfs(int x) // bfs遍历无向图 { st[x]=true; q.push(x); // 借助stl while (q.size()) { auto t = q.front(); q.pop(); for (int i=h[t];~i;i=ne[i]) { int j = e[i]; if (!st[j]) { st[j]=true; q.push(j); } } } } int main() { cin>>n>>m; memset(h,-1,sizeof h); // 不初始化的后果就是TLE while (m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); // 无向图即为特殊的有向图 } int cnt=0; // 求解连通块的数量 for (int i=1;i<=n;i++) { if (!st[i]) { bfs(i); cnt++; } } cout<<(1ll<<n-cnt)<<endl; // 答案为2^{n-cnt} return 0; }
总结
不论是并查集写法，还是dfs和bfs写法，本质都是求解图中的连通子块个数。
因此，我们对求解连通块个数的题型，即可采用并查集和图的遍历这两大类方法，其中图的遍历可以用dfs（代码简洁）或者bfs（思路简单，但借助队列实现代码量较为冗长）
这次确实不难，还是fw，继续努力吧~
__EOF__
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK