3 Sdywolf

尚未进行身份认证

沃是一只蒟蒻

等级
TA的排名 4w+

【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\choosem-1,然后就是一波骚操作:由(xy)=(x−1y)+(x−1y−1)(xy)=(x−1y)+(x−1y−1){x\choosey}={x-1\choosey}...

2018-08-29 20:05:31

【BZOJ】【中国剩余定理】1951: [Sdoi2010]古代猪文

题意求G∑i|n(ni)(mod999911659)G∑i|n(ni)(mod999911659)G^{\sum_{i|n}{n\choosei}}\pmod{999911659}题解由费马小定理ap−1≡1(modp)ap−1≡1(modp)a^{p-1}\equiv1\pmodp得G∑i|n(ni)(modtt)=G∑i|n(ni)(modtt−1...

2018-08-27 20:25:15

【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

【线段树维护矩阵转移】【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

【区间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

【UOJ】【kruskal重构树】【NOI2018】归程

按照高度建最大生成树,构造kruskal重构树,每次连边时新建一个节点表示边权连到两端的父亲上。这样一棵树满足小根堆的性质。所以可以倍增跳到最顶端,然后答案就是子树里的最小权值(这里的权值为到1的最短路)。代码#include<cstdio>#include<cstring>#include<algorithm>#include<queu...

2018-08-18 22:29:21

【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\geqslant0,i+j\geqslantk|A_{v+i,u+j}+={i+j\choosei},考虑组合意义,从(v,u)(v,u)(v,u)开始每次往右或往下走,走大于等于kkk布的方案数,直接DP。#include<cstdio>...

2018-08-13 20:48:54

【UOJ】UER#3.A 开学前的作文

找规律。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intT,n,m,ans;intmain(){freopen("A.in","r",stdin);freopen("A.out","w",stdout);sc

2018-08-13 20:47:25

【容斥】Topcoder SRM div1-3 12004. SetAndSet

取反,变成or和相同。同一位,为1的不能放在同一边,并查集加容斥搞。第一次在TC上做题,机制轻喷。。。代码#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<vector>usingnamespacest...

2018-08-07 22:29:22

【ZROI】【数学相关】【计数问题】【17 提高 6】异或统计

首先考虑这个问题的简化版:求∑(ai xor aj)∗(aj xor ak)∑(ai xor aj)∗(aj xor ak)\sum(ai\xor\aj)*(aj\xor\ak),这就等价于求∑j((∑ai xor aj)(∑aj&a

2018-07-08 20:42:47

【ZROI】【数学相关】【17 提高 5】剪刀石头布

根据期望的线性性,可以计算获胜盘数的期望为wa∗∑bi+wb∗∑ci+wc∗∑aiwa∗∑bi+wb∗∑ci+wc∗∑aiwa*\sumbi+wb*\sumci+wc*\sumai,然后分类讨论,由于wa和wb都不会为0,所以∑bi=∑c[i]∑bi=∑c[i]\sumbi=\sumc[i],并且,如果wa+wb=1e9wa+wb=1e9wa+wb=1e9,那么∑bi<=∑ai∑b...

2018-07-08 20:41:54

【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>=a−1c>=a−1c>=a-1,...

2018-07-08 20:41:24

【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

【ZROI】【DP】【17 提高 3】建造

假设我们已经确定了一个建造的顺序,那么如何计算按照这个顺序建造的方案数?这就相当于确定一个数组d,其中∑di<=X∑di<=X\sumd_idi>=max{hi,hi+1}di>=max{hi,hi+1}d_i>=max\{h_i,h_{i+1}\},为了方便起见,记∑max{hi,hi+1}=S∑max{hi,hi+1}=S\summax\{h_i,h_{i+1}\}...

2018-07-08 20:40:02

【ZROI】【高维前缀和】【lucas定理】【17 提高 2】World Of Our Own

第3步a0^a1^a1^a2^a1^a2^a2^a3第2步a0^a1^a1^a2a1^a2^a2^a3第1步a0^a1a1^a2a2^a3第0步a0a1a2a3每次的合并操作相当于每个数往上走一步或是往左上走一步,那么,最终第iii个数在第jjj步走到位置0(将原来1~n重新编号为0~n-1,这样可以方便计算)的方案数为C...

2018-07-08 20:39:23

【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

【数位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

【康复训练】【cdq分治】【BZOJ】3295: [Cqoi2011]动态逆序对

Description对于序列A,它的逆序对数定义为满足i题解cdq分治.将删除操作倒序看就是加入操作,然后就是一个经典的三位偏序问题了。代码#include<cstdio>#include<cstring>#include<algorithm>#definemaxn100006#definemaxm50006#...

2018-05-30 17:12:27

Emacs配置

(custom-set-variables;;custom-set-variableswasaddedbyCustom.;;Ifyouedititbyhand,youcouldmessitup,sobecareful.;;Yourinitfileshouldcontainonlyonesuchinstance.;;I...

2018-05-27 19:24:17

【康复训练】【主席树】【BZOJ】1112: [POI2008]砖块Klo

DescriptionN柱砖,希望有连续K柱的高度是一样的.你可以选择以下两个动作1:从某柱砖的顶端拿一块砖出来,丢掉不要了.2:从仓库中拿出一块砖,放到另一柱.仓库无限大.现在希望用最小次数的动作完成任务.题解主席树。只要求出中位数、比中位数小的数的总和和个数、比中位数大的数的总和和个数。代码#include<cstdio>#include<c...

2018-05-27 16:34:28

查看更多

勋章 我的勋章
    暂无奖章