省选测试7

A 同桌的你

题目大意 ： 每人选一个人，进行配对，定义满意为这一对中存在一个人选了另一个人，在满意的对数最多的情况下，让满意的配对中异性的配对尽量多，给出构造

• 容易发现选择关系建出图来的话就是一颗内向基环树，如果我们把同性的便权设为 1e6+1，异性的便权设为 1e6+2，这样就是在这颗基环树上选出一些边，一个点连的边（无论是入度还是出度）只能有一条边被选，让选出的边权和ans最大，这样满意的对数就是 ans/(1e6+1)，异性的对数就是 ans%(1e6+1)

• 这样知道怎么断环就可以直接树上DP了。

• 定义f[i][0/1]表示在以i为跟的子树中，选(1)或不选(0)根所造成的最大贡献，转移看式子应该好懂

[f[x][0]=sum_{yin son_x}max(f[y][0],f[y][1]) ]

[f[x][1]=max_{yin son_x}{f[x][0]-max(f[y][0],f[y][1])+f[y][0]+dis(x,y)} ]

• 给出构造的话就是在更新f[x][1]的时候记录下来从哪里转移的就可以了

• 对于基环树就一定要断一条环边了，对于这道题断任意一条环边都一样，分别考虑不选这条边，和选这条边

  • 不选这条边的话，那么在DP到这条边的时候跳过就好了

  • 选的话就得让这条便的两个端点x,y不能被其他点匹配，这样在转移f[i][1]的时候遇到儿子是x或y的时候就跳过，假如将x作为跟，就不转移f[y][1]，将它设为0

Code

Show Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

struct Edge {
    int n, t, d;
}e[N*2];
int h[N], edc;

void Add(int x, int y, int z) {
    e[++edc] = (Edge) {h[x], y, z}, h[x] = edc;
}

bool v1[N], v2[N], *v, c[N], d[N];
ll f1[N][2], f2[N][2], (*f)[2], ans;
int n, t[N], a[N], in[N], q[N], od, g1[N], g2[N], (*g), stk[N], tp;

void Dfs(int x, int fa) {
    v[x] = 1;
    //v标记是否访问
    for (int i = h[x], y; i; i = e[i].n)
        if (!v[y=e[i].t]) Dfs(y, x), f[x][0] += max(f[y][0], f[y][1]);
    //f就是Dp数组
    for (int i = h[x], y; i; i = e[i].n) {
        if ((y = e[i].t) == fa) continue;
        if (od == 1 && (d[x] && d[y])) continue;
        if (od == 2 && (d[x] || d[y])) continue;
        ll tmp = f[x][0] - max(f[y][0], f[y][1]) + f[y][0] + e[i].d;
        if (tmp > f[x][1]) f[x][1] = tmp, g[x] = y;//g记录从哪转移
    }
}

