[SDOi2012]吊灯

嘟嘟嘟

这题想了半天，搞出了一个\(O(10 * d * n)\)（\(d\)为\(n\)的约数个数）的贪心算法，就是能在子树内匹配就在子树内匹配，否则把没匹配的都交给父亲，看父亲能否匹配。交上去开了O2才得了60分。按讨论中的方法卡常后还是A不了，就放弃了。

正解需要推一个结论，就是一棵树能被分成\(x\)个大小相同的联通块，必须满足至少有\(\frac{n}{x}\)个子树的大小为\(x\)的倍数。
证明啥的yy一下就好啦……
想到这个结论后，我还是没想出复杂度更优的算法……最后看题解才知道，你开个桶记录子树大小，每次枚举倍数就能把\(n\)降成\(\sqrt{n}\)了……

啊忘说了，讨论中的卡常就是根据题中树的构造方法，把dfs改成逆序扫一遍，减小常数。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1.2e6 + 5;
const int NUM = 19940105;
inline ll read()
{ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) last = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(last == '-') ans = -ans;return ans;
}
inline void write(ll x)
{if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0');
}int n, fa[maxn];
struct Edge
{int nxt, to;
}e[maxn];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{e[++ecnt] = (Edge){head[x], y};head[x] = ecnt;
}int num[maxn], cnt = 0;
In void init(int n)
{for(int i = 1; i * i <= n; ++i)if(n % i == 0){num[++cnt] = i;if(i * i < n) num[++cnt] = n / i;}sort(num + 1, num + cnt + 1);
}int ans;
int dp[maxn];
In bool dfs(int now, int _f)  //我的O(n)贪心
{for(int i = 1; i <= n; ++i) dp[i] = 1;for(int i = n; i; --i){if(dp[i] > ans) return 0;if(dp[i] == ans) dp[i] = 0;dp[fa[i]] += dp[i];}return 1;
}int siz[maxn], tot[maxn];
In bool judge(int x)
{int ret = 0;for(int i = x; i <= n; i += x) ret += tot[i];return ret >= n / x;
}
In void solve()
{fill(siz + 1, siz + n + 1, 1);fill(tot + 1, tot + n + 1, 0);for(int i = n; i; --i){siz[fa[i]] += siz[i];++tot[siz[i]];}for(int i = 1; i <= cnt; ++i){ans = num[i];if(judge(num[i])) write(ans), enter;}
}int main()
{n = read(); init(n);for(int i = 2; i <= n; ++i) fa[i] = read();puts("Case #1:");solve();for(int t = 1; t <= 9; ++t){printf("Case #%d:\n", t + 1);for(int i = 2; i <= n; ++i) fa[i] = (fa[i] + NUM) % (i - 1) + 1;solve();    }return 0;
}

转载于:https://www.cnblogs.com/mrclr/p/10459887.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！