BZOJ4817 [Sdoi2017] 树点涂色

题目链接

Solution

这题很???
我们把相同颜色的点之间连的边看成preferred edge
那么操作1就是access
查询的时候用链剖维护一下区间最值就行了。

Hints

然而LCT写挂了两次
先是rotate的时候把一个x打成了k,
然后是splay的时候没有判isroot(fa[x])。
一些注意的地方:
1、LCT和链剖的father要分开记。
2、access的时候要注意处理now断开的那部分子树。

Code

#include<bits/stdc++.h>
#define FIO "sample"
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int maxn = 100010;

struct edge{
    int nxt,to;
    edge(){}
    edge(int nxt,int to):nxt(nxt),to(to){}
}e[maxn<<1];
template<typename T> inline void Max(T &x,T y) {if(x<y) x=y;}

int n,m,last[maxn],cnt=1,f[maxn],top[maxn],dfn[maxn],pos[maxn],dep[maxn],ch[maxn][2];
int sz[maxn],ind=0,mx[maxn<<2],tag[maxn<<2],son[maxn],fa[maxn];

inline void insert(int u,int v){e[++cnt]=edge(last[u],v);last[u]=cnt;}
inline void addedge(int u,int v){insert(u,v);insert(v,u);}

inline void dfs(int x)
{
    dep[x]=dep[f[x]]+1;
    sz[x]=1;son[x]=0;
    for(int i=last[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v^f[x])
        {
            f[v]=x;dfs(v);sz[x]+=sz[v];
            if(sz[v]>sz[son[x]]) son[x]=v;
        }
    }
}

inline void dfs2(int x,int chain)
{
    top[x]=chain;pos[dfn[x]=++ind]=x;
    if(son[x]) dfs2(son[x],chain);
    for(int i=last[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v^f[x]&&v^son[x])
            dfs2(v,v);
    }
}

inline int lca(int x,int y)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

inline void update(int x)
{
    mx[x]=max(mx[x<<1],mx[x<<1|1]);
}

inline void pushdown(int x)
{
    if(tag[x])
    {
        int ls=x<<1,rs=x<<1|1;
        tag[ls]+=tag[x];
        tag[rs]+=tag[x];
        mx[ls]+=tag[x];
        mx[rs]+=tag[x];
        tag[x]=0;
    }
}

inline void build(int x,int l,int r)
{
    tag[x]=0;
    if(l==r){mx[x]=dep[pos[l]];return;}
    int mid=l+r>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    update(x);
}

inline void modify(int x,int l,int r,int lx,int rx,int val)
{
    if(l>=lx&&r<=rx) {mx[x]+=val;tag[x]+=val;return;}
    int mid=l+r>>1;pushdown(x);
    if(lx<=mid) modify(x<<1,l,mid,lx,rx,val);
    if(rx>mid) modify(x<<1|1,mid+1,r,lx,rx,val);
    update(x);
}

inline int query(int x,int l,int r,int lx,int rx)
{
    if(l>=lx&&r<=rx) return mx[x];
    int mid=l+r>>1,res=0;pushdown(x);
    if(lx<=mid) Max(res,query(x<<1,l,mid,lx,rx));
    if(rx>mid) Max(res,query(x<<1|1,mid+1,r,lx,rx));
    return res;
}

inline bool isroot(int x) {return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);}
#define ir isroot
inline int get(int x) {return ch[fa[x]][1]==x;}
#define gt get

inline void rotate(int x)
{
    int y=fa[x],z=fa[y],k=gt(x);
    if(!ir(y)) ch[z][gt(y)]=x;
    fa[ch[y][k]=ch[x][k^1]]=y;
    fa[fa[ch[x][k^1]=y]=x]=z;
}

inline void splay(int x)
{
    for(int y=fa[x];!ir(x);rotate(x),y=fa[x])
        if(!ir(y))
            rotate(gt(x)==gt(y)?y:x);
}

#define end(x) (dfn[x]+sz[x]-1)

