日常 - Gemini Boy - ACM之路~
浅谈莫比乌斯反演
莫比乌斯反演是应用在有限偏序集上的容斥原理，什么是有限偏序集：令X是一个集合，X上的关系R是一个“性质”，在X的任意俩个给定的元素之间，这个性质可能成立也可能不成立。说的更正式一点，X上的关系是X×X的一个子集R，而X×X是X的元素的序偶集合。常见的偏序有：有一个集合含于另一个集合以及由一个整数被另一个整数。它们是在给定俩个集合互相都不是对方自己以及给定俩个整数彼此都不能整除意义下的偏序。
莫比乌斯反演：
- f(x) = sigma{g(d)}其中x % d == 0，则g(x) = sigma{miu(d) * f(x/d)}
- f(x) = sigma{g(d)}其中d % x == 0，则g(x) = sigma{miu(d/x) * f(d)}
莫比乌斯反演中miu(x) =
- 1 {x中含有偶数个不同的质因子}
- -1 {x中含有奇数个不同的质因子}
- 0 {其他情况}
求miu(x)的代码：
const int maxn = 1001000;
int prime[maxn], miu[maxn], cnt;
bool check[maxn];
void Mobius() {
memset(check, false, sizeof(check));
cnt = 0; miu[1] = 1;
for (int i = 2; i < maxn; i++) {
if (!check[i]) {
prime[cnt++] = i;
miu[i] = -1;
}
for (int j = 0; j < cnt; j++) {
if (i * prime[j] > maxn)
break;
check[i*prime[j]] = true;
if (i % prime[j])
miu[i*prime[j]] = 1;
else {
miu[i*prime[j]] == 0;
break;
}
}
}
}
随想
还有47天就是南京现场赛了。凭心而论，压力很大，现在天天只能睡5,6个小时，就要爬起来坐到电脑前做题。当然这不能怪别的，只能怪自己在过去的一年多没有好好练，挖的坑太大，可能没有时间填坑了。但是既然努力了1年多了，就不想在这最后的几十天留下遗憾。
列一下ToDoList(自己之前搞的不错的东西就不列出来了)：
1.动态规划
- 数位DP
- 树形DP
- 状态压缩
2.数据结构
- 树套树
- CDQ分治
- 树链剖分
- 动态树
3.字符串
- AC自动机
- 后缀数组
- hash
- 后缀自动机
4.图论
- 网络流
- 连通分量
5.数学
- 高斯消元
- 概率与期望
- 组合数学
- 线性方程
要做的一些比赛：
POI 15-19th
Andrew Stankevich Contest 1-10
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31687#overview
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31688#overview
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31294#overview
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31535#overview
...(未完待续)
树形DP
hdu 1520：http://acm.hdu.edu.cn/showproblem.php?pid=1520
每个节点有权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？
f[u][0]：表示当前节点没选。那么f[u][0] += sum{max(f[v][0], f[v][1]) : v是u的子节点};
f[u][1]；表示当前节点选了。那么f[u][1] += sum{f[v][0] : v是u的子节点};
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 6666;
int f[maxn][2], n, p, q, val, root;
bool vis[maxn];
vector<int> son[maxn];
void dfs(int u) {
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
dfs(v);
f[u][0] += max(f[v][1], f[v][0]);
f[u][1] += f[v][0];
}
}
void work() {
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &val);
f[i][1] = val;
f[i][0] = 0;
son[i].clear();
}
memset(vis, false, sizeof(vis));
while (scanf("%d %d", &p, &q)) {
if (p == 0 && q == 0)
break;
son[q].push_back(p);
vis[p] = true;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == false) {
root = i; break;
}
}
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
}
int main() {
while (~scanf("%d", &n)) {
work();
}
return 0;
}
数位统计
坑向~
zoj 2334
bzoj 1293
bzoj 2752
bzoj 1782
bzoj 2783
bzoj 2762
bzoj 1935
bzoj 3411
bzoj 3686
bzoj 2653
bzoj 2116
bzoj 2584
bzoj 1018
bzoj 2827
bzoj 2658
poj 3580
bzoj 1758
bzoj 2329