CCPC-Wannafly Winter Camp Day5 Div2

Cactus Draw
题解:
每个节点的X坐标就是当前点的深度,y坐标为当前点是这个深度下的第几个点。

#include <bits/stdc++.h>

const int MAXN = 10000;

using namespace std;

vector<int>d[MAXN];

int n,m; 
int deep[MAXN],x[MAXN],y[MAXN];
bool vis[MAXN];

void dfs(int u,int h){
    vis[u] = true;
    
    x[u] = h;y[u] = ++deep[h];
    
    for(int i = 0;i < d[u].size();i++){
        int v = d[u][i];
        if(!vis[v]){
            dfs(v,h+1);            
        } 
    }
} 


int main()
{
    scanf("%d %d",&n,&m);
    
    int u,v;
    
    for(int i = 1;i <= m;i++){
        scanf("%d %d",&u,&v);
        d[u].push_back(v);
        d[v].push_back(u);
    }
    
    dfs(1,1);
    
    for(int i = 1;i <= n;i++){
        printf("%d %d\n",x[i],y[i]);
    }
    
    return 0;
}

Division
题解:我们考试的时候是直接暴力做除法的,每次从优先队列中间取一个数出来做除法,但是这个时间复杂度其实是有点大的,我们可以计算一下对于$10^{5}$需要做次数为$log_{2}{10^{5}}≈15$次除法以后就会变成0,,而0无论怎么做除法都是0,所以当这个数变为0以后我们就不用把这个数字加入优先队列了。

#include <bits/stdc++.h>

using namespace std;
int n,k;
int d;

long long ans;

priority_queue<int>Q;

int main()
{
    scanf("%d %d",&n,&k);
    
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&d);
        Q.push(d);
    } 
    
    while(k-- && !Q.empty()){
        d = Q.top();Q.pop();
        d >>= 1;
        if(d)Q.push(d);
    }
    
    while(!Q.empty()){
        ans = ans + Q.top();Q.pop();
    }
    printf("%lld\n",ans);
    return 0;
}

Nested Tree

Div2:题解:如果我们把这棵树建出来,这棵树的大小为$10^{6}$,我们直接DFS计算出树上每条边连接的两颗子树大小一边是可以直接DFS统计出来的,另外一边就用数的总大小计算一下,然后这条边的贡献就是两棵子树大小相乘

Div1:题解:占坑

#include <bits/stdc++.h>

const int MAXN = 4000000,MOD = 1e9+7;

using namespace std;

int n,m,e;
int head[MAXN],sz[MAXN];
bool vis[MAXN];

long long ans;

struct node{
    int u,v,next;
}edge[MAXN];

inline void addedge(int u,int v){
    edge[++e] = (node){u,v,head[u]};head[u] = e;
    edge[++e] = (node){v,u,head[v]};head[v] = e;    
}

void dfs(int u){
    vis[u] = true;sz[u] = 1;
    
    for(int i = head[u];i;i = edge[i].next){
        int v = edge[i].v;
        if(!vis[v]){
            dfs(v);
            ans += ((long long)(sz[v])*(long long)(n*m-sz[v]))%MOD;
            ans %= MOD;
            sz[u] += sz[v];
        }
    }
}

int main()
{
    int a,b,u,v;
    scanf("%d %d",&n,&m);

    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        for(int j = 1;j <= m;j++){
            addedge((j-1)*n+u,(j-1)*n+v);
        }
    }

    for(int i = 1;i < m;i++){
        scanf("%d %d %d %d",&a,&b,&u,&v);
        addedge((a-1)*n+u,(b-1)*n+v);
    }
    
    dfs(1);
    ans %= MOD;
    ans += MOD;
    ans %= MOD;
    printf("%lld\n",ans);
    return 0;
}

Special Judge

题解:计算几何板子题,就是需要注意对端点的处理

模板代码

主函数如下

int ES[2222];
int ET[2222];
int PX[1111];
int PY[1111];

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);

    for(int i=0;i<m;i++)
    {
        scanf("%d %d",ES+i,ET+i);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",PX+i,PY+i);
    }
    
    
    int ans=0;
    for(int i=0;i<m;i++)
    {
        Line fi;
        fi.s.x=PX[ES[i]];
        fi.s.y=PY[ES[i]];
        fi.e.x=PX[ET[i]];
        fi.e.y=PY[ET[i]];
        for(int j=i+1;j<m;j++)
        {
            Line se;
            se.s.x=PX[ES[j]];
            se.s.y=PY[ES[j]];
            se.e.x=PX[ET[j]];
            se.e.y=PY[ET[j]];
            
            Point smp,fop1,fop2;
            if( fi.s == se.s ){
    
                smp=fi.s;fop1=fi.e;fop2=se.e;
                Point vct1=smp-fop1;
                Point vct2=smp-fop2;
                if(vct1*vct2.len()==vct2*vct1.len()) ++ans;
            }
            else if( fi.e == se.s){
    
                smp=fi.e;fop1=fi.s;fop2=se.e;
                Point vct1=smp-fop1;
                Point vct2=smp-fop2;
                if(vct1*vct2.len()==vct2*vct1.len()) ++ans;
            }
            else if( fi.s == se.e ){
    
                smp=fi.s;fop1=fi.e;fop2=se.s;
                Point vct1=smp-fop1;
                Point vct2=smp-fop2;
                if(vct1*vct2.len()==vct2*vct1.len()) ++ans;
            }
            else if( fi.e == se.e ){
    
                smp=fi.e;fop1=fi.s;fop2=se.s;
                Point vct1=smp-fop1;
                Point vct2=smp-fop2;
                if(vct1*vct2.len()==vct2*vct1.len()) ++ans;
            }
            else{

                if(fi.segcrossseg(se)) ++ans;
            }
        
        }
    }
    
    printf("%d",ans);
    
    return 0; 
 } 
Last modification:January 29th, 2019 at 03:32 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment