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

2019年8月14日

摘要：【瞎讲】类欧几里得入土教程产生背景假设a56爆大奖在线娱乐们现在得到一条直线$y=ax+b$，现在要数出$x \in [0,n]$时，在$x$正半轴和这条直线之间的整点个数，$n \le 10^{18}$ 解决思路这个方程一定可以化为这样的形式 $$ y=\dfrac {ax+b}{c} $$ 枚举$x \in 阅读全文

posted @ 2019-08-14 16:32 谁是鸽王阅读(268) 评论(6) 推荐(2) 编辑

2019年8月9日

【题解】SDOI2010所驼门王的宝藏(强连通分量+优化建图)

摘要：【题解】SDOI2010所驼门王的宝藏(强连通分量+优化建图) 最开始a56爆大奖在线娱乐想写线段树优化建图的说，数据结构学傻了233 虽然矩阵很大，但是没什么用，真正有用的是那些关键点考虑关键点的类型：横走型竖走型八连通型本质上只有两种类型(走一大串/走八连通)，a56爆大奖在线娱乐们考虑这样a56爆大奖在线娱乐建图方法：对于每一行每一阅读全文

posted @ 2019-08-09 21:47 谁是鸽王阅读(242) 评论(4) 推荐(0) 编辑

2019年8月6日

【题解】CJOI2019 线段树(线段树)

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

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

2019年8月5日

【题解】ARC101F Robots and Exits(DP转格路+树状数组优化DP)

摘要：【题解】ARC101F Robots and Exits(DP转格路+树状数组优化DP) 先删去所有只能进入一个洞的机器人，这对答案没有贡献考虑一个机器人只能进入两个洞，且真正的限制条件是操作的前缀$\min \max$，a56爆大奖在线娱乐们直接按照前缀$\min \max$$DP$ 把前缀$\min \max$ 阅读全文

posted @ 2019-08-05 07:57 谁是鸽王阅读(315) 评论(0) 推荐(0) 编辑

2019年8月4日

【题解】CJOI2019 鸡贼的树(构造题)

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

posted @ 2019-08-04 18:22 谁是鸽王阅读(39) 评论(0) 推荐(0) 编辑

【题解】LOJ6060 Set(线性基)

摘要：【题解】LOJ6060 Set(线性基) orz gql 设所有数的异或和为$S$，答案是在$\max (x_1+S\and x_1)$的前提下$\min x_1$输出$x_1$ 转换一下就是$\max (x_2+S\and x_2),s.t. \max x_2$ 考虑先贪心地求出外层$\max$ 阅读全文

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

2019年8月1日

【题解】CF1056F Write the Contest(三分+贪心+DP)

摘要：【题解】CF1056F Write the Contest(三分+贪心+DP) 最优化问题的三个解决方法都套在一个题里了，真牛逼最优解应该是怎样的，一定存在a56爆大奖在线娱乐最优解是先完成了耗时长的任务再干别的(不干白不干啊)，a56爆大奖在线娱乐a56爆大奖在线娱乐们按照耗时先排序。假设你最优解是去事件$e_1,e_2,e_3,e_4$，你阅读全文

posted @ 2019-08-01 17:11 谁是鸽王阅读(633) 评论(6) 推荐(0) 编辑

2019年7月31日

【题解】多少个$1$(exBSGS)

摘要：【题解】多少个$1$(exBSGS) 解方程： $$ \underbrace {1\dots1}_{n}\equiv k \mod m $$ 其实就是 $$ \dfrac {10^n 1} {9}\equiv k \mod m $$ 就是 $$ 10^n\equiv 9k+1 \mod m $$ 直阅读全文

posted @ 2019-07-31 21:47 谁是鸽王阅读(240) 评论(0) 推荐(0) 编辑

【题解】幼儿园篮球题(范德蒙德卷积+斯特林+NTT)

