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

2020年5月21日

【题解】CJOI2019 Monument (扫描线+计算几何)

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

posted @ 2020-05-21 11:28 谁是鸽王阅读(0) 评论(0) 推荐(0) 编辑

2020年5月13日

0512考试题面+官方题解 (mark)

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

posted @ 2020-05-13 19:43 谁是鸽王阅读(3) 评论(0) 推荐(0) 编辑

2020年4月29日

【题解】AT2273 Addition and Subtraction Hard(DP)

摘要：【题解】AT2273 Addition and Subtraction Hard(DP) 一个数对答案最终的贡献是$+/ 1$，决定一个数的在最终答案里的贡献在于它在多少个$ (\dots)$之中。考虑一个$O(n^3)DP$，设$dp(i,j)$a56爆大奖在线娱乐确定$i$个数字前面的左括号，总共有$j$个" 阅读全文

posted @ 2020-04-29 19:23 谁是鸽王阅读(219) 评论(0) 推荐(0) 编辑

2020年4月27日

【题解】CJOI2020 密码(二分)

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

posted @ 2020-04-27 20:09 谁是鸽王阅读(5) 评论(0) 推荐(0) 编辑

【题解】Another Coin Weighing Puzzle (构造)

摘要：【题解】Another Coin Weighing Puzzle (构造) 或许，这就是 "神仙题" 吧你有$n$包硬币，每包硬币里面都恰好有$k$个硬币。有一包硬币是假的，且假的硬币比真硬币重，且同种硬币重量相同(是个实数)。你可以使用天平称硬币，使用天平的条件是两边有数量相等的硬币阅读全文

posted @ 2020-04-27 16:14 谁是鸽王阅读(1231) 评论(3) 推荐(1) 编辑

2020年4月20日

【题解】P3747 [六省联考2017]期末考试 (单位根反演)

摘要：【题解】P3747 [六省联考2017]组合数问题(单位根反演) 就是要a56爆大奖在线娱乐们求 $$ \sum_{i=0}^k {nk\choose ik+r} $$ 换一个形式 $$ =\sum_{i=0}^{nk} {nk\choose i} [k|i r] $$ 单位根反演带入 $$ ={1\over k}\ 阅读全文

posted @ 2020-04-20 17:34 谁是鸽王阅读(221) 评论(1) 推荐(0) 编辑

2020年4月19日

【题解】LOJ2462完美的集合(树DP 魔改Lucas)

摘要：【题解】LOJ2462完美的集合(树DP 魔改Lucas) 省选模拟考这个？？？？？？？？？？？？？？？？？？？题目大意: 有一棵树，a56爆大奖在线娱乐点有两个属性，一个是重量$w_i$一个是价值$v_i$。a56爆大奖在线娱乐们称一个点集$S$合法当且仅当该集合是一个联通块$\qquad (1)$ 该集合的所有点的重量和$\ 阅读全文

posted @ 2020-04-19 15:13 谁是鸽王阅读(358) 评论(1) 推荐(1) 编辑

2020年4月16日

人生感悟

摘要：不会的算法，肯定不会考阅读全文

posted @ 2020-04-16 20:17 谁是鸽王阅读(302) 评论(3) 推荐(0) 编辑

2020年4月15日

【题解】Heaps of Fun (概率论)

摘要：【题解】Heaps of Fun (概率论) 看完题解才发现讲题的时候讲的是什么屎，你说的分段是指分两段吗....... 简要题意: 给定你一棵树(不一定是二叉树)，a56爆大奖在线娱乐点有个随机点权，在$[0,a[u]]$均匀分布，问你这棵树满足堆性质(小根堆)的概率是多少？取值如果是整数可以直接DP，但是如果阅读全文

posted @ 2020-04-15 15:32 谁是鸽王阅读(421) 评论(0) 推荐(1) 编辑

【题解】TopCoder 11351 TheCowDivOne (单位根反演)

摘要：【题解】TopCoder 11351 TheCowDivOne (单位根反演) "传送门" 题目大意: 你有$n$头牛，编号$0\sim n 1$。问你从中选出$k$头牛，且选出牛的编号的和为$n$的倍数，问有多少方案，答案对1e9+7取模。$k\le n \le 10^9$ 这个可以用一个二元生成阅读全文

posted @ 2020-04-15 08:44 谁是鸽王阅读(390) 评论(0) 推荐(0) 编辑

2020年4月13日

【题解】P5904 [POI2014]HOT-Hotels (长链剖分)

摘要：【题解】P5904 [POI2014]HOT Hotels (长链剖分) https://www.luogu.com.cn/problem/P5904 题目大意是问一棵树上距离两两相等的三元组的数量观察到这样的三元组一定有一个交点。一个naive的想法是a56爆大奖在线娱乐们枚举这个交点，然后换根DP就行，分两种情阅读全文

posted @ 2020-04-13 16:56 谁是鸽王阅读(240) 评论(0) 推荐(0) 编辑

2020年4月2日

【题解】HNOI2017 简要题解

摘要：【题解】HNOI2017 简要题解 D1 ~~面对数据编程情况下 270~~ 单旋(树状数组) 发现每次splay的东西的都是最值。以最小值x伸展到根来举例，这也就意味着rotate的时候一直没得左子树，那么原树的改动是 $fa[x]$和$rs[1][x]$ 连边除了$rs[1][x]$中的点，其阅读全文

posted @ 2020-04-02 16:22 谁是鸽王阅读(222) 评论(1) 推荐(0) 编辑

2020年3月16日

【CJOI2020】Problem B. 回文问题(弦图)

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

posted @ 2020-03-16 22:44 谁是鸽王阅读(12) 评论(0) 推荐(0) 编辑

2020年3月9日

【题解】Bichromization(构造)

摘要：【题解】Bichromization(构造) "咕咕咕" 删边操作直接令其=1e9就好了，图的构造肯定先想想直接构造成树怎么做，a56爆大奖在线娱乐们直接令需要满足$D_i$的条件的那些最短路就=一条边。那么直接弄出一颗WB相间的森林即可，并且令父边=$D_i$。但是每棵树的根节点没有父边啊！仔细思考发现，找到一个阅读全文

posted @ 2020-03-09 21:30 谁是鸽王阅读(199) 评论(0) 推荐(0) 编辑

2020年3月7日

【题解】NOIO2020 冒泡排序(树状数组)

摘要：【题解】NOIO2020 冒泡排序(树状数组) 考虑在k次冒泡后的排列中的一个逆序对$ia_j$。因为这个$a_i$的存在，意味着$a_j$没有被往右边交换过(否则不会存在一个$a_i a_j$)。对于a56爆大奖在线娱乐没有被交换到右边的数，他前面总共有$k$个比他大的数被交换走了。记$ans[i]$a56爆大奖在线娱乐原序阅读全文

posted @ 2020-03-07 14:21 谁是鸽王阅读(267) 评论(0) 推荐(0) 编辑

2020年2月20日

【题解】bzoj4310跳蚤(SA)

摘要：【题解】bzoj4310跳蚤(SA) cao 还有二分字典序这种操作。。。。问题性质显然满足二分性，但是a56爆大奖在线娱乐们只能对数进行二分，但是如果可以根据一个数确定一个字符串就好了。用SA可以实现，根据一个整数x，可以在$O(\min (n,ans))$，得到字典序在所有子串中x位的那个串具体是什么。二分阅读全文

posted @ 2020-02-20 09:22 谁是鸽王阅读(160) 评论(0) 推荐(0) 编辑

2020年2月17日

【题解】NOI2017 蔬菜(贪心)

摘要：【题解】NOI2017 蔬菜(贪心) 考虑这样一个事实：假如你在很长的一段时间内卖了很多蔬菜，但其中只有$p$天你卖了菜。那么其实你在$p$天内也可以完成同样的操作。这是因为 1. 菜的收益不随时间而改变 2. 菜不存在体积的区别题目每天消失固定$x_i$蔬菜的限制可以看做a56爆大奖在线娱乐蔬菜有一个消失时阅读全文

posted @ 2020-02-17 10:34 谁是鸽王阅读(180) 评论(0) 推荐(0) 编辑

2020年2月16日

