mayaohua2003-CSDN博客

原创 Goodbye，OI！

开始的开始，我们都是孩子最后的最后，渴望变成天使站在中科院计算所的玻璃门前，我静静等候着代晨昕。玻璃门不时拉开，来来往往的人们纷纷通过，可这扇门并不是为我敞开的。回头望去，外面的树木光秃秃的，街上没有喧哗的人声，只能听到偶尔传来的车声。距离最后一场比赛已经过了两天，在这时候我才终于意识到，我的OI生涯结束了。初识OI生在广州，我与许多有那么一点点聪明的小孩子一样，小学五年级就开始准备小升初了。作为家附近的好学校，二中自然成为了我妈的一个目标。但二中的招生方式与众不同，办了一个奇奇怪怪的信息班，.

2021-02-18 16:16:03 17827 18

原创 About Me

这里是一名juruo oier，有多弱，从他高一才注册这个博客就可以看出来了。他来自GD，欢迎来跟他交流OI内容，当然，也可以来交流本季新番，B站id黑色的与白色的一切。...

2018-12-09 21:22:43 2702 7

原创 Codeforces gym 102482 D

不妨最后再加上初始时的rrr个宝石。考虑某个人得到宝石个数的EGF，显然有F(x)=∑i≥0i!xii!=11−xF(x)=\sum_{i\geq 0}\frac{i!x^i}{i!}=\frac{1}{1-x}F(x)=∑i≥0i!i!xi=1−x1。那么总的分配数目为d![xd]Fn(x)=d!(n+d−1d)d![x^d]F^n(x)=d!\binom{n+d-1}{d}d![xd]Fn(x)=d!(dn+d−1)。这里为了方便，后面都除去d!d!d!。考虑组合意义，相当于每个人得到任意个

2020-12-25 23:18:40 560

原创 Codeforces gym 100531 E

不想再碰第二次的题目。首先我们需要对正则表达式建出对应的ϵ−NFA\epsilon-NFAϵ−NFA，这个就按正常的正则表达式解析就行。这里ϵ−NFA\epsilon-NFAϵ−NFA上的每条转移弧长度是000（ϵ\epsilonϵ）或111（字符）。不过我第一次写，出了一堆问题。这里的正则表达式允许空串，于是有可能出现连续的运算符。同时我按lrj书上介绍的方法把一些点合并了，然后WA爆了，不知道是我实现错了还是确实不可以，最后改成暴力做法才过。接着考虑怎么解决原问题。显然直接DP即可，令fi,jf_

2020-12-25 22:47:25 388

原创 Codeforces gym 101242 F

想了很久才会。这里实际上给出了一棵带权有根树，我们需要给每个点分配一个重儿子，使每个叶子得到一条链。令第iii条河流对应点到根深度为did_idi，显然它的答案为n−f(di)+1n-f(d_i)+1n−f(di)+1，其中f(di)f(d_i)f(di)为最多能分配出的长度≤di\leq d_i≤di的链数目。令S(i)S(i)S(i)为f(i)f(i)f(i)对应的某个方案中所选的≤i\leq i≤i的链的叶子集合。我们断言，对于∀j≥i\forall j\geq i∀j≥i，一定存在某个方

2020-12-25 22:34:31 317

原创 Codeforces gym 101173 L

不妨令所有变量以v1v^1v1为基准，相同为000，不同为111。那么考虑每个变量在另两组取值，可能是00,01,10,1100,01,10,1100,01,10,11。000000意味着在三组中都相同，可以用xi→!xix_i\to !x_ixi→!xi来限制。由于三组变量互相不完全相同，因此01,10,1101,10,1101,10,11中至少有两组出现。事实上，如果三组都出现了，显然无解，因为这时候令一组变量取值v∗v^*v∗在这三组中都取111，000000那组取000，那么任意选择(i,j

2020-12-25 22:10:21 208

原创 Codeforces gym 101239 G

被打爆了，看了claris的题解才会。考虑最终我们想要怎么样的结构：显然我们会从v2v_2v2开始，每ttt长度划一段（最后一段可能不满）。我们可以将模型转化为询问所有相邻两段的分界点，每个时刻可以询问若干个，使得询问时间形成一棵分治树，且对于每个分界点xxx，我们需要在它对应的速度到达lll之前或同时刻询问，否则之后我们会无法区分x−ϵx-\epsilonx−ϵ和x+tx+tx+t了。我们考虑枚举答案kkk。令rkr_krk表示到第kkk次询问我们还需要区分[v1,rk][v_1,r_k][v1

2020-12-25 22:00:58 218

原创 Codeforces gym 101221 A

这题wqy讲过，完全不懂。事实上，对于∀n≥3\forall n\geq 3∀n≥3，下面我们都可以给出一个nnn步的构造。这显然是一个下界：考虑定义一个局面的势能是iii和i+1i+1i+1都有箱子且种类不同的个数，初始局面势能是2n−12n-12n−1，最终局面势能是111，每次操作至多减少222的势能，因此至少要nnn步。如何构造呢？对于3≤n≤73\leq n\leq 73≤n≤7，我们都可以手构或搜索出一个nnn步的解。事实上，对于n=4∼7n=4\sim 7n=4∼7，有一个nnn步的解只

2020-12-25 21:48:10 225

原创 Codeforces gym 100269 I

比较恶心的搜索题。首先翻转操作至多用一次，且只有用和不用的区别，于是可以枚举是否使用。可以发现行和列的排列是无关的，且分别有646^464种。而数字的交换相当于允许任意排列，可以考虑最小表示法。这样一个算法就很明显了，我们直接对于每个数独，枚举它是否进行翻转操作，以及行和列的排列，最后求出得到的新数独的最小表示尝试匹配。但是这样复杂度有点高。由于操作是可逆的，容易发现可以用meet in middle来优化，对于一个数独我们枚举它是否进行翻转以及行的排列，得到一个中间状态，对于另一个数独我们枚举它做列

2020-12-25 21:36:32 178

原创 Codeforces gym 101173 B

先证明一个引理：在AAA中选一个点集SSS，BBB中选一个点集TTT，则V=S∪TV=S\cup TV=S∪T可被匹配覆盖，当且仅当SSS可被匹配覆盖且TTT可被匹配覆盖。必要性显然，充分性考虑找出一个覆盖SSS的匹配UUU，覆盖TTT的匹配VVV，则UUU与VVV的对称差一定是若干个偶环或链，容易调整成合法匹配。那么现在只需要对两边分别统计了。首先分别对两边的每个点集预处理出是否能被匹配覆盖。这可以利用Hall定理，预处理每个点集SSS的相邻点集N(S)N(S)N(S)，看∣N(S)∣≥S|N(S)|

2020-12-25 21:29:17 194

原创 Codeforces gym 101173 I

比较麻烦的DP。预处理出来transi,j,ktrans_{i,j,k}transi,j,k表示提示iii和jjj同向，接下来的序列会从iii的初始位置开始并匹配完iii，且jjj已经匹配了前k−1k-1k−1个是否会合法。然后考虑做一个DP，从左往右依次加入数字。令fst,lv,ld,rv,rdf_{st,lv,ld,rv,rd}fst,lv,ld,rv,rd表示现在已经确定了集合ststst中的提示；现在从右往左的下一个提示是lvlvlv，我们现在的序列匹配了lvlvlv的ldldld开始的后缀

2020-12-24 12:47:40 231

原创 Codeforces gym 101190 L

首先写一个DP。从小到大排列质数p1=2,p2=3,…p_1=2,p_2=3,\ldotsp1=2,p2=3,…。令fi,jf_{i,j}fi,j表示用≥pj\geq p_j≥pj的质数凑出总和iii的方案数，gi,jg_{i,j}gi,j为对应的长度和。那么可以发现101810^{18}1018对应的最大的总和kkk在200020002000左右，可以承受。然后可以类似数位DP的思路来输出答案了：我们枚举总和，然后由于总和相同按字典序排列，因此可以从小往大搜索，记录当前前缀对应的数位和，如果中

2020-12-24 12:37:17 164

原创 Codeforces gym 100851 H

由于对称性，我们可以假设任意一个′x′'x'′x′作为t=0t=0t=0对应的立方体，以及任意确定方向，并给它的顶点标上坐标。然后我们考虑从这个立方体开始逐渐确定其他的立方体代表的是哪个，这是容易做到的：我们如果已经确定了一个正方体顶点对应的坐标，那么考虑它的六个面，若某个面与另一个正方体相连，我们相当于知道了那个正方体其中四个顶点的坐标，另外四个是相对的，容易确定。如果确定的过程中发现冲突，也即两个正方体代表的相同，显然就无解了。时间复杂度为O(1)\mathcal O(1)O(1)。#includ

2020-12-24 12:31:23 154

原创 Codeforces gym 101471 J

很厉害的题目。首先发现vvv是没有意义的，我们可以将Flubber流量乘上vvv，最后除vav^ava即可。我们先算出只考虑Flubber的最大流量AAA，只考虑水的最大流量BBB，以及总的最大流量CCC，显然C≥max⁡(A,B)C\geq \max(A,B)C≥max(A,B)。那么我们可以发现一个性质：我们可以任意分配CCC给两种物质，只要满足分配给Flubber的W≤AW\leq AW≤A，分配给水的C−W≤BC-W\leq BC−W≤B即可。证明可以考虑最大流最小割定理：我们先加入一个超级源点

2020-12-24 12:25:15 205

原创 Codeforces gym 101612 H

问题相当于最大化最终树的最大匹配。考虑我们如果确定了一个加入连通块的顺序，使每个连通块的根节点指向之前连通块的某个节点。那么每次加入的新连通块如果原本的最大匹配必定包含根节点，显然加入后不会有额外的增量，随便找一个点作为父亲即可；否则如果之前连通块还有不在最大匹配中的节点（也即最大匹配不满），我们将它作为当前连通块根的父亲，可以有额外111的增量。那么现在算法就很明显了，我们显然会优先加入那些最大匹配必定包含根节点的连通块，然后加入那些没被匹配的点数>1>1>1的连通块，最后加入没被匹

2020-12-24 12:07:13 156

原创 Codeforces gym 100269 H

将每个串理解为它的k−k-k−前缀和k−k-k−后缀对应字符串（区分前后缀）之间的连边，我们可以得到一个二分图。原问题变为这个二分图的最小点覆盖。这是经典问题，直接dinic即可，最后我们选的点是残量网络中左部图与源点不连通和右部图中与源点连通的点。时间复杂度为O(nklog⁡k+n32)\mathcal O(nk\log k+n^{\frac{3}{2}})O(nklogk+n23)。#include <bits/stdc++.h>#define inf 0x3f3f3f3f#de

2020-12-24 11:58:56 185

原创 Codeforces gym 101630 K

首先可以注意到对于序列aia_iai，我们可以倒着贪心来线性求解，这也说明对于任意的s mod qs\bmod qsmodq，要么无解要么有唯一解。而对于序列整体乘一个gcd⁡(r,q)=1\gcd(r,q)=1gcd(r,q)=1的数字rrr，显然不改变解的存在性和唯一性。于是，我们说明了我们可以对序列整体乘一个rrr来求解。考虑取一个阈值BBB，对nnn按大小分别处理。对于n≤Bn\leq Bn≤B的情形，我们考虑直接解决这个背包问题。这里容易用折半搜索和哈希做到O(2n2)\mathcal O(

2020-12-24 11:54:26 151

原创 Codeforces gym 102511 J

可以发现只有1∼1091\sim 10^91∼109之间的lll是有用的。一个最暴力的想法是对每一个有用的lll，分别算出每名选手在此时的总得分，然后可以算出每名选手此时的排名并更新对应的答案，可惜lll的范围太大，这么做不太现实。不过我们可以换一个角度思考，我们只需要知道每名选手的最好排名，而排名的定义是分数不超过他的选手人数，那么我们可以尝试对于任意两名选手iii和jjj，算出在哪些时刻jjj的得分不超过iii的得分，这样也容易得到答案。事实上，下面我们将会证明，所有jjj得分不超过iii得分的时刻，

2020-12-24 11:37:58 178

原创 Codeforces gym 100851 B

首先我们需要观察一些二又十进制数字具有的性质：二又十进制数字的十进制表示下只有000和111，且最高位为111。二又十进制数字在十进制下的非空后缀去除前导零后一定为000或者二又十进制数字。(1)(1)(1)是显然的，而为了证明(2)(2)(2)，我们需要先考虑形式化判定一个数字是否为二又十进制的过程。令n=(c1c2⋯ck)10n=(c_1 c_2\cdots c_k)_{10}n=(c1c2⋯ck)10，那么nnn是二又十进制的当且仅当c1=1,ci∈0,1,∀1≤i≤kc_1=1,c

2020-12-24 11:08:49 173

原创 Codeforces gym 101190 C

仙人掌可以看作是在一棵树上加入若干个边不相交的简单环所得到的无向图。那么我们分别考虑构造树和简单环，再尝试将它们组合起来，最终得到构造仙人掌的算法。树的构造可以考虑以任意节点作为根节点，DFS递归构造每个节点的子树。要构造某个节点xxx的子树，首先我们依次递归xxx的每个儿子yyy的子树，再将yyy的子树与节点xxx合并到同个图，顺便加入xxx与yyy之间的边。若我们将节点xxx设为颜色111，节点yyy设为颜色222，xxx所在图中其它节点设为颜色333，即可通过对xxx所在图中颜色111和222之间点

2020-12-24 11:05:43 143

原创 Codeforces gym 101142 B

简单构造题。首先转化为有xxx个人左右都是男生，yyy个人左右都是女生。接着可以发现这相当于隔222个位置的人之间，有xxx组都是男生，yyy组都是女生。先考虑另一个问题：一个长为nnn的环，有xxx对相邻的人都是男生，yyy对相邻的人都是女生，问有解条件。显然需要满足x+y≤nx+y\leq nx+y≤n且与nnn奇偶性相同，且x+y=nx+y=nx+y=n的话当且仅当x=nx=nx=n或y=ny=ny=n时有解（全为男生或全为女生）。如果x+y≤n−2x+y\leq n-2x+y≤n−2且与nnn奇

2020-12-21 22:32:38 170

原创 Codeforces gym 101471 G

若当前模式非空，考虑包含它的n∗mn*mn∗m的最小矩形，则它的四条边上都有满单元格。那么经过一次操作后，往外扩一格得到的(n+2)∗(m+2)(n+2)*(m+2)(n+2)∗(m+2)的新矩形四条边上都至少有两个满单元格，改变至多一个格子的状态后，四条边上仍至少有一个满单元格。这说明一个n∗mn*mn∗m的模式，经过一次操作后至少会变成(n+2)∗(m+2)(n+2)*(m+2)(n+2)∗(m+2)的。考虑倒推，若现在的模式是n∗mn*mn∗m的，我们尝试找出上一次的（下面的做法说明了如果存在，这是

2020-12-21 22:22:58 170

原创 Codeforces gym 100269 C

考虑直接枚举所有不同的串AAA（显然是初始串的子串）。若我们预处理出任意两个后缀的LCP，对于一个固定的串AAA，我们容易在O(count(A))\mathcal O(count(A))O(count(A))的时间复杂度内判定是否有合法方案。注意到∑Acount(A)=O(n2)\sum_{A}count(A)=\mathcal O(n^2)∑Acount(A)=O(n2)，于是我们暴力枚举即可。时间复杂度为O(len2)\mathcal O(len^2)O(len2)。#include <b

2020-12-21 22:05:05 249 1

原创 IOI2021集训队作业

（即将）退役选手诈尸啦！今年的集训队作业来自于 21 场 ICPC 竞赛，所有竞赛均在 Codeforces 的 GYM 中可以找到（下面列表中结尾的数字代表其在 GYM 中的场次编号，例如 101221 对应 http://codeforces.com/gym/101221）。A 2014 ACM-ICPC World Finals，101221。B 2015 ACM-ICPC World Finals，101239。C 2016 ACM-ICPC World Finals，101242。D 2

2020-12-21 13:25:38 959

原创 UOJ 494

这是myy出的神仙题，我花了很多天时间才看懂题解。这份题解参考myy的官方题解和yhx的题解，大概算是后者的详细证明版本。我们接下来的定义都是在一个特殊的字典序意义下的，也就是一个串的前缀大于自身（也可以理解为给每个有限长字符串最后加一个U\tt{U}U，然后在通常字典序意义下比较）。另外我们定义两个字符串的严格<<<与严格>>>，字符串sss严格<t<t<t意味着存在位置i>0i>0i>0，使s[1…i−1]=t[1…i−1]s[1

2020-11-27 13:16:04 498

原创 Codeforces Round 1416 简要题解

A. k-Amazing Numbers略B. Make Them Equal略C. XOR Inverse略D. Graph and Queries处理仅含删边的图连通性问题，可以离线后倒着处理，转化为仅含加边的图连通性问题，可以简单地用并查集维护。不仅如此，我们还可以尝试对连通块的合并建出一个有根树森林，其中叶子节点是初始时的点，每次合并两个连通块新建一个点作为它们的共同父亲即可。这样，任意时刻某个连通块对应的点集对应某个子树，若我们只维护真实的节点，可以理解为dfs序上一段区间。这样问

2020-11-23 23:21:16 254

原创 Codeforces Round 1404 简要题解

A. Balanced Bitstring略B. Tree Tag略C. Fixed Point Removal先考虑对固定的数组aaa如何求解。显然如果某个初始的i<aii<a_ii<ai一定不可移除，否则我们为了移除它，需要某个时刻在[1,i−1][1,i-1][1,i−1]之间移除恰好i−aii-a_ii−ai个。那么我们从左到右扫描，记录当前可移除的最大个数sumsumsum，若i≥aii\geq a_ii≥ai且sum≥i−aisum\geq i-a_isum≥i

2020-11-22 14:51:26 235

原创 Codeforces Round 1396 简要题解

A. Multiples of Length略B. Stoned Game略C. Monster Invaders问题可以转化为从level 111开始，每次花费ddd的时间移动到一个相邻的level，然后对于level iii，我们有两种选择：第一种是花费pi=r1ai+r3p_i=r_1a_i+r_3pi=r1ai+r3时间，需要至少经过level iii一次；第二种是花费qi=min⁡(r1(ai+2),r1+r2)q_i=\min(r_1(a_i+2),r_1+r_2)qi=mi

2020-11-22 14:27:42 268

原创 Codeforces gym 102822 简要题解

博主诈尸啦！来更点cf题解。A. A Colorful Grid分类讨论鬼题。先考虑一下最后的网格图的连通性。我们考虑某一个连通块，如果存在某个连通块外的点与连通块内至少两个点相邻，或者至少两个连通块外的点与连通块内某个点相邻，那么连通块都能继续扩大。这样容易发现，最终可能的连通块一定要么是横着切成若干块，要么是竖着切成若干块，当然也可以是整个网格图完全连通。接下来我们的算法是枚举每一类情况，看看是否能构造出解，如果均不行就无解。如果整个网格图完全连通。不妨设n≤mn\leq mn≤m，若n≤2n\

2020-11-22 08:09:40 716

原创 NOI2020 游记

或许是一个不错的ending吧。不出意外的话，很快就能写上退役记了。从初二开始看大佬们的退役记，看着看着，我也上高三了。Day -?WC因为已经知道国家队无望，所以没写论文也没报营员交流。现在想来还是有点可惜，可能会成为OI生涯的遗憾吧。比赛日感觉三个题都有点无聊，写了前两题，T3没时间只交了暴力。看群友们人均AK，结果出分一看我全场第一，吓到了。晚上一看果然是数据错了，把只写了暴力的我送到第一。看起来CCF也不打算修数据，于是这场娱乐赛就这样结束了。报了ZR的十连测，也跟dcx一起报了牛客多校。

2020-08-22 23:19:08 3035 5

空空如也

空空如也