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