【题解】AGC007E Shik and Copying String(贪心)

摘要：【题解】AGC007E Shik and Copying String(贪心) 刚开始看完题以为是一个老鼠进洞模型，不过发现这里还要求不同种类的匹配不可香蕉，而且代价不是一定的... 追踪最终得到的串$T$a56爆大奖在线娱乐字符$T_i$的来源，可以发现是一条引向$p include include includ 阅读全文

posted @ 2020-02-16 00:15 谁是鸽王阅读(151) 评论(0) 推荐(0) 编辑

2020年2月15日

【题解】AGC027C ABland Yard (dfs+构造)

摘要：【题解】AGC027C ABland Yard (dfs+构造) 因为可以a56爆大奖在线娱乐出无限的串，a56爆大奖在线娱乐肯定在走环。考虑这个环的性质，在�a56爆大奖在线娱乐庖桓龅阌型愫筒煌阆嗔５庋母拍钐罅耍悸撬跣∫幌绿跫悸羌〉穆闾跫幕返奶卣鳌� 可以发现环构成的路径一定是AABB.AABB.......的形式，也就阅读全文

posted @ 2020-02-15 21:47 谁是鸽王阅读(206) 评论(0) 推荐(0) 编辑

2020年2月7日

【题解】CF739D Recover a functional graph(构造+二分图匹配)

摘要：【题解】CF739D Recover a functional graph(构造+二分图匹配) 题目大意一个图被称为F图当且仅当a56爆大奖在线娱乐点出度为1。可以发现这个图是一个内向基环森林，给出所有点到它能到达的环(只会有一个)的距离dis和那个环的长度len，然而有些点的信息模糊了，用？代替，可以是任何数。阅读全文

posted @ 2020-02-07 17:09 谁是鸽王阅读(322) 评论(0) 推荐(0) 编辑

【题解】gym102361E Escape(分层图)

摘要：【题解】gym102361E Escape(分层图) https://vjudge.net/problem/Gym 102361E 容易证明不会存在共用转换器的合法方案，因为出口互不相同且一旦共用转换器，要么以后走一样的路(这样就到最后两个机器人到了一个出口)，要么有一个机器人的路径是非法的(同理) 阅读全文

posted @ 2020-02-07 11:33 谁是鸽王阅读(296) 评论(0) 推荐(0) 编辑

2020年2月3日

【题解】CF616(Div 2)简要题解

摘要：【题解】CF616(Div 2)简要题解 A 分类讨论若数码和是奇数若最后一个数是奇数：找到从前往后第一个奇数数位删掉若最后一个数是偶数：不断删除最后一个数直到这个剩下的数是奇数，由于之前删掉的数都是偶数a56爆大奖在线娱乐对数码和$\mod 2$不会有影响。再做一遍第一个算法即可。若数码和是偶数若最后一阅读全文

posted @ 2020-02-03 01:41 谁是鸽王阅读(218) 评论(0) 推荐(0) 编辑

2020年1月30日

【题解】CodeChef - TREDEG (prufer+生成函数+多项式exp)

