B、Black and white

题目大意

地图规模为 $5000*5000$ 级别，点权 $w_i(0\le w_i<10^5)$ 依靠公式生成，你可以花费点权那么多钱涂黑一个点，如果长方形中 $3$ 个顶点被涂黑了，那么剩下的顶点可以免费涂黑，询问将整张图涂黑的最小代价是多少？

Solution

考点：并查集

我们如何看待涂黑 $3$ 个点第四个点可以免费这个是我们解题的关键。

将 $3$ 个点沿着 $x$ 轴 $y$ 轴方向一路延申，你会发现选中的三个点才会联通在一起，并且我们可以免费填涂的第四个点也在他们的连通块之中。

那么我们把每个 $w_i$ 看成连接了 $(i,n+j)$ 这样行列两个点的权值，做一次特殊一点的最小生成树即可。

#include <bits/stdc++.h>
using namespace std;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 1e5 + 7;
ll n, m;
ll a, b, c, d, p;
vector<pai> G[N];

int fa[5005 * 2];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int solve() {
    n = read(), m = read(), a = read(), b = read(), c = read(), d = read(), p = read();
    ll pre = a, now;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            now = (pre * pre * b + pre * c + d) % p;
            pre = now;
            G[now].push_back({ i, n + j });
        }
    }
    for (int i = 1; i <= n + m; ++i)    fa[i] = i;
    int fu, fv;
    ll res = 0;
    int sz = 0;
    for (int i = 0; i < p; ++i) {
        for (auto& [u, v] : G[i]) {
            fu = find(u), fv = find(v);
            if (fu != fv) {
                fa[fv] = fu;
                res += i;
                ++sz;
                if(sz == n + m - 1){
                    print(res);
                    return 1;
                }
            }
        }
    }

    return 1;
}

int main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

C、Minimum grid

题目大意

你有一个 $n*n(1\le n\le 2e3)$ 的矩阵，他里面有 $m(1\le m\le 8e5)$ 个位置必须填非负整数，并且要求填入的数必须 $0\le a_{ij}\le k(1\le k\le 1e6)$ 。

并且给出每行的最大值 $c_i$ ，以及每列的最大值 $d_j$ ，要求我们构造一个这样合理的行列最大值矩阵的最小 $\sum a_{ij}$ 是多少。

Solution

考点：匈牙利算法

首先我们肯定是从小往大开始枚举填入数的大小，接下来我们可以知道有哪些行，哪些列他们的最大值就是这个数。

因为我们被允许填 $0$ ，所以我们在每一行每一列存在一个他要求的 $c_i,d_j$ 就行了。那么对于一些不相交的行列来说，我们并不能少填某些数，只有在某行某列的最大值相同，并且这行这列还被允许填入数字 $i$ 的时候，这时我们填入一个最大值相当于同时满足了 $2$ 个条件，那么我们就可以少算一次 $i$ 。

那么可能会有某一行和很多列的最大值相同，也可能会有很多汗和某一列的最大值相同，那么求解这个最大匹配的问题就用到匈牙利算法就行了。

最终这个 $i$ 就被计算了行数加列数减去匹配数那么多次。

#include <bits/stdc++.h>
using namespace std;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e3 + 7, M = 1e6 + 7;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};
ll n, m, k;

vector<int> rows[M], cols[M], G[N << 1];
bool vis[N][N];

bool st[N << 1];
int match[N << 1];

