Overview:

ACdream 群【第三次原创群赛】将于【11月17日星期六晚19点】进行。本次原创群赛由[sjtu]ftiasch（人称 GXX 神牛、叉妹）出题。欢迎大家积极参与～【冠军】和【ACdreamOJ第10000次提交】的ID我们将会赠送小礼品一份 。。 比赛传送门。。。。

（。。。看样子叉娘不愿意在 blog 里贴太学术的东西。。。以下授权转发。。。
ac-dream-3rd.tar （题目、标程、解题报告、测试数据。。。

Official Solutions:

Xor

考虑第\(i\)个二进制位，因为\(n\)是奇数，所以\(A\)中第\(i\)位\(0\)和\(1\)的个数不相等(对于\(B\)也成立）。于是可以确定\(x\)的第\(i\)位，最后再验证\(x\)是否合法即可。

Triangle

由叉积的表达式，知道面积只跟坐标的奇偶性有关，枚举每个点的类型即可。

Tranform

广搜的复杂度是… \[N(1 + \frac{1}{2} + \cdots + \frac{1}{N}) = O(N \log N)\].

Product

\[v(A) = \frac{\prod_{a \in A}(1 + a) – \prod_{a \in A}(1 – a)}{2}\]

Permanent

状压动态规划。

Path

如果 \(x\) 是可行的，那么 \((x – 2)\) 也是可行的，所以可以动态规划求出最长的奇数和偶数。注意负数的情况。

#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100000;

int n, q, parent[N];

int find(int i) {
    return parent[i] == -1 ? i : (parent[i] = find(parent[i]));
}

int edge_count, first_edge[N], to[N << 1], length[N << 1], next_edge[N << 1];

const int INF = 100000000;

int down[N][2], limit[2];

void add_edge(int u, int v, int w) {
    to[edge_count] = v;
    length[edge_count] = w;
    next_edge[edge_count] = first_edge[u];
    first_edge[u] = edge_count ++;
}

#define UPDATE(x, a) x = max(x, a)

void dfs(int p, int u) {
    down[u][0] = 0;
    down[u][1] = -INF;
    for (int iter = first_edge[u]; iter != -1; iter = next_edge[iter]) {
        int v = to[iter];
        int l = length[iter];
        if (v != p) {
            dfs(u, v);
            for (int x = 0; x < 2; ++ x) {
                for (int y = 0; y < 2; ++ y) {
                    UPDATE(limit[x + y + l & 1], down[u][x] + down[v][y] + l);
                }
            }
            for (int y = 0; y < 2; ++ y) {
                UPDATE(down[u][y + l & 1], down[v][y] + l);
            }
        }
    }
}

int main() {
    assert(scanf("%d%d", &n, &q) == 2);
    assert(1 <= n && n <= N);
    assert(1 <= q && q <= N);
    memset(parent, -1, sizeof(parent));
    edge_count = 0;
    memset(first_edge, -1, sizeof(first_edge));
    for (int i = 0; i < n - 1; ++ i) {
        int a, b, c;
        assert(scanf("%d%d%d", &a, &b, &c) == 3);
        assert(1 <= a && a <= n);
        assert(1 <= b && b <= n);
        assert(1 <= c && c <= 2);
        a --;
        b --;
        assert(find(a) != find(b));
        parent[find(a)] = find(b);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
    limit[0] = limit[1] = -INF;
    dfs(-1, 0);
    while (q --) {
        int l;
        assert(scanf("%d", &l) == 1);
        if (l < 0) {
            puts("No");
        } else {
            int t = l % 2;
            puts(l <= limit[t] ? "Yes" : "No");
        }
    }
    return 0;
}

Multiplication

\[C[k] = (A[1] + A[2] + \cdots + A[k]) \cdot B[k] + (B[1] + B[2] + \cdots + B[k]) \cdot A[k] – A[k] \cdot B[k]\]

Matching

利用 Tutte matrix 可以得到很短的\(O(N^3)\)算法。

#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100;
const int MOD = 1000000000 + 7;

int n, a[N][N];

int inverse(int a) {
    return a == 1 ? 1 : (long long)(MOD - MOD / a) * inverse(MOD % a) % MOD;
}

int main() {
    assert(scanf("%d", &n) == 1);
    assert(1 <= n && n <= N);
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            assert(scanf("%d", &a[i][j]) == 1);
        }
    }
    for (int i = 0; i < n; ++ i) {
        assert(a[i][i] == 0);
        for (int j = 0; j < n; ++ j) {
            assert(a[i][j] == a[j][i]);
            assert(a[i][j] == 0 || a[i][j] == 1);
        }
    }
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            if (a[i][j]) {
                a[i][j] = rand() % MOD;
                a[j][i] = MOD - a[i][j];
            }
        }
    }
    int rank = 0;
    for (int i = 0; i < n; ++ i) {
        int pivot = rank;
        while (pivot < n && !a[pivot][i]) {
            pivot ++;
        }
        if (pivot < n) {
            for (int j = 0; j < n; ++ j) {
                swap(a[rank][j], a[pivot][j]);
            }
            {
                int times = inverse(a[rank][i]);
                for (int j = 0; j < n; ++ j) {
                    a[rank][j] = (long long)a[rank][j] * times % MOD;
                }
                for (int k = 0; k < n; ++ k) {
                    if (k != rank && a[k][i]) {
                        int times = a[k][i];
                        for (int j = 0; j < n; ++ j) {
                            (a[k][j] += MOD - (long long)a[rank][j] * times % MOD) %= MOD;
                        }
                    }
                }
            }
            rank ++;
        }
    }
    assert(!(rank & 1));
    printf("%d\n", rank >> 1);
    return 0;
}

