BZOJ3004: 吊灯(结论 毒瘤)
2018-09-18 06:25:01来源:博客园 阅读 ()
题意
$n$个节点的树,判断能否划分成$\frac{n}{k}$个大小为$k$的联通块
Sol
首先$k$必须是$n$的倍数。
然后刚开始我就非常傻的以为输出所有约数就行了。。
但是图是这样,$k = 2$的话肯定是不行的。
结论:若$k$是可行的,则至少有$\frac{n}{k}$个节点的大小为$k$的倍数
证明:直接归纳吧。
$k = n$的时候显然
$k = n / 2$的时候,我们要把树划分成互不相交的两块,这两块一定是完全独立的,且分别有自己的根节点。
剩下的继续归纳即可,注意这里我们为什么要是“至少”,因为整棵树是联通起来的,我们在判断$k$的时候,大小为$2k$的也会被统计入答案
然后这题卡dfs,不愧是SDOI。。
#include<cstdio> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int MAXN = 2 * 1e6; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N; vector<int> ap; int fa[MAXN], tim[MAXN]; void rebuild() { memset(tim, 0, sizeof(tim)); // for(int i = 1; i <= N; i++) v[i].clear(); for(int i = 2; i <= N; i++) fa[i] = (fa[i] + 19940105) % (i - 1) + 1; } int siz[MAXN]; /*void dfs(int x, int fa) { mdzz卡dfs,不愧是SDOI啊。。 siz[x] = 1; for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(to == fa) continue; dfs(to, x); siz[x] += siz[to]; } }*/ void solve(int id) { printf("Case #%d:\n", id); for(int i = 1; i <= N; i++) siz[i] = 1; for(int i = N; i >= 1; i--) siz[fa[i]] += siz[i]; for(int i = 1; i <= N; i++) tim[siz[i]]++; for(int i = 0; i < ap.size(); i++) { int num = ap[i], cnt = 0; for(int j = num; j <= N; j += num) cnt += tim[j]; if(cnt >= N / num) { printf("%d\n", num); } } } int main() { N = read(); for(int i = 1; i <= N; i++) if(N % i == 0) ap.push_back(i); for(int i = 2; i <= N; i++) fa[i] = read(); solve(1); for(int i = 2; i <= 10; i++) { rebuild(); solve(i); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:洛谷P2062 分队问题(dp)
- 博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++ 2019-01-23
- cf550C. Divisibility by Eight(结论) 2018-09-05
- 程序部署到服务器后非常慢!!! 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash