- 博客(76)
- 收藏
- 关注
RSS订阅
原创 真的退役了（NOIP2018赛后总结）
OI退役总结这次是真的退役了orzAFO然后这次比赛总体表现没有预期的这么好但总归是退役了没有胜利的喜悦也罢，辛苦过后的释然倒是真的令人难忘的周五晚上到了宾馆，去学军报了个到（学军紫金港其实不是很大，但是他们有小超市！！！！而且还很大！！！还有小猫猫！！！！！）总体来说心态还是比较OK的。半夜老舅把他的HASEE送到，一台非常强的游戏本！如有神助！！！Day1非常的简单，前...
2018-11-13 15:30:48
899
1
原创 HGOI11.8集训题解
题解今天是暴力局嘛…第一题——玩具装箱——（toy）【题目描述】一些玩具从左开始依次装成若干箱，每个箱子只能装最多MMM个且编号连续的玩具。在某个箱子里装若干个玩具的费用计算方法：如果该箱子里最大的玩具为 aaa，最小的为 bbb，玩具个数为 sss，则费用为 K+s∗(a−b)K+s*(a-b)K+s∗(a−b)KKK是箱子本身的费用，所有箱子的费用都相等。求最小费用...
2018-11-08 15:47:50
336
原创 HGOI11.7集训题解
今天这个比赛还行…题目没有昨天的难orz好歹有分…第一题——俄罗斯方块（game）【题目描述】现在有一个无限行，C列的游戏平台，每一次下落的方块是下列的7个图形的一种：每个方块从无限高处下落，对于每一次方块落地，我们要求方块的每一部分都必须与地面（最底面或己落下的方块上表面）接触。给出每一列的初始高度和下落方块的形状，求出指定方块落地的方法总数。定义落地的方法总数为方块落地后，...
2018-11-07 13:57:09
354
原创 HGOI11.6集训题解
题解距离退役不到5天了，今天的比赛却基本爆零，完全想不出正确的算法，只能尽力骗分…还是不是很会考试，心态爆炸第一题——准备（a）【题目描述】给出一个长度为N的数组，要求进行任意次循环位移使得∑∣a[i]−i∣\sum|a[i] -i|∑∣a[i]−i∣ 最小。我真的在考试的时候想不出来QAQ大概就是从在循环的时候，每个点的值对答案的贡献都是1，然后在变成正负就只有一次的...
2018-11-06 19:29:36
260
原创 HGOI11.5集训题解
题解今天居然死在了大模拟上面orz我不是一个好的码农第一题——数独（sudoku）【题目描述】（题目太长，直接截图）这个实力考模拟，但是merge的题面我最后五分钟才看懂。字符串读入读错orz，实力爆零。就模拟吧，数组随便开就过了orz。考细心#include <bits/stdc++.h>using namespace std;void fff(...
2018-11-06 18:31:46
265
原创 HGOI11.4集训题解
题解又是做 NOI.AC 的题，题目质量还行，但估计不是原创的洛谷上面第一题找得到原题，只是改了题面而已第一题——地砖设计【题目描述】要求用正方形边长的颜色填满m∗nm*nm∗n的地图，相同颜色不能相邻，要求输出地图的字典序最小。颜色用ABCD等填满这个我以为是无脑贪心，结果有点小难度，贪心策略不正确。正确的贪心策略是从左往右一个个节点枚举，在枚举到当前节点的时候向右...
2018-11-04 18:07:40
170
原创 HGOI11.3集训题解
题解今天这个打 NOI.AC 的模拟题，打得我心里发毛，这个要是到联赛我不是爆零？题目质量蛮高的，官方给出的题解就比较的随意了（其实他给我markdown写好了233）第一题——排队【题目描述】给出长度为n的数列，以及目标中位数x，要求改变数列元素大小，使得最终数列中位数为x，修改1的代价为1，求修改代价和最小是多少这个水题就排个序，贪心修改就好了（这个不是显然？），然...
2018-11-03 16:08:17
160
原创 HGOI11.2集训题解
题解今天这个题其实都是乱搞的…但最后一道题暴力分没拿好（没过滤前导零），有点可惜LJ老师说得对，你可以不会很多算法，但你要会考试第一题——集合划分（partition）【题目描述】给定一个包含NNN个非负整数的集合AAA，请将AAA分成两个子集P,QP,QP,Q，使得P∩Q=∅P\cap Q=\varnothingP∩Q=∅，且gcd(∏Pi,∏Qi)gcd(\prod{P_i}...
2018-11-02 15:17:01
155
原创 HGOI11.1集训题解
题解我觉得我剩下的日子已经不多了，这一份题解很有写的意义。第一题——序列（sequence）【题目描述】小Z 有一个序列，定义f(x)为x 在十进制下的位数，特别地，求∑1≤i&lt;j≤nf(ai+aj)\sum_{1\leq i &lt;j\leq n}f(a_i+a_j)1≤i<j≤n∑f(ai+aj)其中n≤106,ai≤108n\leq10^...
2018-11-01 18:27:08
447
原创 浅谈DP优化
其实这个写起来是自己总结用的，当然如果能够帮助到你，那也是非常棒的一件事情DP其实在现在已经算是考烂掉的题目了，类型很多，题目很杂，但思想大概就是从已有结果当中选出当前阶段的结果了，本身是对于暴力枚举的最优性优化，利用记忆化减少了前置阶段的枚举。DP优化其实是在枚举前置状态上的一个更优解的选择从而减少枚举的转移对象。复杂度大概都是从O(n2)O(n^2)O(n2)优化到O(n)−O(nlo...
2018-10-30 15:58:03
1836
原创 浅谈乱搞+暴力
人生第一次浅谈算法。都看liuzibujian大佬日常浅谈第一次浅谈就写这些算法。其实都是应试上的技巧，所以在AC和正确算法这种事情这里就不会提及了暴力先说最基本的暴力。这个世界上只有两种算啊，暴力和优化暴力。最出名的优化暴力就是分块和莫队。分块思想其实最常用的就是一般的分块。当然还有整除分块，一个在静态情况下，如果需要修改其实也是可以支持的但确实比较麻烦orz整除分块这个事情...
2018-10-30 07:23:18
476
原创 HGOI10.28集训题解
题解今天这个题没一个正常的早上睡过头了，起来肝还痛着第一题——Jingle【题目描述】给出若干字符W/H/Q/E/S/T/X分别代表节拍大小1、1/2、1/4、1/8、1/16、1/32、1/64，用/分割为单元，求有多少个单位的节拍刚好为1。水题，不讲！#include <bits/stdc++.h>using namespace std;inlin...
2018-10-28 14:51:22
133
原创 HGOI10.27集训题解
题解今天差点爆零第一题——fht【题目描述】给出NNN和MMM，求出∑i=1N∑j=1M(NModi)∗(MModi)\sum_{i=1}^{N}\sum_{j=1}^{M} (N Mod i)\ast(M Mod i)i=1∑Nj=1∑M(NModi)∗(MModi)我们可以发现首先这个公式可以变形成(∑i=1NNModi)∗(∑j=1MMModj)(\sum_{i=1}^{...
2018-10-27 16:42:09
272
1
原创 HGOI10.25集训题解
题解我重回战场！第一题——列队(line)【题目描述】给出n,mn,mn,m，表示数的个数和条件数目。条件形式为三元组（A，B，C），表示B在A之后C个数（C可能为负数）要求求出满足条件的数列是否存在，若不存在输出impossible，否则输出最大数和最小数的最小差值。这个题和AT3882一样的题目意思，但是这个最大值最小值的差值让我只拿了5分orz正解是带权值并查集，...
2018-10-26 08:00:44
221
原创 NOIP2018初赛总结（退役之战）
纵使失败，身后也是一片光辉第一次认认真真的参加noip，也是最后的一次了。考完第一时间估分只有72。能否进入复赛全部看今年的机位和水军的素质了平心而论，今年的题在我做下来，确实要比往年的要难很多。往年的题一个小时就可以水过分数线，而今年的题做了一个多小时才第一遍做完（也有可能是心理影响）。但确实不像学军的人所说，分数线要80+这么高。选择题只有十五道题，其中四题信仰题，两题概率期望，...
2018-10-13 23:13:07
1610
2
原创 浅谈概率期望
这个可能是我OI退役之前的最后一篇博客了orz期望概率是我这辈子都做不对的题orz先定义一下一些期望概率的概念吧…基本事件ω(也称样本点)： 一次试验可能出现的每一个直接的结果。也就是随机试验不能够再分解的结果。如：E1有两个基本事件：E1 ={出现正面}， E2={出现反面}E2有六个基本事件： Ei ={出现 i 点}，i=1,2,3,4,5,6样本空间Ω：全体基...
2018-10-12 15:33:15
411
原创 历年NOIP提高组初赛选择解析（至2006年。未完结）
这又是一篇没有代码的题解这个题解不会根据一年年的来，而是根据题型来的。大家收好啊…orz题型1——数学题1.1集合计算1、（NOIP2004–T1-单选）设全集I=I=I={a,b,c,d,e,f,ga, b, c, d, e, f, ga,b,c,d,e,f,g}，集合A=A =A= {a,b,ca, b, ca,b,c}，B=B =B= {b,d,eb, d, eb,d,e}...
2018-10-08 20:45:33
1834
原创 HGOI-国庆七连测-day7-fina
题解终于最后一天了QAQ但还要赶作业来续命啊QAQ今天的题比较水orz第一题——小X的质数（prime）【题目描述】给出Q&amp;ThinSpace;(Q≤107)Q\,(Q\leq 10^7)Q(Q≤107)组询问[l,r](l,r≤107)[l,r](l,r\leq10^7)[l,r](l,r≤107)，求在区间内是质数或者是两个质数相乘的数的个数。大水题欧拉筛求...
2018-10-07 13:17:57
179
原创 HGOI-国庆七连测-day6
题解今天是沙雕题集合…第一题就要打150+但毫无营养，第三题一题更比四题强…蒟蒻实在是没有办法orz有生之年不要让我碰到那个出题人德州扑克真的沙雕第一题——德克萨斯扑克(texas)题目太长了orz，懒得概括…就是一个暴力模拟+注意细节+要耐心这个是我这辈子打的最刺激的第一题。#include <bits/stdc++.h>using names...
2018-10-06 16:02:05
236
原创 OIer的赛前小结
只是为了不让自己这么虚，也顺便总结一下考试经验看了前辈们的总结觉得…画风神奇orz初赛首先说明，初赛时间还是比较充裕的，一个小时左右一份卷子就可以干完，所以要多花时间检查。1、选择题1.5分一个，能拿就拿…不能拿就算了orz…猜一个…但考前还是要总结之前做过的卷子什么的，算法和编码是硬核，但是一些计算机基础还是要靠临时抱佛脚的orz2、问题求解这个选之又悬的题目…最多考的题型1....
2018-10-05 17:00:56
176
原创 HGOI-国庆七连测-day5
题解今天又是暴力的一天…天天都是暴力暴力…还能不能好好学oi了orz我又把暴力打崩了orz我还没有找到暴力的精髓第一题——马里奥（Mario）【题目描述】给出一个m∗nm*nm∗n的字符图，#表示浮岛，_表示半空，马里奥可以从相邻的浮岛自由移动，也可以用梯子爬到上下的浮岛上。给出传送门的位置，马里奥的初始位置是在图的左下角。求出梯子最少要多长。这个就是裸暴力嘛…就是...
2018-10-05 16:14:05
160
原创 HGOI-国庆七连测-day4
题解今天这个题和昨天的题目完全不是一个水平的吗…orz今天这个打第三题的时间昨天还在打第一题…就不能两天的题目匀一下么…第一题——吴翼的木棍(kusac)【题目描述】给出n条长度为1的木棍，可以在任意位置进行切割，要求木棍平均分配给m个人的情况下切的刀数最少。感谢dasxxx大佬提供算法思路。可以算出，每个人平均分到nm\frac{n}{m}mn的长度。可以把这些木棍...
2018-10-04 14:38:41
169
原创 HGOI-国庆七连测-day2
题解其实今天的题目不是很难…但是内存炸了第一题就爆零了orz第一题——八数码【题目描述】给出你两个九宫格包含数字0-8，每次操作能够将0进行上下左右某个方向上的交换，问最少多少次交换到目标的情况。达不到就输出-1。emmm其实是一道万年老题，当年学bfs的时候打过一次，关键在于去重，hash压缩之后进行bfs。但是我忘记开map了，而是本机测的时候开了一个9∗1089*...
2018-10-02 16:58:50
213
原创 HGOI-国庆七连测-day1
题解今天这个题可以说是很悬了，第一题花了两个小时，还只是交了个暴力orz，有点硬核…第一题——bread【题目描述】区间内n个无色积木进行m次染色，每次将[(i∗p+q)mod[(i*p+q)mod[(i∗p+q)mod n+1,(i∗q+p)modn + 1,(i*q+p)modn+1,(i∗q+p)mod n+1]n +1]n+1]区间内染上i，原有颜色会被覆盖，求最终颜色。...
2018-10-01 15:46:53
207
原创 NOIP历年提高组问题求解总结
这个是一个没有代码的题解开学之后就只有在机房里刷刷初赛题了（我不想提前退役qwq），但是有正当理由的弹(bu)性(zuo)作业和选修课当然是能翘就翘了，物理真的难qwq。讲一讲历年的初赛题的问题求解吧，写个题解给各位大佬看着玩…题面的话为了省去篇幅，各位都还是自己去百度一下吧。2004第一题是一道笨笨的容斥原理，画个韦恩图就可以做出来了，大家自己尝试一下就可以了。第二题其实是一...
2018-09-19 21:35:08
1019
原创 HGOI8.23集训题解
题解 今天是信心赛吗？第一题——方程式（equation）【题目描述】给出n次方程的系数，求出所有根（重根也要输出）。n≤7n≤7n\leq 7，根的大小1≤x≤201≤x≤201\leq x \leq20且为整数求根其实很简单，数据这么小，暴力就好了。主要问题是重根手打模拟大除法的系数。#include <iostream>...
2018-08-23 13:47:21
141
原创 HGOI8.22集训题解
题解 暴力骗分真奇妙第一题——函数返回值（fun）【题目描述】给出T个n，求出公式f(n)=∑lcm(i,j)==n1≤i≤j≤n1f(n)=∑1≤i≤j≤nlcm(i,j)==n1f(n)=\sum_{1\leq i \leq j \leq n}^{lcm(i,j)==n}1纯暴力，30分。可以通过规律发现，lcm(i,j)=ij/gcd(i,j)l...
2018-08-22 19:36:48
143
原创 HGOI8.20集训题解
题解 蛮难的今天，题面还有错，SDOI题。第一题——直径（diameter）【题目描述】求出给出带点权树上最长链满足链上gcd不等于1。题面刚开始错了，求的是链上两两不互质，那就只有O(n3)O(n3)O(n^3)暴力才能做…后来标答第一句就和题意不一样我…说一下标答，其实就是求树上直径的变形，加上了gcd的限制，枚举每一个质因数，然后将能将它的倍数的点都...
2018-08-21 20:32:46
149
原创 HGOI8.21集训题解
题解 以后第一题就出数学题我把出题人摁在地上打。第一题——（sum）（没中文）【题目描述】有T组数据，给出数y(y≤1018),py(y≤1018),py(y\leq10^{18}),p，求所有满足y|xy|xy|x且f(x)=yf(x)=yf(x)=y的所有数的和对p取模。其中f(x)f(x)f(x)是因数的个数。如果有无穷多个x则输出-1真的是，早上打...
2018-08-21 20:14:14
249
原创 HGOI8.17集训题解
题解 今天其实还行第一题——矩形涂色（table）【题目描述】水题，读入的时候，如果在边界上就只要两步，不然就要四步。#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <vec...
2018-08-17 18:22:34
148
原创 HGOI8.16集训题解
题解 日常爆零orz第一题——玛雅文字（mayan）【题目描述】解读玛雅文字向来不简单，因为单词中的字母顺序可以是任意排列的。今天，科研团队找到了你来解决一个简化过的问题——在给定的一段玛雅文字 S 中，求出给定的单词 T 出现了几次，并保证 S 和 T 均由大小写字母构成。限制1s 32M1≤|T|≤ 3000，|T|≤|S|≤ 3,000,000【inpu...
2018-08-16 15:51:03
280
原创 HGOI8.15集训题解
题解 不好意思，今天大凶（虽然洛谷上是小吉）第一题——吃蛋糕（cake）【题目描述】给出方程ax+by=cax+by=cax+by=c，求出非负解的个数（a,b,c≤1014a,b,c≤1014a,b,c\leq10^{14}）。这个一看就知道是欧几里得拓展求出一组解，然后求出x最小的非负解和y最小的非负解。假设ax+by=cax+by=cax+by=c的...
2018-08-15 18:13:26
315
原创 HGOI8.14集训题解
题解 又是一天爆零日orz 我已经尽力在概括题意啦..版权原因就不开放正式体面了！第一题——capacitor（今天没有中文的题干）【题目描述】给出一个分数，abab\frac{a}{b}，给若干次操作，每次操作只能将两个数变成c1+c2c1+c2c_1+c_2或者两个数变成11c1+1c211c1+1c2\frac{1}{\frac{1}{c_1}+\frac{...
2018-08-14 19:12:47
173
原创 HGOI8.13集训题解
题解 和杭二中搞了十几天..天天不会做..都是一群神仙在那里打架…我这个蒟蒻只能看看。今天和江苏常州打了一套比赛，觉得比较有难度。第一题——指引（guide）【题目描述】给出n个人和n个门的横纵坐标(x,y)，一扇门只能通过一个人，每个人只能走到他右上方（即横纵坐标都大于等于人的坐标），求至多有多少人可以进门。题目给定x和y都互不相同且0≤x,y≤2n0≤x,y≤2...
2018-08-13 18:47:01
171
原创 各类动态平衡树与可持续化数据结构（坑大，不急）
板子留着，有空补坑#include &amp;amp;amp;amp;amp;amp;amp;amp;lt;cstdio&amp;amp;amp;amp;amp;amp;amp;amp;gt;#include &amp;amp;amp;amp;amp;amp;amp;amp;lt;algorithm&amp;amp;amp;amp;amp;amp;amp;amp;gt;#include &amp;am
2018-08-10 18:48:23
441
原创 HGOI7.28集训题解
题解 省选模拟赛第三天orz。慢慢有点适应了呢…感觉省选就是打一把暴力…但暴力其实感觉还行。第一题——小象和老鼠（lemouse）题目描述S国的动物园是一个N*M的网格图，左上角的坐标是(1,1)，右下角的坐标是(N,M)。小象在动物园的左上角，它想回到右下角的家里去睡觉，但是动物园中有一些老鼠，而小象又很害怕老鼠。动物园里的老鼠是彼此互不相同的。小象的害怕值定义...
2018-07-28 19:36:59
462
1
原创 HGOI7.26集训题解
题解 今天第一天和二中的神仙在一起做题…但是本蒟蒻只能在电脑前看着北大神仙打架啊……人家AK我60……对OI丧失信心。 这是一套连lzw4896s都不怎么会的神仙题。第一题——第一题（diyiti）&lt;——你没有看错【 题目描述】给定两个01串，S,T(下标从0开始）。支持如下3种操作： 修改S第i位的字符，即0-&gt;1,1-&gt;0....
2018-07-26 19:01:38
537
原创 HGOI7.25集训题解
题解 讲道理，其实从算法的思路上来说，实现15年day2的题，在代码量上并没什么难度..但确实还是比较考验思维含量的orz。而我….日常沙雕。第一题——跳石头（stone）【题目描述】给出距离L，在0-L之间有n个点。先在删去m个点使得点之间（包括0和L）的最小距离差最大。ok，这是道一眼就知道的二分题。二分出一个答案，线性扫描区间内的点位置。如果两点...
2018-07-25 16:04:24
178
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人