inline void access(int x)
{
    for(int t=0;x;t=x,x=fa[x])
    {
        splay(x);
        if(ch[x][1])
        {
            int now=ch[x][1];
            while(ch[now][0]) now=ch[now][0];
            modify(1,1,n,dfn[now],end(now),1);
        }
        ch[x][1]=t;
        if(ch[x][1])
        {
            int now=ch[x][1];
            while(ch[now][0]) now=ch[now][0];
            modify(1,1,n,dfn[now],end(now),-1);
        }
    }
}

int main()
{
#ifdef dxymaster
    freopen(FIO".in","r",stdin);
    freopen(FIO".out","w",stdout);
#endif
    n=read(),m=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v);
    }
    f[1]=0;dfs(1);dfs2(1,1);build(1,1,n);
    for(int i=1;i<=n;i++) fa[i]=f[i];
    while(m--)
    {
        int opt=read();
        if(opt==1) access(read());
        else if(opt==2)
        {
            int x=read(),y=read(),k=lca(x,y);int v=query(1,1,n,dfn[k],dfn[k]);
            printf("%d\n",query(1,1,n,dfn[x],dfn[x])+query(1,1,n,dfn[y],dfn[y])-(v<<1)+1);
        }
        else
        {
            int x=read();
            printf("%d\n",query(1,1,n,dfn[x],end(x)));
        }
    }

    return 0;
}

SCOI 2018 不知道干了什么记

省选复习

做了10联测,感觉被大佬们各种虐,有种省选完挂的预感啊。。。

上了OJ才发现自己rating好低。。。炫酷蓝紫色。。。

期间做了ZJOI Day1和一些不知道哪里来的题,看题发现自己啥都不会,只会暴力。。。

然而做完以后发现自己并不会暴力,只会瞎骗分。。。。

然而评测的时候发现,自己并不会骗分,只会报零。。。。

总之就是被各种吊打,只有最后一天的题稍微良心一点。。。写了傻逼的T1和T3.。。但是好像有很多人AK。。。。

省选集训 (Day -4 ~ Day -1)

Day -4

上午去神大ACM,只A了3到签到题。A迷之wa,交了十多发都被卡在了第11个点。。。。

佬队AK后提前离场了,吊打神大,%%%。

下午去中和中学。。好偏僻啊。。听说是在一个镇上???!!!

没去学校看,直接去酒店了。。。

Day -3

上午去听课了??不知道哪里的人来讲的。

讲的线性基,感觉好水啊。然后就开始突突突。

下午上机练习。中和的电脑配置看起来不错,但用着挺糟糕的。。

花了半个小时配环境(大半时间实在卸载。。)然后开始突突突。。

晚上会酒店,看了会儿题,然后突突突。。

Day -2

和前一天好像没啥区别。。

下午lxs发了一套题,把T1、T3写了。。

Day -1

同上

不过这次写的是T2和T3

Day 0

上午起来好困啊。。

以为是下午才模拟考,导致前一天晚上睡得晚。。。

T1傻逼DP。。写了2小时。。。我好菜啊。。(后来发现状态数多了一点,写复杂了。。但是懒得改了。。。)

T2会一个线段树上二分的log方做法。。。然而数据范围很水的样子。。好像这套题里所有的n都没有超过1e4的(雾)

于是写了n方暴力。事实证明我并不能够卡过。。。

T3好像是维护一个最小割。。并不知道怎么维护。。时间也不太够了,就写了一个网络流加一点小优化。。

结果T1T了3个点(真心慢),T2T了4个,T3T了2个。。。

然后下午去神大天街。

好好睡了一觉。

Day 1

早上起的很早,有点困。到了神大,发现两边都坐的是石室的。结果两人都进队了。被支配的恐惧有没有。。

T1写了4个小时。。乍眼一看以为是一道傻逼题。先是想用链剖维护,发现不会。然后又上动态点分。码了两百多行一测样例,然后想了想发现不对。然后觉得是道树套树裸题,发现写不来。

最后写了个跟树深度有关的方法,事实证明出题人没有恶意卡。

然后看T2,推了一下,发现是个二次剩余。但是模数1e16,觉得没法做。最后放弃了,写了个55分暴力。

然后看T3,发现不会。瞎写了一下。

然后,开始绝望。。

最后10分钟突然发现T2要乘爆long long,没时间了,果断选择不改了、继续绝望。

