老是把老的文章发上来好像不是很够意思。其实最近一直都有在做题，在做Fractal128博客的题。本着在退役之前至少能和Fractal聊到一块去的目标，刷了好多他的题，许多题是一边做一边骂的，因为他的题解有时也太偷工减料了。这篇文章我记录一下最近一个月做过的题。凭我这记性看看旧题效果要比做新的好吧。
APIO之后，OI生涯估计就告一段落了。
如果算法真的是我喜欢的东西的话，相信以后也会继续下去。
网络流、二分图之类
这个其实好烧脑。。。（mdzz
[网络流24题]魔术球问题（简化版）
考察点：给出一个DAG，求出其最小路径覆盖（不可重复走的）
啥叫最小路径覆盖？就是用最少的路径条数就把整张DAG的点全部走一遍。
回顾一下二分图的一个基本常识： 最大匹配 = 最小顶点覆盖
那啥，什么事最小点覆盖？//mdzz
二分图最小点覆盖的定义：
二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最小点覆盖。
我们把DAG的每个点拆成两个，把出边和入边分开。
这样我们就搞出了一张二分图对吧。
我们观察一下这张二分图的最小顶点覆盖的特点。
最小顶点覆盖把所有的边都覆盖了。
剩下的点都是路径的终点。//并没有证明（可能是错的
所以最后可以得出：最小路径覆盖数 = 总点数 - 最小顶点覆盖数
BZOJ1143: [CTSC2008]祭祀river
给出一个DAG，求出其最大点独立集（集合间任意两点不联通）
其实我并不会证明。。。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef long long ll;
using namespace std;
int read(){
int x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
int n, m;
bool f[maxn][maxn];
int p[maxn], vis[maxn];
int ind;
bool find(int u){
for (int v = 1; v <= n; v++){
if (vis[v]!=ind && f[u][v]){
vis[v] = ind;
if (!p[v] || find(p[v])){
p[v] = u;
return true;
}
}
}
return false;
}
int hungary(){
int ret = 0;
ind = 1;
for (int i = 1; i <= n; i++, ind++)
if (find(i)) ret++;
return ret;
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
n = read(); m = read();
memset(f, 0, sizeof f);
for (int i = 0; i < m; i++){
int x = read(), y = read();
f[x][y] = true;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] |= f[i][k] & f[k][j];
int num = hungary();
printf("%d\n", n - num);
return 0;
}
BZOJ2127:happiness
神奇的构图。。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
typedef long long ll;
using namespace std;
int read(){
int x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
int n, m, w[maxn][maxn], l[maxn][maxn], a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn], e;
struct ed
{
int f, u, v, l, nex;
}ed[maxn*maxn*6];
int fir[maxn*maxn];
void addedge(int u, int v, int w, int l){
ed[++e].u = u, ed[e].v = v, ed[e].f = w, ed[e].l = e + l;
ed[e].nex = fir[u];
fir[u] = e;
}
queue <int> q;
int dis[maxn*maxn];
bool bfs(){
memset(dis, -1, sizeof dis);
q.push(S); dis[S] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for (int i = fir[u]; i; i = ed[i].nex){
int v = ed[i].v;
if (ed[i].f && dis[v] == -1){
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
if (dis[T] != -1) return true;
return false;
}
int find(int u, int flw = INF){
if (u == T) return flw;
int flow = 0;
for (int i = fir[u]; i; i = ed[i].nex){
int v = ed[i].v;
if (ed[i].f && dis[v] == dis[u] + 1 && (flow = find(v, min(ed[i].f, flw)))){
ed[i].f -= flow;
ed[ed[i].l].f += flow;
return flow;
}
}
return 0;
}
int dinic(){
int ret = 0, flow = 0;
while (bfs()){
//printf("%d\n", dis[T]);
while (flow = find(S))
ret += flow;
}
return ret;
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
n = read(); m = read();
int tot = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
w[i][j] = read(), tot += w[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
l[i][j] = read(), tot += l[i][j];
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m; j++)
a[i][j] = read(), tot += a[i][j];
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m; j++)
b[i][j] = read(), tot += b[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m - 1; j++)
c[i][j] = read(), tot += c[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m - 1; j++)
d[i][j] = read(), tot += d[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
if (i != n) {
int W = (a[i][j] + b[i][j]) ;
addedge(p(i, j), p(i + 1, j), W, 1);
addedge(p(i + 1, j), p(i, j), W, -1);
}
if (j != m){
int W = (c[i][j] + d[i][j]) ;
addedge(p(i, j), p(i, j + 1), W, 1);
addedge(p(i, j + 1), p(i, j), W, -1);
}
int W = 2 * w[i][j] + (a[i][j] + c[i][j] + a[i - 1][j] + c[i][j - 1]) ;
addedge(S, p(i, j), W, 1);
addedge(p(i, j), S, 0, -1);
W = 2 * l[i][j] + (b[i][j] + d[i][j] + b[i - 1][j] + d[i][j - 1]) ;
addedge(p(i, j), T, W, 1);
addedge(T, p(i, j), 0, -1);
}
int x = dinic();
printf("%d\n", tot - x / 2);
return 0;
}
数学、数论、群论之类
BZOJ1004:[HNOI2008]Cards
置换及其应用：
Burnside引理：对于一个置换f，若一个着色方案s经过置换后不变，称s为f的不动点。将f的不动点数目记为C(f)，则可以证明等价类问题为所有C(f)的平均值。
怎么求C(f)?
如果把置换f分解成m(f)个循环额乘积，那么每个循环内所有状态必须相同，假设有K种状态，则$C(f)=k^{m(f)}$
Polya定理：等价类的个数等于所有置换f的$k^{m(f)}$的平均数。
1 |
|
BZOJ2882: 工艺
最小表示法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
typedef long long ll;
using namespace std;
int a[500000], n;
int read(){
int x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
int minR(){
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n){
int t = a[(i + k < n) ? i + k : i + k - n] - a[(j + k < n) ? j + k : j + k - n];
if (!t) k++; else {
if (t > 0) i = i + k + 1; else j = j + k + 1;
if (i == j) j++;
k = 0;
}
}
return min(i, j);
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
n = read();
for (int i = 0; i < n; i++) a[i] = read();
int x = minR();
for (int i = 0; i < n - 1; i++)
printf("%d ", a[(x+i<n)?x+i:x+i-n]);
printf("%d", a[(x+n-1<n)?x+n-1:x+n-1-n]);
return 0;
}
还有一道vijos的13821
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
typedef long long ll;
using namespace std;
int l = 0;
char a[1000010], b[1000010];
int numR(char* a){
int i = 0, j = 1, k = 0;
while (i < l && j < l && k < l){
int t = a[(i + k) % l] - a[(j + k) % l];
if (!t) k++; else {
if (t > 0) i = i + k + 1; else j = j + k + 1;
if (i == j) j++;
k = 0;
}
}
return min(i, j);
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
scanf("%s", a);
scanf("%s", b);
l = strlen(a);
int x = numR(a), y = numR(b);
bool bo = true;
for (int i = 0; i < l; i++)
if (a[(i + x) % l] != b[(i + y) % l]) {
bo = false;
break;
}
if (bo) {
printf("Yes\n");
for (int i = 0; i < l; i++)
printf("%c", a[(i + x) % l]);
} else printf("No\n");
return 0;
}
BZOJ2190: [SDOI2008]仪仗队
线性筛计算欧拉函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef long long ll;
using namespace std;
bool vis[40010];
int phi[40010], p[40010], tot = 0, n;
void get_phi(int n){
for (int i = 2; i <= n; i++){
if (vis[i] == 0){
vis[i] = true; p[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot; j++){
if (i * p[j] > n) break;
vis[i * p[j]] = true;
if (i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j];
break;
} else
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
scanf("%d", &n);
get_phi(n);
ll ans = 0;
for (int i = 2; i < n; i++) ans += (ll) phi[i];
ans *= 2;
ans += 3;
printf("%d\n", ans);
return 0;
}
BZOJ2705: [SDOI2012]Longge的问题
欧拉函数O(sqrt(n))1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef long long ll;
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
ll n, ans = 0;
ll phi(ll x){
ll t = x, ret = x;
for (ll i = 2; i * i <= x; i++)
if (!(t % i)) {
ret = ret / i * (i - 1);
while (!(t % i)) t /= i;
}
if (t > 1) ret = ret / t * (t - 1);
return ret;
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
n = read();
for (ll i = 2; i * i <= n; i++){
if (!(n % i)){
ans += n / i * phi(i);
if (i * i != n) ans += i * phi(n / i);
}
}
printf("%lld\n", ans+n+phi(n));
return 0;
}
BZOJ3043: IncDec Sequence
有趣的差分题（没写代码
未完待续