一点黑科技

一个很骚的写法(如果你也懒)

这样声明的”,\n”实质是一个临时的字符数组(后面是指针[]),而这个字符数组并不需要每次print都声明一次,(解释来自知乎)原因是可以把”,\n”看成一个指针 编译器在编译的时候会把这样的字符串保存到静态区,在程序里每一次使用这个字符串时都会指向那个区域,所以不用担心太大常数。


以下等式皆成立:

因为C语言的底层都是指针,数组的实现也是。对于compiler来说,它们没有区别:


lambda表达式

(SDOI2018正式兹瓷了C++11,所以这让C++11的诸多特性得以发挥功效)

见百度百科?

Codeforces Edu R42 细节决定Rating

提示:题解正文前超长啰嗦部分

我活到现在,还没这么惨过,NOIp都没有。

比赛开始4min的时候,切掉A

 

 

 

嗯没有什么毛病

最后

 

 

用实力告诉你什么叫没带脑子比赛


开始切B

下面两段程序只有这里不一样

为啥第二个会WA?????


C 35min找错

尝试cout某些变量,发现去掉cout和不去掉,结果不一样

你猜哪错了?

35min找这一个字母 我怕不是学文化课学傻了写出i=i来??

然后 忘记判前导零 WA一发

最后,最后还fst了!!

10^9是10位数,我***……

我持盾,持盾。。


D 手速打完

seq[100010] -> WA 一发

改对,交上,Ac。

最后还是fst了!!!!

我***……

我持盾,持盾。。


然后我们愉悦的比赛就结束了。

我都不知道我的脑子飞哪去了……找到和我说一声‘

细节决定Rating啊!

凉凉。


我们还是来扯题解吧

A. Equator

这题巨没意思,加一遍扫一遍完事

注意sum/2还要上取整,也就是+sum%2

B. Students in Railway Carriage

我们貌似其实好像大概一定可以说明贪心是对的

这样,如果有一些空段,它们\geq 2且是一个偶数,

那你无论什么顺序安排反正都一样,填满的格子不能变多。(二元组证一下……)

对于奇数那些,……呃, \geq 3的拆成一段偶数空位和一个空位这样两个空段

这就变成了若干由一个空位,2N个空位组成的空段。

对于一个的那些你怎么放也是固定结果的。

(注意其实\geq 3的,拆出的一个空位,你放黑或白都可以,并不受后面偶数段的影响)

然后你每次挑大的放进那一个就行。挨着放就行,反正次序安排与解的优劣无关

对于一个B这样好像很啰嗦了……

C. Make a Square

解法1,枚举最终状态,每次判断可行并更新答案

解法2,从0到9枚举步数,DFS出终态并判断合法与否

特别注意判终态不含前导零(终态不含即可,非终态?含也行。为什么呢?)

D. Merge Equals

从左向右扫一遍然后开map记录位置,找到一个二元组,递归地消除即可。

特别注意long long

E. Byteland, Berland and Disputed Cities

交了几发,WA了。

所以思路是错的,并不会,留坑了。

F. Simple Cycles Edges

并没来得及看,留坑了。

G. Visible Black Areas

瞅了一眼图好像是个计算几何?并没细看题面,咕咕咕。

SDOI2018划水记

Day -1

上午做了一道网络流,发现自己并不会当前弧优化,于是学之。

刷空间发现大家都去春游了,空间变成相册集,好感–,羡慕++

下午打板子,发现洛谷数据太弱之前的Splay打的都是错的qwq

晚上吃饭的时候才意识到大家都放假了。。。好像食堂也gg了。。超市也gg了。。

决定出去买吃的 冻死我了

在机房吃方便面居然没有被刚 , qtq

十点有一场Edu,然而怕打完太兴奋,最后缺觉而放弃了,跟着老司机(s) Sugar和Refun打了一个场外(口胡)

然而最后还是将近一点钟才睡

Day 0

上午,打盹,打板子。

中午,去潍坊,赶火车

下午,继续打板子

板子板子板子板子qwq

晚上,继续打板子

大家和Yansir一起去超市,窝给zzy安利一包辣条,然而被Yansir抓了,Yansir刚了一顿(又不是我买的吖……我提个篮子有错……罪过,罪过)

“那个爱吃零食的”……被抓颓又一顿沮丧……

最后抓一瓶茶π逃了……

Day 1

起床,吃饭,然后进场

