- 博客(144)
- 收藏
- 关注
RSS订阅原创 【BZOJ】【lucas定理】4403: 序列统计
令m=R−L+1m=R−L+1m=R-L+1如果长度确定为nnn，相当于求∑mi=1xi=n∑i=1mxi=n\sum_{i=1}^{m}x_i=n，用插板法得答案为(n+m−1m−1)(n+m−1m−1)n+m-1\choose m-1，然后就是一波骚操作：由(xy)=(x−1y)+(x−1y−1)(xy)=(x−1y)+(x−1y−1){x\choose y}={x-1\choose y}...
2018-08-29 20:05:31
325
原创 【BZOJ】【中国剩余定理】1951: [Sdoi2010]古代猪文
题意求 G∑i|n(ni)(mod999911659)G∑i|n(ni)(mod999911659)G^{\sum_{i|n}{n\choose i}}\pmod{999911659}题解由费马小定理 ap−1≡1(modp)ap−1≡1(modp)a^{p-1}\equiv 1\pmod p 得 G∑i|n(ni)(modtt)=G∑i|n(ni)(modtt−1...
2018-08-27 20:25:15
319
原创 【Codechef】【主席树维护DP】【SnackDown 2017 Online Elimination Round】PREFIXOR: 异或前缀
如果能处理出每个点往右最多扩展到rgt[i]rgt[i]rgt[i]，那么答案就是 ∑i=lrmin{rgt[i],r}−i=∑i=lrrgt[i]−∑i=lri−∑i=l&rgt[i]>rrrgt[i]−r∑i=lrmin{rgt[i],r}−i=∑i=lrrgt[i]−∑i=lri−∑i=l&rgt[i]>rrrgt[i]−r\sum_{i=l}^{r}min\...
2018-08-24 10:30:33
529
原创 【线段树维护矩阵转移】【Codeforces】573D. Bear and Cavalry
题意给出一个[1,n][1,n][1,n]的排列，每次交换两个数，每次询问一个每一位都与这个数列不同排列，这样的排列的最大权值，一个排列的权值定义为a[i]∗b[p[i]]a[i]∗b[p[i]]a[i]*b[p[i]]。题解如果没有限制，由排序不等式，显然当aaa，bbb都顺序排列是最优解，现在有限制以后，可以证明（其实我不会）：每一位最多与排序后与它相差2的数配对。这样就可...
2018-08-24 10:15:23
471
原创 【区间DP】Codeforces#505D 1025D Recovering BST
题意给n个数，问能否构造出一个相邻节点不互质的二叉搜索树。题解JZ太神了，看了一眼就说区间DP。定义lft[i][j]lft[i][j]lft[i][j]表示[i,j][i,j][i,j]接在i−1i−1i-1的右儿子是否可行，rgt[i][j]rgt[i][j]rgt[i][j]表示[i,j][i,j][i,j]接在j+1j+1j+1的左儿子是否可行。转移就用经典区间DP，枚...
2018-08-20 16:25:09
422
原创 【UOJ】【kruskal重构树】【NOI2018】归程
按照高度建最大生成树，构造kruskal重构树，每次连边时新建一个节点表示边权连到两端的父亲上。这样一棵树满足小根堆的性质。所以可以倍增跳到最顶端，然后答案就是子树里的最小权值（这里的权值为到1的最短路)。代码#include<cstdio>#include<cstring>#include<algorithm>#include<queu...
2018-08-18 22:29:21
210
原创 【UOJ】UER#3.B 开学前的日历
将条件转化为i,j⩾0,i+j⩾k|Av+i,u+j+=(i+ji)i,j⩾0,i+j⩾k|Av+i,u+j+=(i+ji)i,j\geqslant 0,i+j\geqslant k|A_{v+i,u+j}+={i+j\choose i}， 考虑组合意义，从(v,u)(v,u)(v,u)开始每次往右或往下走，走大于等于kkk布的方案数，直接DP。#include<cstdio>...
2018-08-13 20:48:54
286
原创 【UOJ】UER#3.A 开学前的作文
找规律。#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int T,n,m,ans;int main(){ freopen("A.in","r",stdin);freopen("A.out","w",stdout); sc
2018-08-13 20:47:25
239
原创 【容斥】Topcoder SRM div1-3 12004. SetAndSet
取反，变成or和相同。同一位，为1的不能放在同一边，并查集加容斥搞。第一次在TC上做题，机制轻喷。。。代码#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<vector>using namespace st...
2018-08-07 22:29:22
506
1
原创 【ZROI】【数学相关】【计数问题】【17 提高 6】异或统计
首先考虑这个问题的简化版：求∑(ai&nbsp;xor&nbsp;aj)∗(aj&nbsp;xor&nbsp;ak)∑(ai&nbsp;xor&nbsp;aj)∗(aj&nbsp;xor&nbsp;ak)\sum (ai\ xor\ aj)*(aj\ xor\ ak)，这就等价于求∑j((∑ai&nbsp;xor&nbsp;aj)(∑aj&a
2018-07-08 20:42:47
380
原创 【ZROI】【数学相关】【17 提高 5】剪刀石头布
根据期望的线性性，可以计算获胜盘数的期望为wa∗∑bi+wb∗∑ci+wc∗∑aiwa∗∑bi+wb∗∑ci+wc∗∑aiwa*\sum bi+wb*\sum ci+wc*\sum ai，然后分类讨论，由于wa和wb都不会为0，所以∑bi=∑c[i]∑bi=∑c[i]\sum bi=\sum c[i]，并且，如果wa+wb=1e9wa+wb=1e9wa+wb=1e9，那么∑bi&lt;=∑ai∑b...
2018-07-08 20:41:54
685
原创 【ZROI】【DP】【17 提高 5】石头剪刀布
暴力DP可以定义f[i][a][b][c]f[i][a][b][c]f[i][a][b][c]表示到第i个数为止，以0结尾的最长胜利序列长度为a，以1结尾的最长胜利序列长度为b，以2结尾的最长胜利序列长度为c的方案数，显然这样过于暴力了。接下来，我们会发现一个结论，那就是a,b,c任意两个数相差不超过2，证明如下：由于石头的上一个必然是布，所以c&gt;=a−1c&gt;=a−1c>=a-1，...
2018-07-08 20:41:24
412
原创 【ZROI】【贪心】【DP】【17 提高 4】怪物猎人
假设我们已经确定了要杀那几只怪，假设第i只怪在第j天被杀死，那么它对猎人造成的伤害就是(a[i]+j∗d)(b[i]+j∗d)=a[i]∗b[i]+j2d2+j∗d∗(a[i]+b[i])(a[i]+j∗d)(b[i]+j∗d)=a[i]∗b[i]+j2d2+j∗d∗(a[i]+b[i])(a[i]+j*d)(b[i]+j*d)=a[i]*b[i]+j^2d^2+j*d*(a[i]+b[i])，贪...
2018-07-08 20:41:01
355
原创 【ZROI】【DP】【17 提高 3】建造
假设我们已经确定了一个建造的顺序，那么如何计算按照这个顺序建造的方案数？这就相当于确定一个数组d，其中∑di&lt;=X∑di&lt;=X\sum d_idi&gt;=max{hi,hi+1}di&gt;=max{hi,hi+1}d_i>=max\{h_i,h_{i+1}\}，为了方便起见，记∑max{hi,hi+1}=S∑max{hi,hi+1}=S\sum max\{h_i,h_{i+1}\}...
2018-07-08 20:40:02
285
原创 【ZROI】【高维前缀和】【lucas定理】【17 提高 2】World Of Our Own
第3步a0^a1^a1^a2^a1^a2^a2^a3第2步a0^a1^a1^a2 a1^a2^a2^a3第1步a0^a1 a1^a2 a2^a3第0步a0 a1 a2 a3每次的合并操作相当于每个数往上走一步或是往左上走一步，那么，最终第iii个数在第jjj步走到位置0（将原来1~n重新编号为0~n-1，这样可以方便计算）的方案数为C...
2018-07-08 20:39:23
462
原创 【ZROI】【启发式合并】【17 提高 2】Last mile of the way
做法就是每次将一个点的所有子节点的答案合并到这个点上去，暴力的合并可以每次枚举子节点背包的大小，这样的复杂度是O(ns2)O(ns2)O(ns^2)的。可以利用启发式合并的trick，每次将子节点中最重的儿子直接复制过来，然后对于其他子树中的所有节点直接暴力合并，由于合并单个节点的复杂度是O(s)O(s)O(s)的，而每次合并了以后子树大小至少变成了原来的2倍，所以每个节点最多被合并log2nlo...
2018-07-08 20:38:33
296
原创 【数位DP】树状数组
题解考虑如何计算f[l][r]f[l][r]f[l][r]。很显然，可以分别计算l,rl,rl,r的二进制中1的个数，然后减去(最大公共前缀的1的个数)*2。考虑如何统计每一对l,rl,rl,r的最大前缀中1的个数，可以用数位DP。记f[i][j][1/0][1/0]f[i][j][1/0][1/0]f[i][j][1/0][1/0]表示前iii位，最大公共前缀中1的个数为jjj，...
2018-06-05 15:40:03
261
原创 【康复训练】【cdq分治】【BZOJ】3295: [Cqoi2011]动态逆序对
Description对于序列A，它的逆序对数定义为满足i题解cdq分治. 将删除操作倒序看就是加入操作，然后就是一个经典的三位偏序问题了。代码#include<cstdio>#include<cstring>#include<algorithm>#define maxn 100006#define maxm 50006#...
2018-05-30 17:12:27
200
原创 Emacs配置
(custom-set-variables ;; custom-set-variables was added by Custom. ;; If you edit it by hand, you could mess it up, so be careful. ;; Your init file should contain only one such instance. ;; I...
2018-05-27 19:24:17
508
原创 【康复训练】【主席树】【BZOJ】1112: [POI2008]砖块Klo
DescriptionN柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.题解主席树。只要求出中位数、比中位数小的数的总和和个数、比中位数大的数的总和和个数。代码#include<cstdio>#include<c...
2018-05-27 16:34:28
406
原创 【康复训练】【主席树】【51nod】1175 区间中第K大的数
Description一个长度为N的整数序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，第K大的数是多少。 例如: 1 7 6 3 1。i = 1, j = 3，k = 2，对应的数为7 6 3，第2大的数为6。题解主席树代码#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;al...
2018-05-26 15:09:09
239
原创 【学习笔记】主席树
主席树，又称可持久化线段树，顾名思义，就是一种可以访问历史版本的数据结构.所谓访问历史版本，就是在每次修改了线段树以后，并不把原先的树破坏掉，而是在原来的树上新加入一些节点，使得这些节点与原来的线段树的一部分构成了修改后的线段树.考虑线段树的修改操作。由于每次修改最多只会修改lognlognlogn个节点，而对于其他的节点，新旧线段树都是可以共用的，所以，我们只需要将这些对于这些修改过的节...
2018-05-25 15:38:12
1264
原创 【康复训练】【DP】【BZOJ】2298: [HAOI2011]problem a
Description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数) 题解简单DP。每个人有一个名词区间，区间权值为相同区间的个数，题目等价于选出一些不相交的线段，使权值最大。代码#include<cstdio>#include<cstring>#include&...
2018-05-20 21:17:11
158
原创 【康复训练】【BZOJ】5168: [HAOI2014]贴海报
DescriptionBytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委 员 会为选民准备了一个张贴海报的electoral墙。张贴规则如下： 1．electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子； 2．所有张贴的海报的高度必须与electoral墙的高度一致的； 3．每张海报以“A B”表示，即从第A个格...
2018-05-20 18:00:11
262
原创 【康复训练】【BZOJ】3192: [JLOI2013]删除物品
Description箱子再分配问题需要解决如下问题： （1）一共有N个物品，堆成M堆。 （2）所有物品都是一样的，但是它们有不同的优先级。 （3）你只能够移动某堆中位于顶端的物品。 （4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。 ...
2018-05-19 22:30:43
209
原创 【康复训练】【点分治】【BZOJ】2152: 聪聪可可
Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边...
2018-05-19 15:22:25
146
原创 【康复训练】【51nod】1463 找朋友
Description给定： 两个长度为n的数列A 、B 一个有m个元素的集合K 询问Q次 每次询问[l,r]，输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj数据约定： n,Q<=100000 m <= 10 0<=A[i]<=1000000000 1<=B[i]<=n 1<=K[i]<=n 保证B[i]互不相等 I...
2018-05-18 15:16:55
197
原创 【康复训练】【51nod】1711 平均数
DescriptionLYK有一个长度为n的序列a。 他最近在研究平均数。 他甚至想知道所有区间的平均数，但是区间数目实在太多了。 为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。题解二分，树状数组。代码#include<cstdio>#include<cstring>#include<algor...
2018-05-17 20:18:21
335
1
原创 HDU 3853 LOOPS【期望DP】
DescriptionAkemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth
2017-11-10 20:02:04
354
原创 BZOJ 1202: [HNOI2005]狡猾的商人【并查集】【路径迭代】
Description刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i 个月的收入额为Ai(i=1,2,3…n-1,n)， 。当 Ai大于0时表示这个月盈利Ai 元，当 Ai小于0时表示这个月亏损Ai 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。 刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她
2017-11-10 19:32:25
314
原创 BZOJ 4808: 马【二分图】【最大独立集】
Description众所周知，马后炮是中国象棋中很厉害的一招必杀技。”马走日字”。本来，如果在要去的方向有别的棋子挡住（俗称”蹩马腿”），则不允许走过去。为了简化问题，我们不考虑这一点。马跟马显然不能在一起打起来，于是rly在一天再次借来了许多许多的马在棋盘上摆了起来……但这次，他实在没兴趣算方案数了，所以他只想知道在N×M的矩形方格中摆马使其互不吃到的情况下的最多个数。但是，有一个很不幸的消息，
2017-11-10 16:02:44
333
原创 51nod 1952 栈【单调队列】
DescriptionLYK有一个栈，众所周知的是这个数据结构的特性是后进先出的。LYK感觉这样子不太美妙，于是它决定在这个前提下将其改进，也就是说，每次插入元素时，可以在栈顶或者栈底插入，删除元素时，只能在栈顶删除。LYK想知道每次执行完操作后当前栈中元素的最大值是多少。第一行一个数n表示操作次数。接下来n行，每行两个数a。若a<=1，则接下来输入一个数b。若a=0，则在栈顶插入一个数b。若a=1
2017-11-09 19:24:24
301
原创 线性推逆元
逆元是很有用的东西。设p=ki+rp=ki+r， ki+r≡0(modp)k×r−1+i−1≡0(modp)i−1≡−pi×(pmodi)(modp)ki+r\equiv 0(\mod p)\\k\times r^{-1}+i^{-1}\equiv 0(\mod p)\\i^{-1}\equiv -\frac{p}{i}\times(p\mod i)(\mod p) 这样就可以线性推逆元了。
2017-11-09 15:28:20
373
原创 51nod 1122 机器人走方格 V4【组合数学】【矩阵乘法】
Description四个机器人a b c d，在2 * 2的方格里，一开始四个机器人分别站在4个格子上，每一步机器人可以往临近的一个格子移动或留在原地（同一个格子可以有多个机器人停留），经过n步后有多少种不同的走法，使得每个毯子上都有1机器人停留。由于方法数量巨大，输出 Mod 10^9 + 7的结果。题解每个位置都是等价的，可以通过求解从第一个位置到另外的位置的方案数，然后枚举最后每个机器人的位
2017-11-09 13:41:35
399
原创 51nod 1781 Pinball【DP】【线段树】
DescriptionPinball的游戏界面由m+2行、n列组成。第一行在顶端。一个球会从第一行的某一列出发，开始垂直下落，界面上有一些漏斗，一共有m个漏斗分别放在第2~m+1行，第i个漏斗的作用是把经过第i+1行且列数在Ai~Bi之间的球，将其移到下一行的第Ci列。 使用第i个漏斗需要支付Di的价钱，你需要保留一些漏斗使得球无论从第一行的哪一列开始放，都只可能到达第m+2行的唯一 一列，求花费的
2017-11-08 20:49:49
335
原创 BZOJ 1787: [Ahoi2008]Meet 紧急集合【LCA】
Description题解集结地点肯定在三个点中某两点的LCA上，可以刷最小值。当然，通过观察，可以发现如果其中两个LCA相同，那么答案一定在另外一个。代码#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define maxn 500006using namespace std;inline char
2017-11-08 18:57:44
246
原创 51nod 1120 机器人走方格V3【卡特兰数】【卢卡斯定理】
DescriptionN * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。题解答案就是H(N−1)∗2H(N-1)*2%tt。所以就是一个求大组合数模一个质数的题目，可以用卢卡斯定理 (xy)=(x mod py mod p)×⎛⎝⌊xp⌋
2017-11-08 16:33:00
365
原创 51nod 1743雪之国度【最小生成树】【LCA】【并查集】
Description雪之国度有N座城市，依次编号为1到N，又有M条道路连接了其中的城市，每一条道路都连接了不同的2个城市，任何两座不同的城市之间可能不止一条道路。 雪之女王赋予了每一座城市不同的能量，其中第i座城市被赋予的能量为Wi。 如果城市u和v之间有一条道路，那么只要此刻雪之女王的能量不小于|Wu-Wv|，这条道路就是安全的。 如果城市u和v之间存在两条没有重复道路的安全路径（其中每一
2017-11-07 21:11:51
378
原创 BZOJ 1042: [HAOI2008]硬币购物【容斥】【01背包】
Description 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。题解如果没有个数限制，那么这题就是裸的01背包。可以考虑先求出没有限制的方案，这个可以直接01背包，现在我们知道的是没有限制的方案数，要求的是满足所有限制的方案数，考虑容斥，只要能够求出满足特定的条件的方案，就可以利用容
2017-11-06 16:17:14
267
原创 51nod 1398 等公交【概率DP】
Description小镇的公交车站里有N辆公交，标号为0,1,2，…,N-1。这个小镇的公交运作模式比较奇葩，当必须有一辆车离开车站时，系统会随机从N辆车中选择一辆车，其中任意一辆车i被选中的概率为prob[i]/100，当车i被选中后它会离开车站，并且在之后的time[i]的时间内完成它的行程并返回车站。然后系统又开始随机选N辆车之一（存在同一辆车被连续多次选中的可能）。这个车站在0时刻发出第一
2017-11-04 17:47:26
331
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人