3 mayaohua2003

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

GDOI2020 游记

最后一次省选了,这次在广大附中考试,不需要住酒店了。今年因为疫情,GD选择了加入联考,终于在退役前体验到了4.5h3题的省选,不用再码到手残了。Day -?考前两周左右,林老师开始准备模拟赛。模拟赛的题目基本都很老旧,算比较简单,于是AK了不少套。然而dcx连续AK十几套,每场2.5h写完走人,还是比不过。后面跟雅礼的同学联训,与强强lk也交流了一些,希望他今年能进省队吧。对于省选倒是没什么感觉。与去年不一样,没怎么担心自己不进的问题,只希望同学们能进。Day 0前几天都没怎么写题,打算最后一

2020-06-23 22:55:18

Codechef June Challenge 2020 简要题解

这次题目比较简单。The Tom and Jerry Game!略Operations on a Tuple略The Delicious Cake略Convenient Airports注意到答案的下界为2⋅max⁡(N−M−1,⌈d02⌉)2\cdot \max(N-M-1,\lceil \frac{d_0}{2}\rceil)2⋅max(N−M−1,⌈2d0​​⌉),其中d0d_0d0​为度数为000的点个数,下面给出一个能达到这个下界的构造。...

2020-06-19 09:14:24

Codeforces Round 1286 简要题解

A. Garland略B. Numbers on Tree略C2. Madhouse (Hard version)略D. LCC注意到如果存在相遇点对,第一次相遇的一定是相邻的点。那么考虑枚举所有的相邻点对和它们的初始方向,可以得到O(n)\mathcal O(n)O(n)组可能的第一次相遇时间。给它们排序后,只要对每一组算出恰好是该时间相遇的概率即可,差分一下变为给定O(n)\mathcal O(n)O(n)个时刻tit_iti​,算出前tit_iti​时刻都没有相遇的概率。对于一个固定

2020-06-14 20:49:15

Codeforces Round 1292 简要题解

A. NEKO’s Maze Game略B. Aroma’s Search略C. Xenon’s Attack on the Gangs略D. Chaotic V.vp的时候脑子抽了,不知道写了啥,最后也没过。令k=max⁡(ki)k=\max(k_i)k=max(ki​),考虑将1!∼k!1!\sim k!1!∼k!分解质因数,这里可以从小到大计算,每次在上次基础上分解最后一个数即可。将一个数xxx表示为每个质因子出现次数的集合(c1,c2,...,cm)(c_1,c_2,...,c_m)

2020-06-14 17:40:18

Codeforces Round 1290 简要题解

A. Mind Control略B. Irreducible Anagrams略C. Prefix Enlightenment略D. Coffee Varieties (hard version)vp的时候智障的算错了常数,写了一个操作次数2n2k\frac{2n^2}{k}k2n2​WA了,然后不想改了(虽然区别不大)。考虑分治,定义solve(l,r)返回一个l∼rl\sim rl∼r间的下标集合,使得[l,r][l,r][l,r]中每种不同权值恰好在这个下标集合中对应出现一次。令le

2020-06-14 15:25:49

Codeforces Round 1361 简要题解

A. Johnny and Contribution略B. Johnny and Grandmaster略C. Johnny and Megan’s Necklace略D. Johnny and James显然原点发出的各条射线上选择方案可以分别考虑。考虑对于某条射线上的mmm个点按到原点的距离考虑,距离分别为d1<d2<⋯<dmd_1<d_2<\cdots<d_md1​<d2​<⋯<dm​。注意到若第iii个点被选择且是射线上从远到近第

2020-06-14 09:12:59

Codeforces Round 1307 简要题解

A. Cow and Haybales略B. Cow and Friend略C. Cow and Message略D. Cow and Fields略E. Cow and Treats注意到两边牛吃的范围不能相交,并且因为不能跨越,所以两边分别不能选喜好相同的牛。然后可以发现一个方案合法当且仅当分界点两侧的牛忽略其他奶牛可以吃饱(因为可以按要吃的草距离从大到小的顺序安排牛去吃)。那么就很简单了。考虑枚举左侧牛吃到的最右的草iii,此时每种喜好的奶牛就独立了,可以分别做一个简单的贪心和计数

2020-05-31 22:49:19

Codeforces Round 1344 简要题解

A. Hilbert’s Hotel略B. Monopole Magnets略C. Quantifier Question略D. Résumé Review设f(i,x)f(i,x)f(i,x)(0≤x<ai0\leq x<a_i0≤x<ai​)表示bib_ibi​由xxx变为x+1x+1x+1答案的增量,那么有fi(x)=(x+1)(ai−(x+1)2)−x(ai−x2)=−3x2−4x+(a−1)f_i(x)=(x+1)(a_i-(x+1)^2)-x(a_i-x^2)=-

2020-05-26 16:00:01

Codeforces Round 1299 简要题解

A.Anu Has a Function略B.Aerodynamic略C.Water Balancevp的时候猜了一下结论,答案满足每个位置被操作恰好一次,那么显然就是对(i,∑j=1iaj)(i,\sum_{j=1}^{i}a_j)(i,∑j=1i​aj​)的下凸壳上相邻两个点间操作即可,建出下凸壳就做完了。vp完后看了一下题解的证明,挺有意思的。最小化aia_iai​的字典序等价于最小化pi=∑j=1iajp_i=\sum_{j=1}^{i}a_jpi​=∑j=1i​aj​的字典序。同样把

2020-05-26 10:53:46

Codechef May Challenge 2020 简要题解

