本场出3
排名219

E.Math

CY

IMO的一道题，居然变成了签到题。

J.Counting Triangles

WXL

找到三条边使得以此三条边为三角的颜色相同，问能找出多少个这种三角形。
解： a n s = C n 3 − c a n ′ t ans = C_{n}^{3} - can't ans=Cn3​−can′t
式中 c a n ′ t can't can′t指的是不能的，相当于反着求。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
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;
bool edge[8005][8005];
signed main() 
{
    int n, seed;
    ll ans = 0;
    cin >> n >> seed;
    srand(seed);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edge[j][i] = edge[i][j] = read();
    ll no = 0;
    for(int i=0;i<n;++i)
    {
        int blk = 0;
        for(int j=0;j<n;++j)
        {
            if(edge[i][j] == 1) ++blk;
        }
        int wht = n - 1 - blk;
        no += blk * wht;
    }
    cout <<  (n * (n-1)*(n-2)) / 6 - no / 2;
}

A.Guess and lies

WXL
t a g : tag: tag:博弈+dp

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 2e3+3;
int dp[30][N][N];
int calc(int x,int y){
    int ans=19;
    while(ans&&dp[ans-1][x][y]>=0)ans--;
    return ans;
}
int main(){
    memset(dp,-1,sizeof(dp));
    cin >> n;
    for(int i=0;i<=1;++i)
    {
        for(int j=0;j<=1-i;++j)
        {
            dp[0][i][j] = 1-(i+j);
        }
    }
    //t v k
    //i j k
    for(int i=0;i<=18;++i)
    {
        for(int j=0;j<=n;++j)
        {
            for(int k=0;k<=j;++k)
            {
                int u = dp[i][j-k][k];
                int v = dp[i][k][j-k];
                if(u != -1 && v != -1)
                {
                    u = min(u,n-j);
                    dp[i+1][u][j] = max(dp[i+1][u][j], v);
                }
            }
        }
        for(int j=0;j<=n;++j)
        {
            if(dp[i][j][0] != -1)
            {
                int v = dp[i][j][0];
                for(int k=0;k<=n-j;++k)
                {
                    int u = dp[i][k][j];
                    if(u == -1) break;
                    dp[i+1][min(n-j,u)][j] = max(dp[i+1][min(n-j,u)][j],v+k);
                    dp[i+1][min(v+k,n-j)][j] = max(dp[i+1][min(v+k,n-j)][j], u);
                }
            }
        }
        for(int j=0;j<=n;++j)
        {
            for(int k=n-j-1;k>=0;--k)
            {
                dp[i+1][k][j] = max(dp[i+1][k][j], dp[i+1][k+1][j]);
            }
        }
    }
    for(int i=n;i>=1;--i)
    {
        cout << calc(n-i,i) << ' ';
    }

    return 0;
}

C.Minimum grid

补
给你一个 n ∗ n n*n n∗n大小的网格，每一行最大值 b i b_i bi​，每一列最大值 c i c_i ci​，你需要对一些点赋值，使得总的赋值和最小。
将每个数值对应的行，以及每个数值对应的列分别进行存储。枚举每一个数值，范围 [ 1 ∼ k ] [1 \sim k] [1∼k]
枚举当前数值所对应的行和列，如果当前行列可以填数，则将行和列建边，求出行和列的最大匹配数。

