CF 990 Educational Codeforces Round 45

既然补了就简单记录一下。

感觉还算有一点营养。

官方题解传送门：点我

A Commentary Boxes

对拆掉$n mod m$个和新建$m - (n mod m)$求个最小。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll n, m, a, b, r;
    scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
    r = n % m;
    printf("%lld
", min(b * r, (m - r) * a));
    return 0;
}

B Micro-World

对所有数排序，从小到大扫，能吃就吃。

一个细菌如果不被刚好比它大的那个吃掉，那么再大一点的也不能吃掉。

注意到相同的数可能处理起来有一点问题，像我这种懒人就直接开个$map$当平衡树用。

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

int n, k;
map <int, int> mp;

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for (; ch > '9'|| ch < '0'; ch = getchar())
        if (ch == '-') op = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

int main() {
    read(n), read(k);
    for (int v, i = 1; i <= n; i++) {
        read(v);
        ++mp[v];
    }    
    
    map <int, int> :: iterator lst = mp.begin(), now = mp.begin();
    ++now;
    int ans = 0;
    for (; now != mp.end(); ++lst, ++now) 
        if (now -> first <= lst -> first + k) ans += lst -> second;
    
    printf("%d
", n - ans);
    return 0;
}

C Bracket Sequences Concatenation Problem

话说最近的几场中有类似的题目啊。

一个括号序列在自身匹配完之后一定能表示成若干个右括号$+$若干个左括号（比如$))))(((($）的形式，两个括号序列接起来能匹配的充要条件是：

1、前面的那个没有多余的右括号。

2、后面的那个没有多余的左括号。

3、前面的左括号和后面的右括号个数相同。

开个$map$正反扫一扫，注意不要忘记计算一个括号序列自身可能的贡献。

#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;
typedef pair <int, int> pin;
typedef long long ll;

const int N = 3e5 + 5;

int n;
pin a[N];
char s[N];
map <int, int> mp;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        int len = strlen(s + 1), top = 0;
        for (int j = 1; j <= len; j++) {
            if (s[j] == '(') ++top;
            else {
                if (top) --top;
                else ++a[i].first;
            }
        }
        if (top != 0) a[i].second += top;
    }
    
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].second == 0) ans += mp[a[i].first];
        if (a[i].first == 0) ++mp[a[i].second];
    }
    
    mp.clear();
    for (int i = n; i >= 1; i--) {
        if (a[i].second == 0) ans += mp[a[i].first];
        if (a[i].first == 0) ++mp[a[i].second];        
    }
    
    for (int i = 1; i <= n; i++)
        if (a[i].first == 0 && a[i].second == 0) ++ans;
    
    printf("%lld
", ans);
    return 0;
}

D Graph And Its Complement

我觉得这是这场最有趣的一道题。

做出这个首先需要发现一条性质，$n, a, b$一定需要满足$a == 1$或者$b == 1$的形式才可能有解。

可能的意思是说在$a == 1$并且$b == 1$并且$n == 2 || n == 3$的时候无解。

假设原图有超过$1$个连通块，那么对于任意两个联通块来说，取补集之后都会有一条边相连，所以补图一定只有一个连通块。

如果$b$为$1$并且$a$不为$1$可以$swap$过来然后输出补图。

这样子把$1$到$n - a + 1$连成一条链就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1005;

int n, a, b;
bool ans[N][N];

