SRM603

今天凌晨是有srm……不过因为住校自然也是不可能打……
赛后看了一下题目……感觉至少250和500都是可做的……
1k还是比较神奇的……

level 1

一棵树……节点上有权值……
A和B两个人轮流操作……A先手
每次操作:选一条边删掉,保留一个连通块,另一个扔掉
当树被删得只剩一点的时候游戏结束
A要最大化最后一点的权值,B要最小化……
问两个人都够聪明的时候……剩下的那个点的权值是多少……

SOL

首先注意到答案是可以二分的……
那么我们要求判定:将所有权值大于等于k的节点染黑……
问最后能不能剩下一个黑点……

这个怎么做啊……TAT
想了很久发现上sg不太好做……

然后就想办法看看有木有特殊的性质……
首先先手肯定能得到权值最大的度数为1的节点……
只要第一次把这个连的边割掉就能得到这个点的权值了
那么能不能得到更大的呢?
显然是不能的……

首先:容易发现不可能一次删掉当前的所有叶子节点……也就是删完一次之后一定会有上一次删之前的叶子剩下……
因为如果先手能得到比最大的叶子还大的节点的权值……
那么在第二轮轮到后手的时候
后手随便选一个上一轮留下来的叶子“送”先手就可以了……然后先手就囧了
所以答案就是最大的叶子了……

level 2

给定n,k
定义字符串集合S={所有长度为n的且只用到了前k个小写字母的字符串}

我们要统计合法字符串对个数(A,B)……
字符串对(A,B)合法当且仅当存在一个字符串C
满足A+C=C+B(+表示链接两个字符串)
例如
"aac"+"c"="c"+"caa"
所以n=3,k=3时……("aac","caa")合法……

solve

稍加推导就能发现……
存在A+C=C+B等价于A与B循环同构……
接下来统计循环同构字符串个数就好了……
随便乱搞就可以了……

如果你想看结论推导过程的话……
以下是叉姐教大家的理性推导(我的方法就是随便yy……所以就不说了)
假定(A,B)合法,那么假定|C|>=2n
那么C前面和A相等,后面和B相等……
设C=A+S+B
那么A+A+S+B=A+S+B+B
约掉同类的……
得到等式A+S=S+B
那么S也是一个合法的"C"使A+S=S+B
所以我们可以只考虑|C|<=2n的情况
接下来如果|C|>n
那么C的前n个字符和A相等,后n个和B相等……
那么令C=X+Y+Z,且X+Y=A,Y+Z=B
那么稍加分析就能发现Y也能使A+Y=Y+B
所以我们只考虑|C|<=n的情况
接下来……
因为A+C=C+B
那么设设A=C+X,B=Y+C
那么C+X+C=C+Y+C
所以X=Y
那么就是说……
A的一部分前缀与B的一部分后缀相等……剩下的A的后缀与B的前缀相等……
这不就是循环同构么?!
证明完毕

level 3

有(zuo)趣(si)的概率?
给定两个长度相等的随机生成的数组……A[],B[]
可以任意重排A,也可以任意重排B
重排后C[]这样生成:
C[i]=A[i]+B[i]
记c[i]=(i在C[]出现的次数)……
我们要最大化max{c[i]},然后在多个i取到c[i]=max{c[]}的时候,最大化i
输出 最后出现次数最多的值和出现的次数……

SOL

首先我们记a[i]=(i在A[]出现的次数)
记b[i]=(i在B[]出现的次数)
那么c[i]能达到的最大值……
就是……
这个形式挺好理解的……
然后如果我们能对于每个可能的i……求出c[i]能达到的最大值……问题就解决了……
注意到c_i的这个形式与卷积相似……
想到卷积就要想到傅里叶变换……

但是直接优化这个卷积比较难下手……而且我们现在也没有利用到数据随机的特点

我们来看每个a[i]对c[]分别产生的贡献怎么计算……

a[i]对c[j]的贡献就是min(a[i],b[j-i])……

那么我们不妨把min(a[i],b[j-i])看成1*1+1*1+...+1*0+0*0...
就是说我们可以用这个框架来描述

for cnt=1 to n 
        for i=1 to n
            aa[i]=(a[i]>=cnt)
            bb[i]=(b[i]>=cnt)
    for i=1 to n
            for j=1 to n
            c[i+j]+=aa[i]*bb[j]

这个的正确性还是容易看出的……

接下来就可以看出怎么上FFT了……
因为c[i+j]+=aa[i]*bb[j]这句话表明了一切……

问题是for cnt=1 to n这句话带来了n次FFT……
会tle……
但是我们注意到……在随机数据下……一个数字出现的次数很少
也就是说,对于一个limit,满足a[i]>=limit的i是很少的……
接下来我们规定一个limit……将所有a[i]>=limit的i直接平方暴力就可以了……
小于limit的上FFT
就可以过了……limit设为10就可以了

