ZJT's Blog

大変に気分がいい~

清华集训2016 Day4

2017-9-19 12:302017-9-21 12:38
清华集训智力康复待填坑

因为以前做过Day3,所以先跳过了,先来做一做没看过的Day4。


T1

传送门

好像是思博题?直接套一个lucas定理变成了数位dp,然后乱做即可。

不知道为什么清华集训会有这种题。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 110
#define LL long long

int n,k;
const LL P=1000000007;
int a[MAXN],b[MAXN];
LL f[MAXN][8],g[MAXN][8];

void init(){
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    LL _n,_m;
    scanf("%lld%lld",&_n,&_m);
    n=1;
    while(_n || _m){
        a[n]=_n%k;
        b[n]=_m%k;
        _n/=k; _m/=k;
        n++;
    }
}

void dp(){
    for(int j=0;j<8;j++) g[0][j]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<8;j++){
            int s1=j&1,s2=j&2,s3=j&4;
            int limi=s1?k-1:a[i],limj=s2?k-1:b[i];
            for(int vi=0;vi<=limi;vi++)
                for(int vj=0;vj<=limj;vj++){
                    if(!s3 && vi<vj) break;
                    int t1=(s1||vi<limi)?1:0;
                    int t2=(s2||vj<limj)?2:0;
                    int t3=(s3||vi>vj)?4:0;
                    int t4=t1|t2|t3;
                    if(vi<vj) f[i][j]=(f[i][j]+g[i-1][t4])%P;
                    else f[i][j]=(f[i][j]+f[i-1][t4])%P;
                    g[i][j]=(g[i][j]+g[i-1][t4])%P;
                }
        }
    }
    printf("%lld\n",f[n][0]);
}

void solve(){
    init();
    dp();
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    int T;
    scanf("%d%d",&T,&k);
    while(T--) solve();
    return 0;
}

无压力1A。


T2

传送门

我们把所有边权都减$k$,然后就便乘了找一条链使得平均值的绝对值最小。看起来一脸分数规划,然后就想到二分答案。

我们考虑二分的过程中,需要判断答案是否小于$c$。大概就是要找一条链,使得$$-c<\frac{\sum_{i\in S}w_i}{|S|}<c$$

我们变一下形,就变成了$$\sum_{i\in S}w_i-c<0,\sum_{i\in S}w_i+c>0$$

然后点分一下,把第一个不等式作为约束条件,用一个数据结构维护第二个东西的max,然后就能做啦!

不过似乎有什么不对。。。这个做法复杂度好像是3个log??

然后yww就告诉我这题正解就是3个log。。。然后就不虚了,大力写了一个3个log的乱搞。为了优化常数,把点分的时候要搞的动态开点线段树改成了每次离散化之后用二分+树状数组来搞。

为了锻炼1A能力(雾),所以过了大样例就直接交了!(好吧其实是懒得对拍)结果45分WA了。。。感觉任何稍微有点难度的题都无法1A啊??药丸啊?

看了看发现四个dfs中的第四个里面调用的是第三个dfs的函数。。。原因竟是写dfs4的时候直接复制的dfs3,然后忘记改了。。我去这也能有45分,这都啥数据啊。。。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

const LL INF=1LL<<62;

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,numb;
int g[MAXN],nume=0;
int size[MAXN],maxs[MAXN],root,sums;
int visit[MAXN],numvisit,pt[MAXN];
int rk[MAXN];
LL lim,s1[MAXN],s2[MAXN];
pair<LL,int> b[MAXN];

namespace Fenwick{
    LL c[MAXN];

    void init(){ for(int i=0;i<MAXN;i++) c[i]=-INF; }

    void insert(int x,LL y){
        while(x<=numb){
            if(y>c[x]) c[x]=y;
            x+=x&(-x);
        }
    }

    LL max(int x){
        LL res=-INF;
        while(x){
            if(c[x]>res) res=c[x];
            x-=x&(-x);
        }
        return res;
    }

    void undo(int x){
        while(x<=numb){
            c[x]=-INF;
            x+=x&(-x);
        }
    }
}

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void findRoot(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && !visit[e[i].to]){
            findRoot(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(sums-size[x]>maxs[x]) maxs[x]=sums-size[x];
    if(maxs[x]<maxs[root]) root=x;
}

void build(int x){
    pt[visit[x]=++numvisit]=x;
    findRoot(x,0);
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            sums=size[e[i].to];
            root=0;
            findRoot(e[i].to,0);
            build(root);
        }
}

