J Counting Triangles

题意

给了一个算法，该算法能够接受一个seed并生成n个节点以及n+1条边权。每条边权要么为1要么为0.问这些点能够组成多少个三条边都是同色的三角形。

题目理解

一开始以为是硬算，计算所有的同色边数量，然后组合数算答案。但是后面发现这样会漏算很多情况，因此本题std为计算异色角数量。说人话就是一个三角形要么有两个异色角，要么全为同色角，只有以上两种三角形类型。因此只要计算有多少个异色角再/2，最后用组合数计算所有点可以组成的三角形数量C(3,n)，用总数减掉上面计算的异色边三角形数量即可。计算异色角的过程以每个点枚举，计算当前点连接的黑色边和白色边的数量，然后两个数量相乘（等价于排列组合）就是当前点的所有异色角数量。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pai;
const int N = 8000 + 10;
const int mod = 1e9 + 7;
ll prime[N];
bool vis[N];
bool edge[8005][8005];
int bl[N], wh[N];

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;
}

inline bool reads(ll &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void getPrime() {
    memset(vis, false, sizeof(vis));
    for (int i = 2; i < N; i++) {
        if (prime[i] == 0) {//数字i没有被标记，说明数字i是素数，把i存入数组prime[]中，代表素数个数的prime[0]自增1
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= N; j++) {
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 1; i <= prime[0]; i++) {
        vis[prime[i]] = true;
    }
}

ll qp(ll b, ll p) {
    ll k, ans = 1;
    ll base = b, ansp = p;
    for (; p; p >>= 1) {
        if (p & 1) ans = (ll) ((ans * base));
        base = (ll) ((base * base));
    }
    return ans;
}

void cal(int n) {
    ll nums = 0;
    for (int i = 0; i < n; i++) {
        nums += wh[i] * bl[i];
    }
    ll dif = nums / 2;
    ll add1 = (n * (n - 1) * (n - 2)) / 6;
    cout << add1 - dif;
}

void solve() {
    int n, seed;
    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();
            if (edge[i][j] == 1) {
                bl[i]++;
                bl[j]++;
            } else {
                wh[i]++;
                wh[j]++;
            }
        }
    cal(n);
}

int main() {
    ll t;
    solve();
    return 0;
}

F 24dian

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pai;
const int N = 28600 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-6;
int n, m;
int cnt = 0;
vector<double> ans[N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

int dfs(vector<double> v) {
    int l = v.size();
    if (l == 1) {
        if (fabs(v[0] - m) < eps)return 2;
        return 0;
    }
    vector<double> nv;
    int res = 0;
    for (int i = 0; i < l; i++) {
        for (int j = i + 1; j < l; j++) {
            nv.clear();
            for (int k = 0; k < l; k++)if (k != i && k != j)nv.push_back(v[k]);
            nv.push_back(v[i] + v[j]);
            res |= dfs(nv);
            nv.pop_back();
            nv.push_back(v[i] * v[j]);
            res |= dfs(nv);
            nv.pop_back();
            nv.push_back(v[i] - v[j]);
            res |= dfs(nv);
            nv.pop_back();
            nv.push_back(v[j] - v[i]);
            res |= dfs(nv);
            nv.pop_back();
            if (fabs(v[i]) > eps) {
                nv.push_back(v[j] / v[i]);
                int flag = 2;
                if ((int) v[i] && (int) v[j] % (int) v[i])flag = 1;
                res |= min(flag, dfs(nv));
                nv.pop_back();
            }
            if (fabs(v[j]) > eps) {
                nv.push_back(v[i] / v[j]);
                int flag = 2;
                if ((int) v[j] && (int) v[i] % (int) v[j])flag = 1;
                res |= min(flag, dfs(nv));
                nv.pop_back();
            }
        }
    }
    return res;
}

int main() {
    read(n);
    read(m);
    if (n < 4) {
        printf("0\n");
        return 0;
    }
    vector<double> v;
    for (int i = 1; i <= 13; i++)
        for (int j = i; j <= 13; j++)
            for (int x = j; x <= 13; x++)
                for (int y = x; y <= 13; y++) {
                    v.clear();
                    v.push_back(i);
                    v.push_back(j);
                    v.push_back(x);
                    v.push_back(y);
                    if (1 == dfs(v)) {
                        ans[cnt++] = v;
                    }
                }
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%.0lf ", ans[i][j]);
        }
        puts("");
    }
    return 0;
}

B Black and white

题意

有一个nm的棋盘，初始为白色。每一个(i,j)位置染成黑色都有对应的代价，但是每22个格子中只需要染其中三个就可以免费染第四个，问染黑棋盘的最小代价。

题目理解

二分图上求最小生成树，只要在n*m条边中选出n+m条边联通就可染黑所有的格子。（why）

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

#define rep(a, b, c) for (int a = b; a <= c; ++a)

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int n, m;
int C[10001][10001];
int dis[10001];
bool vis[10001];
int A[5001 * 5001];

ll prim() {
    memset(dis, 0x3f, sizeof(dis));
    ll res = 0;
    for (int i = 0; i < n + m; ++i) {
        int t = -1;
        for (int j = 1; j <= n + m; ++j) {
            if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
                t = j;
            }
        }
        vis[t] = true;
        if (i)
            res += dis[t];
        for (int j = 1; j <= n + m; ++j) {
            dis[j] = min(dis[j], C[t][j]);
        }
    }
    return 1ll * res;
}

int main() {
    int a, b, c, d, p;
    memset(C, 0x3f, sizeof(C));
    cin >> n >> m >> a >> b >> c >> d >> p;
    A[0] = a;
    rep(i, 1, n * m) {
        A[i] = (1ll * A[i - 1] * A[i - 1] % p * b % p + A[i - 1] * c + d) % p;
    }
    rep(i, 1, n) {
        rep(j, 1, m) {
            C[i][j + n] = A[m * (i - 1) + j];
            C[j + n][i] = A[m * (i - 1) + j];
        }
    }

    cout << prim() << endl;

    return 0;
}