首页 > 其他分享 >2022杭电多校7

2022杭电多校7

时间:2022-09-25 16:35:47浏览次数:56  
标签:杭电多校 题意 int cin 每次 石头 2022 三角形

这场难度有点大 可改的题没几个

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

相关文章