BZOJ4817 [Sdoi2017] 树点涂色

题目链接

Solution

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

Hints

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

Code

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

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,光荣报零。。。

BZOJ3944 杜教筛

(被owenowl要求加上的内容)flx 教我杜教筛,虽然他没做这道题。

传送门,戳这里

Problem

Description

题目

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个 非负整数N,代表一组询问

Output

一共T行,每行两个用空格分隔的数ans1,ans2

Sample

Input

Output

Solution

杜教筛裸题。

下面是我学杜教筛的一点经验,和大家分享一下。
如果您已经精通杜教筛,请跳过下面的内容,直接看注意事项。

如果您还不会莫比乌斯反演,请先学习反演再看本文。否则,可能一头雾水。

一般求Phi函数和mu函数都用线性筛,可以在O(n)的时间内求出1~n的所有phi值和mu值。下面是线性筛的代码,主要思想就是筛质数,然后根据phi和mu的积性函数性质筛后面的数。

Markdown炸了。。没法打数学公式。。

但是对于n很大求前缀和的情况(比如本题),O(n)的复杂度就不够了。这个时候就需要一种新的方法————杜教筛。

设h = f ⊗ g,设f的前缀和为S,而h的前缀和易求,那么可以用杜教筛。经过推导,可以得到:
杜教筛公式

首先考虑对μ函数的前缀和(欧拉函数同理):
构造一个g(i)=1!那么,有:

M(x)为mu[x]的前缀和:

求phi函数的时候,如何构造g(x)留给读者自行思考。

杜教筛关键在于构造g函数与f函数进行卷积,再通过杜教筛的公式递归求值。(可以是另一个杜教筛)
有几个注意事项:

1、首先,在用杜教筛之前,先用线性筛把开始较小的一些数(1~n^(2/3))的phi和mu给筛出来,再调用杜教筛,这样可以优化一下复杂度。

2、在用杜教筛枚举i求phi(x/i)时,分段枚举,对于一段x/i相同的i的区间只枚举一次,再乘以这一段的大小即可。否则可能会T掉

3、对于线性筛筛出来的值,要用数组存,不要用map,否则会多一个log,很可能T掉;

Code bzoj 3944

附上AC代码,前几十行写了读入优化,可以跳过。
本题AC需要靠运气,或者您去学洲阁筛吧。