前言

最近写完代码才开始整理复盘的$Blog$，确实感觉有些太匆忙了，而且很多东西都忘光光了…

我是咋写的，我为啥这么写，这个为什么这么漂亮（

这场倒是提醒了我行列棋盘有时可以搞成二分图，有时可以搞生成树（实际上这两个也不冲突）…

复盘

B - Black and white

本题最核心的部分是把涂色问题转化为行和列相连通的问题。

我们观察可以发现，假设每一行和每一列都是一个点，在某一方格上涂色相当于连接了某一行和某一列，当这些点连接了$n+m-1$条边互相连通后，就能够填满整个图形。

也就是说，我们需要选择联通行和列的权值和最小的$n+m-1$条边。

如果想到这一步，就能转化为最小生成树的问题。

/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 5005
//#define int long long
using namespace std;
int a, b, c, d, p, n, m, a1, a2, cost[maxn][maxn];
struct Edge{
    int u, v, w;
    bool operator < (const Edge &A){
        return w < A.w;
    }
}E[maxn * maxn];
int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}
long long ans;
int suc, uset[maxn + maxn];
int find(int x){
    return x == uset[x] ? x : uset[x] = find(uset[x]);
}
void unioon(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy)    return;
    ans += cost[x][y - n]; suc++;
    uset[fx] = fy;
}
signed main(void)
{
    n = read(); m = read();
    a = read(); b = read(); c = read(); d = read(); p = read();
    a1 = a;
    for(int i = 1; i <= n * m; i++)
    {
        a2 = (1LL * a1 * a1 * b + a1 * c + d) % p;
        cost[(i + m - 1) / m][i % m == 0 ? m : i % m] = a2;
        a1 = a2;
    }
    /*
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            printf(j == m ? "%lld\n" : "%lld ", cost[i][j]);
    */
    int cnt = 0, pos = 1;
    for(int i = 1; i <= n + m; i++)    uset[i] = i;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            E[++cnt] = (Edge){i, n + j, cost[i][j]};
    sort(E + 1, E + cnt + 1);
    while(suc < n + m - 1)
        unioon(E[pos].u, E[pos].v), pos++;
    printf("%lld\n", ans);
    return 0;
}

此外，还有Bitset优化的一种做法，见【多校训练】2021牛客多校3_MEET YOU FIRST TIME-CSDN博客

