谁是鸽王 - 博客园_a56爆大奖在线娱乐

2019年2月14日

【题解】[APIO2009]会议中心

摘要：【题解】 " P3626 [APIO2009\]会议中心" 真的是一道好题！！！刷新了a56爆大奖在线娱乐对倍增浅显的认识。此题若没有第二份输出一个字典序的方案，就是一道$sort+$贪心，但是第二问使得a56爆大奖在线娱乐们要用另外的办法。考虑到题目的性质，贪心地想，假如a56爆大奖在线娱乐们已经选择了区间$i$，a56爆大奖在线娱乐们就可以~~盖将自其变者而观之阅读全文

posted @ 2019-02-14 16:44 谁是鸽王阅读(346) 评论(7) 推荐(0) 编辑

2019年2月13日

【题解】[P4178 Tree]

摘要：【题解】 " P4178 Tree" 一道点分治~~模板~~好题不知道是不是a56爆大奖在线娱乐见到的题目太少了，为什么这种题目都是暴力开值域的桶QAQ？？问点对，考虑点分治吧。直接用值域树状数组开下来，统计的时候直接往树状数组里面查询。记得每一层先把这一层的答案统计一下，统计的方法就是刚刚讲的在桶里查。问题是阅读全文

posted @ 2019-02-13 12:20 谁是鸽王阅读(150) 评论(0) 推荐(0) 编辑

【题解】扑克牌游戏

摘要：【题解】 "扑克牌游戏 " 假如a56爆大奖在线娱乐们知道一个答案，那么a56爆大奖在线娱乐们剩下的问题就是去检查这个答案是否合法。显然可以拿$m$做文章，假设a56爆大奖在线娱乐们最终可以得到$ans$组套牌，那么对于每张牌，如果它的数量比$ans$小，a56爆大奖在线娱乐们就需要拿$joker$补。多的就没关系了。很棒的思路，还有一个贪心做法，也很神仙。 "or 阅读全文

posted @ 2019-02-13 08:22 谁是鸽王阅读(167) 评论(0) 推荐(0) 编辑

【题解】quake

摘要：【题解】$quake$ 题目大意 a56爆大奖在线娱乐们共有报酬$f$元，一条边有它的价值$w_i$,有它的建造时间$t_i$。要求建一些边，生成一颗树。求最大的利润率。数据范围 $n\le 400$ $m\le10000$ $Solution$ 实际上$n,m$出到$\le 100000$应该也是没问题的。分数阅读全文

posted @ 2019-02-13 08:15 谁是鸽王阅读(186) 评论(0) 推荐(0) 编辑

【题解】cycle

