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

第二场

第三场

Educational Codeforces Round 25 B

 【题目】

B. Five-In-a-Row

time limit: per test1 second
memory limit: per test256megabytes
input: standard input
output: standard output

Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it’s Alice’s turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.

Input

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters ‘X’ being a cross, letters ‘O’ being a nought and ‘.’ being an empty cell. The number of ‘X’ cells is equal to the number of ‘O’ cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.

Output

Print ‘YES’ if it’s possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print ‘NO’.

Examples
Input
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........
Output
YES
Input
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........
Output

NO

Link: http://codeforces.com/contest/825/problem/B
【题意】
X是否能在一步以内连成五子.可以则赢.

【题解】

数据量不大,枚举八个方向即可,注意,每次只能往一个方向走,不能拐弯.而且必须枚举八方向,不能只枚举向下的几个方向.
如果找到第一个五子,则往后就不需要计算了.

【Sourcr Code】
github: Educational Codeforces Round 25 B.cpp

#include<bits/stdc++.h>
using namespace std;
char mp[11][11];
bool re;
int d[8][3]={{0,1},{1,0},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};

bool check(int x,int i,int y,int j){
    if(x+i>=0&&x+i<10&&y+j>=0&&y+j<=10)
        return true;
    else return false;
}

void dfs(int x,int y,int win,int ct,int dir){
 //   if(dir==3)
 //       printf("(%d,%d):%d %d\n",x,y,win,dir);
    if(win==5 || re){re=true;return;}
    int i=d[dir][0],j=d[dir][1];
    if(check(x,i,y,j)){
        if(mp[x+i][y+j]=='X') dfs(x+i,y+j,win+1,ct,dir);
        if(mp[x+i][y+j]=='.' && ct==0) dfs(x+i,y+j,win+1,1,dir);
    }
}

int main(){
    re=false;
    for(int i=0;i<10;++i)
        gets(mp[i]);
    for(int i=0;i<10;++i){
        if(re)break;
        for(int j=0;j<10;++j){
            if(mp[i][j]=='X'){
                for(int k=0;k<8;++k){
                    dfs(i,j,1,0,k);
                    if(re)break;
                }
                if(re)break;
            }
        }
    }
    if(re)printf("YES\n");
    else printf("NO\n");
    return 0;
}

/**
....X.....
...X.OOOO.
..X.......
.X........
..........
..........
..........
..........
..........
..........
**/