出汗+慌……Refun小哥哥长的真好看(雾

rqy在我右面的右面的右面 ……慌+1

键盘超级脏 慌+2

发密码,慌+3

看题……慌+4

我tm什么鬼博弈…………???!?!

慌+998244353

!!去刚第二题……

不久发现是个贪心,45min写+调+拍……并没有意识到di都相等会挂掉

慌–,莫名自信(sad

天真的以为A了第二题

滚去写T1,发现状压可过,不想写++

树是一条链……强行不用主席树A掉这部分数据……唉我怎么做的来着??忘了…………

打完T3,35min passed

滚回去想T1,想出了std……好麻烦……写不完了……写暴力吧

送了25,写。 35min passed,写完了。

自信不对拍T1T3,暴力很稳的我异常自信感觉很虚

就这样滚出考场,估计25+100+15,(然而……)

滚去吃饭,被dkw Hack掉T2,sad++,感觉药丸

下午去大礼堂讲题,真tm难走都迷路了

颓废大麻茶,%rqy……等着出成绩

发现T1想的是std,然而没写……据说很短……sad++++++++

2:55被告知T2卡精, 没加eps!!panic+=998244353

这题都是什么画风啊……还有我怎么这么弱啊……

这么弱啊……

发成绩,看榜,讲题……T3是生成函数+线段树,然而并没有听懂线段树怎么用……

rk45,sad++

rqy太强啦!强力rk2

dkw在山西rk2……强啊……今年A队爷出现了……

Capella没建子文件夹,心疼Capella

cwbc拿了rk1,cwbc太强啦!

大家都比我强.jpg

……也应该吧……弱校弱选手……划水++

Refun似乎考的不好,祝他D2翻盘!

晚上去超市颓废饮料,发现没有大麻茶,sad++。 又拿了一瓶茶π跑了……茶π真好喝

颓废hp4电影,打Miller-Rabin,在群里水,和学长们讨论人生

Day 2

进场,看题。

T1一眼费用流,打!

我用费用强行创造优先级……记录一发每个导师的最靠后的学员……这不就行了?

增广完一个点我让他当前志愿的后续志愿的边强制满流,瞎证了一发好像是对的。(并没有意识到贪心可以拿分……)

打完了……过了四个鬼知道多弱的样例,扔着不管了,自信不对拍

10:40了,woc

T2弃疗,拿T3暴力去。

发现就算不kmp也有n^3的分数,真棒。写写写,分类讨论推答案推到11:45,模拟之。

好像要补集转化……?我求一下不在左面的和不在右面的区间然后合并再讨论不就好了嘛。

草稿纸好像不够……

唉。然后我枚举左端点暴力判断吧……好像很稳

我需要查询他有多少合法的右端点,显然是当前左端点后面一个合法区间里啊!先预处理。

好了,终终终于打完了。拍样例,小改一下,过了。

暴力一向很稳的我自信不对拍,发现T1第二问做错了,去改T1。有退流啊!我最后要手动枚举才行啊!

没改对,瞎证明了一发,发现之前的好像是对的(弱智的我)。

100+0+25

吃晚饭直接出了成绩,0+0+25。本来的翻盘梦想破灭了,R2再见。

没事可干,继续颓废hp4电影,内心毫无波动。等着Yansir看完测评,目测滚出前100

zzy强势翻盘,太强啦!Refun强势翻盘,太强啦!

dkw rk4进队,……祝他NOI18 Au吧。

rqy和cwbc好像都100多了,但是tyc好像拿了超级多的分????有225???!!

wodema。

迷迷糊糊滚回昌邑……在烟台南站颓hp4电影结果被Yansir刚了……sad++

最后rk68,然而rk68和rk200并没有区别,本来的翻盘梦想破灭了,R2再见。

Day 1000000007

发名单了,rk100多,NOIp强力拖后腿。

sad+=1000000007;

滚回去面对同学们……

被Yansir打电话刚,感觉嗓子都不是自己的了……

突然发现满腔热血搞了一年OI结果啥比赛也没结果……

Get lost in the cruel world.

没结果就是没结果,我也没什么话说。

真没什么话可说。

弱校,弱人,学的晚,低智商,爱颓,啥都不会。

哪天你在街上看到一个这样的人,那是我。

Codeforces R473

我这个代码能力下降到\rm{-INF}

并查集板子打了15分钟 还有谁??

气死了

算了赶紧写完赶紧睡觉

A. Mahmoud and Ehab and the even-odd game(真长)

就这题!!!卡了我五分钟!!我觉得它长的像SG,是它的错还是我的?!

一定注意a \leq n!!

然后你就会发现这游戏最多就一轮

B. Mahmoud and Ehab and the message(这个更长?)

然后并查集板子+map……能这个点打Cf的都能看出来也不说了……

C. Mahmoud and Ehab and the wrong algorithm(哇,还是这么长)

送分(ming)构造题

两问分别长这样

注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制(也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的)))