bool find(int u) {
    for (auto& v : G[u]) {
        if (st[v])    continue;
        st[v] = 1;
        if (match[v] == -1 || find(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int solve() {
    n = read(), m = read(), k = read();
    int x, y;
    for (int i = 1; i <= n; ++i) {
        x = read();
        rows[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        x = read();
        cols[x].push_back(n + i);
    }
    for (int i = 1; i <= m; ++i) {
        x = read(), y = read();
        vis[x][y] = 1;
    }

    ll res = 0;
    for (int i = 1; i <= k; ++i) {
        if (rows[i].size() == 0 && cols[i].size() == 0)
            continue;
        for (int i = 1; i <= n + n; ++i)    G[i].clear();
        for (auto& row : rows[i])
            for (auto& col : cols[i])
                if (vis[row][col - n]) {
                    G[row].push_back(col);
                    G[col].push_back(row);
                }

        ms(match, -1);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            ms(st, 0);
            if (find(i)) ++cnt;
        }
        res += (rows[i].size() + cols[i].size() - cnt) * 1ll * i;
    }
    print(res);

    return 1;
}

int main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

E、Math

题目大意

想要你求解 $xy+1|x^2+y^2$ 的 $(x,y)$ 有多少对？ $1\le x\le y\le n,1\le n\le 1e5$ 。

Solution

考点：~~OEIS~~韦达定理

赛中的时候通过枚举 $x$ ，然后把全部合理的 $y$ 丢进OEIS之后发现真有这个数列8 27 30 64 112 - OEIS。

然后就发现了生成的公式： $f_0=x\\f_1=x^3\\f_i=x^2*f_{i-1}-f_{i-2}$

然后枚举全部可能的 $x$ ，得到全部的 $f_i$ ，之后进行 $lower\_bound$ 就行了。

关于正确的韦达定理解法可以看看这个博主的E.Math 解题报告（结论、打表）。

const int N = 1e7 + 7;
const ll M = 1e18 + 1;
ll n, m;
ll f[N]; // f[i] = x^2 * f[i-1] - f[i-2]
int cnt = 0;

void init(){
    for (ll i = 2; i * i * i <= M; ++i) {
        ll x = i, y = i * i * i;
        while (y <= M) {
            f[++cnt] = y;
            if ((M + x) / i / i < y)    break;
            ll tmp = y * i * i - x;
            x = y;
            y = tmp;
        }
    }
    sort(f + 1, f + 1 + cnt);
}

int solve() {
    n = read();
    print(upper_bound(f + 1, f + 1 + cnt, n) - f);

    return 1;
}

F、24dian

Solution

对这个题目挺无语的，比较讨厌这种有先决条件的题目，你首先要会传统意义上的 $24$ 点才能做出这题，我就没听说过这种游戏，题目也不带解释。如果你会玩原先的 $24$ 点，那么这题就变成一个纯模拟题，就是原先的基础上加了必须要有不能整除的除法方案。

const int N = 1e6 + 7;

const double eps = 1e-8;
ll n, m;
vector<vector<int>> res;
vector<int> v;

int cnt1, cnt2;

bool isok(const double& x) {
    return x > (int)x + eps;
}

bool isok(const double& x,const double& y) {
    return isok(x) || isok(y) || isok(x / y);
}

void dfs2(bool ok, vector<double> a) {
    int sz = a.size();
    if (sz == 1) {
        if (fabs(a[0] - m) < eps) {
            ++cnt1; // 一组构成m的解
            if (ok)    ++cnt2; // 构成m的前提下还要有分数的解
        }
        return;
    }
    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j < sz; ++j) {
            if (i == j)    continue;
            vector<double> p;
            for (int k = 0; k < sz; ++k) {
                if (k != i && k != j)
                    p.push_back(a[k]);
            }

            p.push_back(a[i] + a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] - a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] * a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] / a[j]);
            dfs2(ok | isok(a[i], a[j]), p);
            p.pop_back();
        }
    }
}

bool check(const vector<int> a) {
    cnt1 = cnt2 = 0;
    vector<double> b(n);
    for (int i = 0; i < n; ++i)    b[i] = a[i];
    dfs2(false, b);
    if (cnt1 && cnt1 == cnt2)    return true;
    return false;
}

void dfs1(int dep, int pre) {
    if (dep == n + 1) {
        if (check(v))
            res.push_back(v);
        return;
    }
    for (int i = pre; i <= 13; ++i) {
        v.push_back(i);
        dfs1(dep + 1, i);
        v.pop_back();
    }
}

