2017-10-20 NOIP模拟赛2-白红宇

2017-10-20 NOIP模拟赛2

阅读量：4948 次

发布时间：2019-06-11

本文共 4083 字，大约阅读时间需要 13 分钟。

P98

a

【问题描述】

你是能看到第一题的 friends 呢。

——hja

世界上没有什么比卖的这么贵的弹丸三还令人绝望的事了，所以便有了这

么一道题。定义?(?)为满足(? × ?)|?的有序正整数对(?,?)的个数。现在给定

?，求

∑?(?)

?=1

【输入格式】

一行一个整数?。

【输出格式】

一行一个整数代表答案。

【样例输入】

【样例输出】

【数据范围与规定】

3。

60%的数据，1 ≤ ? ≤ 1000。

对于100%的数据，1 ≤ ? ≤ 10 11 .

P98 zhxb

第 3 页共 6 页

#include
      
       #include
       
        using namespace std;int sum[1010],n;int Clac(int x){    int res=0;    for(int i=1;i<=x;i++){        for(int j=1;j<=x;j++){            if(x%(i*j)==0)res++;            if(i*j>x)break;        }    }    return res;}int main(){    freopen("a.in","r",stdin);freopen("a.out","w",stdout);    sum[1]=1;    cin>>n;    for(int i=2;i<=n;i++){        sum[i]=sum[i-1]+Clac(i);    }    printf("%d",sum[n]);}

暴力

b

【问题描述】

你是能看到第二题的 friends 呢。

——laekov

Hja 和 Yjq 为了抢男主角打了起来，现在他们正在一棵树上决斗。Hja 在 A

点，Yjq 在 B 点，Hja 先发制人开始移动。每次他们可以沿着一条边移动，但

一旦一条边被对方走过了自己就不能再走这条边了。每条边上都有权值，他们

都希望自己的权值尽量多。现在给你这棵树以及他们俩开始的位置，问 Hja 能

够获得的最大权值。

【输入格式】

第一行两个整数?,?，代表树的点数和询问的个数。

? − 1行每行三个整数?,?,?，代表从?到?有一条权值为?的边。

接下来?行，每行两个整数?,?代表一次询问。

【输出格式】

对于每次询问，输出一个整数代表答案。

【样例输入 1】

2 1

1 2 3

1 2

【样例输出 1】

【样例输入 2】

3 2

1 2 3

1 3 1

2 3

1 3

【样例输出 2】

P98 zhxb

第 4 页共 6 页

【数据范围与规定】

30%的数据，1 ≤ ?,? ≤ 1000。

另外30%的数据，? = 1。

对于100%的数据，1 ≤ ?,? ≤ 10 5 ,0 ≤ ? ≤ 10 3 ,1 ≤ ?,?,?,? ≤ ?。

P98 zhxc

第 5 页共 6 页

/*    暴力找lca，顺便把整个路径存下来    看看路径中有多少线段，根据奇偶判断走到中点后下一步谁先走    然后用那个中点做根dfs，维护字树大小    将根的字数大小排个序，谁先走谁取奇数子树    然后输出Hja走的和*/#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 100010using namespace std;int n,m,num,head[maxn],fa1[maxn],q1[maxn],q2[maxn],cnt,cnt2,dep1[maxn],top[maxn],sz1[maxn],son[maxn];int who,sz[maxn],Sz[maxn],cn; struct node{    int to,pre,v;}e[maxn*2];void Insert(int from,int to,int v){    e[++num].to=to;    e[num].v=v;    e[num].pre=head[from];    head[from]=num;}void dfs(int now,int father){    dep1[now]=dep1[father]+1;    fa1[now]=father;    sz1[now]=1;    for(int i=head[now];i;i=e[i].pre){        int to=e[i].to;        if(to==father)continue;        dfs(to,now);        sz1[now]+=sz1[to];        if(!son[now]||sz1[to]>sz1[son[now]])son[now]=to;    }}void dfs2(int now,int father){    top[now]=father;    if(son[now])dfs2(son[now],father);    for(int i=head[now];i;i=e[i].pre){        int to=e[i].to;        if(to==son[now]||to==fa1[now])continue;        dfs2(to,to);    }}int Lca(int a,int b){    while(top[a]!=top[b]){        if(dep1[top[a]]
          
           dep1[b])swap(a,b);    return a;}void dfs3(int now,int father){    for(int i=head[now];i;i=e[i].pre){        int to=e[i].to;        if(to==father)continue;        sz[to]=e[i].v;        dfs3(to,now);        sz[now]+=sz[to];    }}bool cmp(int x,int y){
    return x>y;}int main(){    //freopen("Cola.txt","r",stdin);    //freopen("Cola.out","w",stdout);    //freopen("b.in","r",stdin);freopen("b.out","w",stdout);    scanf("%d%d",&n,&m);    int x,y,z;    for(int i=1;i
           
            =1;j--)q1[++cnt]=q2[j]; if(cnt%2==0)who=2;//下一步yjq先走 else who=1;//下一步hja先走 int point=q1[cnt/2+1]; //cout<
            
             <
             
              =1;j--){ if(q1[j]==point)break; to2=q1[j]; } //cout<
              
               <<' '<
               
                <