CS round--36

发布时间:2017-7-9 7:15:29
来源:分享查询网

https://csacademy.com/contest/round-36/summary/

C题是一个贪心,最坏情况是,一开始肯定是每一对袜子都抽一个,然后就需要N个袜子了。后面的情况就是相同的了。

就是,整个数组变成了1、1、1、1、1、1、1、1、1这样,之后任意拿一个袜子,都会增加1pair,然后1-->0,很明显第二次拿应该在刚才那个地方拿,使得0-->1,这样pair数不增加,然后又回到1、1、1、1、1、...这样的状态。所以以后就是在同一种颜色里面操作就好了。

对于本来是奇数的情况,全部拿完是最坏的情况,因为有一个袜子匹配不了。

对于本来是偶数的情况,拿奇数个是最坏的情况,因为这样也有一个袜子匹配不了。

然后直接贪心。

D题是一个树的dfs

用一个数组表示当前的集合,cnt表示集合的大小。

每个节点都有insert, erase操作,dfs的时候,回溯的时候反向更新就好(就是本来insert的变成erase)

但是要注意它时候有这个操作,就是本来是erase的,然而当前集合压根就没这个元素,这是有一个没用的操作。

回溯的时候不要重新insert就好

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;const int maxn = 1e5 + 20;struct Edge {    int u, v, tonext;}e[maxn * 2];int first[maxn], num;struct Node {    int val;    bool isUsed;    Node(int _val, int _isUsed) {        val = _val, isUsed = _isUsed;    }};vector<Node> vc[maxn];void addEdge(int u, int v) {    e[num].u = u, e[num].v = v, e[num].tonext = first[u];    first[u] = num++;}int ans[maxn];bool in[maxn];int cnt;void dfs(int cur) {    for (int i = 0; i < vc[cur].size(); ++i) {        int val = vc[cur][i].val;        if (val > 0) {            if (in[val]) continue;            in[val] = true;            cnt++;            vc[cur][i].isUsed = true;        } else {            val = -val;            if (!in[val]) continue;            in[val] = false;            cnt--;            vc[cur][i].isUsed = true;        }    }    ans[cur] = cnt;    for (int i = first[cur]; ~i; i = e[i].tonext) {        dfs(e[i].v);    }    for (int i = 0; i < vc[cur].size(); ++i) {        if (vc[cur][i].isUsed == false) continue;        int val = vc[cur][i].val;        if (val > 0) {            assert(in[val] == true);            in[val] = false;            cnt--;        } else {            val = -val;            in[val] = true;            cnt++;        }    }}void work() {    memset(first, -1, sizeof first);    int n;    cin >> n;    for (int i = 1; i <= n - 1; ++i) {        int u;        cin >> u;        addEdge(u, i + 1);    }    for (int i = 1; i <= n; ++i) {        int k;        cin >> k;        while (k--) {            int val;            cin >> val;            vc[i].push_back(Node(val, false));        }    }    dfs(1);    for (int i = 1; i <= n; ++i) {        cout << ans[i] << endl;    }}int main() {#ifdef local    freopen("data.txt", "r", stdin);//    freopen("data.txt", "w", stdout);#endif//    IOS;    work();    return 0;}
View Code

返回顶部
查看电脑版