BerryKanry-CSDN博客

原创 NOIP2017 冬游记--浅谈划水一年欢乐爆0（实时更新）

11.104.10 pm划水一年还是终于等来了这个时候，GX信息学竞赛队伍浩浩荡荡的离开学校，去清水河坐上明天准备AK的王队长的小轿车，沾一下AK大佬之气

2017-11-10 16:10:14 1238 1

原创 POJ 3162 浅谈尺取法区间问题运用及多源树上路径统计

世界真的很大 NOIP近在咫尺，已是迫在眉睫之时今天却还是这么水做完一道上周的遗留问题这个尺取法为什么叫这个名字我也没搞懂看题先：description：一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最大距离和最小距离的差小于M，问怎么取使得天数最多？inp

2017-11-06 19:57:30 762

原创 HDU 2196 浅谈树上多源最长路动态规划求法

世界真的很大树上最长的路径==树的直径树的直径的求法应该都知道了，那对于树上的每个点，求出从他出发最远的路径这个当然可以每一个点DFS一遍得到，但是不如这个O（n）复杂度的算法来的优秀看题先：description：给出一棵树，求出对于每个点，他到树上理他最远的点的距离input：多组数据，到EOF 每组数据第一行一个整数n表示节点数接下来n-1行每行两个整数

2017-11-03 21:23:08 1035

原创浅谈n阶汉诺伊塔问题拓展动态规划求法

世界真的很大这不是一道题汉诺塔问题的基本思想应该还是了然于心了花了1个小时来思考汉诺塔问题的精髓，就是子结构的问题，用递归就很好解决了但是在柱子很多的情况下，有可能子结构多样化，再指定最大的分散是否还是最优呢来探讨一下这个神奇的印度玩意儿description：给定n，m求n个盘子m个柱子的汉诺塔问题答案input：两个整数n，moutput：答案先来谈谈

2017-11-03 17:58:54 1556

原创 BZOJ 2815 浅谈有向图必经点问题总结+拓扑序+倍增LCA灭绝树求法

世界真的很大昨天算是感觉到了真的有人这么无聊就是有这种人，也管不得了，还是收起心情才是必经点问题在考试中也算是出现过好几次了，之前都用了其他的蜜汁方法水过去，昨天终究还是用了什么灭绝树感觉还是要总结一下必经点这么一个东西了当然听说支配树是可以完全搞定所有问题的，不过常数较大罢了，这个就不讨论了看题先：description： http://www.lydsy.com/Judg

2017-11-03 07:57:17 1562 2

原创 leetcode：Integer to Roman 浅谈古罗马OI生活之数字的研究

世界真的很大算是一道大模拟模拟题有些时候直接按照题目的要求来写会很麻烦，但是稍微转化思路之后会很简单模拟题有时候也是有思维含量的，也是要小心注意才是description： T组数据，每组数据给出一个正整数，输出其在罗马数字下的表示方法input：第一行一个整数T，接下来T行每行一个整数output：输出T行，每行一个字符串表示答案首先什么是罗马数字呢？就是很多

2017-11-02 19:35:36 69290 2

原创 BZOJ 1951 浅谈猪王国古代文字及中国剩余定理合并半拓展LuCas

世界真的很大本来只是想找一道水题热热手，结果调了好久，听说大佬都是1A太强了前几天做了一道拓展Lucas以为这道题也是但是其实没有那么复杂如果是拓展Lucas那么mod数一般会给出，像这种直接告诉你的肯定有猫腻，仔细一分析就能发现看题先：description： “在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关

2017-11-01 19:54:59 569 1

原创 POJ 1463 浅谈简单树形动态规划及树上最小点覆盖

世界真的很大很多经典的图论问题放在树上就显得简单二分图的最小点覆盖这里就变成了一个简单的树形DP而已看题先：description：鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时候他无法快速找到解决方案，那么他很伤心。现在他有以下问题。他必须捍卫一座中世纪城市，其道路形成一棵树。他必须将最少数量的士兵放在节点上，以便他们可以观察所有的边缘。你可以帮助他吗？您的程序应