void Print(int x, bool od) {
    //od 为 0表示他被父亲选了，不能再和儿子匹配
    v[x] = 1;
    if (od && f[x][1] > f[x][0]) printf("%d %d
", x, g[x]);
    //od 为 1 可以匹配儿子，当选了比不选优的时候就选儿子
    for (int i = h[x], y; i; i = e[i].n)
        if (!v[y=e[i].t]) Print(y, !((y == g[x]) && od && f[x][1] > f[x][0]));
}

int main() {
    for (int T = read(); T; --T) {
        edc = ans = 0;
        memset(c, 0, n + 1);
        memset(v1, 0, n + 1);
        memset(v2, 0, n + 1);
        memset(h, 0, n * 4 + 4);
        memset(in, 0, n * 4 + 4);
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        n = read();
        for (int i = 1; i <= n; ++i)
            t[i] = read(), a[i] = read(), in[t[i]]++;
        //t[i] i 喜欢的人
        //a[i] i 的类型
        //in[i] i 的入度
        int l = 1, r = 0;
        for (int i = 1; i <= n; ++i) {
            int d = N + (a[i] != a[t[i]]);//边权
            Add(i, t[i], d); Add(t[i], i, d);//加双向边
            if (!in[i]) q[++r] = i;//没入度的入队
        }
        while (l <= r) {//拓扑
            int x = q[l++]; c[x] = 1;
            //c[x] 为 1 表示拓扑过这个点，说明他不在环上
            if (!--in[t[x]]) q[++r] = t[x];
        }
        for (int i = 1; i <= n; ++i) {
            if (v1[i] || c[i]) continue;
            //如果一个点被访问过或不在环上就跳过
            d[i] = d[t[i]] = 1; //d为1 的点是当前选的边的两个端点
            od = 1; v = v1; g = g1; f = f1; Dfs(i, 0);
            //od是Dfs中要用的类型
            od = 2; v = v2; g = g2; f = f2; Dfs(i, 0);
            f[i][1] = f[i][0] + N + (a[i] != a[t[i]]); g[i] = t[i];
            //f2还得匹配上当前i和t[i]的边
            ans += max(f2[i][1], max(f1[i][0], f1[i][1]));
            d[i] = d[t[i]] = 0; stk[++tp] = i;
            //stk栈记录以哪些点为跟过，输出路径时要用到
        }
        printf("%lld %lld
", ans / N, ans % N);
        memset(v + 1, 0, n);//清空标记
        while (tp) {
            int i = stk[tp--];
            if (max(f1[i][0], f1[i][1]) > f2[i][1]) g = g1, f = f1;
            else g = g2, f = f2; Print(i, 1);
        }
    }
    return 0;
}

B 大水题

题目大意 ： 选择两头牛使得他们之间的距离最远并且在两头牛之间出现过的每种牛的个数相等并不能少于K

• 算一个区间牛的个数的话很容易想到用前缀和优化，考虑如何快速的判断区间出现的每种个数是否相等

• 可以Hash，对于每种牛做个前缀和，有数的都和第一个减一下，类似差分，然后hash起来

• 这样就可以枚举出现牛的集合，遇到没在枚举集合内的牛就清空哈希表

Code

Show Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;
const int N = 1e5 + 5, bs = 1331;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

int n, m, c[1<<8], ans = -1, h[N], hac, stk[N], tp, tot, s[9];

struct Node {
    int x, k;
}a[N];

bool operator < (const Node &a, const Node &b) {
    return a.x < b.x;
}

struct Hash {
    int n[N], v[N]; ull x[N];
    int & operator [] (ull w) {
        int ha = w % N;
        for (int i = h[ha]; i; i = n[i])
            if (x[i] == w) return v[i];
        n[++hac] = h[ha]; x[hac] = w; 
        stk[++tp] = ha; h[ha] = hac;
        return v[hac] = -1;
    }
}mp;

void Clear() {
    hac = tot = 0;
    memset(s, 0, sizeof(s));
    while (tp) h[stk[tp--]] = 0;
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = (Node) {read(), read()};
    sort(a + 1, a + n + 1);
    for (int S = 1; S < 1 << 8; ++S) {
        c[S] = c[S>>1] + (S & 1);
        if (c[S] < m) continue;
        int K; Clear(); mp[0] = a[1].x;
        for (int k = 1; k <= 8; ++k)
            if (S & 1 << k - 1) K = k;
        for (int i = 1; i <= n; ++i) {
            ull ha = 0; tot += !s[a[i].k]++;
            if (!(S & 1 << a[i].k - 1)) {
                Clear(); mp[0] = a[i+1].x; continue;
            }
            for (int k = 1; k < K; ++k)
                if (S & 1 << k - 1)
                    ha = ha * bs + s[k] - s[K];
            int &x = mp[ha];
            if (x == -1) x = a[i+1].x;
            else if (tot >= m) ans = max(ans, a[i].x - x);
        }
    }
    printf("%d
", ans);
    return 0;
}

C 佛罗里达 (Unaccepted)

题目大意 ： n个人两两之间有矛盾值，分成两组，让两组矛盾最大值和最小

• 以前随机化可以过，然后各种大佬一起给卡掉了

Code

Show Code