C.Friends
题意：
给你一棵树，要你求每个节点在6步以内的结点数量。
思路：
一般看过挑程的都会想到树上点分治。 然而我结束之后才看
树上点分治 请移步 poj1741
官方的题解思路是这样的:
f[rt][len] 预处理的节点rt的子孙结点中，距离其长度为 len 的节点个数
ans[rt][len] 整棵树上，距离rt为len的节点个数
f 可以通过一遍简单深搜即可获得
而 ans[rt][len] = f[rt][len] + ans[fa[rt]][len-1] – f[fa[rt]][len-1]
这里必须得指出，官方的题解有错误之处。最后减去的 f[fa[rt]][len-1] 将会减去除开 rt 以外的所有子树，这是不符合题意的。
正确形式应该是 ans[rt][len] = f[rt][len] + ans[fa[rt]][len-1] – f[rt][len-2] （当然这时的len必须大于等于2
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5;
char str[maxn];
int idx, n;
int head[maxn];
int num[maxn][10];
int ans[maxn][10];
bool vis[maxn];
struct node {
int to;
int nxt;
} edges[maxn << 1];
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void getNum(int pre, int r)
{
int v;
if (pre != 0) {
ans[pre][1]++;
ans[r][1]++;
}
for (int id = head[r]; id != -1; id = edges[id].nxt) {
v = edges[id].to;
if (pre != v) {
getNum(r, v);
num[r][1]++;
for (int i = 2; i < 7; i++)
num[r][i] += (num[v][i - 1] + 1);
}
}
}
void getAns(int fa, int r, int len)
{
int v;
if (fa != r)
ans[r][len] = num[r][len] + ans[fa][len - 1] - num[r][len - 2];
//printf("ans[%d][%d]: %d\n", r, len, ans[r][len]);
for (int id = head[r]; id != -1; id = edges[id].nxt) {
v = edges[id].to;
if (v != fa)
getAns(r, v, len);
}
}
void init()
{
idx = 0;
memset(num, 0, sizeof num);
memset(ans, 0, sizeof ans);
for (int i = 0; i <= n; i++)
head[i] = -1;
}
int main()
{
int T, u, v;
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d", &n);
init();
for (int i = 1; i < n; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
getNum(0, 1);
for (int i = 1; i < 7; i++)
ans[1][i] = num[1][i];
for (int i = 2; i < 7; i++) {
getAns(1, 1, i);
}
printf("Case #%d:\n", cas);
for (int i = 1; i <= n; i++)
printf("%d\n", ans[i][6]);
}
return 0;
}
E.One Stroke
题意：
给定一棵完全二叉树，每个节点上都有一个权值。要求你连接尽可能多的节点，且权值和不超过给定数值。
思路：
官方说是尺取法。不知道什么算法，之后补一下。
但是！！！！特么居然暴力能过！！！这数据就真的过分了………………
看到暴力能过的时候我真的是有点崩溃，回来写个暴力果然一A了………………
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1e6 + 5;
int n, k;
int val[maxn << 2];
int dfs(int r, int sum, int dep)
{
int le = 0, ri = 0;
if (val[r << 1] == -1 && val[r << 1 | 1] == -1)
return dep;
if (val[r << 1] != -1 && sum + val[r << 1] <= k)
le = dfs(r << 1, sum + val[r << 1], dep + 1);
if (val[r << 1 | 1] != -1 && sum + val[r << 1 | 1] <= k)
ri = dfs(r << 1 | 1, sum + val[r << 1 | 1], dep + 1);
return max(le, ri);
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &k);
memset(val, -1, sizeof val);
for (int i = 1; i <= n; i++)
scanf("%d", val + i);
int ans = -1;
for (int i = 1; i <= n; i++)
if (val[i] <= k)
ans = max(ans, dfs(i, val[i], 1));
printf("%d\n", ans);
}
return 0;
}
K.DeadLine
题意：
有一堆bug，给你每个bug修复的最后期限，要求每个bug都要在各自的期限到来或之前完成，一个程序员每天只能修复一个bug，求至少需要多少个程序员。
思路：
一般思路都会是，先排个序，扫一遍记录多余的时间，如果遇到重复的就减去多余的时间，如果没有多余的时间人数就 +1 。
当然，不可能这么简单……题目数据设置特别大……需要的是一个O(n)的算法。
最后还是没写出来，提供的题解是这样的思路：
定义一个数组，表示 deadline = 下标idx 的 bug数量。然后我们 1-n 扫一遍，记录前 idx 的bug数目num。
其中 一个程序员 idx 天能处理 idx 个 bug，那么 num 个 bug 就需要 num/idx 取上界。
妙哉！
#include <cstdio>
#include <cstring>
int arr[1000005];
using namespace std;
int main()
{
int n,x,maxx,num,t;
while(scanf("%d",&n)!=EOF) {
memset(arr,0,sizeof arr);
maxx=1;
num=0;
for(int i=1;i<=n;i++) {
scanf("%d",&x);
if(x<=n)
arr[x]++;
}
for(int i=1;i<=n;i++) {
num=num+arr[i];
t=num/i+(num%i!=0);
maxx=maxx>t?maxx:t;
}
printf("%d\n",maxx);
}
return 0;
}