2017-11-01 16:44:16 1799 1

原创 HDU 1520 浅谈简单树形动态规划

世界真的很大趁着早上还没开始考试，悄咪咪地做一道树形DP input里面没读出是多组数据，WA了两发才发现orz 主要是感觉还是不是很熟悉，特别是对于树形这一方面地问题趁着NOIP之前赶紧地复习一下就从这道水题开始吧看题先：description：题目给出一棵树，每个节点都有其权值。如果选择了一个节点则不可以选择其父节点，问能取得的最大值input： Employees

2017-11-01 08:08:47 649

原创 BZOJ 2125 浅谈沙漠中的顽强植物仙人掌图TarJan点双连通构型改造LCA在线最短路

世界真的很大这是今天的第三题，真的是当时我反应过来是仙人掌的时候，大脑就闪过“沙漠中的顽强植物” 使用的方法很厉害，虽然可能比较超纲，但是的却算是学到了思路理清用不了多久但是调试的时候由于对于点双连通分量的不熟悉所以说用了比较久的时间今天一天怎么感觉又快莫名其妙的过去了啊 NOIP2017看题先：description：给一个N个点M条边的连通无向图，满足每条边最多属于一个

2017-10-31 22:00:24 596

原创 BZOJ 2142 浅谈LuCas EXtra拓展卢卡斯定理解合数组合式

世界真的很大今天考试的第一题，讲道理拓展Lucas算NOIP？还好学会了考试的时候一看，思路和解法都非常简单，简单到已经不是这道题的主要部分了，求几个组合数就完了，模拟了一下样例过了，很开心然后一看，嗯？mod怎么是一个合数呢？ EXLucas看题先：description：一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E

2017-10-31 16:03:35 977 1

原创 CodeVS 2245 浅谈二维线段树优化间距限制型LCS动态规划状态转移

世界真的很大终于算是学会了这个什么二维线段树了233 今天第二题考了这道题，讲道理当时DP方程已经到必须一个二维数据结构来维护的地步了当时整个人是蒙蔽的，这玩意儿我不会啊然后感觉大家都做出来了，就很慌，怀疑有没有什么别的解法，可能是自己想复杂之类的就想了很久，然后第三题的暴力转正解就没有去检查： BZOJ 2744 就炸说一句事后诸葛亮的话，这道题要是我当时会二维线段树岂不

2017-10-30 22:01:22 512

原创 BZOJ 2744 浅谈异或二进制分析及二分图最大团

世界真的很大今天考试的第三题发现了点性质但是时间复杂度分析不能过实在是没有什么思路了写了个暴力寄希望于评测机跑的快一点没想到居然是正解看题先：description：在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国

2017-10-30 19:12:28 717

原创 NOIP 2017.10.27 总结+心得

世界真的很大恭喜RNG 今天的考试要是再考炸真的要回家种田了幸好还将就但是于我自己来讲还是有诸多不足之处 3道题都还有提升的空间，但是总是无法抓住，还是太弱啊看题先：1：水题的典范一开始一看以为有什么性质，可能真的有吧，反正我没发现暴力构造b串，然后直接for去匹配匹配用hash就好 wa一个点以为是卡hash，其实是数组开小了233，WA？我的就是正解还有一种做法

2017-10-28 17:30:09 488

原创 BZOJ 4326 NOIP 2015 DAY2 T3 浅谈二分及树上差分数组DFS动态统计

世界真的很大今天正值全校运动会然而却被困机房想着写完这道题就下楼看运动会于是乎一A，老天luogu的“大凶”能奈我何？于是还剩一点时间，所以写一下博客看题先：description：公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司，该公司有很多个

2017-10-26 15:03:56 591

原创 BZOJ 1673 浅谈深度优先式搜索及斐波拉契启发式AstaR剪枝

世界真的很大 Astar刷的第三题都感觉不是很A*了但就是剪枝的思路有一点”基于未来状态“的，”启发式“的味道搜索在NOIP的考察还是比较多的，实在不行就爆搜，剪枝和优化都很优秀的话，说不定还能水过去几道题呢看题先：description：约翰有一架用来称牛的体重的天平．与之配套的是N(1≤N≤1000)个已知质量的砝码（所有砝码质量的数值都在31位二进制内）．每次称牛时，他都把某头

2017-10-26 12:07:00 545

原创 BZOJ 1085 浅谈迭代加深式法则及Astar启发式搜索路径诱导

世界真的很大 Astar的第二题，在Astar剪枝的同时使用了迭代加深的搜索方式将谈谈迭代加深搜索和Astar的估价函数在剪枝方面的应用听起来可能感觉不可做其实就是暴力+优化而已搜索题写起来还是很舒服的只是调起来就不是那么亲民了好在调的还算比较快看题先：description：　在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按

2017-10-25 21:43:14 564

原创 BZOJ 1598 浅谈AstaR启发式搜索有向图网络K阶最短路

世界真的很大今天考了字符串没看空限被86M卡空间唉，下次一定注意了草草地学了一下这个什么Astar算法，也不算是完全了解吧就找了这道题来做做 Astar好像听说在AI方面有很多运用，但是只是在竞赛中的话一般用做搜索的剪枝和顺序处理这道题体现的是后者看题先：description： BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后

2017-10-25 20:05:41 640

原创 NOIP 2017.10.24 总结+心得

世界真的很大今天的考试厄运缠身，orz 好端端的224变成了137，NOIP要真考成这样恐怕是要退役了一些小错误和细节处理的问题，实在是。。尽量通过模拟赛吧自己的问题测出来再即使修改免得NOIP真的面临退役的命运233看题先：1。讲道理NOIP DAY T1这个难度？反正我是不信其实不算太难，但是真的有点打脑子心路历程如下：是K的倍数？想到NOIP 2016 DAY

2017-10-24 22:04:18 1331

原创 BZOJ 4517 浅谈错位排列组合计数

世界真的很大讲道理本来5分钟的水题卡了我半个小时一直RE 原因竟是因为cout？改成printf就对了？？EXM？看题先：description：求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的满足条件的序列可能很多，序列数对 10

2017-10-23 21:51:07 698

原创 NOIP 2017.10.23 总结+心得

世界真的很大完了再这么考下去NOIP怕是要跪讲道理今天三道水题考了100分也是可以的第一题卡常卡了20分，第二题玄学错误只剩20分，本来想着前两道题稳了就没看第三题，补一会儿觉，结果第三题也是一道水题哎哎哎 AK这种flag果然不能乱立233 明天要好好调整状态了讲道理虽然题很水但是不可否认命题的质量还是很高，没有白做但感觉我可能考试时候真的白做了233看题先：1. 这

2017-10-23 20:30:19 482

原创 BZOJ 1853 浅谈等价类容斥原理+越界LONG LONG数位比较

世界真的很大这道题思路和原来的某道题等价：BZOJ 2393 但是在细节处理上有一点点不一样的地方，这样夸方位比较的方法有点扯但是值得一记看题先：description：在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[

2017-10-22 21:05:49 460

原创 BZOJ 2393 浅谈题目性质深度挖掘及容斥原理DFS写法

（助威TEAM WE) 世界真的很大容斥原理这种东西~~虽然只是刷了几道水题而已但感觉还是要总结一波数论的复习差不多就要结束了？希望不要耽误太多时间吧~还要留时间给DP的第二轮复习最后的容斥原理看题先：description： ~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~ 现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~ 但

2017-10-22 20:10:14 624

原创 BZOJ 2839 浅谈容斥原理组合计数及欧拉定理优化二维幂指数

世界真的很大前几天做了一道容斥原理的题，发现并不怎么会这类东西，赶快找几道题写写看了几篇题解不知所云果然还是不简单，按自己理解写了过后发现过不了样例发现还是考虑的不仔细，认真研究一波之后才马马虎虎地搞懂了一知半解看题先：description：一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为

2017-10-21 16:46:10 785 1

原创 NOIP 2017.10.20 总结+心得

（以此纪念S7死在8强的卫冕冠军）世界中的很大今天考试，数论的第二试怎么说呢，今天的预计最好得分应该是240，然而实际得分130 这当然是自己的问题，然而还剩下许多可以总结的地方，尤其是第一题，做不出来简直是自己害死的自己第三题也算是一个警醒了，多说无益看题先：1。当时考试的时候，一看这个函数，恩，欧拉函数求和直接就是n了，然后感觉可以抛开前面一坨，反正m只有10，最后快速幂乘

2017-10-20 20:07:31 507

原创 BZOJ 2982 浅谈组合数学Lucas定理

世界真的很大这道题是真的水看题先：description：求C(n,m) mod 10007 m,n∈[1,2*10^8]input：第一行一个整数t，表示有t组数据。(t<=200) 接下来t行每行两个整数n, m，如题意。output： T行，每行一个数，为C(n, m) mod 10007的答案。mod数小，n，m大 Lucas定理求解即可由于n的范围

2017-10-18 21:56:20 546

原创 BZOJ 2467 浅谈不看mod高斯消元惨痛教训及基环树生成树性质分析

世界真的很大讲道理看到这道题我就想到高斯消元看了一下复杂度OK之后直接一个Matrix Tree定理套上去码了一个小时过不了样例，才发现mod的是一个2007？不是素数？没有逆元？好像是有不用逆元的写法但我不会老老实实的想正解瞟了一眼题目性质之后还是比较简单、、看题先：description：有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在

2017-10-18 21:08:14 519

原创 BZOJ 2111 浅谈完全二叉树组合数递推半未来状态设计转移

世界真的很大略略的有点难懂的题目，想出来了还是比较简单完全二叉树的性质，很大一部分上决定了这道题的递推方法组合数能干嘛？还是有了一点点更加清楚的认知吧看题先：description：称一个1,2,…,N的排列P1,P2…,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，…N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值input：

2017-10-18 17:40:31 373

原创 BZOJ 1053 浅谈正统素数的侧面反素数A.N.T.

世界真的很大数的本质之类的东西，唯一分解定理除了通过一个数来分解得到素数的唯一分解，通过枚举素数来反推原数也是常用的做法。写的时候还是要注意细节，数论什么的一定要从数本身入手讲道理其实解法最后和数论没有什么关系也没有什么关系看题先：description：　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0i

2017-10-18 14:29:47 489

原创 NOIP2011 DAY2 T2 浅谈二分答案

世界真的很大今天晚上算是正式进入数论的复习范围了捡了几道NOIP的历年数论题来练手，除了高精度以外这道题一开始独体硬是没有读懂然后读懂了之后还算是比较简单233看题先：description：这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是： 1、给定 m 个区间[Li，Ri]； 2、选出一个参数 W；

2017-10-16 22:01:06 357

原创 HiHoCoder 1181 浅谈fleury算法求解无向图欧拉路径

世界真的很大欧拉路是一个老大难的问题，尽管性质什么的还是比较熟悉，但忽然想起来好像连求欧拉路的算法都不会哎。。。然后通过某大佬的blog知道了这道题，算是裸题了吧题面就非常有意思description：在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具，这些道具其实是一块一块骨牌。主角继续往前走，面前出现了一座石桥，石桥的尽头有一道火焰墙，似乎无法通

2017-10-16 19:30:30 455

原创 POJ 3040 浅谈矩阵快速幂优化LogN斐波拉契函数求解

世界真的很大讲道理矩阵这个东西还完全不怎么会怎么办？赶紧复习一波再找一道水题刷一刷矩阵优化线性函数求解曾经也听说过，但今天不知怎么奇困无比然后公式推起来巨慢但其实还是比较简单看题先：description：求斐波拉契数列第n项input： The input test file will contain multiple test cases. Each test cas

2017-10-15 19:58:05 334

原创 HDU 4738 浅谈无向图边双连通求TarJAn求桥及如何“炸桥”

世界真的很大这道题还算是比较裸的题了，但是坑点很多但是主体代码不难写，好在有高人提前指出了坑点，才没有调多久 tarjan敲的越来越熟练了233看题先：description：给一个无向图，求找出一条边，使得删除这条边以后整个图就不连通了，找出满足的边里权值最小的那个，找不到输出-1input： There are no more than 12 test cases.

2017-10-13 20:50:02 486 1

原创 BZOJ 1562 浅谈匈牙利算法性质挖掘以【变换序列】即最小字典序构成

世界真的很大匈牙利算法并不是一个有许多性质可以挖掘或者拓展的算法但是对于其思路还是必须要熟悉才行。邻接表的具体构建方式已经忘得差不多了，只是背的到算是都复习了一遍认真想起来其实也不是很难看题先：description： input： output : 要求选一种满足题意的“置换”，使得字典序最小不懂置换是什么的话就看这里：传送门所谓满足条件，就是说原先序

2017-10-13 19:50:05 483

原创 BZOJ 4808 浅谈精准卡时二分图最大独立集

世界真的很大这道题虽然并不是很难，但也算是卡了一下原先的不成熟二分图写法吧按照自己的理解建的双向边用了这么久的却没有什么问题，但是在这道题上却完美的T掉了。。无奈只得改成有二分图一侧向另一侧连单向边不幸啊。。。付阔达看题先：description：众所周知，马后炮是中国象棋中很厉害的一招必杀技。”马走日字”。本来，如果在要去的方向有别的棋子挡住（俗称”蹩马腿”），则不允

2017-10-13 15:05:43 421

原创 HDU 1150 浅谈二分图最小点覆盖水题

世界真的很大这道题基本上还是比较简单，怎么感觉最近老是在做水题。。不要在意，即使是水题也有可以总结的地方抱着这样的感觉来写博客。。但是感觉字数什么的会很少吧。。看题先：description：有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器B需要设置

2017-10-13 11:13:55 364

原创 POJ 1364 浅谈奇妙整数集合Z范围内超级源转化

世界真的很大本来这道题是一道大水题，但是有一个非常大的坑 WA了数次，高人指点一项确实如此，细想一会儿才有种恍然大悟的感觉差分约束不仅仅是模型转化的问题，建图时的细节问题也值得注意看题先：description：一次，在一个王国，有一个女王，那个女王正在期待一个婴儿。女王祈祷：“如果我的孩子是一个儿子，只有他是一个健全的国王”，9个月后，她的孩子出生，确实生下了一个漂亮的儿子。

2017-10-13 09:57:44 506

原创 LuoGu 1983 浅谈如何【车站分级】即数据架构调整加强线段树优化时空复杂度转换

世界真的很大这道题本来的原题基本上是一道做烂了的拓扑序水题但是数据如果加到1e5呢？虽说可以优化空间从nm到2*n，但是建边的时间nm是省不了的详细讲讲线段树对于区间赋值问题的利用看题先：description：一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：

2017-10-12 22:06:02 453 2

原创 BZOJ 4443 浅谈二分+二分图即四分图性质利用

世界真的很大作为二分图的一道经典题在做了这么多二分图之后还没有做过实在是太可惜了今天讲课提到了这道题知道怎么做但是没写过总觉得心慌然后1A，哼哼看题先：description：小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。input如：第一

2017-10-12 21:46:01 351

原创 POJ 1523 浅谈无向图TarJan连通块割顶分割技术

世界真的很大昨天晚上还有十分钟的时候开始写这道题，未果今天上午考试下午讲课晚上好不容易有时间来写这道题，成功犯了一个小小的错误不必深究 POJ的读入方式怎么这么恶心woc。。看题先：description：无向图求割点和去除割点后连通分量的个数input： The input will contain the description of several networks.

2017-10-12 20:32:26 516

空空如也

空空如也