D. Mahmoud and Ehab and another array construction task(最长!)

这题,扫一下然后质因数分解

如果分解有重那么立即断开,前面的原样输出,后面的贪心地选一个质数输出

注意特判

E. Mahmoud and Ehab and the xor-MST(哈!变短了吧!)

我们考虑……有什么好考虑的。。。

那就……从高位来考虑?

当前考虑的,要求mst的点集的所有点权,在目前位上, 必然是n_1 \text{ — } n_x这一部分是0,然后n_{x+1} \text{ — } n_{last}1,那么点 x+1 \text{ — } last之间独立连边,1 \text{ — } x之间独立连边,这么做,可以保证对答案贡献都是0,是最优的。

·

但是如果当前确实有一个满足上述条件的x存在的话,

(其实也就是现在考虑的点集的最大点权的点,点权模掉2^{w-1}大于等于2^w,其中w是当前考虑的位数)

(也就是这一位上有1的出现,所以点被划成了这一位是0 \; , \; 1两个子点集)

那么还要把左右两个点集联通。先加上这样的代价 :2^w

·

我们其实并不关心这两个点集是怎么内部联通的,因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了,对吧?

但是0集那个子问题是可以预处理的,要不然会T。

f[i]表示从02^i-1的贡献和。怎么转移?这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿:f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……

我希望我这题说明白了.

(我怕我long long的位运算出锅于是打了快速幂……)

F. Mahmoud and Ehab and yet another xor task

留坑

BZOJ3083 遥远的国度

遥远的行星? 神奇的国度?

NO,遥远的国度.

这题真皮OVO

考虑换根之后只有两种情况答案会变

一是根与询问点重合 答案整棵树

二是在询问点的子树内,这时候需要……枚举子树树根!

然后用dfs序来判断,这玩意是连续的(嗯……?),而且在每个子树内也是连续的(!)

锁定在哪颗子树内!

然后你抓着这个子树的根节点把它拎起来,这整棵树其余的部分就耷拉到下面了

然后你就会发现这时候实际是询问这个红色的部分

然后就行了。

画风奇怪??

 

BZOJ4196 | NOI2015 软件包管理器

呀,我又来骗访问了QAQ

其实就是刨的模板题,不过题面真tm长

 

BZOJ3158&3275 [双倍经验] Number|千钧一发

这俩是一个题。

拿「千钧一发」说吧,你会发现显然如果对于一个i,如果a_i是偶数的话,他一定满足条件2,反过来如果a_i是奇数的话,他一定满足条件1,很好证明,就不说了。

然后你会发现这样一件事情:二分图

我们考虑补集转化,求最少的必须不选的b_i们,这大概……就是一个最小割。

最小割。怎么建图?源点汇点分别连所有奇数/偶数,边权b_i,然后奇偶之间互相连边,边权\rm{INF}

为什么是\rm{INF}?

因为……呃……表示这条边一定不会被割掉,那我们假设他连接了u \; , \; v两个结点,你需要挑一个,把他和源点或者汇点的边割掉。也就意味着最小割增加了b_u或者b_v的权,也就是不选其中一个。

然后这样就形成了超级复杂的关系网络然后就瞎跑Dinic就可以过了

注意!邻接表要开很大,而且两个题范围不一样!

(但是奇怪的是范围较大的\rm{Number}却跑得快

 

BZOJ1016 | JSOI2008 最小生成树计数

题面不放

这是道好题 一开始还以为是\rm{Matrix Tree}定理,后来发现不是QAQ

其实暴搜可过

先一遍Kruskal,顺便把权值相等的边们分到一个块里面,随便怎么实现都行 记录一下每个块有多少边在MST中出现过

然后重置一下并查集,枚举块,每个块跑DFS选哪些边(注意连通性,如果这条边加入成环就不能选,这很显然qwq),答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等,证明?

开始时,每个点单独构成一个集合。

首先只考虑权值最小的边,将它们全部添加进图中,并去掉环,由于是全部尝试添加,那么只要是用这种权值的边能够连通的点,最终就一定能在一个集合中。

那么不管添加的是哪些边,最终形成的集合数都是一定的,且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢?我们将之间得到的集合每个集合都缩为一个点,那么权值第二小的边就变成了当前权值最小的边,也有上述的结论。

因此每个阶段,添加的边数都是相同的。我们以权值划分阶段,那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

 

点击图片跳转原题

 

 

 

 

 

哦,还有,这段代码BZOJ编译会CE,不知道为什么她就是不支持C++11   [摊手]