当前数值的贡献为：(当前值对应的行数+当前值对应列数-最大匹配数)*当前值。
使用vector进行存储，所对应的值就是
[ v 1 [ n o w ] . s i z e ( ) + v 2 [ n o w ] . s i z e ( ) − m a x p i p e i ] ∗ n o w ， [v_1[now].size()+v_2[now].size()-max_{pipei}]*now， [v1​[now].size()+v2​[now].size()−maxpipei​]∗now，(now为当前值)
此处的最大匹配值可以理解为当前行和列的最大值均已经满足，可以填0的最大数量。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10, M = 1e6 + 10, inf = 1e8;
int n, m, k, x;
int mp[N][N];
vector<int> G1[M], G2[M];
vector<int> G[N];
int st[N], match[N];
bool dfs(int u){
    for(auto j : G[u]){
        if(st[j]) continue;
        st[j] = 1;
        if(match[j] == -1 || dfs(match[j])){
            match[j] = u;
            return 1;
        }
    }
    return 0;
}
int cal(){ 
    memset(match, -1, sizeof(match));
    int res = 0;
    for(int i = 1; i <= n + n; i++){
        memset(st, 0, sizeof(st));
        if(dfs(i)) res++;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++) cin>>x, G1[x].push_back(i);
    for(int i = 1; i <= n; i++) cin>>x, G2[x].push_back(i+n);
    for(int i = 1; i <= m; i++){
        int x, y; cin>>x>>y;
        mp[x][y] = 1;
    }
    ll ans = 0;
    for(int now = k; now >= 1; now--){
        if(G1[now].size() == 0 && G2[now].size() == 0) continue;
        for(int i = 1; i <= n + n; i++) G[i].clear();
        for(auto i : G1[now])
            for(auto j : G2[now])
                if(mp[i][j-n]) G[i].push_back(j), G[j].push_back(i); 
                // 建图
        ll maxpipei = cal()/2;
        ll maxm = G1[now].size() + G2[now].size() - maxpipei;
        ans = ans + maxm * now;
    }
    cout<<ans<<endl;
    return 0;
}

B.Black and white

补
为了实现最少花费，需满足：在我们涂完若干个点后，其他的点对总花费不再有贡献（涂黑这些点时不花钱了）
我们会发现 ：最少，我们需要涂黑 n + m - 1 个点，且涂完这些点后 所有的行 和所有的列 会都在一个联通块里面

举例 如下：
不妨令 n = 2，m = 2，此时我们最少需要涂 3个点
令 g[1][1] = g[1][2] = g[2][1] = 1，g[2][2] = 3
为了最少花费，我们要涂的三个点显然是：(1,1)，(1,2)，(2,1)
涂完(1,1)后，我们把 行1 和 列1 放到一个联通块里面
涂完(1,2)后，我们把 行1 和 列2 放到一个联通块里面
涂完(2,1)后，我们把 行2 和 列1 放到一个联通块里面
到此，所有的行 和 所有的列 都在一个联通块里了，同时我们也实现了最少花费

在这个例子中，涂黑任意三个点都可以实现 把所有的行 和 所有的列 都放在一个联通块里
但为了 最少花费，所以我们选择的是 (1,1)，(1,2)，(2,1) 这三个点
我们提炼出两个关键字 联通块、最小花费：连通块（并查集）+ 最小花费 = Kruskal(最小生成树)

所以该题使用 Kruskal 求最小(花费)生成树

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e7+10;
const int M = 5010;

struct node{
    int x,y;
    ll v;
    bool operator < (const node & u) const { return v < u.v; }
}A[N];
int fa[2*M];
int n,m,a,b,c,d,p;

void Init(){
    A[0].v=a; 
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)  {
        int id=m*(i-1)+j;
        A[id]={i,j,((ll)A[id-1].v*A[id-1].v*b+(ll)A[id-1].v*c+d)%p};
    }
}

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void kruskal(){
    //选若干个点（最少n+m-1个）,使得所有行，所有列在一个联通块里面
    ll res=0,cnt=n+m-1;
    for(int i=1;i<=n+m;i++) fa[i]=i; // 1~n 表示行，n+1~n+m 表示列

    sort(A+1,A+1+m*n);
    for(int i=1;i<=m*n;i++){
        int x=A[i].x,y=A[i].y,v=A[i].v;
        x=find(x),y=find(n+y);
        if(!cnt) break;  
     // 按理说 没有 cnt 这个变量 应该也可以，但是去掉后 只能过90% 剩下的10% 会 T，不知道为啥
        if(x!=y){    
            fa[x]=y;
            res+=v;
            cnt--;
        }
    }
    cout<<res<<endl;
}

int main(){
    cin>>n>>m>>a>>b>>c>>d>>p;
    Init();
    kruskal();
    return 0;
}