int main() {
    scanf("%d%d%d", &n, &a, &b);
    if (a != 1 && b != 1) return puts("NO"), 0;
    if (a == 1 && b == 1) {
        if (n == 2 || n == 3) return puts("NO"), 0;
        for (int i = 1; i < n; i++) ans[i][i + 1] = ans[i + 1][i] = 1;
        puts("YES");
        for (int i = 1; i <= n; i++, putchar('
'))
            for (int j = 1; j <= n; j++)
                putchar(ans[i][j] + '0');
        return 0;
    }
    
    bool flag = 0;
    if (a == 1) swap(a, b), flag = 1;
    if (flag) memset(ans, 1, sizeof(ans));
    for (int i = 1; i <= n - a; i++) ans[i][i + 1] ^= 1, ans[i + 1][i] ^= 1;
    
    puts("YES");
    for (int i = 1; i <= n; i++, putchar('
'))
        for (int j = 1; j <= n; j++) {
            if (i == j) putchar('0');
            else putchar(ans[i][j] + '0');
        }
    
    return 0;
}

E Post Lamps

这题我纠结了很长时间的第一个样例，因为怎么玩都有比样例输出更好的答案，直到我在$announcement$里面发现了这样一句话：

感觉无话可说……

先考虑没有“不能放”的限制的时候怎么做，对于每一个亮度$k$，贪心地把它放在$0, k, 2k, cdots$直到大于等于$n$。

现在加入限制条件，考虑如果在跳的时候遇到了一个障碍，就尝试在这个障碍前面最近的一个不是障碍的位置放灯，如果这样还是不可以照亮它，那么直接无解。

障碍在$0$的时候可以直接无解。

可以用一个并查集，遇到障碍就把父指针指向前一个位置，这个并查集可以路径压缩。

注意到这个复杂度其实是一个调和级数，虽然并不是特别严格，但是根本跑不满。

应该比$D$简单吧。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const ll inf = 1LL << 60;

int n, m, k, ufs[N];
ll a[N];
bool b[N];

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for (; ch > '9'|| ch < '0'; ch = getchar())
        if (ch == '-') op = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

template <typename T>
inline void chkMin(T &x, T y) {
    if (y < x) x = y;
}

int find(int x) {
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

int main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= n; i++) ufs[i] = i;
    for (int pos, i = 1; i <= m; i++) {
        read(pos);
        if (pos == 0) return puts("-1"), 0;
        b[pos] = 1;
        ufs[pos] = pos - 1;
    }     
    b[n] = 1, ufs[n] = n - 1;
    for (int i = 1; i <= k; i++) read(a[i]);
    
    ll ans = inf;
    for (int i = 1; i <= k; i++) {
        int cnt = 0; ll res = 0;
        for (int j = 0; j < n; j += i) {        
            if (!b[j]) ++cnt;
            else {
                int pos = find(ufs[j]);
                if (j - pos < i) ++cnt, j = pos;
                else {
                    res = inf;
                    break;
                }
            }    
        }
        if (res != inf) res = 1LL * cnt * a[i];
        chkMin(ans, res);
    }
    
    printf("%I64d
", ans == inf ? -1 : ans);
    return 0;
}

F Flow Control

虽然网络流已经差不多忘得一干二净了，但是流量守恒这一点还是能记住手玩出来的。

先把所有的$s_i$求和，如果不为$0$一定不合法。

注意到当有环的时候有一些边可以随便流，等价于就算这些边不存在（流量为$0$）也能出解。

所以做一棵生成树就好了，不在生成树中的边流量输出$0$。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair <int, int> pin;

const int N = 2e5 + 5;

int n, m, tot = 0, head[N], ufs[N], dep[N];
ll a[N], sum[N];
bool vis[N];
pin pat[N];

struct Edge {
    int to, nxt;
} e[N << 1];

inline void add(int from, int to) {
    e[++tot].to = to;
    e[tot].nxt = head[from];
    head[from] = tot;
}

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for (; ch > '9'|| ch < '0'; ch = getchar())
        if (ch == '-') op = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

int find(int x) {
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

inline bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return 0;
    ufs[fx] = fy;
    return 1;
}

inline bool chk() {
    ll tmp = 0;
    for (int i = 1; i <= n; i++) tmp += a[i];
    return (!tmp);
}

void dfs(int x, int fat, int depth) {
    dep[x] = depth, sum[x] = a[x];
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y == fat) continue;
        dfs(y, x, depth + 1);
        sum[x] += sum[y];
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        ufs[i] = i;
    }
    read(m);
    for (int x, y, i = 1; i <= m; i++) {
        read(x), read(y);
        pat[i].first = x, pat[i].second = y;
        if (!merge(x, y)) continue;
        vis[i] = 1;
        add(x, y), add(y, x);    
    }
    
    if (!chk()) return puts("Impossible"), 0;
    
    dfs(1, 0, 1);
    
    puts("Possible");
    for (int i = 1; i <= m; i++) {
        if (vis[i]) 
            printf("%lld
", dep[pat[i].first] < dep[pat[i].second] ? sum[pat[i].second] : -sum[pat[i].first]);
        else puts("0");
    }
    
    return 0;
}

G GCD Counting

因为统计的时候复杂度是只和$gcd$的个数有关的，所以可以直接大力点分治，复杂度也是没问题的。

但是点分治真的写不对这样太无脑了，考虑正解提到的稍微有一点技术含量的做法。

用$h(i)$表示树上能被$i$整除的路径的数量，注意到在树上一定是若干个满足条件的联通块选点之后求和。

一个$siz$为$n$的连通块的贡献是$frac{n(n + 1)}{2}$。

那么最后的答案

$$ans_x = sum_{i = x}^{left lfloor frac{n}{x} ight floor}mu(i)h(xi)$$

我选择用一个并查集合并一下。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
const int Maxn = 2e5;

int n, a[N], tot = 0, head[N], fa[N];
int pCnt = 0, pri[N], mu[N], ufs[N], siz[N];
bool np[N], vis[N];
ll ans[N], f[N];
vector <int> h[N], vec;

struct Edge {
    int to, nxt;
} e[N << 1];

inline void add(int from, int to) {
    e[++tot].to = to;
    e[tot].nxt = head[from];
    head[from] = tot;
}

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for (; ch > '9'|| ch < '0'; ch = getchar())
        if (ch == '-') op = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline void sieve() {
    mu[1] = 1;
    for (int i = 2; i <= Maxn; i++) {
        if (!np[i]) 
            pri[++pCnt] = i, mu[i] = -1;
        for (int j = 1; j <= pCnt && pri[j] * i <= Maxn; j++) {
            np[i *  pri[j]] = 1;
            if (i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
}

void dfs(int x, int fat) {
    fa[x] = fat;
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y == fat) continue;
        dfs(y, x);
    }
}

int find(int x) {
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

inline bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return 0;
    if (siz[fx] < siz[fy]) ufs[fx] = fy, siz[fy] += siz[fx];
    else ufs[fy] = fx, siz[fx] += siz[fy];
    return 1;
}

int main() {
    sieve();
    
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        h[a[i]].push_back(i);
    }
    for (int x, y, i = 1; i < n; i++) {
        read(x), read(y);
        add(x, y), add(y, x);
    }
    dfs(1, 0);
    
    for (int i = 1; i <= Maxn; i++) {
        for (int j = i; j <= Maxn; j += i)
            for (int k = 0; k < (int)h[j].size(); k++) {
                int x = h[j][k];
                ufs[x] = x, siz[x] = 1, vis[x] = 0;
                vec.push_back(x);
            }
        
        for (int j = 0; j < (int)vec.size(); j++) {
            int x = vec[j];
            if (fa[x] && a[fa[x]] % i == 0) merge(x, fa[x]);
        }
        
        for (int j = 0; j < (int)vec.size(); j++) {
            int x = vec[j], fx = find(x);
            if (vis[fx]) continue;
            f[i] += 1LL * siz[fx] * (siz[fx] + 1) / 2;
            vis[fx] = 1;
        }
        
        vec.clear();
    }
    
    for (int i = 1; i <= Maxn; i++)
        for (int j = i; j <= Maxn; j += i)
            ans[i] += 1LL * mu[j / i] * f[j];
    
    for (int i = 1; i <= Maxn; i++) {
        if (!ans[i]) continue;
        printf("%d %I64d
", i, ans[i]);
    }
    
    return 0;
}