这次赛时没打,赛后补了下题目,被最后一题打爆,特意学了一波相关姿势。Triple Sort略Chef and Bitwise Product略Sorting Vases显然MMM个交换的意义就是将位置划分为若干等价类。那么可以将最初的每个数iii写成(ui,vi)(u_i,v_i)(ui​,vi​)的形式,代表一开始在等价类uiu_iui​,最后要到等价类viv_ivi​。考虑将数字间的交换当做一条边,那么得到的每个弱连通分量需要满足每个等价类在uuu中出现次数等于在vvv中出现次数。并且对于

2020-05-21 12:45:01

[学习笔记]Tutte矩阵与FKT算法求平面图完美匹配数

第一篇学习笔记,之后可能会更更多这些中文资料比较匮乏,现存题目不多的算法相关的学习笔记。FKT算法很久之前就听说过了,选择看了下网上的中文资料,然后发现仅有的一两篇博客还没有证明,于是丢掉了。最近做codechef月赛遇到了Tutte矩阵求解最大匹配相关的内容,于是学习了一波证明。于是决定自己写一篇博客,详细介绍一下这个很有意思的东西,介绍的过程会按我个人的理解,可能讲的不是很严谨,轻喷。先介绍几个完美匹配相关的概念。对于图G=(V,E)G=(V,E)G=(V,E)(∣V∣=n|V|=n∣V∣=n为偶

2020-05-21 10:55:02

Codeforces Round 1320 简要题解

A. Journey Planning略B. Navigation System略C. World of Darkraft: Battle for Azathoth略D. Reachable Strings注意到操作是可逆的,于是可以考虑将两个串分别操作到终态,判断终态是否相同。显然如果′0′'0'′0′的个数不相同一定非法,否则考虑每次操作后,′0′'0'′0′的位置的奇偶性不变,...

2020-04-29 12:42:14

Codeforces Round 1340 简要题解

第一次听说因为有假题unrated了。。。A. Nastya and Strange Generator略B. Nastya and Scoreboard略C. Nastya and Unexpected Guest考虑一个分层图最短路的算法。先给did_idi​排序去重。令F[i][j]F[i][j]F[i][j]表示走到did_idi​,时间 mod  (g+r)=j\...

2020-04-29 10:36:17

Codeforces Round 1336 简要题解

发现好久没写题解了,补几场cf的题解。A. Linova and Kingdom略B. Xenia and Colorful Gems略C. Kaavi and Magic Spell略D. Yui and Mahjong Set吐了,辛辛苦苦推了一年依次问1∼n1\sim n1∼n的算法,结果交上去WA了,又分析了半天发现只有当n>5n>5n>5的时候才能保证正...

2020-04-28 23:35:26

Codeforces Round 1338 简要题解

A. Powered Addition略B. Edge Weight Assignment略C. Perfect Triples找找规律容易发现答案跟四进制相关。考虑将数字写成四进制,容易观察并归纳证明:所有匹配的(a,b,c)(a,b,c)(a,b,c)位数都相同,并且位数相同,最高位为111,222和333的数字分别会作为aaa,bbb和ccc出现,互相匹配,且aaa从小到大取遍所...

2020-04-17 23:00:19

Codechef April Challenge 2020 简要题解

这次的题目难度比较高,有一做的价值,不过照例没有challenge的题解。Strange Number略Squared Subsequences略Ready Bitwise略Perfect Power Divisors写下式子发现显然是个容斥,令F(i)F(i)F(i)表示∑i=2⌊Nk⌋(i⋅⌊Nik⌋)\sum_{i=2}^{\lfloor \sqrt[k] N \rfloor...

2020-04-17 21:55:17

Codeforces Round 1280 简要题解

A. Cut and Paste略B. Beingawesomeism略C. Jeremy Bearimy略D. Miss Punyverse令点iii的权值ci=wi−bic_i=w_i-b_ici​=wi​−bi​,则一个连通块有贡献当且仅当∑ci>0\sum c_i>0∑ci​>0。考虑一个显然的DP,设F[i][j][k]F[i][j][k]F[i][j]...

2020-04-08 22:22:02

Atcoder agc041简要题解

A - Table Tennis Training略B - Voting Judges略C - Domino Quality当N≤3N\leq 3N≤3时特判。经过一些构造,可以在N=4,5,6,7N=4,5,6,7N=4,5,6,7时都构造出每行每列恰有333个的方案,具体构造的方案可以看代码。注意到在NNN的一个每行每列恰有333个的方案右下方放一个N=4N=4N=4的方案,就可以...

2020-04-06 23:31:28

Codeforces Round 1329 简要题解

爆炸的一场,掉分掉傻了。A. Dreamoon Likes Coloring略B. Dreamoon Likes Sequences略C. Drazil Likes Heap被一个div1C题彻底打爆了。注意到我们对一个权值当前所在的点调用fff后,这个权值就被删去了。但是如果直接删去最大的2h−2g2^h-2^g2h−2g个权值,可能导致最后剩下的不是完全二叉树。换个角度,我们考...

2020-04-05 11:47:11

Atcoder agc040简要题解

补一下最近几场的agc。A - ><略B - Two Contests略C - Neither AB nor BA先考虑没有′C′'C'′C′的情况。注意到如果存在多对′AA′'AA'′AA′或′BB′'BB'′BB′且有解,随便消去一对都可以得到一组合法解。那么考虑将2k−12k-12k−1和2k2k2k分一组,如果相同直接消掉,易证有解当且仅当剩下的′AB′'AB'′A...

2020-04-03 11:53:37

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。