2017 杭电多校训练赛 补题




第一场

1003 Colorful Tree hdoj6035

题意: 给定一棵树,树上各点之间的距离定义为 两点路线上不同颜色的个数。求这课数上n*(n-1)/2(即所有)的路径长度之和。
题解: (来自网络)
** //思路**:Answer = 所有颜色种类 * 所有路径数量 – 每一种颜色有多少路径没有经过 .

一开始假设每条路径都经过了所有颜色,再把每种颜色没经过的路径数减去就行,这个应该很好理解。问题是怎么算没经过的路径数?操作是这样的,如果算颜色1没经过的路径数,我们先把图里所有颜色是1的节点遮起来(假设这个点不存在,图在这个点是断路),图就被分成了很多块,每块的值= 那一块里的顶点数*(那一块里的顶点数-1)/2
所有块的值加起来就是不经过颜色1的所有路径数。

到这里是不是还是很好理解,那么问题来了,怎么实现?…题解里说用虚树什么的…

用一个DFS即可,复杂度O(n)

用Size数组储存以每个节点为根节点的子树大小(即子树里节点的个数),Sum数组…很难解释,大概是表示以每种颜色为根节点的子树的大小和,但不是非常准确,如果以颜色2为根节点的子树里还含有颜色为2的节点,那只要算根节点这个颜色为2的子树大小即可,若在以这个颜色为2的点为根节点的子树之外还有颜色为2的点,那还要加上这个点的值…不知道能不能理解…解释不清楚,大概就这个意思…

以下图颜色2为例,代码里最后的for里(即以根第一个节点计算中)减去的(n-sum[2])*(n-sum[2]-1)/2的那部分减去的是下图橙色圈里的那块,dfs里减去pp那部分是下图里蓝色圈的那块。其他具体的按照自己的理解再思考思考。

#include<bits/stdc++.h>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
//c[]数组是每个节点的颜色
int c[maxn],head[maxn],len,sum[maxn],size[maxn],vis[maxn];
LL d;
//边表
//邻接表
struct node{
    int v,next;
}p[maxn<<1];

void addedge(int u,int v){
    //有向边指向点的编号
    p[len].v=v;
    //每条边的下一条边是上一次纪录的边的号码
    p[len].next=head[u];
    //邻接表的方法
    //len为当前边的编号

    //只记录当前节点的最后一个边的位置
    head[u]=len++;
}
//对树进行dfs
void dfs(int x,int fa){
    //非这个点为根的所有该颜色的点
    LL pre=sum[c[x]];
    //size数组是当前节点的子节点总数目
    size[x]=1;
    int add=0;
    //通过邻接表对当前节点x进行dfs
    //等于0则退出
    for(int i=head[x];~i;i=p[i].next){
        //如果遇到反向边了,跳过,继续往其他边走
        if(p[i].v==fa)
            continue;
        dfs(p[i].v,x);
        size[x] += size[p[i].v];
        //计算当前节点子树所有和当前节点颜色不同的点的个数
        LL count = size[p[i].v] - sum[c[x]] + pre;
        pre = sum[c[x]];
        //当前子树的不同颜色点的个数
        add += count;
        //假设其他颜色都是白色,d即等于不同颜色所组成的边的总个数
        d += count*(count-1)>>1;
    }
    //计算以x为根节点子树的所有与x不同颜色的点的个数
    sum[c[x]] += add + 1;
}

int main(){
    int n,tcase=1;
    while(~scanf("%d",&n)){
        memset(head,-1,sizeof(head));
        memset(sum,0,sizeof(sum));
        memset(vis,0,sizeof(vis));
        d=len=0;
        LL number = 0;
        for(int i=1;i<=n;++i){
            scanf("%d",&c[i]);
            //记录颜色,颜色范围是[1,n]
            if(!vis[c[i]]){
                vis[c[i]]=1;
                number++;
            }
        }
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1,0);
        //ans初始等于(颜色个数)*(所有边的个数)-d(d为每个颜色在每个子树上被减去的不会经过那个颜色的路径的个数)
        LL ans=(number*(n-1)*n>>1)-d;
        for(int i=1;i<=n;++i){
            //不存在的颜色不需要计算,把已存在的颜色计算一下
            if(vis[i]&&i!=c[1]){
                //在根节点中与颜色i不同的颜色的个数
                LL count=n-sum[i];
                //每个颜色的路径数=(n*(n-1)>>1)-(count*(count-1)>>1)
                //以根节点为中心减去不同于当前颜色的路径的个数
                //最终得到的ans即为 每个颜色路径个数 的和
                ans-=count*(count-1)>>1;
            }
        }
        printf("Case #%d: %lld\n",tcase++,ans);
    }
    return 0;
}

1006 Function hdoj6038

这道题似懂非懂的写了出来…
大体是寻找循环节.
我写的代码有点乱…
原式为: f[i]=b[f[a[i]]]
A:{1,0,2} B{0,1}
可组成f: 000 111 110 001
A:{2,0,1} b{0,2,3,1}
可组成f: 000 231 312 123
以i -> a[i] i -> b[i] 为图的边进行Tarjan.
用Tarjan判断a和b各自有几个环(强连通分量),并且记录下每个环的大小.
然后AC代码如下(以后思路清楚了再重新看看…):

//HDU 6038
#include<bits/stdc++.h>

using namespace std;
const int maxn=100000+100;
const int mod=1e9+7;
typedef long long int lli;
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int a[maxn],b[maxn];

stack<int> S;
map<int,int> A,B;

//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

inline lli qp(lli aa,lli x){
    if(aa == 0) return 0;
    lli ans = 1;
    for(;x;x>>=1){
        if(x&1) ans = ans*aa % mod;
        aa = aa*aa % mod;
    }
    return ans % mod;
}

void dfs(int u,map<int,int>& T){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v,T);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            //未回溯时计算low数组需要通过pre数组
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        int cnt=0;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            cnt++;
            if(x==u)break;
        }
        T[cnt]++;
    }
}

void Tarjan(int n,map<int,int>& T){
    while(!S.empty()){
        S.pop();
    }
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i,T);
    }
}

int main(){
    int n,m,kase=0;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;++i){
            scanf("%d",&b[i]);
        }
        //对aTarjan
        for(int i=0;i<n;++i){
            addAdge(i,a[i]);
        }
        Tarjan(n,A);
        for(int i=0;i<n;++i){
            G[i].clear();
        }
        //对bTarjan
        for(int i=0;i<m;++i){
            addAdge(i,b[i]);
        }
        Tarjan(m,B);
        for(int i=0;i<m;++i){
            G[i].clear();
        }

        long long ans=1;
        map<int,int>::iterator it1;
        map<int,int>::iterator it2;
        for(it1=A.begin();it1!=A.end();it1++){
            long long tmp=0;
            for(it2=B.begin();it2!=B.end();it2++){
                if(it1->first%it2->first==0){
                    tmp=tmp+it2->second*it2->first;
                }
                //printf("%d %d : %d %d\n",it1->first,it2->first,it1->second,it2->second);
            }
            ans=ans*qp(tmp,it1->second)%mod;
        }
        printf("Case #%d: %lld\n",++kase,ans);
        A.clear();
        B.clear();
    }
    return 0;
}

1008 Hints of sd0061 hdoj6040

第二场

第三场