/* .................................................................................................................................. */

const int N = 369;

int P[N], F[N], B[N], Q[N], head, tail;
bool G[N][N], InB[N], inQ[N]; int mark[N], tot;
int n, s, t, match;

#define pre F[P[i]]
int lca(int u, int v){
    ++tot; RST(mark);
    for (int i=u;i;i=pre){ i=B[i]; mark[i]=tot; }
    for (int i=v;i;i=pre){ i=B[i]; if (mark[i]==tot) return i;}
}

void blossoming(int u,int v){

    int z = lca(u, v); RST(InB);

    for (int i=u;B[i]!=z;i=pre){
        if (B[pre]!=z) F[pre]=P[i];
        InB[B[i]]=true;
        InB[B[P[i]]]=true;
    }
    for (int i=v;B[i]!=z;i=pre){
        if (B[pre]!=z) F[pre]=P[i]; //同理
        InB[B[i]]=true;
        InB[B[P[i]]]=true;
    }

    if (B[u]!=z) F[u]=v;
    if (B[v]!=z) F[v]=u;
    REP_1(i, n)
      if (InB[B[i]]){
          B[i]=z;
          if (!inQ[i]){
              Q[tail++]=i;
              inQ[i]=true;
          }
      }
}

void change(){
    int x,y,z=t; while (z){
        y=F[z], x=P[y];
        P[y]=z, P[z]=y, z=x;
    }
}

bool bfs(){

    RST(F, inQ); REP_1(i, n) B[i] = i;
    head=0; tail=1, Q[0]=s, inQ[s]=1;

    while (head < tail){
        int u=Q[head++];
        REP_1(v, n) if (G[u][v] && B[u]!=B[v] && P[u]!=v){
            if (s==v || P[v] && F[P[v]]) blossoming(u,v);
            else if (!F[v]){
                F[v] = u; if (P[v]){
                    Q[tail++] = P[v];
                    inQ[P[v]] = true;
                }
                else{
                    t = v, change();
                    return true;
                }
            }
        }
    }
    return false;

}

int EBC(){
    int match = 0; RST(P); REP_1_N(s, n) if (!P[s] && bfs()) ++match;
    return match;
}

void init(){
    RD(n); REP_2_1(i, j, n, n) RD(G[i][j]);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    init(); OT(EBC());
}

Cut

一条边可以切开，当且仅当两边联通块都是偶数。

Component

考虑联通块不包括重心，则最多只能有\(\frac{n}{2}\)的大小。于是就算包含重心的联通块的最小权值，有一个熟知的动态规划算法可以做到\(O(N^2)\)。之后点分治即可。复杂度仍然是\(O(N^2)\)。

"熟知的动态规划算法"可以参见何森的集训队论文。

#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2000;
const int INF = 1000000000;

int n, weight[N], parent[N], answer[N + 1];
vector <int> adjacent[N];

int find(int i) {
    return parent[i] == -1 ? i : find(parent[i]);
}

bool mark[N];
int size[N], max_tree[N];
vector <int> nodes;
int minimum[N + 1][N + 1];

#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)

void dfs(int p, int u) {
    size[u] = 1;
    max_tree[u] = 0;
    nodes.push_back(u);
    foreach (iter, adjacent[u]) {
        int v = *iter;
        if (v != p && !mark[v]) {
            dfs(u, v);
            size[u] += size[v];
            max_tree[u] = max(max_tree[u], size[v]);
        }
    }
}

void divide(int root) {
    nodes.clear();
    dfs(-1, root);
    int total = size[root];
    int new_root = -1;
    int min_cost = INF;
    foreach (iter, nodes) {
        int u = *iter;
        int ret = max(total - size[u], max_tree[u]);
        if (ret < min_cost) {
            new_root = u;
            min_cost = ret;
        }
    }
    nodes.clear();
    dfs(-1, new_root);
    int m = nodes.size();
    minimum[m][0] = 0;
    for (int i = 1; i <= m; ++ i) {
        minimum[m][i] = INF;
    }
    for (int i = m - 1; i >= 0; -- i) {
        int id = nodes[i];
        for (int j = 0; j <= m; ++ j) {
            minimum[i][j] = minimum[i + size[id]][j];
            if (j) {
                minimum[i][j] = min(minimum[i][j], minimum[i + 1][j - 1] + weight[id]);
            }
        }
    }
    for (int j = 1; j <= m; ++ j) {
        answer[j] = min(answer[j], minimum[1][j - 1] + weight[new_root]);
    }
    mark[new_root] = true;
    foreach (iter, adjacent[new_root]) {
        int v = *iter;
        if (!mark[v]) {
            divide(v);
        }
    }
}

int main() {
    assert(scanf("%d", &n) == 1);
    assert(1 <= n && n <= N);
    for (int i = 0; i < n; ++ i) {
        assert(scanf("%d", weight + i) == 1);
        assert(1 <= weight[i] && weight[i] <= 1000000);
    }
    memset(parent, -1, sizeof(parent));
    for (int i = 0; i < n - 1; ++ i) {
        int a, b;
        assert(scanf("%d%d", &a, &b) == 2);
        a --;
        b --;
        adjacent[a].push_back(b);
        adjacent[b].push_back(a);
        assert(find(a) != find(b));
        parent[find(a)] = find(b);
    }
    for (int i = 1; i <= n; ++ i) {
        answer[i] = INF;
    }
    memset(mark, 0, sizeof(mark));
    divide(0);
    for (int i = 1; i <= n; ++ i) {
        printf("%d%c", answer[i], i == n ? '\n' : ' ' );
    }
    return 0;
}

/* .................................................................................................................................. */

const int N = 3009;

int A[N], f[N], dp[N][N];
VI adj[N]; bool vis[N]; int sz[N];
int n, res;

#define v adj[u][i]
void dfs(int u){
    vis[u] = true, sz[u] = 1;
    FLC(dp[u], 0x3f), dp[u][1] = A[u];

    REP(i, SZ(adj[u])) if (!vis[v]){
        dfs(v), sz[u] += sz[v];
        DWN_1(j, sz[u], 2) DWN_1(k, min(sz[v], j-1), 1) // 剪枝 .. .
            checkMin(dp[u][j], dp[u][j-k] + dp[v][k]);
    }
    REP_1(i, sz[u]) checkMin(f[i], dp[u][i]);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    REP_1_C(i, RD(n)) RD(A[i]);

    FLC(f, 0x3f); DO(n-1){
        int x, y; RD(x, y);
        adj[x].PB(y), adj[y].PB(x);
    }

    dfs(1); REP_1(i, n-1) OT(f[i]);
    cout << f[n] << endl;
}

Posted by xiaodao
Category: ACdream