void dfs1(int x,int p,int limw){
    b[++numb]=make_pair(s1[x],x);
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=limw && e[i].to!=p){
            s1[e[i].to]=s1[x]+e[i].w-lim;
            s2[e[i].to]=s2[x]+e[i].w+lim;
            dfs1(e[i].to,x,limw);
        }
}

bool dfs2(int x,int p,int limw){
    if(b[1].first+s1[x]<0){
        int l=1,r=numb;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(b[mid].first+s1[x]<0) l=mid;
            else r=mid-1;
        }
        if(s2[x]+Fenwick::max(l)>0) return 1;
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            if(dfs2(e[i].to,x,limw)) return 1;
    return 0;
}

void dfs3(int x,int p,int limw){
    Fenwick::insert(rk[x],s2[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            dfs3(e[i].to,x,limw);
}

void dfs4(int x,int p,int limw){
    Fenwick::undo(rk[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            dfs4(e[i].to,x,limw);
}

bool gao(int x){
    s1[x]=s2[x]=0;
    numb=0;
    dfs1(x,0,visit[x]);
    sort(b+1,b+numb+1);
    for(int i=1;i<=numb;i++) rk[b[i].second]=i;
    Fenwick::insert(rk[x],0);
    bool flag=0;
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=visit[x]){
            if(dfs2(e[i].to,x,visit[x])){
                Fenwick::undo(rk[x]);
                for(int j=g[x];(~j) && (i^j);j=e[j].next)
                    if(visit[e[j].to]>=visit[x])
                        dfs4(e[j].to,x,visit[x]);
                return 1;
            }
            dfs3(e[i].to,x,visit[x]);
        }
    Fenwick::undo(rk[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=visit[x])
            dfs4(e[i].to,x,visit[x]);
    return 0;
}

bool gao_tot(LL _lim){
    lim=_lim;
    for(int i=1;i<=n;i++) if(gao(pt[i])) return 1;
    return 0;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("B.in","r",stdin);
#endif
    Fenwick::init();
    memset(g,-1,sizeof g);
    LL avg;
    scanf("%d%lld",&n,&avg);
    LL maxans=0;
    for(int i=1;i<n;i++){
        int u,v;
        LL w;
        scanf("%d%d%lld",&u,&v,&w);
        addEdge(u,v,w-avg);
        addEdge(v,u,w-avg);
        if(abs(w-avg)>maxans) maxans=abs(w-avg);
    }
    maxs[0]=0x7FFFFFFF;
    root=0; sums=n;
    findRoot(1,0);
    build(root);
    LL l=0,r=maxans+1;
    while(l<r){
        LL mid=(l+r)>>1;
        if(gao_tot(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l-1);
    return 0;
}

然后就悲剧地没有成功1A。。。感觉自己不仅实力弱,而且做题的时候还经常池沼。。。这样下去真的要完啊。


T3

(待续。。。)

查看详细内容

清华集训2016 Day3

2017-9-19 12:292017-9-23 21:9
清华集训智力康复待填坑

占坑。。。

因为以前做过这套题,所以就先跳过了,最后再来再过一遍。

ps.因为集训队作业来了,所以可能会无限期延迟。。。

查看详细内容

清华集训2016 Day2

2017-9-13 6:62017-9-19 12:59
清华集训智力康复

接着上次的三题,开始做清华集训2016第二天的三道题。


T1

传送门

这题第一眼看上去感觉很鬼畜,有点像之前做过的那种大量推导的数竞题,于是尝试一下看看自己推不推得出来。

一看这题的多项式次数较少,想了想感觉可以把每项拆出来做,这样就变成了求解:$$S_d(n)=\sum_{k=0}^n k^d\binom{n}{k}x^k(1-x)^k$$

发现长得很像二项式定理。二项式定理怎么证的?不就是归纳吗。然后归纳了一下(因为最后没用到,所以这里就不把归纳的过程和结果写出来了),发现$S_d$和$S_k(0\leq k \leq d)$都有关系,所以直接暴力搞出所有$S_d$不太现实。

然后转念一想,这个过程中出现$S_0$到$S_d$的那么多项,好像就是因为把$(k+1)^d$展开了。那如果我一开始就不是$k^d$,直接带着$\binom{k}{d}$的牛顿级数来做,好像就可以把展开从一堆项变成两项了,那岂不是很妙?而且给的多项式是点值,如果要搞出来正常多项式,就要写快速插值了,然而我又没写过+基本不会,那可能只能搞一搞牛顿展开了啊?

然后就把定义换了一下,并且进行归纳:$$ \begin{aligned} S_d(n)&=\sum_{k=0}^n \binom{k}{d}\binom{n}{k}x^k(1-x)^k \\&=\sum_{k=0}^{n-1}\binom{k+1}{d}\binom{n-1}{k}x^{k+1}(1-x)^{(n-1)-k} \\&+\sum_{k=0}^{n-1}\binom{k}{d}\binom{n-1}{k}x^k(1-x)^{(n-1)-k+1} \\&=x(S_{d-1}(n-1)+S_{d}(n-1))+(1-x)S_d(n-1) \\&=S_d(n-1)+xS_{d-1}(n-1) \end{aligned} $$

然后发现这玩意去掉$x$之后就是个反过来的杨辉三角。。。算上$x$的话,第$i$行会乘上一个$x^i$,即$S_d(n)=\binom{n}{d}x^d$。于是我们可以轻易算出$S_k(n),0\leq k\leq m$,然后只需要把点值转成牛顿多项式$\sum_kc_k\binom{x}{k}$后代进去算即可: $$ ans=\sum_{k=0}^mc_kS_k(n) $$

点值转牛顿多项式大家都会吧?就是一个非常naive的二项式反演:$$ \begin{aligned} f(x)&=\sum_{k=0}^mc_k\binom{x}{k} \\&=\sum_{k=0}^xc_k\binom{x}{k} \end{aligned} $$

其中第二步是因为给出点值的坐标都是在$[0,m]$内的。进行反演后,得到:$$ c_k=\sum_{x=0}^k(-1)^{k-x}f(x)\binom{k}{x} $$

这个东西随便卷积一下就出来了。这样就愉快地做完这道题啦!

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

const LL P=998244353;

int n;
LL m,x;
LL fac[MAXN],invfac[MAXN];
LL binom[MAXN];
LL c[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void init(){
    fac[0]=1;
    for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%P;
    invfac[MAXN-1]=getPow(fac[MAXN-1],P-2);
    for(int i=MAXN-2;i>=0;i--)
        invfac[i]=invfac[i+1]*(i+1)%P;
    binom[0]=1;
    for(int i=1;i<=n;i++)
        binom[i]=binom[i-1]*(m-i+1)%P*getPow(i,P-2)%P;
}

namespace GaoFFT{
    void FFT(LL *a,int len,int flag){
        static int rev[MAXN];
        rev[0]=0;
        for(int i=1;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
        for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
        for(int l=2;l<=len;l<<=1){
            LL w=getPow(3,(P-1)/l);
            for(int i=0;i<len;i+=l){
                LL temp=1;
                for(int j=0;j<l/2;j++){
                    LL t1=a[i+j],t2=a[i+j+l/2]*temp;
                    a[i+j]=(t1+t2)%P;
                    a[i+j+l/2]=(t1-t2)%P;
                    temp=temp*w%P;
                }
            }
        }
        if(flag==-1){
            LL invn=getPow(len,P-2);
            for(int i=0;i<len;i++) a[i]=a[i]*invn%P;
            for(int i=1;i<len;i++) if(i<len-i) swap(a[i],a[len-i]);
        }
    }

    void gao(){
        static LL t1[MAXN],t2[MAXN];
        int sizew;
        for(sizew=1;sizew<=n;sizew<<=1);
        sizew<<=1;
        for(int i=0;i<=n;i++){
            t1[i]=c[i]*invfac[i]%P;
            if(i&1) t1[i]=-t1[i];
            t2[i]=invfac[i];
        }
        FFT(t1,sizew,1);
        FFT(t2,sizew,1);
        for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i]%P;
        FFT(t1,sizew,-1);
        for(int i=0;i<=n;i++){
            c[i]=t1[i]*fac[i]%P;
            if(i&1) c[i]=-c[i];
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    scanf("%lld%d%lld",&m,&n,&x);
    init();
    for(int i=0;i<=n;i++) scanf("%lld",c+i);
    GaoFFT::gao();
    LL ans=0,temp=1;
    for(int i=0;i<=n;i++){
        ans=(ans+c[i]*binom[i]%P*temp)%P;
        temp=temp*x%P;
    }
    printf("%lld\n",(ans%P+P)%P);
}

又是愉快的1A。

这道题难度其实不算难,但看起来比较鬼畜,考场上的话心态可能会受到影响。其实仔细想想,不掉进多项式展开的坑里面,还是蛮好做的(?)。不过根据我场上必定挂题的惯例,这题场上做的话一定会挂(确信)。

T2

传送门

喜闻乐见提答题!

不过好久没做提答了(上次做是在noi前),感觉做起来非常吃力。做的时候看了下时间,前两h只拿了35~56分。。。一共做了3到4h才过掉。不过这好像还是我第一次独立A掉一道提答题?(我还是太弱了)

这题的题意还是需要理解一会儿的。。下面按照切的顺序来讲一讲每个点的做法:

1号点:这个点送分的。。。把题目看懂之后应该就会了吧。。?

2号点:显然也是送分,裸的kmp瞎搞,然而我FST了。。。原因是他要求包含的串只有小写字母,然后我就傻逼了只处理了小写字母,别的字符直接reject了。。。然后就GG了。样例太弱了,场上的话估计根本发不现这个问题,直接少掉11分。

10号点:看起来很不可做的点,然而非常可做。。。因为长度很小,所以直接建立100个点,代表一个大小100的if的栈,然后随便弄弄就行了。细节可能有点烦。

5号点:不懂为啥只有100。。。考虑二进制下能否被11整除,其实就是把1 1或者-1 -1移位之后,从高到低加在原串上,看看最后是不是全0就行了。这个过程中可以直接允许-1的出现,所以分别弄几个代表当前为是0/1/-1的状态瞎搞就行了。

这是几个比较好做的点,后面的点有点不好想(好吧其实是我比较傻逼想了半天)

3,4号点:要处理括号序列啊。。。考虑括号序列合法当且仅当任何一个前缀和都非负,且总和为0(左括号为1,右括号为-1)。直接做显然会爆节点数限制,所以我们考虑设一个k=80左右,建立k以内的所有状态,然后如果加减1的时候还在范围内,就直接在范围里面动。然而肯定会有超出k的情况,那么我们就把这个括号序列转成一个更小的括号序列,其中新序列中的每个括号跟原序列中的k个括号等价。这样的话每次序列长度会至少除以k,所以复杂度是对的。注意如果先加到k后回到0,这时再-1的话是不知道到底可不可行的,因为可能这次-1的时候前面的和是k的倍数。所以还要把减了一些(减的最大幅度小于k)之后再加回去的情况也考虑进去,这些情况是比较特殊的。具体实现有(fei)点(chang)麻烦,事实上要搞3k个状态(可能是我池沼了,也许不需要这么多),分别代表正的前缀和,负的前缀和,以及减到负再加回正的前缀和。减到负再加回正其实等价于新序列中的一个")(("。瞎处理一下就能做出来了,写的时候很容易被恶心到

8,9号点:看起来最不可做,然而仔细想想发现+和\_没有一丁点区别。。。而且好像"(0+"和"("是等价的(同样0换成1,+换成\_也等价)。所以去掉数字和+\*之后就变成括号序列啦,跟3,4号点一样,然而要加大量处理,更加恶心

5,6号点:最后做这两个点是因为前面死活想不到,结果后来想了想发现比3,4,8,9简单多了。。。一个斐波那契串可以看作一堆"a"和"b"排在一起,自然也可以看作一堆"b"和"ba"(如果不能的话显然不合法)。这样的话把"b"换成"a","ba"换成"b",跟原来的合法性是相同的。所以每次大概长度减了一半,也愉快地做完啦(状态数量巨少无比)。

代码:太多太长就不放啦

顺便看了看rank1的答案,状态数量比我少几十倍。。。太恐怖了(虽然可能是因为我没调参,k太大了)。


T3

传送门

看完题目之后想了想感觉虚树上面乱搞好像可做,然后就开始爆写虚树+各种奇妙dp。然后写着写着,写到150行的时候发现做法是假的,好像还要维护线性变换套在一起的类似前缀和的东西,好像还要$2\times 2$矩阵求逆。结果最后写到200+行的时候发现自己的做法在$n_a=n_b=n_c=0$的时候还是错的,然后。。。然后就愉快地弃题啦。

然后就去看了题解,发现出题人是陈老师。。。恐怖。。。然后题解没给分数分布,不知道是不是因为根本没人做。。。?

看了看题解,好像是虚树上面点分。。。而我之前爆写的那个zz做法居然是60分暴力。。。我的一堆xjb预处理到了题解上变成了"处理出一些信息标记在边上"??然后更恐怖的是uoj上这题只有5人过,还有人代码18K。。。这题能改。。。?

不知道以后会不会回来改这题,总之先跳过吧。。。

查看详细内容

清华集训2016 Day1

2017-9-8 21:232017-9-13 7:45
清华集训智力康复

颓了一个暑假感觉自己已经不适合打OI了。。。

结果突然被钦点去做清华集训题,可能有点不知所措。。。?

反正估计大部分题都不可做,就当恢复一下智商吧。


T1

传送门

上来发现是博弈论,感觉自己过了一个暑假已经想不动任何思维题了,有点想弃的冲动。。。 然而仔细想想似乎挺可做的?

考虑一棵以x为根,大小为n子树的sg函数,设$sg[x]$为以x为根的子树的sg函数,考虑下一步能怎么走。

显然有n种走法,分别代表删掉每个点到根的路径。删完之后会剩下一些子树,而这些子树在后面的博弈中就都是独立的了,可以把他们的sg异或起来作为这一步的sg。而我们要求的就是所有这n个点所对应的这些"删剩下的子树的sg的异或"的mex。

考虑删掉一条路径后剩下的子树长啥样。注意到一个点会成为删剩下子树的根,当且仅当他的父亲出现在删除的路径中,并且他自己不在路径里。那么就考虑统计每个点自己的sg函数和所有儿子的sg函数的异或和(根节点比较特殊,不用算自己的sg,而且这时候根本不知道他的sg是多少,但是算完这个点准备算他的父亲的时候,要把他的sg值算上),我们把这个东西记为$g[x]$,显然把要删除的路径上的所有点的$g[x]$异或起来,每个路径上的点会被异或两次从而被抵消,而他们的不在删除路径上的儿子则会被算刚好一次。这样就建立起了初步的模型。

接下来的问题就是怎样统计每个点到根的$g[x]$的异或和。我们可以把一棵子树所有的点到根的g的异或和存在trie里面,这样的话从子树的trie中转移时,只需要将trie里面的所有异或一个值(即根节点的g值),然后用类似线段树合并的思想去把这些子树的trie合并起来。(这其实好像就是带标记的线段树合并。。。)然后每次在整个子树的trie中二分找,就能找到mex啦!

代码:

#include <cstdio>
#include <cstring>
#define MAXN 100010

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m,maxbit=32768;
int g[MAXN],nume;
int sg[MAXN],tg[MAXN];
int root[MAXN];

namespace Trie{
    struct node{
        int ch[2];
        int tag,s;
    }a[2000000];

    int size;

    int newnode(){
        int x=++size;
        a[x].ch[0]=a[x].ch[1]=a[x].tag=a[x].s=0;
        return x;
    }

    void init(){
        size=0;
    }

    void pushdown(int x,int bit){
        if(a[x].tag){
            if(a[x].tag&bit){
                a[x].ch[0]^=a[x].ch[1]^=a[x].ch[0]^=a[x].ch[1];
                a[x].tag^=bit;
            }
            if(a[x].ch[0]) a[a[x].ch[0]].tag^=a[x].tag;
            if(a[x].ch[1]) a[a[x].ch[1]].tag^=a[x].tag;
            a[x].tag=0;
        }
    }

    int create(int v,int bit){
        if(!bit){
            int x=newnode();
            a[x].s=1;
            return x;
        }
        int x=newnode();
        a[x].s=1;
        a[x].ch[(v&bit)?1:0]=create(v,bit>>1);
        return x;
    }

    int merge(int x,int y,int bit){
        if(!x) return y;
        if(!y) return x;
        if(!bit) return x;
        pushdown(x,bit); pushdown(y,bit);
        a[x].ch[0]=merge(a[x].ch[0],a[y].ch[0],bit>>1);
        a[x].ch[1]=merge(a[x].ch[1],a[y].ch[1],bit>>1);
        a[x].s=a[a[x].ch[0]].s+a[a[x].ch[1]].s;
        return x;
    }

    int mex(int x,int bit){
        if(!bit || !x) return 0;
        pushdown(x,bit);
        if(a[a[x].ch[0]].s<bit) return mex(a[x].ch[0],bit>>1);
        else return mex(a[x].ch[1],bit>>1)|bit;
    }
}

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    tg[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            tg[x]^=sg[e[i].to];
        }
    root[x]=Trie::create(tg[x],maxbit);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            Trie::a[root[e[i].to]].tag^=tg[x];
            root[x]=Trie::merge(root[x],root[e[i].to],maxbit);
        }
    sg[x]=Trie::mex(root[x],maxbit);
    Trie::a[root[x]].tag^=sg[x];
}

void solve(){
    memset(g,-1,sizeof g);
    memset(sg,-1,sizeof sg);
    nume=0;
    Trie::init();
    scanf("%d%d",&n,&m);
    while(m--){
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    int res=0;
    for(int i=1;i<=n;i++)
        if(sg[i]==-1){
            dfs(i,0);
            res^=sg[i];
        }
    if(res) puts("Alice");
    else puts("Bob");
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
}

然后就一A了。。。 原来清华集训这种奇妙比赛里面也有这么可做的题。。。


T2

传送门

这题的题面什么鬼啊。。。感觉把他读懂并不容易啊?

大概就是给你一个奇妙进位制,每一位的大小都不同,然后给你一个下标为这种进位制的数组c,让你构造另一个数组b,使得$c[i]=\Sigma_{j\leq\leq i}b[j]$,其中$j\leq\leq i$表示j的每一位都小于等于i.

一开始想容斥,想了一个$O(3^{log_2n})$的枚举子集容斥的dp,不过显然过不了。后来仔细想想发现自己傻逼了,直接从高到低对每一位容斥就好了。

假设当前我们要算的位置下标是$i$,最高位是$i_k$,其他位是$i_{[0,k-1]}$,那么$j\leq\leq i$当且仅当$j_k\leq i_k$且$j_{[0,k-1]}\leq\leq i_{[0,k-1]}$。我们要去掉所有满足至少一位严格小于$i$的$j$,那就先考虑$j_k<i_k$的情况,直接把$c[i_{[0,k-1]},i_k]-=c[i_{[0,k-1]},i_k-1]$,之后就只用考虑$0$到$k-1$位的情况,直接递归下去做就行了。

然后就自信写了一发,结果70分WA了。。原因是没有再最高位补一个非常大的进位,然后一旦所有位大小乘起来小于n,就会有一些位置根本没被算到。。。(智障*1)

然后又自信交了一发,结果98分T了!竟有这种操作???

结果后来发现自己的复杂度根本就是假的,这个做法考虑每位的时间复杂度是$T(n)=kT(n/k)+O(n)$.如果每个k都等于1,就会一直$O(n)$下去,然后就变成$O(n^2)$啦!(智障*2)

然后把所有$k=1$的都去掉了,这回复杂度变成真的$O(nlog(n))了$,结果又忘记把这些1输出了。。。又WA了一次。。。(智障*3)

结果就是梦游一样地交了四次才过,感觉早上做题跟智障根本没什么区别。。。(好吧本来就是智障)

代码:

#include <cstdio>
#include <cstring>
#define LL long long
#define MAXN 2000010

int n,m;
int c[MAXN];
LL a[MAXN];

void init(){
    int _m;
    scanf("%d",&_m);
    printf("%d\n",_m);
    for(int i=1;i<=_m;i++){
        int t;
        scanf("%d",&t);
        printf("%d ",t);
        if(t>1) c[++m]=t;
    }
    puts("");
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld",a+i);
    puts("");
    printf("%d\n",n);
    c[++m]=1000000000;
    LL temp=1;
    bool flag=0;
    for(int i=1;i<=m;i++){
        if(flag) c[i]=1;
        else if(temp*c[i]>=n){
            c[i]=(n-1)/temp+1;
            flag=1;
        }else{
            temp*=c[i];
        }
    }
}

void gao(LL *a,int k,LL num){
    if(!k) return;
    LL s0=num/c[k];
    for(int i=c[k]-1;i>=0;i--){
        if(i){
            for(int j=0;j<s0;j++)
                a[i*s0+j]-=a[(i-1)*s0+j];
        }
        gao(a+i*s0,k-1,s0);
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("B.in","r",stdin);
#endif
    init();
    int _n=n;
    n=1;
    for(int i=_n;i<n;i++) a[i]=0;
    for(int i=1;i<=m;i++) n*=c[i];
    gao(a,m,n);
    for(int i=0;i<_n;i++) printf("%lld ",a[i]);
    return 0;
}

顺便发现了uoj的一个神秘特性?好像输出的时候一行一个和用空格分开都会给对。。。


T3

传送门

想了半天不会做啊。。。我还是太弱了。。。

正解非常巧妙(我感觉我这种傻逼不太可能想得到),利用了两条路径的交也是一条路径,且任何一条路径经过的点数等于边数+1,然后差分之后就变成了求点权和减边权和最大的路径。

然后为了维护权值最大的路径,我们先做一个重链剖分,然后考虑最优路径的一些性质。 首先最优路径要么是一条竖着的链,要么在最高点有两个儿子的分支。也就是说最多有两个儿子的分支(这不是废话吗)。 对于两个儿子都是轻儿子的情况,显然每次更改一条路径,只会经过$O(log(n))$条轻边。所以对于每个点直接非常暴力地维护一个堆,堆里面维护每个轻儿子往下走最多能走出多大的权值。对于每条被影响到的轻边暴力修改堆,并用最大值和次大值更新答案就可以了。

那么对于重儿子被修改的情况,我们可以维护一个线段树,统计树链上的一些信息,通过在线段树里储存之前那些堆里的信息来维护答案。 细节比较复杂(雾),可以参考代码。

然后就开始码码码。。。码完之后调了调发现90分WA了。诶只wa了10分,那应该只是什么地方的细节写炸了啊?结果越改分越少,最后只剩50分。。。

结果后来发现算法是假的,两个儿子都是轻儿子的情况也可能发生在重链里面,还要把最大和次大都扔到线段树里面。。。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define LL long long
#define MAXN 100010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct Heap{
    priority_queue<LL> Q1,Q2;

    void insert(LL x){ Q1.push(x); }
    void remove(LL x){ Q2.push(x); }

    LL top(){
        while(!Q2.empty() && Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
        if(Q1.empty()) return 0;
        return Q1.top();
    }

    LL top2(){
        while(!Q2.empty() && Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
        if(Q1.empty()) return 0;
        LL x=Q1.top();
        Q1.pop();
        while(!Q2.empty() && Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
        if(Q1.empty()){
            Q1.push(x);
            return 0;
        }
        LL y=Q1.top();
        Q1.push(x);
        return y;
    }
}h[MAXN],ans;

namespace SegTree{
    struct node{
        int lc,rc;
        LL sl,sr,s,s0,delta,tag;
    }a[MAXN<<2];

    int size;

    int create(int l,int r){
        int x=++size;
        if(l==r) return x;
        int mid=(l+r)>>1;
        a[x].lc=create(l,mid);
        a[x].rc=create(mid+1,r);
        return x;
    }

    void pushup(int x){
        a[x].s0=a[a[x].lc].s0+a[a[x].rc].s0-a[x].delta;
        a[x].s=max(max(a[a[x].lc].s,a[a[x].rc].s),a[a[x].lc].sr+a[a[x].rc].sl-a[x].delta);
        a[x].sl=max(a[a[x].lc].sl,a[a[x].lc].s0+a[a[x].rc].sl-a[x].delta);
        a[x].sr=max(a[a[x].rc].sr,a[a[x].rc].s0+a[a[x].lc].sr-a[x].delta);
    }

    void pushdown(int x){
        if(a[x].lc){
            a[a[x].lc].tag+=a[x].tag; a[a[x].lc].s0+=a[x].tag; a[a[x].lc].sl+=a[x].tag;
            a[a[x].lc].sr+=a[x].tag;  a[a[x].lc].s+=a[x].tag;  a[a[x].lc].delta+=a[x].tag;
            a[a[x].rc].tag+=a[x].tag; a[a[x].rc].s0+=a[x].tag; a[a[x].rc].sl+=a[x].tag;
            a[a[x].rc].sr+=a[x].tag;  a[a[x].rc].s+=a[x].tag;  a[a[x].rc].delta+=a[x].tag;
        }
        a[x].tag=0;
    }

    void add(int x,int cl,int cr,int l,int r,LL v){
        if(l<=cl && cr<=r){
            a[x].tag+=v; a[x].s+=v; a[x].sl+=v; a[x].sr+=v; a[x].s0+=v; a[x].delta+=v;
            return;
        }
        pushdown(x);
        int mid=(cl+cr)>>1;
        if(r<=mid) add(a[x].lc,cl,mid,l,r,v);
        else if(l>mid) add(a[x].rc,mid+1,cr,l,r,v);
        else{
            a[x].delta+=v;
            add(a[x].lc,cl,mid,l,r,v);
            add(a[x].rc,mid+1,cr,l,r,v);
        }
        pushup(x);
    }

    void add2(int x,int cl,int cr,int pos,LL v1,LL v2){
        if(cl==cr){
            a[x].sl+=v1; a[x].sr+=v1; a[x].s+=v1+v2;
            return;
        }
        pushdown(x);
        int mid=(cl+cr)>>1;
        if(pos<=mid) add2(a[x].lc,cl,mid,pos,v1,v2);
        else  add2(a[x].rc,mid+1,cr,pos,v1,v2);
        pushup(x);
    }

    LL query(int x,int cl,int cr,int pos){
        if(cl==cr) return a[x].s0;
        int mid=(cl+cr)>>1;
        if(pos<=mid) return query(a[x].lc,cl,mid,pos);
        else return query(a[x].rc,mid+1,cr,pos);
    }
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int q[MAXN][3];
int dep[MAXN],pre[MAXN],size[MAXN],son[MAXN],top[MAXN],w[MAXN],numw;
int len[MAXN],root[MAXN];
LL delta[MAXN],now_s[MAXN],now_sl[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    size[x]=1; 
    pre[x]=p;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dep[e[i].to]=dep[x]+1;
            dfs(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>size[son[x]])
                son[x]=e[i].to;
        }
}

void dfs2(int x,int p){
    w[x]=++numw;
    ans.insert(0);
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }else{
        len[top[x]]=numw-w[top[x]]+1;
        root[top[x]]=SegTree::create(1,len[top[x]]);
        ans.insert(0);
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && e[i].to!=son[x]){
            top[e[i].to]=e[i].to;
            dfs2(e[i].to,x);
            h[x].insert(0);
        }
}

void add(int x,int y,LL v){
    int rt=root[top[x]];
    SegTree::add(rt,1,len[top[x]],w[y]-w[top[x]]+1,w[x]-w[top[x]]+1,v);
}

void update(int x,LL v2){
    ans.remove(now_s[x]);
    ans.insert(now_s[x]=SegTree::a[root[x]].s);
    if(pre[x]){
        //ans.remove(h[pre[x]].top()+h[pre[x]].top2()+SegTree::query(root[top[pre[x]]],1,len[top[pre[x]]],w[pre[x]]-w[top[pre[x]]]+1));
        LL sl0=now_sl[x];
        LL t1=-h[pre[x]].top(),t2=-h[pre[x]].top2();
        h[pre[x]].remove(sl0);
        h[pre[x]].insert(now_sl[x]=SegTree::a[root[x]].sl-delta[x]);
        t1+=h[pre[x]].top(); t2+=h[pre[x]].top2();
        //ans.insert(h[pre[x]].top()+h[pre[x]].top2()+SegTree::query(root[top[pre[x]]],1,len[top[pre[x]]],w[pre[x]]-w[top[pre[x]]]+1)+v2);
        if(t1 || t2) SegTree::add2(root[top[pre[x]]],1,len[top[pre[x]]],w[pre[x]]-w[top[pre[x]]]+1,t1,t2);
    }
}

void gao(int x,int y,LL v){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
        add(x,top[x],v);
        delta[top[x]]+=v;
        update(top[x],v);
        x=pre[top[x]];
    }
    if(dep[x]<dep[y]) x^=y^=x^=y;
    add(x,y,v);
    while(x){
        update(top[x],0);
        x=pre[top[x]];
    }
}

void debug(int x){
    while(x){
        printf("%d ",x);
        x=pre[x];
    }
    puts("");
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("C.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    dep[1]=1;
    dfs(1,0);
    top[1]=1;
    dfs2(1,0);
    for(int i=1;i<=m;i++){
        char c;
        while((c=getchar())!='+' && c!='-');
        if(c=='+'){
            int u=read(),v=read(),w=read();
            gao(u,v,w);
            q[i][0]=u; q[i][1]=v; q[i][2]=w;
        }else{
            int t=read();
            gao(q[t][0],q[t][1],-q[t][2]);
        }
        printf("%lld\n",ans.top());
    }
    return 0;
}

总结

做完这几道题,感觉自己越来越弱了。。。从sb题奥妙重重连WA几次,到难题不会做,想都没想清楚就开始写,结果越WA分越少。感觉如果现场打这套题,有可能200分都不到。

看来还是得练练一次AC的能力,同时对拍也得打好。现在做散题一直都没有对拍的习惯,感觉现场比赛药丸啊(已经因为没打好对拍在大赛中GG过一次or数次了),以后还是打现场比赛制的套题好点吧。总之这套题做的不怎么好,希望接下来做的几套题能有一点微小的进步。

查看详细内容