摘要：【题解】 "CodeChef TREDEG " (prufer+生成函数+多项式exp) 好毒瘤的数据范围... 先转prufer，现在问题就变成了a56爆大奖在线娱乐要生成一个$n 2$长度的序列，每a56爆大奖在线娱乐序列的权值定义为每种数的$\prod$(每种数出现个数+1)，可以直接使用指数型生成函数生成，具体的： $$ ( 阅读全文

posted @ 2020-01-30 21:45 谁是鸽王阅读(292) 评论(0) 推荐(0) 编辑

2020年1月29日

【题解】AT1984 Wide Swap(拓扑排序)

摘要：【题解】AT1984 Wide Swap(拓扑排序) 排列问题的一大套路是考虑arc数组(arc[data[t]]=t) 然后题目那个swap的性质，就转换为了对于arc数组相邻的值，若其差大于等于$k$则可以交换，否则不能。考虑arc数组上�a56爆大奖在线娱乐饬礁鍪�$x,y$(假设x的位置x$a56爆大奖在线娱乐$x$位置上的阅读全文

posted @ 2020-01-29 21:35 谁是鸽王阅读(200) 评论(0) 推荐(0) 编辑

【题解】CF917D Stranger Trees(prufer序列+二项式反演)

摘要：【题解】CF917D Stranger Trees(prufer序列+二项式反演) 考虑有一个东西叫做$prufer$序列，然后个东西叫做 "图联通方案数" 。然后a56爆大奖在线娱乐们考虑先算一下至少 $k$条边在方案里的方案数，a56爆大奖在线娱乐们可以用树形dp $dp(i,j,k)$a56爆大奖在线娱乐对于$i$节点及其子树，共有$j$条阅读全文

posted @ 2020-01-29 15:33 谁是鸽王阅读(370) 评论(0) 推荐(0) 编辑

2020年1月27日

【题解】UVA - 11255(Burside)

摘要：【题解】 "UVA 11255 " (Burside) OI生涯第一道Burside? 上次伦的火箭课件已经进行了扫盲，具体来说，定理内容是这样的: 从a56爆大奖在线娱乐浅薄的知识来看，Polya只是Burside的计数版本 Burside 设置换群$G$，以及一个可以被这个群作用的集合$S$，那么$G_S$的轨道阅读全文

posted @ 2020-01-27 12:01 谁是鸽王阅读(208) 评论(3) 推荐(0) 编辑

2020年1月16日

【题解】P3980 [NOI2008]志愿者招募(费用流求线性规划)

摘要：【题解】P3980 [NOI2008]志愿者招募(费用流求线性规划) 题意有$m$种志愿者以及$n$天，每种志愿者有固定的服务区间(天)，雇佣一个志愿者有不同的费用$c_i$。假设每种志愿者无限多，第$i$天至少要有$a[i]$个志愿者，问最小花费加入辅助变量$y_i$把问题化为$=a[i]$。阅读全文

posted @ 2020-01-16 21:50 谁是鸽王阅读(192) 评论(3) 推荐(0) 编辑

2020年1月11日

【题解】AT2064 Many Easy Problems(转换+NTT)

摘要：【题解】AT2064 Many Easy Problems(转换+NTT) 给定一棵树，请你回答$k\in[1,n]$由$k$个点生成出来的虚树(steiner)的所有方案的大小的和。对于这种分元素然后a56爆大奖在线娱乐元素对答案有一个相同的贡献的计数，一般都是考虑对于一个点考虑对于答案的贡献。对于一个确定的$ 阅读全文

posted @ 2020-01-11 21:28 谁是鸽王阅读(224) 评论(0) 推荐(0) 编辑

【题解】AT1983 BBQ Hard (格路)

摘要：【题解】AT1983 BBQ Hard (格路) 题目就是要求 $$ \sum_{i=1}^n \sum _{j i}^n {a_i+b_i+a_j+b_j \choose a_i+a_j} $$ 其中$n\le 2\times 10^5,a_i,b_i\in [1,2000]$ 这个式子有很强的组阅读全文

posted @ 2020-01-11 20:13 谁是鸽王阅读(212) 评论(0) 推荐(0) 编辑

2020年1月7日

【总结】不同卷积如何来搞

摘要：【总结】不同卷积如何来搞 md老子又tmd卷积构造错调一天，a56爆大奖在线娱乐来向smy && 高哥学习，总结一下不同的形式如何卷积等号和为定值从0到上界全遍历 $$ a_i=\sum_{j=0}^i b_j c_{i j} $$ 最简单的形式，也是最基础的形式 $j\in[l,r]\cap [0,i]$ 此阅读全文

posted @ 2020-01-07 22:56 谁是鸽王阅读(211) 评论(0) 推荐(0) 编辑

【题解】Gnutella Chessmaster(数据删除)

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

posted @ 2020-01-07 19:06 谁是鸽王阅读(42) 评论(0) 推荐(0) 编辑

2020年1月5日

【题解】天天爱仙人掌(数据删除)

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

posted @ 2020-01-05 14:16 谁是鸽王阅读(11) 评论(1) 推荐(0) 编辑

2020年1月3日

【瞎讲】 Cayley-Hamilton 常系数齐次线性递推式第n项的快速计算 (m=1e5,n=1e18)

摘要：【~~背诵~~瞎讲】 Cayley Hamilton 常系数齐次线性递推式第n项的快速计算 (m=1e5,n=1e18) 看CSP看到一题“线性递推式”，不会做，去问了问zsy怎么做，他并不想理a56爆大奖在线娱乐并丢给a56爆大奖在线娱乐以下方法： $$ \text{Cayley Hamilton} $$ ~~下文会根据CH定理证明阅读全文

posted @ 2020-01-03 16:58 谁是鸽王阅读(493) 评论(0) 推荐(0) 编辑

2020年1月2日

计算几何小结计算几何小结

摘要：计算几何小结计算几何是个好东西，写代码感觉在写LemonLime(不你没真正写过)，一层层堆叠起来，真(难)好(调)玩。占坑阅读全文

posted @ 2020-01-02 23:01 谁是鸽王阅读(162) 评论(0) 推荐(0) 编辑

2020年1月1日

【题解】P2521 [HAOI2011]防线修建(动态凸包)

摘要：【题解】P2521 [HAOI2011]防线修建(动态凸包) 凸包是易插入不好删除的东西，按照剧情a56爆大奖在线娱乐a56爆大奖在线娱乐们时光倒流然后问题就是维护凸包的周长，支持加入本来很简单，但是计算几何就是一些小地方经验不足容易WA和RE 然后代码注释里有一些经验阅读全文

posted @ 2020-01-01 15:29 谁是鸽王阅读(167) 评论(0) 推荐(0) 编辑

2019年12月31日

头文件

摘要： mark 阅读全文

posted @ 2019-12-31 09:42 谁是鸽王阅读(194) 评论(1) 推荐(0) 编辑

2019年12月30日

关于SAM和广义SAM

摘要：关于SAM和广义SAM 不是教程某些思考先记下来 SAM 终于学会了这个东西诶...... 一部分重要性质确定一个重要事情，S构造出的SAM的一个重要性质是当且仅当对于S的�a56爆大奖在线娱乐庖桓龊笞海梢源�1号节点走到终止状态。专业的名词叫做有限状态自动机。 trans\[st\]\[c\]a56爆大奖在线娱乐的是对于状阅读全文

posted @ 2019-12-30 23:02 谁是鸽王阅读(859) 评论(0) 推荐(1) 编辑

2019年12月29日

【简要题解】Hihocoder 重复旋律1-9简要题解

摘要：【简要题解】Hihocoder 重复旋律1 8简要题解 | 编号 | 名称标签 | 难度 | | : : | : | : : | | "1403" | "后缀数组一·重复旋律" | Lv.4 | | "1407" | "后缀数组二·重复旋律2" | Lv.4 | | "1415" | "后缀数组三· 阅读全文

posted @ 2019-12-29 11:41 谁是鸽王阅读(182) 评论(0) 推荐(0) 编辑

2019年12月27日

【题解】Uoj#30 Tourist(广义圆方树+树上全家桶)

摘要：【题解】Uoj 30 Tourist(广义圆方树+树上全家桶) 名字听起来很霸气其实算法很简单.... 仙人掌上的普通圆方树是普及题，但是广义圆方树虽然很直观但是有很多地方值得深思说一下算法的流程: 对于所有点强连通分量 (强联通，意味着要找极大的那个)，建立一个虚点$u$，然后把环内所有边断开阅读全文

posted @ 2019-12-27 20:21 谁是鸽王阅读(152) 评论(0) 推荐(0) 编辑

【题解】#6622. 「THUPC 2019」找树 / findtree(Matrix Tree+FWT)

摘要：【题解】 6622. 「THUPC 2019」找树 / findtree(Matrix Tree+FWT) 之前做这道题不理解，有一点走火入魔了，甚至想要一本近世代数来看，然后通过人类智慧思考后发现，这道理可以用~~打马后炮~~别的方式来理解。先放松一点条件，假如位运算只有a56爆大奖在线娱乐，定位某一颗生成树，阅读全文

posted @ 2019-12-27 11:56 谁是鸽王阅读(347) 评论(0) 推荐(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