- 博客(34)
- 收藏
- 关注
RSS订阅转载 OI回忆录
写于NOI2018退役之后 thkkk yali很久以前就想记录一下自己的OI历程，退役后终于开工了。初中一直在学校培训奥数，对OI一无所知，甚至从没有听说过，初一初二的奥数还是可以的，到初三后就不是非常好了。高中进了雅礼后，每人都要报一门竞赛，我当然就报了数竞，搞了快一个学期，被组里的人吊着打，家长想让我退出，但当时自己就是想搞竞赛，不想只学文化课，于是想看看能不能转去别的竞赛...
2018-07-22 19:19:00
284
转载 NOI2018退役记
7月16日来雅礼洋湖报到后，自己没怎么搞颓，打了一些模板保持一下状态，考day1的前一天晚上做了一下三维偏序的模板题，居然因为一个傻B错误调了好久，直到周围的人都回寝只剩我一个人了才A掉。其实我退役也是与一直以来都有的一个毛病有关系的，那就是在写代码上太慢了，经常把一个简单的问题写的很复杂，而且还写的慢，写完后很大概率要调试很久，而我一直没有努力尝试去改变这个毛病。还有一个问题是dp有点...
2018-07-21 20:00:00
125
转载 uoj221【NOI2016】循环之美
前面部分比较简单，就是无脑化式子，简单点讲好了。首先肯定在\((x,y)=1\)时才考虑这个分数，要求纯循环的话，不妨猜猜结论，就是y必须和K互质。所以答案是\(\sum_{i=1}^n \sum_{j=1}^m [(i,j)=1] [(j,k)=1]\)。然后用 \([(i,j)=1]=\sum_{d|i,j} \mu(d)\)大力化一化，很快就会得到：\[\sum_{d=1}^...
2018-05-02 20:38:00
94
转载 uoj220【NOI2016】网格
刚了几个小时啊，这tm要是noi我怕不是直接滚粗了。我判答案为1的情况试了几种做法，最后终于想到了一个靠谱的做法，然后细节巨多，调了好久，刚拿到97分时代码有6.2KB了，后来发现有些东西好像没啥用就删到了5KB了，然后发现hack数据T掉了，就写了个哈希表换掉了map才过...真累对了，我最开始判1是先求的割点再判断，只不过我感觉好像没有必要求割点啊，直接判也是对的，就把那段删掉了，...
2018-05-02 15:31:00
105
转载 HNOI2018游记
day0没干啥事，下午去看了头号玩家，突然对闪灵及其他一些恐怖片产生了兴趣，可能这就是晚上睡的不是很好的原因2333。晚上本来准备打打模板，但是玩游戏去了，最后只打了打两三个模板，感觉很虚，万一考到了什么带花树，km就要GG了。day1有点紧张，拿到题目后仔细看了几遍题目才开始考虑做题顺序1->3->2，但是t1我好像想错了?思考两个小时后无果，打完暴力就走人了。看到t...
2018-04-17 15:11:00
103
转载 bzoj3142[HNOI2013]数列
五分钟就推完了...如果模数为质数还有一些简单的搞法，不是质数我好像只想到这一种简便一点的。枚举每天与前一天的差值，第一天有 n-差值之和 的取法：\[\sum_{x_1=1}^M \sum_{x_2=1}^M ... \sum_{x_{k-1}=1}^M (N-\sum_{i=1}^{k-1}x_i)\]\[ans=M^{k-1}*N-\sum_{x_1=1}^M \sum_{...
2018-04-05 12:03:00
87
转载 bzoj3576[HNOI2014]江南乐
首先整个局面的SG值等于各个独立子局面的SG值异或和，于是只要求SG(1~100000)了。考虑将一堆i个石头分成j堆时，它的后继状态是 {\((j-i \ mod\ j)\) 个 \((i/j)\)，\((i\ mod \ j)\) 个 \((i/j+1)\)}，这个后继状态的SG值同样等于这j个局面的SG异或和，于是要计算SG(i)就只需枚举将它分成j=1~i堆(j>i是没有...
2018-03-30 17:47:00
73
转载 bzoj3572[HNOI2014]世界树
只说一下大概做法吧，我这个做法好难写(或许有的地方是可以简便的做到的)，首先建虚树，把虚树上的"议事处"叫做黑点，其他点叫做白点。对于每个白点算出最近的黑点以及到它的距离(这个我是dfs一遍用线段树维护深度做的)，那么这个白点可以看做那个黑点了，只不过计算距离时要多加一个值，然后dfs一遍，对于虚树上的每条边都计算一下它对两个端点答案的贡献，具体的贡献是原树在这条链上所有的点及其子树。...
2018-03-29 10:27:00
74
转载 ZJOI2018游记
day0上午想了一个做法切掉了HNOI2016网络,居然拿了几个oj的rk1。下午登上了去衢州的高铁，高铁上一直在颓coc，进攻的太频繁了，金钱爆库了...晚上到了衢州饭店，环境还可以，发现居然和yyc住一个房间，太健美了。day1去衢州二中，听浙江大爷讲课，一脸懵逼，不知所措。发现这里的椅子蛮舒服的，于是就小憩了一下10点才开始听课，具体讲了什么忘的差不多了，反正一天下来估计只听...
2018-03-22 18:58:00
104
转载 bzoj4538[HNOI2016]网络
首先容易想到一个log^2的做法，就是这个答案是可以二分的，那么使用线段树套线段树，第一个线段树是权值线段树，第二个线段树记这些权值的路径在每个点的经过次数。那么询问就是在权值线段树上看右儿子的那个点是不是被右儿子的所有路径都覆盖到了，即那个点的经过次数等于右儿子的路径数，如果是那么就往左儿子走，否则往右儿子走。显然这个空间复杂度不能接受，而且效率令人堪忧，于是用整体二分加bit即可，...
2018-03-18 20:11:00
62
转载 bzoj4537[HNOI2016]最小公倍数
如果信息只有一维，就可以直接排序，扫一遍的过程中用并查集来维护，也就是u和v需要连通且连通块内的最大边权等于询问的边权。现在有两维，我一开始还往分治的方向去想，但是询问所需要的在每一层中的信息不好合并，于是就考虑分块。首先把边按a排序，分块，把询问挂在第一个a大于询问a的那条边所在的块上，然后每一块内的边，每一块上的询问按b排序。从左往右扫每个块，并把这个块左边的所有边都加入并查集中...
2018-03-17 22:09:00
113
转载 bzoj2658[ZJOI2012]小蓝的好友(mrx)
题目链接校内模拟赛出了这题，然后考试时写出了一个做法，评测机貌似有点慢被卡成90了，原题上可以A掉。首先可以知道\(O(n^2)\)的做法，就是只算全0的矩形个数，枚举下边界是哪一行，定义\(h\)值表示这个点向上碰到的第一个1的距离，然后可以从左到右枚举右边界，用单调栈维护以每个列作为左边界的矩形最大高度，那么以某一列作为右边界的对答案的贡献就是单调栈中的元素和。然后数据随机，可以...
2018-03-02 10:33:00
83
转载 uoj316【NOI2017】泳池
题目链接\(S=k\)可以拆成\(S\le k\)减去\(S\le k-1\)。用\((i,j)\)表示第i行第j列。设\(g(i,j)\)表示前i行前j列都安全其他未知满足条件的概率，\(h(i,j)\)表示前i行前j列是安全的但是\((i+1,j)\)是危险的，其他未知，满足条件的概率。当\(i*j>k\)时两个数组的值都是0。\(g(i,j)\)的转移可以在\(i+1\...
2018-02-25 20:25:00
71
转载 bzoj1925[SDOI2010]地精部落
题目链接\(f(i,j)\)表示长度为i，由1~i构成且结尾数字为j，结尾为'V'形状的序列方案数。\(g(i,j)\)表示长度为i，由1~i构成且结尾数字为j，结尾为'^'形状的序列方案数。转移比较明显，就是结尾选了j的话那么就把1 ~ j-1 及 j+1 ~ i 映射到 1 ~ i-1 ，根据形状判断上一位的大小转移。\[g(i,j)=\sum_{k>j}f(i-1,k...
2018-02-14 09:59:00
63
转载 uoj348【WC2018】州区划分
题目链接直接讲吨吨吨给的标准做法吧。记\(f(i,j)\)表示各个州(可以重叠)的城市数量之和为i，这些州的并集为j的方案数，反正若有两个州之间有交集最后的\(|j|\)会不等于\(i\)。有\(f(i,s)=\sum_{s1} \sum_{s2}[s1|s2==s] \ f(i-|s2|,s1)*can(s2) (\frac{vals(s2)}{vals(s)})^p\)\(f(...
2018-02-12 09:54:00
87
转载 uoj349【WC2018】即时战略
题目链接WC出了点意外滚粗了，来补补题。\(O(n^2)\)的时间复杂度，\(O(nlogn)\)的询问次数应该还是比较好想的，每次要打通到x的路径，对当前已知的树不断的找重心并询问在重心的哪颗子树中走过去。注意到有加点的操作，用紫荆花之恋的那种做法可以做到\(O(nlog^2n)\)，但我不会写...听wys讲课说可以用LCT，想了一下发现挺简单的就去用LCT写了这题。反正就是把1...
2018-02-11 09:30:00
81
转载 bzoj4816[SDOI2017]数字表格
题目链接以下除法均指除后下取整\[\prod_{i=1}^n \prod_{j=1}^mf(gcd(i,j))\\=\prod_{x}f(x)^{\sum_i \sum_j [gcd(i,j)=x] } \\=\prod_{x}f(x)^{ \sum_{x|d}\mu(\frac{d}{x})\frac{n}{d} \frac{m}{d} }\\=\prod_{d}(\p...
2018-01-28 16:38:00
77
转载 uoj131【NOI2015】品酒大会
题目链接很容易想到p和q"r相似"就等价于在后缀数组中q与p之间的height值\(\ge r\)，也就是说\(<r\)的那些height值会把排好序后的后缀分割成若干段，可以想到倒序枚举r，每当r减小1时，中间把他们分开的那些"屏障"就会减少一些，两边的集合会合并到一起，现在的问题就是给定一个集合，支持合并操作，每次询问元素乘积最大值（方案数显然是\(C_{siz}^2\)）。...
2018-01-24 14:30:00
90
转载 bzoj3595[Scoi2014]方伯伯的OJ
题目链接直接动态开点线段树，维护所有可能出现的位置\([-m,n+m]\)，并按排名排列元素，记个区间元素个数以及底层节点代表的编号，再搞个map记每个编号对应在线段树中出现的位置即可，跑的飞快，远超平衡树。#include<cstdio>#include<cstdlib>#include<cstring>#include<iostre...
2018-01-11 20:59:00
87
转载 LOJ2325「清华集训 2017」小Y和恐怖的奴隶主
题目链接首先dp很显然，\(f(i,s)\)表示到了第i轮，各种血量人数的情况为s今后的期望攻击boss次数。那么有\(f(i,s)=\frac{1}{num+1}*\sum_{s->s'}(f(i+1,s')+0/1)\)，num为奴隶主个数，当攻击boss时后面的贡献就是1，否则是0，s可以用一个m位k+1进制数来表示(代表血量为1,2,3的奴隶主个数)。然后处理出s的转移...
2018-01-07 19:19:00
95
转载 LOJ2324「清华集训 2017」小Y和二叉树
题目链接瞎jb贪一发就过了。首先度数<=2且编号最小的点一定是中序遍历最靠前的点，我们从这个点开始dfs一遍算出子树中度数<=2且编号最小的点记为\(f(i)\)，然后从这个点开始一步一步确定出它到根的路径。如果这个点度数还剩2(也就是除掉之前确定的左儿子后的度数)，那么选\(f(i)\)小的作为右儿子，如果度数剩1，那么比较\(f(i)\)与i谁更小，若\(i<=...
2018-01-06 17:36:00
106
转载 NOI2011阿狸的打字机
题目链接昨天晚上yy出了一个做法后，感觉...好难打啊...，于是先回去休息。今天来打时，还是感觉细节好多，于是就打了两个小时。打完过了编译后，居然过了样例，直接交，尼玛居然过了???......还好自己没有犯什么错误，不然就调死了...进入正题询问(x,y)时，就相当于在fail树中问x这个单词节点的子树中有多少个是y的前缀。先建AC自动机，显然暴力一个词一个词的插入是...
2017-12-07 17:14:00
48
转载 HNOI2008GT考试
题目链接考虑dp，f(i,j)表示做到了第i位(共n位)，当前的后缀串与A1~Aj相匹配 接下来的方案数。转移的话枚举一个k=0~9表示这位选什么，如果选了以后，匹配的位置会改变到 j' ，j'可以通过预处理A串的next数组（就是kmp里面的那个）然后不断向前跳得到，所以f(i,j) = ∑ f(i+1, j')。发现转移系数与i无关，因此可以用next数组处理出系数矩阵（长宽...
2017-12-06 21:13:00
47
转载 集训队互测2016Unknown(UOJ191)
题目链接前面部分和lzz的题解是一样的。首先将输入点(x,y)变为(-y,x)然后，只需找一个向量与(-y,x)的点积最大，即找一个向量在(-y,x)上的投影最长。此时所有的点都是在x轴上方的，容易发现答案一定是在凸包上的，再继续观察，如果有一个点在凸包而不在上凸包上，那么它的右上角及左上角一定有一个点，因此这个点一定不是最优的，所以答案一定在上凸包上，且可以在上凸包上二分。...
2017-11-25 18:38:00
162
转载 NOIP2017总结 & 题解
day1t1的结论貌似在哪见过，自己稍微验证了一下貌似没记错就没有管了。t2一道很好(keng)的模拟题啊t3自己做题好慢啊，想出来dp打上去最后几分钟才过了大样例，我写的是记忆化搜索，判-1很好判，没时间加上去了可惜了，不过还是自己做题太慢了。然后由于没拍，不确定自己dp对不对，就特判了k=0粘了一个暴力，没想到暴力错了，70变成50...基础不扎实gg100+100+50=250...
2017-11-21 21:45:00
146
转载 SDOI2017树点染色
题目链接发现1操作很像lct中的access，然后它每次染的又是一个新颜色，因此同一个颜色就在同一颗splay里了，且一个点到根的权值val[i]也就是到根路径上虚边的个数，然后看access时会对哪些点的val[i]产生影响。以下的原儿子表示原来与x在同一颗splay中的儿子 (注意不是splay中x的儿子，是原树中x的儿子，即splay中x的后继)。当x断开与它原儿子所在...
2017-11-20 21:58:00
87
转载 NOI2014魔法森林
题目链接把边按a从小到大排序，枚举一条边，相当于只考虑<=ai的边，根据b做一个最小生成树再算答案。用lct维护这个最小生成树，要加入的这条边若会形成环，则找到x到y路径上最大的b，与当前边比较看加还是不加(加就把那条边删掉)。维护边权可以把边看做一个点，点权为边权，并与原边的两个端点连边。#include<cstdio>#include<...
2017-11-18 11:37:00
164
转载 HNOI2017影魔
题目链接单调栈＆线段树离线处理询问，首先用单调栈预处理出左边第一个大于它的数head[i]及右边第一个大于它的数tail[i]，然后从左到右及从右到左各进行一遍下述操作：从右到左枚举一个点i，作为区间的左端点，然后对于i+1到tail[i]在线段树中全部加上p2,若tail[i]不等于n+1就把tail[i]加上p1-2*p2 (因为[i,tail[i]]这个区间是要加上p1...
2017-11-15 09:33:00
41
转载 CQOI2015任务查询系统
题目链接主席树。把区间的影响挂在左端点与右端点，建树时顺便对应的插入与删除。维护一段值域区间的和与数字个数，查询时要注意与第k大的数相同的数可能有很多。复杂度O(nlogn)#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream&g...
2017-11-09 21:48:00
65
转载 ZJOI2007报表统计
题目链接比较简单的一道平衡树题。第三个操作可以直接用map完成(加进去一个数只会让答案变小，于是与它的前面后面一个数做差更新答案即可)，只考虑前两个操作。·维护区间内的最大最小值，以及区间相邻两数最小差值。·对于insert x k ,相当于在x+1前插入k,再用一个树状数组维护原数组中的每个数在现在的数组中是第几个，这个操作相当于对 x+1 ~ n 的排名全部加了1。...
2017-11-09 21:35:00
99
转载 FJOI2007轮状病毒 行列式递推详细证明
题目链接题目给了你一个奇怪的图，让你求它的生成树个数。开始写了一个矩阵树：#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<vector>#include<algorithm>...
2017-10-12 19:14:00
89
转载 HNOI2017单旋
原题链接我的方法是用另外一颗splay(以原来输入的关键码作为关键字)维护原树节点深度信息，使得在操作时能在原树上快速定位与查询。为了方便，以下提到的splay都是维护信息的那颗splay，而不是用来模拟原来操作的那棵树。对于插入，直接在splay中insert，再看它的前驱与后继谁的左/右儿子是空的，记录dep=dep[..]+1对于单旋最小值m，发现在原树中m的右子树...
2017-10-11 11:00:00
99
转载 NOI2017整数
原题链接发现进位或退位时，会有连续的一段1变成0或连续的0变成1，然后在后面产生一个进位或退位。于是我们只需要一颗线段树支持区间赋值，查询左边第一个1/0，以及单点查询值。可以把a按二进制拆开去修改，复杂度是O(nlognloga)的，这样好像过不去。于是我的做法是在线段树的每个叶子节点存30位，用一个int保存，修改时就只需将a拆成跨过叶子节点的两部分，每部分直接加到对应的叶子...
2017-10-10 20:46:00
77
转载 NOI2017蚯蚓排队
原题链接发现 k<=50 ，在插入和删除时最多会影响不超过 k2 个串，用链表实现插入和删除,然后只需用哈希表维护每个长度不超过k的串的出现次数，哈希的话可以先用比较大的范围的值处理冲突，再映射到1e8的桶里统计。考虑复杂度。首先在删除时由于保证了 c<=1000 所以这部分复杂度是O(ck2)的。插入时，如果插入操作很慢只有可能是连接两个长度不小于k的串，而...
2017-10-10 20:25:00
132
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人