首页 > 代码库 > 解题报告
解题报告
（1）树(tree)
【题目描述】
从前在森林里面有一棵很大的树，树上住着很多小动物。
树上有n个房间，第i个房间都住着ai 只第bi 种小动物。
这n个房间用n ? 1条路径连接起来，其中节点1为整棵树的根。
现在每个房间x的小动物们都想知道，以x为根的子树中有多少只他们的同
类？
【输入格式】
第一行一个整数n表示房间数。
之后n行，每行两个数，表示ai,bi。
再之后n ? 1行，每行两个数x,y，表示树上有一条连接x,y的边。
【输出格式】
一行，i个数，第i个数表示以i为根的子树中bi 种小动物有多少只。
【样例输入】
5
2 1
3 1
4 2
5 1
6 2
1 2
1 3
3 4
3 5
2
【样例输出】
10 3 10 5 6
【数据规模与约定】
对于 30%的数据，?? ?? ≤ ?? ≤ 10
对于 60%的数据，?? ?? ≤ ?? ≤ 1000
对于 100%的数据，?? ?? ≤ ?? ≤ 100000,?? ?? ≤ 1000
【解析】
这个题的100做法很巧妙（也不是那么巧。。。）
30分做法：建立邻接矩阵 对于每个结点都遍历整棵子树 时间复杂度n^3
60分做法：建立邻接表建树，对于每个结点都遍历整棵子树，时间复杂度n^2
100分做法：vector数组存边 用f[b[i]]记录遍历到这个点的小动物个数，用遍历完后f[b[i]]减去遍历前的f[b[i]]；
【代码】
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> using namespace std; #define N 100002 vector<int>vec[N]; int a[N],b[N],ans[N],f[N],dad[N],vis[N]; int n,x,y; void dfs(int x) { ans[x]=f[b[x]]; f[b[x]]+=a[x]; for(int i=0;i<vec[x].size();i++) if(dad[x]!=vec[x][i]) { dad[vec[x][i]]=x; dfs(vec[x][i]); } ans[x]=f[b[x]]-ans[x]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dfs(1); for(int i=1;i<=n;i++) { printf("%d",ans[i]); } puts(" ");//相当于printf(""); return 0; }
（2）
小偷（thief）
【题目描述】
有一些小偷想要偷Alex家里的糖果，已知小偷的数量大于等于4个。
这些小偷非常贪心，所以每一个小偷都会偷前一个小偷k倍的糖果。
由于小偷的背包最多只能放n个糖果，所以如果有一个小偷需要偷的糖果
数超过n，那么小偷们就会放弃这个计划。
但是只有小偷自己知道n的值以及小偷的数量。我们现在得到的信息是小
偷们有m种不同的方案来偷糖果，问n的最小值是多少。(只要有任意一个小偷
偷的糖果数不同或小偷的数量不同即为不同方案)
【输入格式】
一行，一个整数m，表示方案数。
【输出格式】
一行，一个整数n，如果无解输出?1。
【样例输入1】
8
【样例输出1】
32
【样例输入2】
10
4
【样例输出2】
-1
【数据规模与约定】
对于 30%的数据，3 ≤ ? ≤ 1000
对于 60%的数据，3 ≤ ? ≤ 100000
对于 100%的数据，3 ≤ ? ≤ 10 15
【解析】：
30分做法：枚举
60分做法：发现n大约是m的三倍，所以我们把所有小于等于m方案求出来排序 求出准确的n
100分做法：发现答案有可二分性 用二分答案去做
【代码】
#include<iostream> #include<cstdio> using namespace std; long long m,l,r,ans; long long check(long long x) { long long k,j;ans=0; for(int i=2;;i++)//枚举K的大小 { for(k=x,j=1;k;k/=i,j++)//j为小偷个数,k为包的大小 { if(j>=4)ans+=k;//如果能满足4个小偷；方案数+k； //k为当前能满足>=4个小偷第一个小偷偷的个数,那么1--k第一个小偷都能偷，就是K种 } if(j<=4)return ans; } } int main() { scanf("%lld",&m); l=8;r=1e16;//二分N的大小，如果4个小偷，k=2；那么n最小也是8 while(l<r) { long long mid=(l+r)>>1; if(check(mid)<m)l=mid+1;//如果当前的包的大小满足不了M种方法，将包扩大 else r=mid; } if(check(l)==m)printf("%d",l);//如果找到的n能满足M，输出； else printf("-1");//否则-1 return 0; }
(3)
挂盘子(plate)
【题目描述】
在墙上有一排m个钩子，任意两个钩子之间的距离都是1。
现在有m个盘子，第m个盘子的半径为ri。现在要将这m个盘子挂在这n个钩
子上，每个盘子都将圆心挂在钩子上，要求任意两个盘子不能有公共部分。
问有多少种不同的方案数。只要有任意一个盘子挂在不同的钩子上即为不
同方案。答案对1000000007取模。
【输入格式】
第一行两个整数n,m。
第二行n个整数，第i个整数表示第i个盘子的半径ri 。
【输出格式】
一行，一个整数表示方案数。如果没有合法方案输出0。
【样例输入】
3 10
1 2 3
【样例输出】
68
【数据规模与约定】
对于 30%的数据，2 ≤ ?? ≤ 5,?? ≤ 30
对于 60%的数据，3 ≤ ?? ≤ 100,?? ≤ 2000
对于 100%的数据，3 ≤ ?? ≤ 4000,?? ≤ 10 9 ,?? ?? ≤ 100000
解题报告