int solve() {
    n = read(), m = read();
    dfs1(1, 1);

    print(res.size());
    for (auto& it : res) {
        for (int i = 0, sz = it.size(); i < sz; ++i) {
            print(it[i], " \n"[i + 1 == sz]);
        }
    }

    return 1;
}

G、Yu Ling(Ling YueZheng) and Colorful Tree

题目大意

给出一棵有根树，根节点是 $1$ ，树上边权告诉你。之后题目有两种操作。

选择一个点 $u$ 把它变成一种颜色 $x$ ，保证任意时间内某种颜色只会有一个唯一的 $u$ 。
询问对于一个点 $u$ ，在他的祖先们中，谁离 $u$ 最近并且满足 $fa$ 的颜色是 $x$ 的倍数，并且 $fa$ 的颜色在区间 $[l,r]$ 中。

Solution

标答写的是树分块+ $Bitset$ ，不过好像没什么人是这么写的。

赛后见了一个暴力的做法居然过了，跑出树上节点的 $dfs$ 序和时间戳。

然后暴力的枚举 $[l,r]$ 中间 $x$ 的倍数，因为颜色和 $u$ 唯一对应，那么我们就可以通过时间戳判断是不是祖先关系。

不过这种做法好像挺假的，看了逆十字的代码，因为颜色都是正的好像祖先关系可以通过二分去找…

const int N = 1.1e5 + 7;
ll n, m;
vector<pai> G[N];
int dep[N], in[N], out[N], tot, pos[N];

void dfs(int u) {
    in[u] = ++tot;
    for (auto& [v, w] : G[u]) {
        if (in[v])    continue;
        dep[v] = dep[u] + w;
        dfs(v);
    }
    out[u] = ++tot;
}

int solve() {
    n = read(), m = read();
    int u, v, w;
    for (int i = 1; i < n; ++i) {
        u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    dfs(1);

    int op, l, r, x;
    while (m--) {
        op = read();
        if (!op) {
            u = read(), x = read();
            pos[x] = u; // 当前颜色x的节点编号为u
        }
        else {
            u = read(), l = read(), r = read(), x = read();
            int be = (l + x - 1) / x * x;
            int ans = LLONG_MAX;
            for (int i = be; i <= r; i += x) {
                if (pos[i] == 0)    continue;
                if (in[pos[i]] <= in[u] && out[pos[i]] >= out[u]) {
                    ans = min(ans, dep[u] - dep[pos[i]]);
                }
            }
            if (ans == LLONG_MAX)    puts("Impossible!");
            else print(ans);
        }
    }

    return 1;
}

J、Counting Triangles

题目大意

题目生成一个完全图，图上边权只有黑白两种，询问有多少个三角形边的颜色完全一致。

Solution

考点：容斥

我们思考在不存在限制的时候选择三角形数目等于 $C_n^3$ ，我们只需要用总数减掉不符合要求的三角形数目即可。

那么我们就要思考什么样的三角形是不符合要求的。一定是有一条边和另外两条边颜色不一样，那么这条不一样的变就会连接两个端点，这两个端点之间也一定连接着不同颜色的多条边。

我们就可以对每个点数他连接的黑边数和白边数，两者相乘就是非法的数量了，注意我们这里要除以 $2$ ，因为黑白，白黑被计算了两次。

int black[8005], white[8005];

int solve() {

    int n, seed;
    cin >> n >> seed;
    srand(seed);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (read())    ++black[i], ++black[j]; // 用他的生成函数
            else ++white[i], ++white[j];
        }


    ll ans = 1ll * n * (n - 1) * (n - 2) / 6, res = 0;
    for (int i = 0; i < n; ++i)    res += black[i] * white[i];

    print(ans - res / 2);

    return 1;
}

2021牛客暑期多校训练营3

B、Black and white

题目大意

Solution

C、Minimum grid

题目大意

Solution

E、Math

题目大意

Solution

F、24dian

Solution

G、Yu Ling(Ling YueZheng) and Colorful Tree

题目大意

Solution

J、Counting Triangles

题目大意

Solution