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

第二场

第三场

2017 Multi-University Training Contest – Team 9 1008

类型:模拟
瞎搞,优化暴力.关键在于理解题意,我还是把它归在模拟吧.
题目连接: :earth_americas:HDU-6168 Numbers

github Code Link: :earth_asia:1008.cpp
Test Code: :earth_asia:1008test.cpp

题解: 用map记录下每个数字出现的次数.然后对b进行排序,首先可以知道,排序后的数组,前两个数一定是a序列的前两个数.然后从这两个数开始拓展,a1+a2必在b中,所以在map中找到a1+a2的数量然后-1,之后把接下来的第一个数Push到a数组中,并且删除一个a1+a3和a2+a3,依次递推.知道a.size()到达sqrt(m/2)或者i>=m为止,结束循环.

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;

int c[maxn];
int m,n;
map<int,int> d;
vector<int> a;
int main(){
    while(~scanf("%d",&m)){
        d.clear();a.clear();
        n=sqrt(m<<1);
        for(int i=0;i<m;++i){
            scanf("%d",&c[i]);
            d[c[i]]++;
        }
        sort(c,c+m);
        a.push_back(c[0]);a.push_back(c[1]);
        d[c[1]]--;d[c[0]]--;
        for(int i=1;i<m && a.size()<n;++i){
            int si=a.size()-1;
            for(int j=0;j<si;++j){
                if(d.find(a[si]+a[j])!=d.end() && d[a[si]+a[j]]>0){
                    d[a[si]+a[j]]--;
         //           printf("IDone %d\n",a[si-1]+a[j]);
                }
            }
            while(d[c[i]]==0){
                int no=c[i];
                while(c[i]==no){
                    ++i;
                    if(i>=m)break;
                }
                if(i>=m)break;
    //            printf("Done %d\n",c[i]);
            }
            if(i<m){
                a.push_back(c[i]);
         //       printf("Push %d\n",c[i]);
                d[c[i]]--;
            }
            --i;
        }
        printf("%d\n",a.size());
        printf("%d",a[0]);
        for(int i=1;i<a.size();++i){
            printf(" %d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

Test Code:

#include<bits/stdc++.h>
using namespace std;
int t[5]={3,7,6,9,10};
vector<int> ans;
int main(){
     freopen("in.txt", "r", stdin);
     freopen("out.txt", "w", stdout);
     for(int i=0;i<5;++i) ans.push_back(t[i]);
     for(int i=0;i<5;++i){
        for(int j=i+1;j<5;++j){
            ans.push_back(t[i]+t[j]);
        }
     }
     printf("%d\n",ans.size());
     for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
    return 0;
}

2017多校训练2 HDU 6047 Maximum Sequence

原题连接: :point_right:Maximum Sequence
题意: 给定一个长度为n的a数组和b数组,要求a[n+1]…a[2*n]的最大总和。 限制条件为ai≤max{aj-j│bk≤j<i}。
题解: 两种方法,一种是线段树,另一种是第一次记录maxv数组,记录每个i到maxindex(A)的最大值,然后动态更新.
github:
1.线段树法: :point_right:1003_Range_Tree.cpp
2.暴力动态更新法: :point_right:1003.cpp

///线段树法
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int maxnode=2000050;

int b[maxnode],N;
int maxv[maxnode];

void build(int o,int l,int r){
    if(l==r){
        if(l>N) return;///预先分配2*N个结点
        scanf("%d",&maxv[o]);maxv[o]-=l;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int query(int o,int l,int r,int ll,int rr){
    if(l>=ll&&r<=rr) return maxv[o];
    int ma=-1,mid=(l+r)>>1;
    if(mid>=ll) ma=max(ma,query(o<<1,l,mid,ll,rr));
    if(rr>mid) ma=max(ma,query(o<<1|1,mid+1,r,ll,rr));
    return ma;
}

void update(int o,int l,int r,int p,int val){
    if(l==r){
        maxv[o]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(o<<1,l,mid,p,val);
    else update(o<<1|1,mid+1,r,p,val);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int main(){
    while(~scanf("%d",&N)&&N){
        build(1,1,2*N);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        LL ans=0;
        for(int i=N+1;i<=2*N;++i){
            int k=query(1,1,2*N,b[i-N],i-1);
            update(1,1,2*N,i,k-i);
            ans=(ans+k)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

///HDU 6047 暴力动态更新法
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+50;
const int mod=1e9+7;
int N;
int a[maxn],b[maxn],maxa[maxn];

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=1;i<=N;++i){
            int aa;
            scanf("%d",&aa);
            a[i]=aa-i;
        }
        maxa[N]=a[N];
        for(int i=N-1;i>=1;--i) maxa[i]=max(maxa[i+1],a[i]);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        long long ans=0;
        ans=(ans+maxa[b[1]])%mod;
        int t=maxa[b[1]]-N-1;
        for(int i=2;i<=N;++i){
            maxa[b[i]]=max(maxa[b[i]],t);
            ans=(ans+maxa[b[i]])%mod;
            t=max(t,maxa[b[i]]-N-1);
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}

2017多校训练1 HDU 6043 KazaQ’s Socks

题目连接: :point_right:KazaQ’s Socks

题意:穿袜子,洗袜子,求洗了多少次袜子…:sweat_smile:

题解:无

github: :point_right:KazaQ’s Socks

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,ans,kase=0;
    while(~scanf("%lld%lld",&a,&b)){
        if(b<=a){
            printf("Case #%lld: %lld\n",++kase,b);
            continue;
        }else{
            long long loop=(a-1)<<1,rg=b-a;
            long long res=rg%loop;
            if(res==a-1) ans=a-1;
            else if(res==0) ans=a;
            else
                ans=res>a-1?res-a+1:res;
            printf("Case #%lld: %lld\n",++kase,ans);
        }
    }
    return 0;
}

2017多校训练1 HDU 6034 Balala Power!

题目连接: :point_right:Balala Power!
Balala

题意: 把26个英文字母看成26进制中的一位,YI一对应起来,给你n个由26个字符组成的字符串,每个字符串代表一个26进制的数,求这n个26进制数的最大的和mod 1e9+7 的结果.注意,可以有前导0,规则是为0的字符不能位于len>1的字符串的开头.

题解: 统计每个字符的总结果,排序,最大的字符赋值25,然后依次往下赋值.然后判断前导0,找到第一个可以为0的存在的字符,将它赋值为0,之后其他的左移一位.(出现前导0的情况表示26个字符都已经出现了).

github:
:point_right:1002.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
struct star{
    int reg[100005];
    bool vi;
    int c;
    bool operator < (const star &A)const{
        for(int i=maxn-1;i>=0;--i){
            if(reg[i]>A.reg[i]) return 1;
            else if(reg[i]<A.reg[i]) return 0;
            else continue;
        }
    }
}ch[30];
char str[100005];
int Hash[30];///字符-权值映射
long long ans,fac[100005];
inline void init(){
    for(int i=0;i<27;++i){
        memset(ch[i].reg,0,sizeof(ch[i].reg));
        ch[i].vi=true;
        ch[i].c=0;
    }
    ans=0;
}
int main(){
    int n,len,p,kase=0;
    fac[0]=1;///预先处理26^i;
    for(int i=1;i<maxn;++i)
        fac[i]=fac[i-1]*26%mod;
    while(~scanf("%d",&n)){
        init();
        for(int i=0;i<n;++i){
            scanf("%s",str);
            len=strlen(str);
            for(int j=0;j<len;++j){
                p=str[j]-'a';
                ch[p].reg[len-j-1]++;
            }
            if(len>1)
                ch[str[0]-'a'].vi=false;
        }
        for(int i=0;i<26;++i){
            for(int j=0;j<maxn;++j){
                if(ch[i].reg[j]>=26){
                    ch[i].reg[j+1]+=ch[i].reg[j]/26;
                    ch[i].reg[j]%=26;
                }
            }
            ch[i].c=i;
        }
        sort(ch,ch+26);
        for(int i=0;i<26;++i)
            Hash[ch[i].c]=26-i-1;
        for(int i=25;i>=0;--i){///从最小的开始判断是否可以为0
            if(ch[i].vi){
                for(int j=25;j>i;--j)
                    Hash[ch[j].c]=Hash[ch[j-1].c];
                Hash[ch[i].c]=0;
                break;
            }
        }
        for(int i=0;i<26;++i){
            for(int j=0;j<maxn;++j){
                ans=(ans+fac[j]*ch[i].reg[j]*Hash[ch[i].c]%mod)%mod;
            }
        }
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}