首页 > 代码库 > 解题报告

解题报告

(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

 

解题报告