最后75+15+0

但是看大家分好像都很低的样子。。然而佬还是那么高,255碾压全场。。

Day2

密码好像是什么吃葡萄不吐葡萄皮。

T1发现是线段树维护一个凸函数。。看起来不是那么好写。。先放着。

T2计算几何??放弃。。。

T3是个什么玩意儿。我只会10分好不好。再看了一遍题,确认无误后,果断选择放弃。。

然后开始码T1。写了大概1h,调过了大样例。然后开始对拍。

可能是我的写法太丑了,对拍居然发现了4个错。。

然后调完,发现常数大。。可能要跑4、5秒。

各种卡常。

最后30+0+0.

Day 3

省赛完挂,退役AFO
要是明年再这样就真GG了

NOIP2017滚粗记

DAY -1s

NOIP考试前还是做了些题(当然和大佬比起来还是差的远)算上校内测试和NOIP历年真题,总共也有一百道吧,还是从中学到了不少的东西。

这些题中大多数都是dp、数论、DS和一些树上的操作,对于图论的训练要稍欠一些,所以今年NOIP滚粗也是可以预见的。

在准备NOIP期间,对于代码能力的训练也是不够的,常常对一些难写的题望而却步。以后将加强这方面的训练,过两天要搞一个训练计划,着重训练这些方面。

NOIP考试前,lxs准备了10套模拟题,其中也不乏好题(当然,为了让考试更加有趣,毒瘤题也是必不可少的)

10套模拟测试常常翻车,rating变化跌宕起伏。。还好最后rating还是翻回了1500(最后一天Unrated(嘻嘻))。

DAY 0

上午写了点板,写了几道线段树的题。

中午lxs开了一会儿会。去隔壁机房学了一会儿linux虚拟机。

下午回家颓了很久,然后晚上去酒店。

DAY 1

上机的感觉:电子科大的电脑屏幕和键盘都好小。。(经常把退格按成回车)

今年的压缩包密码好像是“不忘初心”,这是要告诉我们就算NOIP滚粗了也要继续苟下去吗?。。

一看T1是一道数学题,开始想成了扩欧,还好又看了一遍题发现是非负整数解。然后2分钟写完了。。对拍完用了20分钟。。(为什么这么慢啊!)

T2是一道模拟,稍微想了一下用栈来维护那个for和退出循环。写了半个小时,样例过了,大样例WA了。仔细看看,发现要判forn n为1的情况(而且我读数的时候好像只读了第一个字符,不过大样例精心构造。我试了一下,只读第一个字符好像也可以过。)

T3看了一眼就懵逼了?啥子玩意儿?这是要乱搞的节奏。。推了一会儿,发现先跑最短路,找到能贡献的边重建图,判0环,缩点??!!拓扑序dp。大样例都水过了,结果随手出了一个数据就输出了个“0!!”真是精心构造!

最后没时间了,只好写一个30分的暴力。

DAY 2

密码好像是alphago,怎么不和DAY1搭配啊。

T1是求一个图能不能从上往下联通,并查集写了10分钟,大概调了一下就过了。

T2开始以为是状压dp直接记录每个点选没选,结果写到一半发现是错的。。

于是感觉不妙,直接写了一个记录所有状态的暴力。

学军的数据把我卡到了20。。

luogu上水过了70。。

T3推了半天树状数组,最后还是写暴力+查分+BIT+离线+splay维护+乱搞。splay最后没写出来,怕MLE,把它删了。

结果怎么35啊???

NOW

NOIP大概也过去一周了,作为我OI生涯的第一场考试,也算是一次历练吧。

NOIP代码公开了,对于NOIP2017,我只能说:还好是高一。

下周一出成绩的时候再把成绩表贴上来吧。。

希望CCF的数据水一点,D2T2能水70分。

RESULT

DAY1 100+100+30=230

DAY2 50+60+30=140

TOTAL:140+230=370

没想到的是DAY2T1炸了。把数据下下来测,发现最后几个点T了。

历年和蔼可亲的CCF居然卡我DOUBLE的常!!料不到啊料不到。(不过我转了12次double常数确实也挺大的。。)

