感谢Y总，acwing寒假人多的手速场，冲第一了！！
AcWing 4791. 死或生
某国正在以投票的方式决定 2 名死刑犯（编号$1∼2$）的生死。
共有 n 组人员（编号 $1∼n$）参与投票，每组 $10$ 人。
每组成员只参与一名死刑犯的投票，其中第 $i$ 组人员的投票对象是死刑犯 $t_i$，其中 $x_i$ 人认为他无罪，$y_i$ 人认为他有罪。
在所有人员投票结束后，将对投票结果进行统计。
对于每名死刑犯，如果投他无罪的总票数大于或等于投他有罪的总票数，则他得以生还，否则他将被处死。
请你判断每名死刑犯的生死。
输入格式
第一行包含一个整数$n$ 。
接下来 $n$ 行，每行包含三个整数 $t_i,x_i,y_i$。
保证两名犯人都会被投票。
输出格式
如果第一位死刑犯生还，则在第一行输出 LIVE，否则在第一行输出 DEAD。
如果第二位死刑犯生还，则在第二行输出 LIVE，否则在第二行输出 DEAD。
数据范围
前 33 个测试点满足 $2≤n≤10$。
所有测试点满足$ 2≤n≤1000，1≤t_i≤2，0≤x_i,y_i≤10，x_i+y_i=10$。
输入样例1：
2
1 5 5
2 6 4输出样例1：
LIVE
LIVE简单模拟统计每个人被投的票数和总投票 人数即可，比较2倍关系是否满足，简单模拟问题哦
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main() {
int n;
cin >> n;
int suma = 0, sumb = 0, sumal = 0, sumbl = 0;
while (n--) {
int s, x, y;
cin >> s >> x >> y;
if (s == 1) {
suma += x + y;
sumal += x;
} else {
sumb += x + y;
sumbl += x;
}
}
if (sumal * 2 >= suma)
puts("LIVE");
else
puts("DEAD");
if (sumbl * 2 >= sumb)
puts("LIVE");
else
puts("DEAD");
}
AcWing 4792. 最大价值
已知，小写字母 $a∼z$ 的价值分别为 $w_a,w_b,…,w_z$。
现在，给定一个由小写字母构成的字符串 $S$，请你在这个字符串中插入 $k$ 个小写字母，要求最终得到的字符串的价值尽可能大。
注意：
- 插入的位置可以随意选。
- 插入的字母也可以随意选，可以插入不同字母。
输出最大可能价值。
输入格式
第一行包含一个字符串 $S$。
第二行包含一个整数 $k$。
第三行包含 $26$ 个整数 $w_a,w_b,…,w_z$。
输出格式
一个整数，表示最大可能价值。
数据范围
前 $3$ 个测试点满足，S的长度范围 $[1,5]$。
所有测试点满足，SS 的长度范围$ [1,1000]$，$0≤k≤10^3$，$w_a∼w_z$ 的取值范围 $[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贪心构造
1、求一下最大价值所对应的字母 ch
2、构造最大价值字符串：在 s 后加入 k 次 ch
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main() {
string s;
cin >> s;
ll n, a = 1, mx = 0, b = s.size(), j = 0, z = 0;
cin >> n;
vector<ll> v(26);
for (ll i = 1; i <= 26; i++) {
cin >> v[i];
if (mx < v[i]) {
mx = v[i];
}
}
ll ans = 0;
for (ll i = 0; i < n + b; i++) {
if (i < s.size()) {
ans = ans + ((i + 1) * v[s[i] - 'a' + 1]);
} else {
ans = ans + ((i + 1) * mx);
}
}
cout << ans;
}AcWing 4793. 危险程度
有 $n$ 种化学物质，编号 $1∼n$。
其中，有 $m$ 对物质之间会发生反应。
现在，要将这些化学物质逐个倒入同一个试管之中，具体倒入顺序不限。
我们需要计算一下试管的危险值。
已知，空试管的危险值为 $1$，每倒入一种化学物质，如果该物质能够与之前倒入试管中的一种或多种物质发生反应，则试管的危险值将乘以 $2$。
请你计算并输出，通过合理安排所有化学物质的倒入顺序，能够得到的试管的最大危险值。
输入格式
第一行包含两个整数 $n,m$。
接下来 $m$ 行，每行包含两个整数 $x,y$，表示化学物质 $x$ 和化学物质 $y$ 之间会发生反应。保证同一对化学物质在输入中最多出现一次。
输出格式
一个整数，表示最大危险值。
数据范围
前 44 个测试点满足 $1≤n≤10$。
所有测试点满足 $1≤n≤50$，$0≤m<\frac{n(n−1)}2$，$1≤x<y≤n$。
输入样例1：
1 0输出样例1：
1实际上就是找联通块数量，如果几个之间能反应，就是一个联通块，因此采用并查集搞一个联通块判断就ok了
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
struct DSU {
vector<int> p, cnt;
DSU(int n) : p(n), cnt(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (cnt[x] < cnt[y]) swap(x, y);
cnt[x] += cnt[y];
p[y] = x;
return true;
}
int size(int x) {
return cnt[find(x)];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
long long ans = 1;
DSU d(n);
while (m--) {
int x, y;
cin >> x >> y;
x--, y--;
if (d.merge(x, y)) {
ans <<= 1;
}
}
cout << ans << "\n";
return 0;
}
Comments | 1 条评论