顺便一说……
出现次数最多数字的出现次数的期望是O(log n / log log n)的……
证明看这里……来自nju的资料君

最下面就是讲这个的分析的……所以limit设为10是很靠谱的……

总结

如果这场我来打的话肯定挂得很惨……
因为level1我就往二分的方向上想了很久……这不挂才怪……
level2当场也不一定能推出来
level3说不定能想到fft但是大概想不到当次数比较大的时候乱搞……
简单的说就是思维能力和思维速度太差了……

代码

level_1.cpp
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
struct MaxMinTreeGame{
    int deg[60],n,ans=0;
    int findend(vector<int>fa,vector<int>a){
        n=a.size();
        for(int i=1;i<n;i++)
            deg[fa[i-1]]++,deg[i]++;
        for(int i=0;i<n;i++)
            if(deg[i]==1)ans=max(ans,a[i]);
        return ans;
    }
};
level_2.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MOD=7+(int)1e9;
struct PairsOfStrings{
    int tot,divisors[10000],exact[10000];
    int modpow(int x,int y){
        int cur=1;
        for(;y;y>>=1,x=(long long)x*x%MOD)
            if(y&1)cur=(long long)x*cur%MOD;
        return cur;
    }
    int getNumber(int n,int k){
        tot=0;
        for(int i=1;i*i<=n;i++)
            if(n%i==0){
                divisors[tot++]=i;
                if(n/i!=i)divisors[tot++]=n/i;
            }
        sort(divisors,divisors+tot);
        int ans=0;
        for(int i=0;i<tot;i++){
            int now=modpow(k,divisors[i]);
            for(int j=0;j<i;j++)
                if(divisors[i]%divisors[j]==0)
                    now-=exact[j],now%=MOD;
            exact[i]=now;
            ans=(ans+(long long)now*divisors[i])%MOD;
        }return (ans+MOD)%MOD;
    }
};
level_3.cpp
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<complex>
using namespace std;
#include<vector>
const int N=1<<18;
typedef complex<double> Complex;
const double pi=acos(-1.0);
struct SumOfArrays{
    int n,a[N],b[N],count[N];
    Complex aa[N],bb[N],cc[N];
    vector<int>remain;
    string findbestpair(int len,vector<int>A,vector<int>B){
        n=len;
        memset(count,0,sizeof(count));
        generate(A,a);
        generate(B,b);
        for(int limit=1;limit<=10;limit++){
            for(int i=0;i<N;i++)
                aa[i]=(a[i]>=limit),bb[i]=(b[i]>=limit);
            FFT(aa,N,1);
            FFT(bb,N,1);
            for(int i=0;i<N;i++)
                aa[i]*=bb[i];
            FFT(aa,N,-1);
            for(int i=0;i<N;i++)
                count[i]+=(int)(aa[i].real()/N+0.5);
        }remain.clear();
        for(int i=0;i<N;i++)
            if(a[i]>10)
                remain.push_back(i);
        for(int i=0;i<N;i++)
            if(b[i]>10){
                for(int j=0;j<remain.size();j++)
                    count[i+remain[j]]+=min(a[remain[j]],b[i])-10;
            }
        pair<int,int>Ans=make_pair(-1,-1);
        for(int i=0;i<N;i++)
            Ans=max(Ans,make_pair((int)(count[i]+0.5),i));
        char ans[30];
        sprintf(ans,"%d %d",Ans.first,Ans.second);
        return ans;
    }void generate(vector<int>A,int*a){
        fill(a,a+n,0);
        int p=A[0],q=A[1];
        for(int i=0;i<n;i++){
            a[p]++;
            p=((long long)q*A[2]+(long long)p*A[3]+A[4])%A[5];
            swap(p,q);
        }
    }void FFT(Complex P[], int n, int oper)
    {
        for (int i=1,j=0;i<n-1;i++){
            for (int s=n;j^=s>>=1,~j&s;);
            if(i<j)
                swap(P[i], P[j]);
        }
        for (int d = 0; (1 << d) < n; d++) {
            int m = 1 << d, m2 = m * 2;
            double p0 = pi / m * oper;
            Complex  unit_p0=Complex(cos(p0),sin(p0));
            for (int i = 0; i < n; i += m2) {
                Complex unit = 1;
                for (int j = 0; j < m; j++) {
                    Complex &P1 = P[i + j + m], &P2 = P[i + j];
                    Complex t = unit * P1;
                    P1 = P2 - t;
                    P2 = P2 + t;
                    unit = unit * unit_p0;
                }
            }
        }
    }
};

Comments

comments powered by Disqus