算了,就当花50分买了一个卡常的教训吧。(希望我不要因为这次NOIP以后成为卡常的毒瘤。)

这大概就是今年的NOIP了。我知道我的路还长着呢,认真准备省选吧,来年再战!

NOIP2015 斗地主

NOIP2015 斗地主

传送门

Description

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、 方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。在斗地主中,牌的大小关
系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下:

伪·斗地主规则

Solution

暴力搜索就行了
注意一下dfs枚举的顺序,先顺子,再四带二(两对),再三带一(一对),最后,相同种类的牌一起出就可以了。

开始看着挺吓人的,其实写起来还是挺好写。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int T,n;
int cnt[17],ans=99;
const int size[4]={0,5,3,2};
void dfs(int x)
{
    if(x>ans) return;
    for(int i=3;i;i--)//处理顺子,i是顺子中相同牌的个数
    {
        int l=0;
        for(int j=3;j<=14;j++)
        {
            if(cnt[j]>=i) l++;else l=0;
            if(l>=size[i])
            {
                for(int k=j-l+1;k<=j;k++) cnt[k]-=i;
                dfs(x+1);
                for(int k=j-l+1;k<=j;k++) cnt[k]+=i;
            }
        }
    }
    for(int i=2;i<=14;i++)//处理4带2,注意处理4带两对
    {
        if(cnt[i]>=4)
        {
            cnt[i]-=4;
            for(int j=2;j<=14;j++)
            {
                if(i==j||cnt[j]<2) continue;
                cnt[j]-=2;
                for(int k=2;k<=14;k++) 
                {
                    if(cnt[k]<2||k==j) continue;
                    cnt[k]-=2;dfs(x+1);cnt[k]+=2; 
                }
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)
            {
                if(i==j||cnt[j]<1) continue;
                --cnt[j];
                for(int k=2;k<=15;k++)
                {
                    if(cnt[k]<1||k==j) continue;
                    --cnt[k];dfs(x+1);++cnt[k];
                }
                ++cnt[j];
            }
            cnt[i]+=4;
        }
    }
    for(int i=2;i<=14;i++)//处理3带(1\2)
    {
        if(cnt[i]>=3)//3带2
        {
            cnt[i]-=3;
            for(int j=2;j<=14;j++)
            {
                if(cnt[j]<2||i==j) continue;
                cnt[j]-=2;
                dfs(x+1);
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)//3带1
            {
                if(cnt[j]<1||i==j) continue;
                --cnt[j];dfs(x+1);++cnt[j];
            }
            cnt[i]+=3;
        }
    }
    for(int i=2;i<=15;i++) if(cnt[i]>0) ++x;//剩下的牌只能每种相同的牌单独出,每种牌只用出一次
    ans=min(ans,x);
}
int main()
{
    T=read(),n=read();
    while(T--)
    {
        memset(cnt,0,sizeof(cnt));
        ans=99;
        for(int i=1;i<=n;i++){int x=read();if(x!=0)cnt[x]++;else cnt[15]++;x=read();}
        cnt[14]=cnt[1];dfs(0);printf("%d\n",ans);   
    }
    return 0;
}

2017/9/22~2017/9/23考试总结

2017-9-22
T1
排序贪心裸题。。考试时心慌。。没有认真写代码,数组开小了一半。RE了一半的点。。
T2
解方程。
选树上的每一条边,根据边两边的点,列方程,求出相对大小。再根据根节点的值解方程。解出所有的a值。
T3
卡特兰数或者打表找规律
当时没想到要找公式
写了四个DP水了45分
组合数学找规律这方面还需要加强


2017-9-23
T1
矩阵快速幂,考试的时候想到了,但觉得要T就没有写。
结果是1维矩阵快速幂,O(mod^2*m)的复杂度,可以跑过。
题目也很迷,讲了一大堆原根的内容,结果这道题跟原根有什么关系?
T2
先推一下式子,再通过带权并查集优化。
当时只推了一下式子,没有写并查集,而且题目所说的非负整数没有看到,一直以为样例是错的。。。
当然,出题人坑,本题数据是错的,标程也是错的。。
T3
水题,模拟一下就好。
读入了两次x1,光荣报零。。。