当前位置 : 主页 > 网页制作 > css >

Codeforces Round #588 (Div. 2)

来源:互联网 收集:自由互联 发布时间:2021-06-13
传送门 A. Dawid and Bags of Candies 乱搞。 Code #include bits/stdc++.h#define MP make_pair#define fi first#define se second#define sz(x) (int)(x).size()//#define Localusing namespace std;typedef long long ll;typedef pairint, int pii;c

传送门

A. Dawid and Bags of Candies

乱搞。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
 
 
int a[4];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    for(int i = 0; i < 4; i++) cin >> a[i];
    sort(a, a + 4);
    if(a[0] + a[3] == a[1] + a[2] || a[0] + a[1] + a[2] == a[3]) cout << "YES";
    else cout << "NO";
    return 0;
}

B. Ania and Minimizing

贪心。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
 
int n, k;
char s[N];
 
void run() {
    cin >> s + 1;
    if(n == 1 && k >= 1) {
        cout << 0 << '\n'; return;
    }
    for(int i = 1; i <= n; i++) {
        if(i == 1) {
            if(s[i] > '1' && k) {
                s[i] = '1'; --k;
            }
        } else {
            if(k && s[i] != '0') {
                s[i] = '0'; --k;
            }
        }
    }
    cout << s + 1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    while(cin >> n >> k) run();
    return 0;
}

C. Anadi and Domino

题意:
存在一张图有\(n,n\leq 7\)个点,现在要给他们染上\(1\)~\(6\)的颜色。最后问怎样染色,能够使得\((c_1,c_2)\)这样的对数最多(不计算重复,不考虑顺序,\(c_1,c_2\)表示颜色)。

思路:
一开始想的是随机乱搞一发,结果出了不知道什么错wa了一个点= =
其实直接\(dfs\)就行了,复杂度不会超。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 10;
 
int n, m;
int ans, res;
vector <int> g[N];
int c[N];
bool chk[N][N];
void dfs(int x) {
    if(x == n + 1) {
        res = 0;
        for(int i = 1; i <= n; i++) {
            for(auto it : g[i]) {
                chk[c[i]][c[it]] = 1;
            }
        }
        for(int i = 1; i <= 6; i++) {
            for(int j = i; j <= 6; j++) {
                if(chk[i][j]) {
                    ++res;
                    chk[i][j] = 0;
                }
            }
        }
        ans = max(ans, res);
        return;
    }
    for(int i = 1; i <= 6; i++) {
        c[x] = i;
        dfs(x + 1);
    }
}
void run() {
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    while(cin >> n >> m) run();
    return 0;
}

D. Marcin and Training Camp

题意:
先有\(n\)个人,每个人有两个属性:\(a,b\)。其中\(a\)的含义是,当前这个人会一些技能,技能的\(id\)就为\(a\)里面二进制\(1\)的位置。
\(i\)看不起\(j\),当且仅当\(i\)会一项\(j\)不会的技能。
现在要选择一些人出来作为一支团队,要求不存在一个人看不起其它所有人并且\(b\)的和最大。

思路:
题意不好描述啊感觉= =
首先可以发现一个比较显然的结论:

  • 团队中最大的\(a\)值至少有两个。

因为要\(b\)和最大,所以有推论:

  • 若存在多个人的\(a\)相同,那么他们都可以选择。

处理完上面的情况,剩下的就是\(a\)只出现一次了。接下来又有一个结论:

  • 一个\(a\)能够被选择,当且仅当他作为已选集合的一个子集。

如果不满足上面的条件,那么他就能够看不起其它所有人,除非有其他人\(a\)值和他相同,但这种情况已经排除了。
然后随便写写就好了。


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 7006;
 
struct People{
    ll a, b;
    bool operator < (const People &A) const {
        if(a == A.a) return b < A.b;
        return a < A.a;
    }
}p[N], t[N];
 
int n;
 
