这场难度有点大 可改的题没几个
B. Independent Feedback Vertex Set
题意:
有1-n个点,每个点有权值。初始三个点的互相连接。接下来从第4个点开始,每次给出两个点,保证这两个点之间已经存在边,并与这两个边进行连接。你需
要从这些点中挑出一些点,使得这些点之间不直接相连并且断开这个点四周的边,使得剩下的点组成一片森林,求这些点的权值之和的最大值。
分析:
首先我们要尽可能多选 [最大独立点集]
发现每个三角形最多只能选择一个点
再进一步发现 一个三角形确定了一个选择的点 那么与之相邻的所有三角形也都确定了选哪个点
所以只要初始情况确定了 整个图的状态也就确定了
所以只要枚举第一个三角形选点的情况就好 甚至连图都不用建立
void slove() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pair<int, int>> e(n + 1);
for (int i = 4; i <= n; i++) {
cin >> e[i].first >> e[i].second;
}
int ans = 0;
for (int i = 1; i <= 3; i++) {
int res = 0;
vector<int> color(n + 1);
color[i] = 1;
res += a[i];
for (int j = 4; j <= n; j++) {
int u = e[j].first, v = e[j].second;
if (color[u] == color[v] && color[u] == 0) color[j] = 1, res += a[j];
}
ans = max(ans, res);
}
cout << ans << endl;
}
D. Black Magic
题意:
存在四种石头(类似磁铁),00表示两端都是白色的石头,01表示右端是黑色左端是白色的石头,还有10,11以此类推。将若干个石头排成一列,对于两个石头
相连的部分如果都是黑色的话,这两个石头就会被合在一起。已知四种石头没种石头的数量,求排成一列后最多有多少个石头以及最少多少个石头。
分析:
签到题
void solve() {
int a, b, c, d; cin >> a >> b >> c >> d;
cout << a + b + c - min(b, c) + ((b + c) <= 0 && d) << ' ';
cout << a + b + c + min(a + 1, d) << endl;
}
H. Triangle Game
题意:
给定一个三角形的三条边,每次你可以选择一条边使其减去一个数字,两人轮流进行游戏,如果你操作完这个三角形的面积变成0了那么你就输了,请判断先
手是否必胜。
分析:
对于每次操作 肯定是每次对最大的进行减操作 这样最终会到状态 1 1 1
这样的状态为必败 所以我们猜结论
即进行减一的nim游戏
这个证明只能感性证明
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
int a, b, c;
cin >> a >> b >> c;
cout << (((a - 1) ^ (b - 1) ^ (c - 1)) ? "Win\n" : "Lose\n");
}
return 0;
}
标签:杭电多校,题意,int,cin,每次,石头,2022,三角形
From: https://www.cnblogs.com/wzxbeliever/p/16728076.html