- 博客(133)
- 收藏
- 关注
RSS订阅原创 让我来吐槽几句
现在只能在家里打比赛了，然后在家里看题解，不能到机房去听大佬讲课……这个感觉实在是……非常难受啊！在家里远没有在机房打比赛的感觉好，毕竟家总是温暖的，令人昏昏欲睡特别明显的一点就是，我现在连暴力都打不对了，一个很简单的暴力程序还需要大费周章地调试我曾经最擅长打暴力啊[泪奔]这直接导致每天的分数严重缩水QAQ令人窒息不过也算是暴露了一些问题吧取模运算时（包括加法和乘法）...
2018-08-27 21:40:17
373
原创 contest 0820 总结
contest 0820 总结BY THH学长碰巧做起了第一题，第二题骗了5分，第三题思路正确但是却又WA又T（线段树合并的时候出了巨锅）主要原因有以下几点：DP仍然是我的弱项思考+写代码的速度太慢，导致第三题没有对拍，于是就很惨烈还需要多练一些题，特别是DP，这回的四维DP+状压真是狠呐题解graphcalc...
2018-08-21 11:03:48
265
原创 contest 0820 graph [找规律]
contest 0820 graph [找规律]正难则反当时在这道题上面卡了好久，结果最后倒着来就秒过了…一个小的正方形经过系列旋转得到了大正方形，那么一个格子的黑白状态是一定确定了的。如果正着来找，我们会得到很多没有用的格子的信息；但是倒着来找（一个格子一定是由上一张图的某一个格子经过旋转得到的）就可以精确地找出该格子的黑白状态。所以这道题倒着DFS就可以了。代码...
2018-08-21 11:01:04
281
原创 contest 0820 calc [DP][记忆化搜索]
contest 0820 calc [DP][记忆化搜索]当时竟然不知道暴力怎么打，于是就只骗了5分 Q^Q50pts先把每种合法的边（端点编号差<=lim的边）放到一个数组里面，然后暴搜，最后判断选出来的边构成的图是否合法（每个点的度数都是偶数） 期望得分：40~50pts100pts状压DP我们强制规定边都有方向（从编号大的指向编号小的；也可以反着来）。...
2018-08-21 11:00:09
224
原创 Contest 0816 总结
Contest 0816 总结By THH学长做原创题的感觉就是不一样啊，每一题都是好题啊打比赛的时候怂了。看到第一题是方案数的问题就先溜了，表都没打啊。然后和难度第二的题杠上了，其它的题忘了打暴力，做了一个半小时才知道自己把题读错了[泪奔]，感谢好心的出题人下来给hint，不然就真的爆零了QAQ。第三题是看都没怎么看，谁知道良心的出题人搞了个全No和全Yes的答案啊！总之，打比赛...
2018-08-19 11:23:10
204
原创 contest 0816 quad [倍增][找规律]
contest 0816 quad [倍增][找规律]难得一遇的好题！满足什么条件的四条边才能构成四边形？最大的一条边权小于另三条边边权之和。30pts暴力可过直接暴力找出两个点之间的路径，把点权排序，看相邻的四个点的点权能否构成四边形时间复杂度O(q∗n)O(q∗n)O(q*n)50pts这单独的20分设置很蹊跷，点权不大于3是什么操作？我们会发现只有...
2018-08-19 11:19:34
188
原创 contest 0816 crow [DP][倍增]
contest 0816 crow [DP][倍增]我做了一个半小时才发现把题读错了QAQ感谢好心的出题人下来描述了一遍题意反正在树上往上跳的操作就用倍增我当初知道自己读错题之后意识模糊，啥也不知道了（最后比赛结束前半个小时以为比赛结束了，把代码放进压缩包准备上交时才发现大家根本没有躁动，然后才知道比赛还有半个小时……）还有，如果调试代码调试地意识模糊，最好重写一遍，这样多半就...
2018-08-18 07:54:53
201
原创 contest 0816 euler [找规律]
contest 0816 euler [找规律]出题人真是很良心啊，给了4组小样例让我们找规律，又给了一组大样例让我们验证答案。然而我还是成功地找错了规律。正解有一个结论：无向图的度数和一定是偶数，且奇数度的点的个数一定是偶数个。我们知道，如果一张无向图要构成欧拉回路，那么这张图上的每个点的度数都要是偶数度。结合之前搬出来的那个结论，可以得到另一个结论：一张无向图加上一个点，一定能...
2018-08-18 07:24:49
306
原创 NKOJ3102 取数 [堆][链表]
# NKOJ3102 取数 [堆][链表]题目传送门题解一种很巧妙的链表使用方法。首先考虑一种贪心的做法，把每个数放入大根堆，每次取最大的一个数（跳过与已取的数相邻的数）但这样的做法可能会有问题：如果最大的数比与它相邻两数的和要小，那么答案就可能不是最优的。比如一个数列里面全是类似于2 4 3的子数列，取2和3就比取4要优。所以我们需要设计一种改悔的方法，使得选择堆顶元...
2018-08-17 07:31:16
294
原创 #270 关灯 [DP]
#270 关灯 [DP]题目传送门题解倒着DP。这是道没有枚举上限的DP，所以倒着来应该是最好的。分析可得，倒数第iii个时刻，按下某一个灯最多能够影响到iii个灯。所以就可以以这个信息为关键转移。设f[i][s]f[i][s]f[i][s]表示倒数第iii个时刻，所有灯的开关状况为sss的方案是否可行。具体转移看代码。注意这里实际上并没有得到具体是哪个灯被操作了，...
2018-08-13 22:36:38
231
原创 #267 传送 [贪心]
#267 传送 [贪心]题目传送门题解比赛的时候写了个10分贪心，然后结束前改了一下代码…然后…就彻底0分了……身败名裂QAQ注意，题目里面有这样一句话：保证从任意城市出发，经过若干次传送，都能到达首都。我读掉了，然后码了一份复杂而错误的贪心[心情复杂]。做这题之前一定要把这句话先念三遍。这句话的意思就是，保证任意点之间都有一条路径。而且这是一张有n条边的图，除去从1出发的...
2018-08-13 14:14:11
174
原创 #261 萌新拆塔 [状压DP][三进制]
#261 萌新拆塔 [状压DP][三进制]题目传送门题解这道题真的很毒瘤啊（杜老师应该是只出毒瘤题的），当时看到这道题如此长的题面就直接挂机了[微笑]；而且我还真的以为这道题是“10k模拟+玄学剪枝”，所以根本没有往DP那里去想……可能这就是菜鸡的最高境界吧……如果没有模仿怪，那么这道题就应该是一个一维的二进制DP（不会存在什么时候吃宝石更优的问题），每一位表示这只怪兽是否被打...
2018-08-13 13:49:01
261
原创 附加赛 D [奇技淫巧]
附加赛 D [奇技淫巧]题解显然，第一二种询问是等价的，可以用前缀异或和解决。对于第三种询问，可以维护一个链表，一个数指向下一个与它相等的数的位置，并记下上一个与它相等的数的位置。询问排序后（左端点为第一关键字，右端点为第二关键字），使用树状数组处理询问，树状数组的下标是同学的编号。当删除一个数的时候，只需要把这个数指向的下一个位置加入树状数组。代码#inc...
2018-08-08 15:06:07
257
原创 Day1 A 数对子 [找规律]
Day1 A 数对子 [找规律]懒得粘题面了…..题解错解我最开始打了三个小时的表，发现了一件神奇的事情：[1,k][1,k][1,k]内的“好的”数对的数量是有规律可循的（这个规律极其复杂）！所以每个区间内的“好的”数对的数量就是A[ri]−A[li−1]A[ri]−A[li−1]A[r_i]-A[l_{i-1}]，然后我就愉快地切过此题啦！这当然是很naive的错解...
2018-08-08 13:29:25
359
原创 POJ1655 Balancing Act [DFS]
POJ1655 Balancing Act [DFS]题目描述题目传送门题解找树的重心，板题基本思路就是在DFS中枚举每一个点能否作为树的重心，并不断更新答案代码#include<cstdio>#include<iostream>#include<cstring>#define N 20100using nam...
2018-08-03 12:34:49
210
原创 BZOJ3670 [NOI2014]动物园 [KMP]
BZOJ3670 [NOI2014]动物园 [KMP]题目描述题目传送门题解这道题主要利用了Fail数组（本题中的next数组）的性质。 熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。” 设num[i]num[i]num[i]表示字符串的前iii位中前缀和后缀相等的字符串个数（没有“...
2018-08-01 20:37:23
196
原创 Travel [BFS]
Travel [BFS]话说这道题并没有找到提交的地方…就不写代码了[滑稽]题目描述给定一张n 个点的完全图，边都是无向的。一共有n(n−1)/2 条边，其中有m 条边的边权是a，剩下的边边权都是b。求1 到n 的最短路。数据范围2 ≤ n ≤ 100000; 0 ≤ m ≤ 500000题解一 初步分析这是一张完全图，也就是说任意两点之间必...
2018-08-01 20:04:45
385
原创 DP小结
DP小结DP本质就是状态压缩——只记录和答案有关的值。所以DP的解法大概就是： ①不断探索问题性质（数位DP体现得比较明显，如BZOJ1026 windy数，还有一道缺了题号的题） ②减少那些和答案有关的值的个数（比如要从题目中筛选信息来定出状态，列出方程）。 ——scαpe只是说说而已，DP并没有什么定式。一些方法这些方法说不定可以提供一些思...
2018-08-01 13:36:11
176
原创 BZOJ1799 [AHOI2009]self 同类分布 [数位DP]
BZOJ1799 [AHOI2009]self 同类分布 [数位DP]Description给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。Input两个正整数a,bOutput[a,b]中各位数字之和能整除原数的数的个数题解这道题就是状态不太好理解，其余的部分都比较温和f[i][j][k][1]f[i][j][k][1]f[i][...
2018-08-01 13:33:20
204
原创 SRM625 缺了名字的题目 [DP]
SRM625 缺了名字的题目 [DP]题目描述N 个座位的圆桌,K 个人去坐, 任意时刻联通块数量 <=G（人和桌子座位均有序）求方案数（两个方案数不同当且仅当有一个人的座位不同）数据范围N, K, G <=2000题解设f[i][j]f[i][j]f[i][j]表示前iii个人构成了jjj个联通块的方案数。方程（刷表法）：f[i+1][j+...
2018-08-01 08:03:07
336
1
原创 BZOJ4033 [HAOI2015]树上染色 [树形DP]
BZOJ4033 [HAOI2015]树上染色 [树形DP]Description有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。Input第一行两个整数N,K。接下来N-1行每行三个正整...
2018-07-31 22:20:48
229
原创 大佬云集的暑假集训 流水账
大佬云集的暑假集训 流水账先来挖个坑day1 ~ day2[吴瑾昭]省选级别数论、省选+级别动规等等东西噼里啪啦地打过来，而且新课快得像复习课，实在是…大佬的课day2： 例一：IOI2017 xxx……能搞懂多少算多少吧day3[吴瑾昭]5个小时的比赛，三道题…搜索乱搞，生成树乱搞，还算没有爆零感受到了“被小学生吊打”，“被初一大佬虐场”等等...
2018-07-31 22:10:23
301
原创 rand()原理
rand()原理参考这一篇博客和这一篇博客用rand()之前，要设置一个种子：srand(seed)，否则seed默认为1也可以srand(timd(NULL))，这样每次生成的伪随机数都不一样总的来说，系统的生成大概就是一个一次函数，然后加一个模数rand()=(a∗seed+b)%crand()=(a∗seed+b)%crand()=(a*seed+b) \% c，其中a,b,...
2018-07-31 10:17:21
2845
原创 #238 蔡老板分果子 [哈希 or DFS序]
暑期集训训练赛#1 A [哈希 or DFS序]题目描述春天来了，万物复苏，动物们又到了发情的季节。蔡老板终于下定决心砍下了自家后院的两棵果树，并决定和自己喜欢的人一起分享果树上的果子。这两棵果树一棵是长生果树另一棵是人参果树，两棵树上都有 nnn 个果子，编号为 1∼n1∼n1∼n，并分别由 n−1n−1n−1 段树枝连接起来。 为了把果子分成两份，蔡老板决定再两棵树上各砍一刀，...
2018-07-31 08:23:32
273
原创 BZOJ1026 [SCOI2009]windy数 [数位DP]
BZOJ1026 [SCOI2009]windy数 [数位DP]Descriptionwindy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？Input包含两个整数，A B。Output一个整数题解数位DP常用的思想是前缀思想。因此求...
2018-07-30 20:24:07
194
原创 NKOJ 密码 [暴力]
NKOJ 密码 [暴力]问题描述假发通过了不懈的努力，得到了将军家门锁的密码（一串小写英文字母）。但是假发被 十四和猩猩他们盯上了，所以假发需要把密码传递出去。因为假发不想十四他们发现几松门 前贴的小纸条就是将军家的密码，所以他加密了密码（新八：听起来有点诡异）。加密方法 如下：随机地，在密码中任意位置插入随机长度的小写字符串。 不过，假发相信银桑和他那么多年小学同学，一定能猜中密码是...
2018-07-28 08:09:12
420
原创 洛谷1983 车站分级 [拓扑排序][建图]
洛谷1983 车站分级 [拓扑排序][建图]题目描述一条单向的铁路线上，依次有编号为1,2,…,n1,2,…,n1, 2, …, n的nnn个火车站。每个火车站都有一个级别，最低为111级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站xxx，则始发站、终点站之间所有级别大于等于火车站xxx的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的...
2018-07-24 22:12:20
383
原创 BZOJ1087 [SCOI2005]互不侵犯King [递推][状态压缩]
BZOJ1087 [SCOI2005]互不侵犯King [递推][状态压缩]Description在N×NN×NN×N的棋盘里面放KKK个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。Input只有一行，包含两个数N，K （ 1 &amp;lt;=N &amp;lt;=9, 0 &amp;lt;= K &amp;lt;= N ...
2018-07-24 20:39:07
223
原创 BZOJ2794 [Poi2012]Cloakroom [离线][DP]
BZOJ2794 [Poi2012]Cloakroom [离线][DP]Description有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]Input第一行一个正整数n (n<=1,000)，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (c[i]<=1,000, 1<=a[i]Output输出q行，每...
2018-07-17 08:20:05
319
原创 BZOJ2287 [POJ Challenge]消失之物 [递推+递推]
BZOJ2287 [POJ Challenge]消失之物 [递推+递推]Descriptionftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” – 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <=...
2018-07-15 23:23:18
194
原创 我干了什么蠢事
我干了什么蠢事1.数组开小（看漏了一个0）2.输出调试信息3.文件名打错4.忽略题目条件（榴莲迷宫：二项式定理 20180711-2）
2018-07-13 21:16:16
258
原创 比赛 20180713 解题报告
比赛 20180713 解题报告pia打脸不知道怎么写才不算“找借口”A 分队问题我竟然输出了调试信息唉，救不了了B 子矩阵我先想出了一个方法，然后自信地写了出来，然而调试很久之后才发现是错的到这里时间还剩一个小时，所以我连暴力都没打最后两分钟惶恐地想起暴力还没打，也只好作罢C 数字对本来想去打个表，但是转念一想能打表的DFS也能解决，所以就...
2018-07-13 12:25:10
237
原创 20180710比赛 总结
20180710比赛 总结第一题做过，应老板要求交了份以前的代码第二题，最后半个小时才搞出来，因为忘记判环除了Tarjan缩点、DFS……还有拓扑排序啊！！！该打该打，忘记了上次在重大打比赛T了N次的教训第三题比较简单，比赛开始十分钟就搞定了。然而，朴素的SPFA会TLE，虽然在别的OJ上是A的…所以以后写SPFA判环要优化（SPFA的优化）所以，脑子里要多装一些技巧或者知识点整合...
2018-07-10 11:48:58
312
原创 SPFA的优化
SPFA的优化今天打比赛被朴素的SPFA判环卡了，超时丢了30= = 然而在bzoj上是AC的优化：Orange大佬：SLF和LLL优化递归优化（剪枝）递归优化就是把朴素的SPFA换成了DFS版（一般用于需要判环的情况）注意disdisdis数组要初始化代码#include<iostream>#include<cstdio>#...
2018-07-10 11:36:10
649
原创 2018暑期练习题1 B 雾雨魔理沙
2018暑期练习题1 B 雾雨魔理沙问题描述在幻想乡，雾雨魔理沙是住在魔法之森普通的黑魔法少女。话说最近魔理沙从香霖堂拿到了升级过后的的迷你八卦炉，她迫不及待地希望试试八卦炉的威力。在一个二维平面上有许多毛玉(一种飞行生物，可以视为点)，每个毛玉具有两个属性，分值value和倍率mul。八卦炉发射出的魔法炮是一条无限长的直线形区域，可以视为两条倾斜角为α的平行线之间的区域，平行线之间...
2018-07-09 20:17:21
306
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人