Topcoder SRM 603 Div1 250+550

250:MaxMinTreeGame

题面:

给出一棵树,两人轮流操作,每次一个人可以删去一条边,然后从断开的两个块中选择一个删掉,每个点有一个权值,第一个人想要剩下的点权值尽量大,另一个人想要权值尽量小,问剩下最后的最大点权…

分析:

已知那些度数不为1的点都需要多次操作才能拿到,那么也就是说另一个人肯定不会满足你的需求…
于是乎,答案只能在那些度数为1的点里面选…

代码:

int de[N];
int MaxMinTreeGame::findend(vector <int> edges, vector <int> costs) {
    int ret=0;
    memset(de,0,sizeof(de));
    for(int i=0;i<edges.size();i++)
        de[i+1]++,de[edges[i]]++;
    for(int i=0;i<costs.size();i++)
        if(de[i]==1)
            ret=max(ret,costs[i]);
    return ret;
}

550:PairsOfStrings

题面:

给出一个n,一个k,表示你要用前k个字母构造两个长度为n的字符串,然后满足以下条件…
存在字符串C(可以为空),使得A+C=C+B,然后让你输出方案数..

分析:

因为只要你想C串可以很长很长,然后我们考虑C串的前n项和A是相等的,然后因为C后移n位以后可以自我匹配,说明i_n\le len_c的所有C[i_n+1\to i*(n+1)]都是和A重复的串….
同理,对于串B,C从后往前每n个字母都是B的复制版…
证明了B可以由A旋转得来(旋转就是把第一个字母放到最后)…
我们考虑怎么统计答案,假设A是由x个长度为y的字符串连起来的,这y个字符串都相同,那么当A串旋转y步以后,就回到了原来的位置,那么当前串对答案的贡献就是y.
然后我们考虑为了不重复计算,我们永远用最小的循环节来统计答案,也就是我们当前枚举的循环节内,不能再有其他循环节,有就要删掉.我们设f(y)表示长度为y的字符串的方案数…
f(y)=k^y-\sum_{y\mod i=0}f(i).后面减掉的就是当前串还有更小的循环节的个数…
然后我们直接写一个快速幂,辅助一下…

代码:

LL KSM(LL a,LL b,LL ret=1)
{
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
vector<LL> vec;
LL f[100000];
int PairsOfStrings::getNumber(int n, int k) {
    LL ans=0;
    vec.clear();
    for(LL i=1;i<=sqrt(n);i++)
        if(n%i==0)
        {
            vec.push_back(i);
            if(n>i*i)
                vec.push_back(n/i);
        }
    sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++)
    {
        f[i]=KSM(k,vec[i]);
        for(int j=0;j<i;j++)
            if(vec[i]%vec[j]==0)
                f[i]=((f[i]-f[j])%mod+mod)%mod;
        ans=(ans+vec[i]*f[i]%mod)%mod;
    }
    return ans;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注