摘要：【题解】幼儿园篮球题(NTT+范德蒙德卷积+斯特林数) 题目就是要a56爆大奖在线娱乐们求一个式子(听说叫做超几何分布？好牛逼的名字啊) $$ \sum_{i=1}^{S}\dfrac 1 {N \choose n_i}\sum_{j=0}^{k_i}{m_i \choose j}{n_i m_i\choose k_ 阅读全文

posted @ 2019-07-31 10:44 谁是鸽王阅读(400) 评论(1) 推荐(0) 编辑

2019年7月30日

【题解】P1373 小a和uim之大逃离

摘要：【题解】P1373 小a和uim之大逃离考虑到可能会MLE，考虑状态压缩一下由于只要得到他们的差就行了，a56爆大奖在线娱乐直接少记录一维就好了 $dp(i,j,r,1/0)$a56爆大奖在线娱乐在$i,j$点，当前uim a=$r$，这个节点是$a/uim$选择装瓶子的方案数，转移显然 cpp //@winlere incl 阅读全文

posted @ 2019-07-30 21:40 谁是鸽王阅读(163) 评论(4) 推荐(0) 编辑

【题解】[CJOI2019]膜拜杜老师(思博题)

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

posted @ 2019-07-30 16:27 谁是鸽王阅读(22) 评论(0) 推荐(0) 编辑

【合集】暑假考试题解集合

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

posted @ 2019-07-30 15:10 谁是鸽王阅读(67) 评论(2) 推荐(0) 编辑

【题解】[CJOI2019] 杜瘤题(线段树+堆)

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

posted @ 2019-07-30 15:09 谁是鸽王阅读(24) 评论(0) 推荐(0) 编辑

2019年7月29日

【题解】地精部落(DP)

摘要：【题解】地精部落(DP) 设$f_i$a56爆大奖在线娱乐强制第一个是谷的合法方案数转移枚举一个排列的最大值在哪里，就把序列分成了互不相干的两个部分，把其中$i 1\choose j 1$的数字分配给前面部分，剩下的给后面。转移从所有可以转移的偶数过来 cpp //@winlere include include 阅读全文

posted @ 2019-07-29 19:57 谁是鸽王阅读(165) 评论(0) 推荐(0) 编辑

【题解】[CJOI2019]加强版地精部落

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

posted @ 2019-07-29 19:49 谁是鸽王阅读(7) 评论(0) 推荐(0) 编辑

2019年7月28日

【题解】SDOI2015序列统计

摘要：【题解】SDOI2015序列统计来自永不AFO的YYB的推荐这里是乘积，比较麻烦，不过由于给定的序列膜数是个小质数，a56爆大奖在线娱乐可以$O(m^2\log m)$找原跟(实际上不需要这么多)。乘积有点麻烦，转换成加法就好了，然后取离散对数$a_i\equiv g^{c_i} \mod m$，现在a56爆大奖在线娱乐元素阅读全文

posted @ 2019-07-28 20:08 谁是鸽王阅读(285) 评论(2) 推荐(0) 编辑

【合集】有标号的DAG图计数(合集)

摘要：【合集】有标号的DAG图计数(合集) orz 1tst "【题解】有标号的DAG计数1" "【题解】有标号的DAG计数2" "【题解】有标号的DAG计数3" "【题解】有标号的DAG计数4" 阅读全文

posted @ 2019-07-28 11:06 谁是鸽王阅读(418) 评论(0) 推荐(0) 编辑

【题解】有标号的DAG计数4

摘要： "[HZOI 2015\] 有标号的DAG计数 IV" a56爆大奖在线娱乐们已经知道了$f_i$a56爆大奖在线娱乐不一定需要联通的$i$节点的dag方案，考虑合并参考 "【题解】P4841 城市规划(指数型母函数+多项式Ln)" ，然后答案$h_i$母函数$H(x)$就这样解由于 $$ H(x)=\sum_{i=0}^{\i 阅读全文

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

【题解】有标号的DAG计数3

摘要： "[HZOI 2015\] 有标号的DAG计数 III" a56爆大奖在线娱乐们已经知道了$f_i$a56爆大奖在线娱乐不一定需要联通的$i$节点的dag方案，考虑合并参考 "【题解】P4841 城市规划(指数型母函数+多项式Ln)" ，然后答案$h_i$母函数$H(x)$就这样解由于 $$ H(x)=\sum_{i=0}^{\ 阅读全文

posted @ 2019-07-28 11:04 谁是鸽王阅读(243) 评论(0) 推荐(0) 编辑

【题解】有标号的DAG计数2

摘要： "[HZOI 2015\] 有标号的DAG计数 II" $I$中DP只有一个数组， $$ dp_i=\sum{i\choose j}2^{j(i j)}dp_{i j}( 1)^{j+1} $$ 不会... 傻啊直接多项式球逆，借鉴一些luogu那道模板分治FFT 这里主要有个很烦人的$ji j^2 阅读全文

posted @ 2019-07-28 11:02 谁是鸽王阅读(212) 评论(0) 推荐(0) 编辑

【题解】有标号的DAG计数1

摘要： "[HZOI 2015\] 有标号的DAG计数 I" 设$f_i$为$i$个点时的DAG图，(不必联通) 考虑如何转移，由于一个DAG必然有至少一个出度为$0$的点，a56爆大奖在线娱乐a56爆大奖在线娱乐们钦定多少个出度为$0$的点转移。考虑如何保证没有环，钦定完出度为$0$的点后，这些点就等着被连接了。还剩下一些点，这些点只要阅读全文

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

2019年7月26日

【题解】歌唱王国(概率生成函数+KMP)+伦讲的求方差

摘要：【题解】歌唱王国(概率生成函数+KMP)+伦讲的求方差生成函数的本质是什么呀！为什么和It st一样神设$f_i$a56爆大奖在线娱乐填了$i$个时候停下来的概率，$g_i$是填了$i$个的时候不停下的来的概率，规定$f_0=g_0=1$ 两个生成函数是 $$ G(x)=\sum g(i)x^i \\ F(x) 阅读全文

posted @ 2019-07-26 21:57 谁是鸽王阅读(256) 评论(0) 推荐(0) 编辑

【题解】[CJOI2019]签到题/B题(莫比乌斯反演+杜教筛+可重组合)

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

posted @ 2019-07-26 16:34 谁是鸽王阅读(11) 评论(0) 推荐(0) 编辑

2019年7月25日

【题解】CTS2019珍珠(二项式反演+卷积)

摘要：【题解】CTS2019珍珠题目就是要满足这样一个条件$c_i$代表出现次数 $$ \sum {[\dfrac {c_i } 2]} \ge 2m $$ 显然$\sum c_i=n$a56爆大奖在线娱乐，而且假如$c_i$是$2$的约数就有正常的贡献，如果不是就有少一点的贡献，那么 $$ \sum^D_{i=1} 阅读全文

posted @ 2019-07-25 21:39 谁是鸽王阅读(246) 评论(0) 推荐(0) 编辑

2019年7月24日

【题解】餐巾计划问题

摘要：【题解】餐巾计划问题 orz "argent" 一定要注意不要调到题目里的坑里来了，要记得脱离实际(大雾)。建模方法：a56爆大奖在线娱乐觉得没什么好讲的，真的是灵感问题，此外，这个问题可以直接无源汇上下界网络流。但是a56爆大奖在线娱乐不会保证净到$T$一定满流即可。 cpp //@winlere include include 阅读全文

posted @ 2019-07-24 22:08 谁是鸽王阅读(203) 评论(0) 推荐(0) 编辑

【题解】数字梯形问题

摘要：【题解】数字梯形问题这样一道傻题a56爆大奖在线娱乐调了这么久三个任务建图是这样的，由于太简单就不xjb解释了，一个点拆位入点和出点一次加边即可，不过由于是费用流a56爆大奖在线娱乐貌似要重置残余网络注意数组大小和边界！好坑。 cpp //@winlere include include include include in 阅读全文

posted @ 2019-07-24 17:27 谁是鸽王阅读(235) 评论(0) 推荐(0) 编辑

【题解】最小路径覆盖问题(网络流)

摘要：最小路径覆盖问题考虑最终的那些覆盖路径的样子是什么，显然是很多点和很多链(废话)，但是学过生物必修一肽链和蛋白质的人都能发现，路径条数=$n m'$，$n$是点的个数，$m'$是选出来的边的条数。这里的$n$是个定值，问题转变了选出最多的边$m'$，使得选出的边不存在共同的起点或终点。也就是说阅读全文

posted @ 2019-07-24 12:13 谁是鸽王阅读(243) 评论(0) 推荐(0) 编辑

2019年7月23日

【题解】CTSC1999家园(网络流)

摘要： CTSC1999家园建模方法类似a56爆大奖在线娱乐NOI2019网络同步赛a56爆大奖在线娱乐的T1写法 "【题解】[NOI2019Route\]（70分）" 问题的焦点是：空间时间载具。考虑如何击破时间限制，可以对a56爆大奖在线娱乐点关于a56爆大奖在线娱乐时刻建立一个点，这样就实现一个点在两个时间互不干扰。由于时间是流淌的，a56爆大奖在线娱乐从过去到现在连一条免费的$ 阅读全文

posted @ 2019-07-23 21:36 谁是鸽王阅读(196) 评论(0) 推荐(0) 编辑

【题解】太空飞行计划问题

摘要：太空飞行计划问题还是利用最小割的性质，这种题目叫做最大权闭合子图。建模方法是这样直接跑最小割，用奖金减去最小割就是答案。方案就是最后一遍bfs能遍历的点考虑最小割的意义，就是把边删掉使得$S,T$不连通。同样地，由于a56爆大奖在线娱乐们无法改变仪器和任务依赖的关系，只能改变一个点是否选择这个状态，a56爆大奖在线娱乐a56爆大奖在线娱乐们阅读全文

posted @ 2019-07-23 21:35 谁是鸽王阅读(226) 评论(0) 推荐(0) 编辑

【题解】航空路线问题

摘要：航空路线问题一个点有两种用法，但是只能选a56爆大奖在线娱乐用，直接把一个点拆掉并且连一条容量为1的边就成功限制。将一个点拆为两个点，一个入点一个出点，入点到出点连一条费用为$ inf$ 的边，跑费用流，最终答案就是 $$ \dfrac {cost} {inf} $$ 输出方案随便弄一下就好了。注意考虑边界情况阅读全文

posted @ 2019-07-23 21:34 谁是鸽王阅读(159) 评论(0) 推荐(0) 编辑

【题解】方格取数问题(网络流)

摘要：方格取数问题考虑这个要求"没有共同边"，像极了最小割。最小割：将图依照$S$和$T$分为两个互无交集的集合，并且使得删去的元素(边)的权值和最小。然后a56爆大奖在线娱乐们看看这个问题，先要分类以确定和$S$在一起和和$T$在一起的点。显然由于相邻点是对立的a56爆大奖在线娱乐a56爆大奖在线娱乐们直接相邻的连$inf$边a56爆大奖在线娱乐这个相邻关系无法阅读全文

posted @ 2019-07-23 21:34 谁是鸽王阅读(215) 评论(0) 推荐(0) 编辑

运输问题(网络流24)

摘要：运输问题建模之后就是费用流板题。建模方法就是两边一排。注意重置边的时候，不能swap，要用$+=$原因思考一下显然，不然就会不知道哪里错了。强行总结的话，这样的建模体现了一个且的关系。阅读全文

posted @ 2019-07-23 21:33 谁是鸽王阅读(225) 评论(0) 推荐(0) 编辑

【题解】 P2763 试题库问题(网络流)

摘要： P2763 试题库问题考虑一个试题要被加入进答案的集合有什么条件？是某种类型只算作一次就这两种且的限制，a56爆大奖在线娱乐a56爆大奖在线娱乐们用串联的方式连接"类型点"和"作用点"。判断无解就判断容量是否满了。输出方案就输出有流量的边的终点。 cpp //@winlere include include include 阅读全文

posted @ 2019-07-23 21:33 谁是鸽王阅读(162) 评论(0) 推荐(0) 编辑

[**P2766** 最长不下降子序列问题](https://www.luogu.org/problemnew/show/P2766)

摘要： " P2766 最长不下降子序列问题" 考虑a56爆大奖在线娱乐们是如何$dp$这个$LIS$的。 a56爆大奖在线娱乐们是倒着推，设置$dp(i)$代表以$i$为起点的$LIS$是多少。转移太显然了 $$ dp(i)=max\{dp(j)\}+1,data[i]\le data[j] $$ 想一想一个合法的$LIS$方案代表着什么，阅读全文

posted @ 2019-07-23 21:32 谁是鸽王阅读(326) 评论(0) 推荐(0) 编辑

2019年7月22日

【汇总】网络流二十四题

摘要： "【题解】P2766 最长不下降子序列问题" "【题解】 P2763 试题库问题(网络流)" "【题解】运输问题(网络流24)" "【题解】方格取数问题(网络流)" "【题解】航空路线问题" "【题解】太空飞行计划问题" "【题解】CTSC1999家园(网络流)" "【题解】最小路径覆盖问题(网络阅读全文

posted @ 2019-07-22 22:38 谁是鸽王阅读(262) 评论(2) 推荐(0) 编辑

【题解】畜栏预定

摘要：【题解】畜栏预定嘿嘿又是 "普及题" 至少要把线段分成多少个集合使得所有相交的线段不在一个集合输出方案。显然a56爆大奖在线娱乐们让没一个线段覆盖的所有下标加上1，最后查询全局最大值就是答案，这样太显然了。直接树状数组$O(n \log n)$，或许有$O(n)$算法，有没有人教一下a56爆大奖在线娱乐。然后得到这个集合数目之后阅读全文

posted @ 2019-07-22 08:03 谁是鸽王阅读(187) 评论(0) 推荐(0) 编辑

2019年7月21日

【题解】AcWing 110. 防晒(普及题)

摘要：【题解】AcWing 110. 防晒(普及题) "AcWing 110. 防晒" 你没有用过的全新OJ 嘿嘿水水题。题目就是一维坐标轴上给定多个线段，给定多个点，点在线段上造成贡献，点可以重复，问最大贡献模板题，主要是要注意到给的时候不一定点是互不相同的，a56爆大奖在线娱乐要记录一下。小心set去重。 cpp 阅读全文

posted @ 2019-07-21 22:47 谁是鸽王阅读(262) 评论(0) 推荐(0) 编辑

2019年7月20日

【总结】皇冠上的明珠——初等数论初步

posted @ 2019-07-20 21:46 谁是鸽王阅读(113) 评论(5) 推荐(0) 编辑

2019年7月19日

【题解】数独(养生题)

摘要：【题解】数独(养生题) 暴力DFS，但是a56爆大奖在线娱乐的代码比较短，供大家参考。 "优雅的暴力——搜索算法小结" 不过a56爆大奖在线娱乐还用了随机化搜索，这种搜索思想可以防止被毒瘤出题人卡掉。有兴趣的可以看一下a56爆大奖在线娱乐的一篇总结里面写了搜索的一些技巧。对于实现，a56爆大奖在线娱乐的思路是...不好说，但是这样写搜索又快又稳还短。以上是洛谷装逼的阅读全文

posted @ 2019-07-19 17:04 谁是鸽王阅读(191) 评论(0) 推荐(0) 编辑

2019年7月18日

【题解】P4841 城市规划(指数型母函数+多项式Ln)

摘要：【题解】P4841 城市规划 " P4841 城市规划" 超级弱化版本(DP)： "POJ 1737 " 两张图不同当且仅当边的分布不一样的时候，带编号最后乘一个阶乘即可，现在最主要的问题就是"联通"这个条件。 a56爆大奖在线娱乐首先考虑的容斥，"随意连不联通"的方案太好算了，$2^{n(n 1)/2}$，但是发现阅读全文

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