void run() {
    for(int i = 1; i <= n; i++) cin >> t[i].a;
    for(int i = 1; i <= n; i++) cin >> t[i].b;
    sort(t + 1, t + n + 1);
    ll ans = 0;
    int tot = 0;
    vector <ll> S;
    for(int i = 1, j; i <= n; i = j) {
        ll tmp = 0, cnt = 0;
        j = i;
        while(j <= n && t[i].a == t[j].a) {
            tmp += t[j].b;
            ++cnt; ++j;
        }
        if(cnt > 1) {
            ans += tmp;
            S.push_back(t[i].a);
        } else {
            p[++tot] = t[i];
        }
    }
    for(int i = 1; i <= tot; i++) {
        int ok = 0;
        for(auto it : S) {
            if((p[i].a & it) == p[i].a) ok = 1;
        }
        if(ok) {
            ans += p[i].b;
//            S.push_back(p[i].a);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    while(cin >> n) run();
    return 0;
}

E. Kamil and Making a Stream

题意:
给出一颗树,每个结点都有其权值,先求所有链的\(gcd\)的和。

思路:

  • 比较直接的想法就是\(O(n^2)\)的暴力,对于每个点\(v\),找到其所有的祖先\(u\),计算\(gcd\)
  • 稍微改进一下,不用找到所有的祖先,只需要找到其父亲与所有祖先的\(gcd\)值就行,但复杂度还是没有变。
  • 发现\(gcd\)的个数很少,大概为\(\log_{2}a[v]\)个,因为每个\(gcd\)都为\(a[v]\)因子。所以直接用一个\(map\)来存一下出现次数就行了。

似乎这里\(map\)\(log\)\(gcd\)\(log\)的分开的...


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 1e9 + 7;
 
int n;
ll a[N];
vector <int> g[N];
 
unordered_map <ll, int> mp[N];
ll ans;
 
void dfs(int u, int fa) {
    for(auto it : mp[fa]) {
        ll now = __gcd(it.fi, a[u]);
        mp[u][now] += it.se;
    }
    ++mp[u][a[u]];
    for(auto it : mp[u]) {
        ans = (ans + it.fi * it.se % MOD) % MOD;
    }
    for(auto v : g[u]) {
        if(v != fa) dfs(v, u);
    }
}
 
void run() {
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    while(cin >> n) run();
    return 0;
}

F. Konrad and Company Evaluation

题意:
给出一个\(n\)个点\(m\)条边的有向图,现在有\(q\)次操作,每次可以选择一个点,然后将它所有的入边反转。
问每次操作过后形成的“三元环”数量,这里“三元环”的定义为对于点\(a,b,c\),有\(a->b->c\),那么这就算作一个。
\(n,m,q\leq 10^5\)

思路:

  • 统计三元环时,易知一个点的贡献为\(out[u]*in[u]\),相当于枚举中点。

问题在于每次如何翻转边并且快速统计答案。然后题解就是暴力翻转就行了...
下面简略证明一下:

  • 我们按照每个点的度从大到小排序,并且以度数为\(\sqrt{2m}\)划分界限,左边为“大点”,右边为“小点”。
  • 易知左边点的个数不会超过\(\sqrt{2m}\)个,而右边点的度数不会超过\(\sqrt{2m}\)
  • 现在将所有边分为三类:在“大点”间的,在“小点”间的,以及跨过中线的,然后依次分析:
    • 显然每次对“小点”操作不会超过\(\sqrt{2m}\)
    • 对于跨过中间的,我们先消耗一定复杂度让其全部指向“小点”,易知复杂度不超过\(O(m)\)
    • 那么每次对“大点”操作,第一类复杂度不会超过\(\sqrt{2m}\)(因为个数只有那么多),对于第三类边,只有可能一开始已经翻转过,那么这类边每次操作的复杂度最高为\(O(T)\)\(T\)表示当前时间。所以对于一个“大点”而言,操作一次的最高复杂度为\(O(q+\sqrt{2m})\),最多操作\(\sqrt{2m}\)次。
      • 综上,总的复杂度为\(O(q\sqrt{2m}+m)\)的样子。

然后暴力就行啦,感觉证明的思想核心还是对度数进行分块然后来分析,挺巧妙的~其实简单点想就是,对于每个点只有可能第一次翻转复杂度较高,后面翻转就跟时间有关了,因为每次翻转对于一个点入度最多增加\(1\)
代码很简单:


Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
 
int n, m;
vector <int> in[N];
int d[N];
 
void run() {
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        if(u > v) swap(u, v);
        ++d[u], ++d[v];
        in[u].push_back(v);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) ans += 1ll * (d[i] - sz(in[i])) * sz(in[i]);
    int q; cin >> q;
    while(q--) {
        cout << ans << '\n';
        int x; cin >> x;
        ans -= 1ll * (d[x] - sz(in[x])) * sz(in[x]);
        for(auto v : in[x]) {
            ans -= 1ll * (d[v] - sz(in[v])) * sz(in[v]);
            in[v].push_back(x);
            ans += 1ll * (d[v] - sz(in[v])) * sz(in[v]);
        }
        in[x].clear();
    }
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    while(cin >> n >> m) run();
    return 0;
}
网友评论