/*
 * @date:2021-07-24 13:31:52
 * @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define For(i, x) for (int i = 0; i < (x); ++i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
    return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
    return y < x ? x = y, 1 : 0;
}

const int MAXN = 5000 + 5;

int N, M;
ll a, b, c, d, p;
int A[MAXN][MAXN];
struct Node {
    int val, x, y;
    bool operator < (const Node &x) const {
        return val > x.val;
    }
};
priority_queue<Node> Pq;
bitset<MAXN> C[MAXN];
int Fa[MAXN];

int findFa(int x) {
    return Fa[x] == x ? x : Fa[x] = findFa(Fa[x]);
}

int merge(int x, int y) {
    x = findFa(x), y = findFa(y);
    if (x == y) return x;
    Fa[x] = y;
    C[y] |= C[x];
    return y;
}

int v[MAXN];

int main() {
    scanf("%d%d%lld%lld%lld%lld%lld", &N, &M, &a, &b, &c, &d, &p);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            a = (a * a * b + a * c + d) % p;
            A[i][j] = a;
            Pq.push({A[i][j], i, j});
        }
    }
    int cnt = 0;
    ll val = 0;
    for (int i = 1; i <= M; ++i) {
        Fa[i] = i;
    }
    while (!Pq.empty()) {
        auto x = Pq.top(); Pq.pop();
        int fa = findFa(x.y);
        if (C[fa][x.x]) continue;
        if (v[x.x]) {
            v[x.x] = merge(v[x.x], x.y);
        } else v[x.x] = x.y;
        C[findFa(x.y)][x.x] = 1;
        val += x.val;
        if (++cnt == N + M - 1) break;
    }
    printf("%lld\n", val);
    return 0;
}

C - Minimum grid

观察发现，当某一行某一列的最大值相同时，在此处填数可以同时满足两个条件，能够更好的减少最后的填数和。

因此，可以考虑一种简单的做法。首先按照约束条件将数字全部填入并计算贡献，然后将行列转化为点进行二分图匹配。当匹配成功（行列最大值相同）则减去一次这一匹配的对应权值。

为了使得填数和最小，满足所有约束条件并通过匹配减去了一些填数后，剩下的数字全部填0（因为约束给定的是行列最大值），此时的权值和就是答案。

这种思路还是比较常见的。如第一场使$\sum|a_i-b_i|$最大同样也可以用这个想法来推导。

/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 1000005
#define int long long
using namespace std;
int n, m, k;
int b[maxn], c[maxn], vis[maxn], used[maxn], linker[maxn];
vector<int> G[maxn];
int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}
bool dfs(int u){
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!used[v])
        {
            used[v] = 1;
            if(!linker[v] || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
signed main(void)
{
    int ans = 0;
    n = read(); m = read(); k = read();
    for(int i = 1; i <= n; i++)    b[i] = read(), ans += b[i];
    for(int i = 1; i <= n; i++)    c[i] = read(), ans += c[i];
    for(int i = 1; i <= m; i++)
    {
        int nx = read(), ny = read();
        if(b[nx] == c[ny])
            G[nx].push_back(ny);
    }
    for(int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(vis));
        if(dfs(i))    ans -= b[i];
    }
    printf("%lld\n", ans);
    return 0;
}

E - Math

对于该题的推导做法，只能说赛场上几乎很难想得出来。

不过打表做法还是比较明确的可以看到$(x, x^3)$这一关系。

推导做法有个博主写的不错：2021牛客暑期多校训练营3 E. Math（数论/韦达定理）

/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 8000005
#define int long long
using namespace std;
int t, n;
int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}
void mt(){
    /*
    freopen("tmp.txt", "w", stdout);
    int n = read();
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            if((i * i + j * j) % (i * j + 1) == 0)
                //if(i * i * i != j)
                    printf("%lld %lld %lld\n", i, j, (int)round(pow(i, 1.0/3)));
    */
}

int cnt;
__int128 v1[maxn];
void inits(int lim){
    v1[++cnt] = 1;
    for(int i = 2; i <= lim; i++)
    {
        __int128 n1 = i, n2 = i * i * i;
        while(n2 <= __int128(lim) * lim * lim)
        {
            v1[++cnt] = n2;
            __int128 r = n1;
            n1 = n2;
            n2 = n2 * i * i - r;
        }
    }
    sort(v1 + 1, v1 + cnt + 1);
}
signed main(void)
{
    inits(1e6);
    t = read();    
    while(t--)
    {
        n = read();
        int pos = upper_bound(v1 + 1, v1 + cnt + 1, n) - v1;
        printf("%lld\n", pos - 1);
    }
    return 0;
}

J - Counting Triangles

签到题，关键在于注意到，若有一个三角形三条边是不同颜色的，那么一定有两条边是同色的，而且有两对边是异色的。同色比较难做，我们考虑从反面的异色出发。

我们可以枚举从某个点出去有多少对异色边。由于对于不符合条件的三角形，一定有两对异色边，因此这个枚举出来的答案是真实答案的两倍。通过公式推导出完全图的三角形数目，再减去枚举异色边的对数的一半，就是最终答案了。

/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;

int cnt1[8005], cnt2[8005];
bool edge[8005][8005];

int calc(int v){
    return (v * (v + 1) * (2 * v + 1) / 6 + v * (v + 1) / 2) / 2;
}
signed main(void)
{
    int n, seed;
    cin >> n >> seed;
    srand(seed);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            edge[j][i] = edge[i][j] = read();
        }
    int ans = calc(n - 2), res = 0;
    //printf("%lld\n", ans);
    for(int i = 1; i <= n; i++)
    {
        int nb = 0, nw = 0;
        for(int j = 1; j <= n; j++)
        {
            if(i == j)    continue;
            edge[i][j] ? nb++ : nw++;
        }
        res += nb * nw;
    }
    printf("%lld\n", ans - res / 2);
    return 0;
}

2021牛客多校第三场复盘

2021牛客多校第三场复盘

前言

复盘

B - Black and white

C - Minimum grid

E - Math

J - Counting Triangles