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

2019年7月17日

【题解】P4091 [HEOI2016/TJOI2016]求和

摘要：【题解】P4091 [HEOI2016/TJOI2016]求和 " P4091 [HEOI2016/TJOI2016\]求和" 可以知道$i,j$从$0$开始是可以的，因为这个时候等于$0$。这种题目都要从$0$开始或许比较好(Itst语) 然后就开始化式子吧原式= $$ \sum_{i=0}^{ 阅读全文

posted @ 2019-07-17 22:06 谁是鸽王阅读(199) 评论(0) 推荐(0) 编辑

【题解】康拓展开(养生题)

摘要：【题解】康拓展开(养生题) 养生养生 | 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 | | | | | | | | | | | | 528662 | " 167. 康托展开" | Accepted | 100 | 1129 ms | 阅读全文

posted @ 2019-07-17 08:37 谁是鸽王阅读(199) 评论(0) 推荐(0) 编辑

2019年7月16日

【总结】容斥原理与反演

摘要：【总结】容斥原理与反演这个是个好东西...实际上，容斥和反演没有什么区别。 [TOC] "【题解】CF997C Sky Full of Stars" "【题解】CF451E Devu and Flowers(容斥)" "【题解】CJOI2019 登峰造鸡境 (Prufer序列+斯特林数)" "【题阅读全文

posted @ 2019-07-16 17:12 谁是鸽王阅读(571) 评论(0) 推荐(0) 编辑

【题解】[NOI2019Route]（70分）

摘要：占坑做法是拆掉所有式子，拆完式子看一下，如果A=0，发现边被分为了终点走向n的边和不走向n的边。a56爆大奖在线娱乐边就有了新的边权，并且可以相加。然后通过网络流建模的套路建模使得满足时间的限制，然后由于有负边，a56爆大奖在线娱乐跑spfa，这里60分。然后还有两个点是一条链，送10分。先放代码，还没测，可能会爆零。交上去的阅读全文

posted @ 2019-07-16 15:19 谁是鸽王阅读(219) 评论(1) 推荐(0) 编辑

2019年7月15日

【题解】BZOJ5093图的价值(二项式+NTT)

摘要：【题解】BZOJ5093图的价值(二项式+NTT) 今天才做这道题，是a56爆大奖在线娱乐太弱了强烈吐槽c++这种垃圾语言tmd数组越界不re反倒去别的数组里搞事情a56爆大奖在线娱乐只想说QAQ 推了一张A4纸的式子考虑a56爆大奖在线娱乐点的度数，因为a56爆大奖在线娱乐点虽然有标号但是是等价的，对于a56爆大奖在线娱乐点，对于答案的贡献是$x$，答案输出$n\times 阅读全文

posted @ 2019-07-15 17:44 谁是鸽王阅读(250) 评论(0) 推荐(0) 编辑

2019年7月14日

【题解】P5462 X龙珠

摘要：【题解】P5462 X龙珠赛题 B : " P5462 X龙珠" | 满分: 100分发一个set做法维护两个set，一个按照顺序排序，一个按照值排序。每次从大往小取，问题就变成了判断这个最大值后面是否有数，直接查看一下按照顺序排序的该数是否有后继。编译记得用 c++11 ，请安心食用。阅读全文

posted @ 2019-07-14 19:28 谁是鸽王阅读(236) 评论(0) 推荐(0) 编辑

【题解】[HAOI2018]染色(NTT+容斥/二项式反演)

摘要：【题解】[HAOI2018]染色(NTT+容斥/二项式反演) 可以直接写出式子： $$ f(x)={m \choose x}n!{(\dfrac 1 {(Sx)!})}^x(m x)^{n Sx}\dfrac 1 {(n Sx)!} $$ $f(x)$ 钦定有$x$种颜色出现了恰好$S$的方案然阅读全文

posted @ 2019-07-14 11:23 谁是鸽王阅读(303) 评论(0) 推荐(0) 编辑

2019年7月12日

多项式大合集

摘要：多项式大合集 NTT/FFT "传送门" cpp namespace poly{ const int maxn=1 1] 1|(t&1) 1; } const int mod=998244353; const int g=3; inline int ksm(const int&base,const 阅读全文

posted @ 2019-07-12 11:55 谁是鸽王阅读(276) 评论(0) 推荐(0) 编辑

2019年6月18日

【题解】Codeforces 961G Partitions

摘要：【题解】Codeforces 961G Partitions "cf961G" 好题啊哭了，但是如果没有不小心看了一下pdf后面一页的提示根本想不到题意已知$U=\{w_i\}$，求： $$ \sum _{S}\sum_{s\in S}|s|\sum_{w \in s} w， S是U的一个k划分阅读全文

posted @ 2019-06-18 21:08 谁是鸽王阅读(215) 评论(0) 推荐(0) 编辑

2019年6月13日

【题解】Counting D-sets(容斥+欧拉定理)

摘要：【题解】Counting D sets(容斥+欧拉定理) 没时间写先咕咕咕。 "vjCodeChef CNTDSETS " 就是容斥，只是难了一二三四五$\dots \inf$点题目大意：给定你一个$n$维空间，问你这个空间内有多少个点集满足两点间最大的切比雪夫距离为$d$。两个点集不同，当且仅阅读全文

posted @ 2019-06-13 17:49 谁是鸽王阅读(275) 评论(0) 推荐(0) 编辑

【题解】分特产(组合数+容斥)

摘要：【题解】分特产(组合数+容斥) 一道 "小水题。" 假如没有这个要求a56爆大奖在线娱乐人都要有一个特产的限制a56爆大奖在线娱乐们直接可以组合数。 a56爆大奖在线娱乐们又发现人(本质上)是没有区别的，a56爆大奖在线娱乐容斥的复杂度只有$O(n)$ $n$个人分$m$个特产，a56爆大奖在线娱乐特产有$a_i$个，人可以不拿特产，的方案数就是把$a_i$分成$n$份，而且可阅读全文

posted @ 2019-06-13 16:50 谁是鸽王阅读(242) 评论(0) 推荐(0) 编辑

【题解】P4247 [清华集训]序列操作(线段树修改DP)

摘要：【题解】P4247 [清华集训]序列操作(线段树修改DP) 一道神仙数据结构(DP)题。题目大意给定你一个序列，会区间加和区间变相反数，要你支持查询一段区间内�a56爆大奖在线娱乐庋≡�$c$个数乘起来的和。对19940417取膜。咋做 a56爆大奖在线娱乐们这一类题看来有一个套路就是用线段树维护一个DP数组，然后线段树节点合并就阅读全文

posted @ 2019-06-13 11:38 谁是鸽王阅读(240) 评论(0) 推荐(0) 编辑

2019年6月12日

【题解】没有上司的舞会

摘要：【题解】没有上司的舞会 "5401 没有上司的舞会" a56爆大奖在线娱乐是萌新刚学OI，请问这道树上DP怎么做？太难了不会啊看了题解才会的。 $dp(i,1/0)$a56爆大奖在线娱乐....算了太难了讲不清楚... 不会怎么DFS，只会常数内存都更小的BFS，球大神教a56爆大奖在线娱乐 cpp //@winlere include inc 阅读全文

posted @ 2019-06-12 16:10 谁是鸽王阅读(301) 评论(0) 推荐(0) 编辑

【题解】数字组合(NTT+组合滑稽)

摘要：【题解】数字组合(NTT+组合滑稽) 今天实践一下谢总讲的宰牛刀233，滑稽。 $(1+x)(1+x)(1+x)$的$x^2$系数就代表了有三个一快钱硬币构成的两块钱的方案数量。很好理解，毕竟拆括号这种东西本身就有组合意义。那么假设面值$i$有$a_i$个，那么最终的答案是 $$ G(x)=\ 阅读全文

posted @ 2019-06-12 14:40 谁是鸽王阅读(363) 评论(0) 推荐(0) 编辑

2019年6月10日

【瞎总结】组合模型及其组合意义的阐释

摘要： 13.5k 十分良心阅读全文

posted @ 2019-06-10 22:26 谁是鸽王阅读(1646) 评论(6) 推荐(4) 编辑

【公告】【公告】【公告】【公告】

摘要：公告关于博主的一些公告会放在这里 2019年06月10日16:40:55 由于博主连续被一道计数DP和一道数位DP搞到心态爆炸，博主决定弃坑DP，有什么锅不保证补。有效期至谢总讲数位DP。 2019年06月10日22:30:06 2019年07月29日11:49:32 博客进行了升级，添加了动态背阅读全文

posted @ 2019-06-10 16:44 谁是鸽王阅读(768) 评论(14) 推荐(1) 编辑

2019年6月9日

【题解】CF559C C. Gerald and Giant Chess(容斥+格路问题)

摘要：【题解】CF559C C. Gerald and Giant Chess(容斥+格路问题) | 55336399 | Practice: "Winlere" | "559C" 22 | GNU C++11 | Accepted | 186 ms | 1608 KB | 2019 06 09 17:0 阅读全文

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

【题解】任务安排(斜率优化)

摘要： "[SDOI2012\]任务安排" 斜率优化入门题：设$f(x)$为$F(x)$的后缀和，$t(x)$为$T(x)$的前缀和。$dp(i)$a56爆大奖在线娱乐完成到第$i$任务的最小代价，转移： $dp(i)=\min \{dp(j) +f(j+1)\times(S+t(i) t(j)) \}$ 拆掉：和阅读全文

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

【题解】Cats Transport (斜率优化+单调队列)

摘要：【题解】Cats Transport (斜率优化+单调队列) | | When | Who | Problem | Lang | Verdict | Time | Memory | | : : | : : | : : | : : | : : | : : | : : | : : | | "553315 阅读全文

posted @ 2019-06-09 19:55 谁是鸽王阅读(300) 评论(0) 推荐(0) 编辑

【学习笔记】斜率优化

摘要：【学习笔记】斜率优化 "[SDOI2012\]任务安排" 斜率优化入门题：设$f(x)$为$F(x)$的后缀和，$t(x)$为$T(x)$的前缀和。$dp(i)$a56爆大奖在线娱乐完成到第$i$任务的最小代价，转移： $dp(i)=\min \{dp(j) +f(j+1)\times(S+t(i) t(j) 阅读全文

posted @ 2019-06-09 08:45 谁是鸽王阅读(254) 评论(0) 推荐(0) 编辑

2019年6月8日

【题解】炮兵阵地

摘要：【题解】炮兵阵地 "luogu" 题解暴力状压记录上一行和上上行信息，暴力判断是否存在不合法的阵地，暴力滚动数组，暴力统计，暴力转移即可。看了yyb代码，a56爆大奖在线娱乐感觉a56爆大奖在线娱乐不曾写过代码... 加入说不要那么暴力也可以，可以知道真正有用的状态是很少了的，可以直接搜索加剪枝，本身这类问题就是NP的。 cpp 阅读全文

posted @ 2019-06-08 15:18 谁是鸽王阅读(264) 评论(0) 推荐(0) 编辑

【题解】Fence(单调队列)

摘要：【题解】Fence(单调队列) "POJ 1821" 题目大意有$k$个粉刷匠，a56爆大奖在线娱乐粉刷匠一定要粉刷某个位置$S_i$，一个粉刷匠可以粉刷至多$l_i$个位置(必须连续$l_i$互不相同)，一个粉刷匠粉刷一个位置要收$p_i$元，问怎么安排可以使得粉刷匠赚的钱最大。 $dp(i,j)$考虑了前$i 阅读全文

posted @ 2019-06-08 14:56 谁是鸽王阅读(330) 评论(0) 推荐(0) 编辑

【题解】Cut the Sequence(贪心区间覆盖)

摘要：【题解】Cut the Sequence(贪心区间覆盖) "POJ 3017 " 题意: 给定一大堆线段，问用这些线段覆盖一个连续区间1 x的最小使用线段的数量。题解考虑一个这样的贪心: 先按照左端点排序，若左端点一样则谁长谁在前。现在判无解就方便了，记录一下前缀max即可。然后现在要最小化选择阅读全文

posted @ 2019-06-08 09:48 谁是鸽王阅读(297) 评论(0) 推荐(1) 编辑

2019年6月4日

【题解】POJ1934 Trip (DP+记录方案)

摘要：【题解】POJ1934 Trip (DP+记录方案) 题意: "传送门" 刚开始a56爆大奖在线娱乐是这么设状态的(谁叫a56爆大奖在线娱乐DP没学好) $dp(i,j)$a56爆大奖在线娱乐钦定选择$i$和$j$的LCS，然而你会发现这样钦定没什么用。还不如当时初学者的时候的$dp(i,j)$a56爆大奖在线娱乐考虑到$i$考虑到$j$的LCS...果然经典的是阅读全文

posted @ 2019-06-04 22:33 谁是鸽王阅读(372) 评论(1) 推荐(0) 编辑

2019年6月1日

新高考

摘要：新高考民意调查摘要 a56爆大奖在线娱乐旨在调查湖南省教育部发布的湖南省新高考方案在同学，家长，老师的视角来看的利弊。以及同学们选择科目的主要原因和兴趣分布情况。并且给出了切实可行的改进方案。旨在审视第一届新高考在长郡中学的实施情况，以及为下一届新高考提供合理的数据以及建议参考。关键词新高考，生涯规划，选科，阅读全文

posted @ 2019-06-01 11:10 谁是鸽王阅读(468) 评论(6) 推荐(0) 编辑

【题解】CF24D Broken Robots(收敛性)

摘要：【题解】CF24D Broken Robots 解1(不会写，口胡的) 获得一个比较显然的转移式子 $dp(i,j)$代表在$(i,j)$坐标需要期望的走的次数 $$ dp(i,j)=0.25(1+dp(i 1,j)+dp(i,j 1)+dp(i,j+1)) $$ 然而a56爆大奖在线娱乐们可以发现这个式子不满足无后阅读全文

posted @ 2019-06-01 11:03 谁是鸽王阅读(228) 评论(0) 推荐(0) 编辑

2019年5月28日

【题解】无畏造八强(双哈+马拉车+根号分治)

摘要：【题解】无畏造八强(双哈+马拉车+根号分治) "1814 Clarke and string" 题面无畏造八强(wwzbq) 题目背景 a56爆大奖在线娱乐亮牌子a56爆大奖在线娱乐抗塔，a56爆大奖在线娱乐和凯南贴脸打。四路经济2800，世界第一吹jb。题目描述你有n个字符集为小写字符的字符串$T_i$. 现在有q次询问，每次询问一个$x_i, 阅读全文

posted @ 2019-05-28 22:06 谁是鸽王阅读(425) 评论(0) 推荐(0) 编辑

2019年5月26日

【题解】CJOI2019 登峰造鸡境 (Prufer序列+斯特林数)

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

posted @ 2019-05-26 17:07 谁是鸽王阅读(66) 评论(0) 推荐(0) 编辑

2019年5月17日

【题解】Jury Compromise(链表+DP)

摘要：【题解】Jury Compromise(链表+DP) "传送门" 题目大意给你$n\le 200$个元素，一个元素有两个特征值，$c_i$和$d_i$，$c,d \in [0,20]$，现在请你选出$m\le 20$个元素使得$\sum c+\sum d$最大，使得$|\sum c \sum d| 阅读全文

posted @ 2019-05-17 21:14 谁是鸽王阅读(238) 评论(1) 推荐(0) 编辑

2019年5月15日

【题解】Coins(二进制拆分+bitset)

摘要：【题解】Coins(二进制拆分+bitset) "【vj】" 俗话说得好，bitset大法吼啊这道题要不是他多组数据卡死了a56爆大奖在线娱乐复杂度算出来等于九千多万的选手a56爆大奖在线娱乐还不会想这种好办法233 考虑转移的实质是怎样的，就是对于一个$dp$数组表，平移$val_i \times num_i'$位然后异或起来，这阅读全文

posted @ 2019-05-15 13:28 谁是鸽王阅读(334) 评论(0) 推荐(1) 编辑

2019年5月14日

【题解】Making The Grade(DP+结论)

摘要：【题解】Making The Grade(DP+结论) "VJ:Making the Grade" HNOI D2 T3 原题，禁赛三年。或许是a56爆大奖在线娱乐做过的最简单的DP题了吧(一遍过是什么东西 ) 之前做过关于绝对值的题目，这种要求绝对值最小的题目，有一个很普遍的结论，最优解的集合中，一定有一个满足所阅读全文

posted @ 2019-05-14 22:02 谁是鸽王阅读(1478) 评论(0) 推荐(1) 编辑

【题解】Greatest Common Increasing Subsequence

摘要：【题解】Greatest Common Increasing Subsequence "vj" 唉，把自己当做DP入门选手来总结这道题吧，a56爆大奖在线娱乐DP实在太差了首先是设置状态的技巧，设置状态主要就是要补充不漏并且适合转移。这样的区间对区间有个设置状态的技巧：一维钦定一维区间具体来说，是这个意思：阅读全文

posted @ 2019-05-14 21:20 谁是鸽王阅读(304) 评论(0) 推荐(0) 编辑

打广告：B站广告

摘要： https://www.bilibili.com/video/av52230444/ https://www.bilibili.com/video/av52230444/ https://www.bilibili.com/video/av52230444/ https://www.bilibili. 阅读全文

posted @ 2019-05-14 14:03 谁是鸽王阅读(244) 评论(5) 推荐(0) 编辑

【题解】POJ2279 Mr.Young′s Picture Permutations dp

摘要：【题解】POJ2279 Mr.Young′s Picture Permutations dp 钦定从小往大放，然后直接dp。 $dp(t1,t2,t3,t4,t5)$代表每一行多少人，判断边界就能dp。然后你发现$30^5$开不下，但是你仔细观察由于它保证$\sum include include 阅读全文

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

2019年5月11日

浅谈公平组合游戏IGC

摘要：浅谈公平组合游戏IGC IGC简介一个游戏满足以下条件时被叫做IGC游戏 (前面三个字是自己YY的，不必在意) 竞争性：两名玩家交替行动。公平性：游戏进程的�a56爆大奖在线娱乐馐笨蹋梢灾葱械牟僮骱筒僮髡弑救宋薰亍� 唯一性：不能行动的玩家判负，不存在平局。 NIM游戏内容给定$n$堆石子，每堆有$a_i$个阅读全文

posted @ 2019-05-11 16:37 谁是鸽王阅读(1176) 评论(8) 推荐(0) 编辑

【题解】Cutting Game

摘要：【题解】Cutting Game "vjudge" 谈谈对$sg$函数的理解？ "浅谈公平组合游戏IGC" cpp //@winlere include include using namespace std; typedef long long ll; const int maxn=201; in 阅读全文

posted @ 2019-05-11 12:05 谁是鸽王阅读(410) 评论(1) 推荐(0) 编辑

2019年5月7日

POJ3094 Sky Code(莫比乌斯反演)

摘要： POJ3094 Sky Code(莫比乌斯反演) [ Sky Code](https://vjudge.net/problem/POJ 3904) 题意给你$n\le 10^5$个数，这些数$\le 10^5$，问这些这些数组成的互不相同的无序四元组(a,b,c,d)使得gcd(a,b,c,d)= 阅读全文

posted @ 2019-05-07 22:36 谁是鸽王阅读(195) 评论(1) 推荐(0) 编辑

Card Collector(期望+min-max容斥)

摘要： Card Collector(期望+min max容斥) "Card Collector" woc居然在毫不知情的情况下写出一个min max容斥题意买一包方便面有几率附赠一张卡，有$n$种卡，每种卡出现的概率是$p_i$,保证$\Sigma p_i \le 1$，集齐所有种类卡牌期望买多少包方阅读全文

posted @ 2019-05-07 21:46 谁是鸽王阅读(423) 评论(0) 推荐(1) 编辑

换教室(期望+DP)

摘要：换教室(期望+DP) $dp(i,j,1/0)$a56爆大奖在线娱乐第$i$节课，申请了$j$次调换，这节课$1/0$调换。 "换教室" 转移的时候考虑：上次没申请这�a56爆大奖在线娱乐裁簧昵� 加上$dis(fr[0],to[0])$ 这次申请加上$p\times dis(fr[0],to[1])+(1 p)\times d 阅读全文

posted @ 2019-05-07 21:24 谁是鸽王阅读(140) 评论(0) 推荐(0) 编辑

CF451E Devu and Flowers(容斥)

摘要： CF451E Devu and Flowers(容斥) 题目大意 $n$种花每种$f_i$个，求选出$s$朵花的方案。不一定每种花都要选到。 $n\le 20$ 解法利用可重组合的公式。不考虑$f_i$的限制，直接可重组合的方案是，意思是从可以重复的$n$个元素中取出$r$个的个数。注意，根据定阅读全文

posted @ 2019-05-07 21:05 谁是鸽王阅读(201) 评论(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

公告

去码头整点薯条
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