摘要：【题解】cycle 题目描述给定一个无向图，求一个环，使得环内边权$\div$环内点数最大。数据范围 $n \le 5000$ $m\le 10000$ $Solution$ 考虑到a56爆大奖在线娱乐们可以对答案的式子变一下形， $\frac{\Sigma_{i\in V'} w_i}{|V'|}\le ans 阅读全文

posted @ 2019-02-13 08:09 谁是鸽王阅读(250) 评论(0) 推荐(0) 编辑

2019年2月10日

从不浪费——分治总结

摘要：从不浪费——分治总结充分利用题目的性质，充分利用已知的信息，就是分治降低时间复杂度的保证。序列上的纯粹分治例一 "CJOI2019矩阵级数" 考虑式子的含义，是不是$\Sigma^{n} A^i =\Sigma^{\frac{n}{2}}A^i+A^{\frac{n}{2}}\Sigma^{\ 阅读全文

posted @ 2019-02-10 20:30 谁是鸽王阅读(216) 评论(0) 推荐(0) 编辑

【题解】[CJOI2019]Cipher

该文被密码保护。阅读全文

posted @ 2019-02-10 17:44 谁是鸽王阅读(76) 评论(2) 推荐(1) 编辑

【题解】[CJOI2019Chebnear]

摘要：【题解】[CJOI2019Chebnear] 题目描述给定平面上有$n$个仇人，$(x,y) ,x,y \in R^+$ ，$n$个人都是仇人关系，而有仇人关系的一对人的切比雪夫距离若$\le k$则会发生“吵架”。可是，对于有些仇人$i$和$j$，先记为三元组$P(t,i,w)$,他们的的仇人关阅读全文

posted @ 2019-02-10 17:14 谁是鸽王阅读(260) 评论(6) 推荐(1) 编辑

2019年2月9日

智商的比拼——思维题思考指南

摘要：智商的比拼——思维题思考指南最近做了几道思维题，感觉思维题就是烧脑，而且费劲，而且做不出QAQ！！思维题可能分一下几个类别吧鲨壁结论题。神犇之于结论题，如鱼之于水。而a56爆大奖在线娱乐之于结论题，QAQ。 1. 数论大法好。有些题目直接数学建模找结论啊QAQ，就比如[Running]这道题，关键性的东西就是$ 阅读全文

posted @ 2019-02-09 22:46 谁是鸽王阅读(212) 评论(0) 推荐(0) 编辑

【总结】图论小总结【题解】P1330封锁阳关大学

摘要：【题解】【总结】 " P1330 封锁阳光大学" &&图论小总结这道题其实有一点点难度，不过a56爆大奖在线娱乐能经过思考做出来说明还是没有普及组$D1T1$难度的。考虑一条边的两边要有且仅有一个点被选中...这不就是染色吗？想到此，聪明的你一定就知道怎么做了。这题唯一的坑点就是不一定图是联通的，a56爆大奖在线娱乐要$for 阅读全文

posted @ 2019-02-09 22:04 谁是鸽王阅读(174) 评论(1) 推荐(0) 编辑

【题解】P1407国家集训队稳定婚姻

该文被密码保护。阅读全文

posted @ 2019-02-09 19:26 谁是鸽王阅读(53) 评论(0) 推荐(0) 编辑

【题解】P3258松鼠的新家

摘要：【题解】 " P3258 [JLOI2014\]松鼠的新家" 树链剖分板子题。总结一点容易写错的地方吧： `if(d[top[u]] using namespace std; define RP(t,a,b) for(register int t=(a),edd=(b);t=edd; t) def 阅读全文

posted @ 2019-02-09 18:38 谁是鸽王阅读(82) 评论(0) 推荐(0) 编辑

乱计乱划

该文被密码保护。阅读全文

posted @ 2019-02-09 11:23 谁是鸽王阅读(43) 评论(12) 推荐(0) 编辑

2019年2月8日

【题解】P3796【模板】AC自动机（加强版）

摘要：【题解】 " P3796 【模板】AC自动机（加强版）" 记录当前$cnt$是第几个"星"。记录第几个串是对应着第几个星。这里补充一点对于$AC$自动机的理解。可能一直有个问题a56爆大奖在线娱乐没有想明白，就是打标记的点只有一个，然而匹配时，假若一个分支包括了另一个不同的分支该怎么办。实际上，a56爆大奖在线娱乐们可以在匹配的时候阅读全文

posted @ 2019-02-08 22:41 谁是鸽王阅读(99) 评论(0) 推荐(0) 编辑

【模板】P3806点分治1

摘要：【模板】 " P3806 【模板】点分治1" 很好的一道模板题，很~~无脑~~经典。讲讲淀粉质吧，~~很营养~~，实际上，点分治是树上的分治算法。根据树的特性，树上两点的路径只有一下两种情况：路径经过根$( )$ 路径不经过根$( )$ 显然对于$( )$a56爆大奖在线娱乐们可以通过指定一个新的根使得$( )$ 阅读全文

posted @ 2019-02-08 16:50 谁是鸽王阅读(270) 评论(1) 推荐(0) 编辑

【题解】P2602[JZOI2010]数字计数

摘要：【题解】 " P2602 [ZJOI2010\]数字计数" 乍看此题，感觉直接从数字的位上面动手，感觉应该很容易。但是仔细看数据范围，发现如果不利用计数原理，肯定会超时，考虑数码出现的特征: $A000$到$A999$，四位数中的$A$总共出现了$999 0+1$次。假设$A$在第$k$位上，那么阅读全文

posted @ 2019-02-08 14:33 谁是鸽王阅读(138) 评论(1) 推荐(0) 编辑

2019年2月7日

【题解】P2444 病毒

摘要：【题解】 " P2444 [POI2000\]病毒" 一道$ac$自动机好题... 考虑危险的字符串是什么意思，就是在这个a56爆大奖在线娱乐串中有模式串的匹配，这样的匹配可以通过$ac$自动机完成。那么给定一个字符串如何判断是否有病毒，直接就是看ac自动机是否匹配成功。考虑“无限长的安全字符串”代表什么意思，阅读全文

posted @ 2019-02-07 19:46 谁是鸽王阅读(185) 评论(0) 推荐(0) 编辑

2019年2月5日

【题解】[P3557 POI2013]GRA-Tower Defense Game

摘要：【题解】 " P3557 [POI2013\]GRA Tower Defense Game" 这道题是真的\ 根据题目给的$k$,可以知道，a56爆大奖在线娱乐们随便放塔，只要不全放一起，一定是a56爆大奖在线娱乐合法的方案。直接枚举就好了，脑子都不用，时间复杂度$O(n)$ cpp include using namespace 阅读全文

posted @ 2019-02-05 21:43 谁是鸽王阅读(214) 评论(0) 推荐(0) 编辑

2019年2月3日

【学习笔记】拟阵

该文被密码保护。阅读全文

posted @ 2019-02-03 21:31 谁是鸽王阅读(3) 评论(0) 推荐(0) 编辑

【题解】DZY Loves Chinese

摘要：【题解】 "DZY Loves Chinese II" 不吐槽这题面了... 考虑如何维护图的连通性，如果把图的变成一颗的$dfs$生成树，那么如果把一个节点的父边和他接下来所有的返祖边删除，那么a56爆大奖在线娱乐们就可以确定图的连通性改变了。考虑如何快速维护这个东西。可以考虑这样对于每条非树边，给他一个随机阅读全文

posted @ 2019-02-03 20:11 谁是鸽王阅读(164) 评论(2) 推荐(0) 编辑

2019年2月2日

【题解】[Ghd]

摘要：【题解】 "Ghd" 一道概率非酋题？题目很有意思，要a56爆大奖在线娱乐们选出大于$\frac{n}{2}$个数字使得他们的最大公约数最大。那么a56爆大奖在线娱乐们若随便选择一个数字，他在答案的集合里的概率就大于$0.5$了。 a56爆大奖在线娱乐们若连续随机选择$10$次，那么a56爆大奖在线娱乐们答案判断失误的概率不就是$\frac{1}{2^{10}} i 阅读全文

posted @ 2019-02-02 20:40 谁是鸽王阅读(220) 评论(0) 推荐(0) 编辑

2019年1月31日

【题解】CF264B Good Sequences

摘要：【题解】 " CF264B Good Sequences" 具有很明显的无后效性。考虑$dp$。考虑初始条件，显然是$dp(0)=0$ 考虑转移，显然是$dp(t)=max(dp[k])+1$其中$gcd(data[t],data[k]) 1$ 这样的转移是$O(n^2)$的！显然超时。发现值阅读全文

posted @ 2019-01-31 14:25 谁是鸽王阅读(266) 评论(0) 推荐(0) 编辑

2019年1月30日

【题解】P3162CQOI2012组装

摘要：【题解】 "[CQOI2012\]组装" 考虑化为代数的形式，序列$\left[a_i \right]$a56爆大奖在线娱乐选取的$i$种类仓库的坐标。 $ans=\Sigma(a_i x)^2,( )$，展开: $ans=nx^2 2\Sigma a_ix+\Sigma a_i^2( )$ (\ \)是二次函数看阅读全文

posted @ 2019-01-30 18:20 谁是鸽王阅读(359) 评论(0) 推荐(0) 编辑

2019年1月29日

【题解】P2279消防局的设立

摘要：【题解】 " P2279 [HNOI2003\]消防局的设立" 又是一道贪心。随便指定一个点为根，可以知道在覆盖了一个节点的子树的情况下，消防站越高越好。那么a56爆大奖在线娱乐们就贪心吧。$trick$是按深度$push$到$queue$里，然后直接取出来判断、贪心。咕咕咕 cpp include includ 阅读全文

posted @ 2019-01-29 20:32 谁是鸽王阅读(171) 评论(0) 推荐(0) 编辑

【题解】 P5022旅行

摘要：【题解】 " P5022 旅行" 当给定你一颗树的时候，这题就是一道送分题，凉心啊！但是给定你一颗基环树呢？暴力断环直接跑。但是数据范围$n\le 1000$ 乱做就完事了。考场上这样想的，对于$m=n?$的情况，得出来的最佳方案一定没有经过一条树边。那么a56爆大奖在线娱乐们直接枚举那条边不能走，直接$O( 阅读全文

posted @ 2019-01-29 20:26 谁是鸽王阅读(278) 评论(0) 推荐(0) 编辑

【题解】 P5021赛道修建

摘要：【题解】 " P5021 赛道修建" ~~二分加贪心，轻松拿省一（a56爆大奖在线娱乐没有QAQ）~~ 题干有提示：输出格式：输出共一行，包含一个整数，a56爆大奖在线娱乐长度最小的赛道长度的最大值。注意到没，，还要多明显？那么a56爆大奖在线娱乐们考虑二分。直接二分答案，假设a56爆大奖在线娱乐们得到了二分答案$x$，a56爆大奖在线娱乐们就利用这个答案检查是否可行。考虑阅读全文

posted @ 2019-01-29 20:12 谁是鸽王阅读(226) 评论(2) 推荐(0) 编辑

【题解】P3129高低卡(白金)High Card Low Card

摘要：【题解】 " P3129 [USACO15DEC\]高低卡(白金)High Card Low Card (Platinum)" 考虑贪心。枚举在第几局改变规则，在改变规则之前，尽量出比它大的最小的牌，在改变规则之后，尽量出最大的比它小的牌。前面记录一个$f(x)$后面记录一个$g(x)$ 此时，你阅读全文

posted @ 2019-01-29 19:58 谁是鸽王阅读(275) 评论(0) 推荐(0) 编辑

【题解】P1156垃圾陷阱

摘要：【题解】 " P1156 垃圾陷阱" 乍看此题，a56爆大奖在线娱乐们感觉状态很多，很复杂。遇到这类型条件比较多的$dp$，a56爆大奖在线娱乐们不要首先考虑全部设出来，而是要看到这些状态的本质。而在这道题目中，时间和高度就是关键。考虑卡门吃掉垃圾：时间改变，高度不变。考虑卡门垫上垃圾：时间改变，高度改变。也就是说，垃圾变阅读全文

posted @ 2019-01-29 14:48 谁是鸽王阅读(205) 评论(0) 推荐(0) 编辑

【题解】P1613跑路

摘要：【题解】 " P1613 ~~鸽王~~跑路" 一道思维好题！考虑$2^k$的传递性。直接64遍$floyd$求所有$2^k$的路径，转移方程是 $dp(i,j,k)=[dp[i][t][k 1]$&&$dp[t][j]][k 1]$ 有了这个之后先$O(n^3)$预处理，然后根据这样的数组直接建边阅读全文

posted @ 2019-01-29 14:26 谁是鸽王阅读(143) 评论(0) 推荐(0) 编辑

【题解】P3939数颜色

摘要：【题解】 " P3939 数颜色" 不要数据结构和模板学傻了... 考虑到兔子们交换都是相邻的，说明任�a56爆大奖在线娱乐淮谓换恢换嵋�$O(1)$的变化。 a56爆大奖在线娱乐们开很多$vector$存没种兔子的下标就好了。到时候二分查找查询。复杂度$O(nlogn)$ cpp include include include i 阅读全文

posted @ 2019-01-29 11:43 谁是鸽王阅读(227) 评论(0) 推荐(0) 编辑

【题解】NOI2015软件包管理器

摘要：【题解】 " P2146 [NOI2015\]软件包管理器" 实际上就是树链剖分板子题。对于$install$操作，直接查询它到$0$节点有多少已经安装了的，再用总数减去它。对于$uninstall$操作，记录一个$dfs$序结束时间的$endseg[]$数组，直接把$\left[toseg_i 阅读全文

posted @ 2019-01-29 11:36 谁是鸽王阅读(192) 评论(0) 推荐(0) 编辑

【题解】 P1092虫食算

摘要：【题解】 " P1092 虫食算" 老题了，很经典。用到了一些搜索套路。可行性剪枝,劣者靠后,随机化,$etc......$ 搜索设�a56爆大奖在线娱乐埠苡屑记桑枰桓�$adjustment$参数可以很方便地在两个方程之间切换。调试递归最好在递归到下一层递归之前输出关键信息。阅读全文

posted @ 2019-01-29 11:28 谁是鸽王阅读(266) 评论(0) 推荐(0) 编辑

【题解】HNOI2013比赛

摘要：【题解】 " P3230 [HNOI2013\]比赛" 将得分的序列化成样例给的那种表格，发现一行和一列是同时确定的。这个表格之前是正方形的，后来长宽都减去一，还是正方形。问题形式是递归的。这就启示a56爆大奖在线娱乐们可以把这个正方形$hash$起来，直接搜索。平局和胜场可以很显然地算出来， $draws=\fr 阅读全文

posted @ 2019-01-29 11:21 谁是鸽王阅读(332) 评论(0) 推荐(0) 编辑

【题解】P4799[CEOI2015 Day2]世界冰球锦标赛

摘要：【题解】 " P4799 [CEOI2015 Day2\]世界冰球锦标赛" 发现买票顺序和答案无关，又发现$n\le40$，又发现从后面往前面买可以通过$M$来和从前面往后面买的方案进行联系。可以知道是双搜。从后往前搜索，$2^{\frac{n}{2}}$枚举记录到中间时剩下多少钱的方案，记为$h 阅读全文

posted @ 2019-01-29 11:04 谁是鸽王阅读(216) 评论(0) 推荐(0) 编辑

【题解】AT2043 AND Grid

摘要：【题解】 " AT2043 AND Grid" a56爆大奖在线娱乐们考虑直接构造两个互补的图切分别联通的图，然后原图有的大家都有就构造完成了。 cpp include include include include include include include include include include in 阅读全文

posted @ 2019-01-29 10:54 谁是鸽王阅读(232) 评论(0) 推荐(0) 编辑

【题解】CF45G Prime Problem

摘要：【题解】 " CF45G Prime Problem" 哥德巴赫板子题？ $\frac{n(n+1)}{2}$若是质数，则不需要分了。上式若是奇数，那么拆成2和另一个数。上式若是偶数吗，直接$O(n)$枚举。加上暴力判质数，复杂度$O(n\sqrt{n})$ 没写，蒯别人的吧 cpp // 阅读全文

posted @ 2019-01-29 10:45 谁是鸽王阅读(433) 评论(0) 推荐(0) 编辑

【题解】CF359B Permutation

摘要：【题解】 " CF359B Permutation" 求一个长度为$2n$的序列，满足$\Sigma |a_{2i} a_{2i 1}| |\Sigma a_{2i} a_{2i 1}|=2k$ 这种带绝对值的题目套路就是把绝对值拆开。看看$n=2$时候的情况 $\left[1,2,3,4\righ 阅读全文

posted @ 2019-01-29 10:33 谁是鸽王阅读(235) 评论(0) 推荐(0) 编辑

【题解】CF989C A Mist of Florescence

摘要：【题解】 " CF989C A Mist of Florescence" 题目大意：让你构造一个$n?m$矩阵，这个矩阵由4种字符填充构成，给定4个整数，即矩阵中每种字符构成的四联通块个数，$n,m$需要你自己定，但是不能超过50 发现a56爆大奖在线娱乐联通块至少有一个。考虑重复利用条件，a56爆大奖在线娱乐们直接构造一个$5 阅读全文

posted @ 2019-01-29 10:23 谁是鸽王阅读(221) 评论(0) 推荐(0) 编辑

【题解】P3599 Koishi Loves Construction

摘要：【题解】 " P3599 Koishi Loves Construction" $\mod n$ 考虑如何构造，发现$n$一定在第一位，不然不行。$n$一定是偶数或者是$1$，不然 $n|\frac{n(n+1)}{2}$则最后一项一定会和第一项相同。考虑让他们的前缀和变成这样子的数列$\left[ 阅读全文

posted @ 2019-01-29 10:18 谁是鸽王阅读(294) 评论(0) 推荐(0) 编辑

【题解】P5151 HKE与他的小朋友

摘要：【题解】P5151 HKE与他的小朋友实际上，位置的关系可以看做一组递推式，$f(a_i)=f(a_j),f(a_j)=f(a_t),etc...$那么a56爆大奖在线娱乐们可以压进一个矩阵里面。考虑到这个矩阵是$O(n^2logn)$的，a56爆大奖在线娱乐们观察a56爆大奖在线娱乐们单位矩阵的性质，发现每行的轮换的。那么a56爆大奖在线娱乐们愉快地只记录第一层阅读全文

posted @ 2019-01-29 09:53 谁是鸽王阅读(172) 评论(1) 推荐(0) 编辑

Winlere

去码头整点薯条
2018.6.2-2020.6.21 : NOIp/CSP/HNOI || 2020.7.16-2020.8.20 NOI-D || 2021.9-2022.11 ICPC/CCPC || 2022.12-今 S3L research intern || 2023.3 - 今 SC/ISC/ASC

公告

Winlere

去码头整点薯条 2018.6.2-2020.6.21 : NOIp/CSP/HNOI || 2020.7.16-2020.8.20 NOI-D || 2021.9-2022.11 ICPC/CCPC || 2022.12-今 S3L research intern || 2023.3 - 今 SC/ISC/ASC

公告

去码头整点薯条
2018.6.2-2020.6.21 : NOIp/CSP/HNOI || 2020.7.16-2020.8.20 NOI-D || 2021.9-2022.11 ICPC/CCPC || 2022.12-今 S3L research intern || 2023.3 - 今 SC/ISC/ASC