- 博客(123)
- 收藏
- 关注
RSS订阅原创 2021牛客多校第一场I Increasing Subsequence-期望DP
[传送门][https://ac.nowcoder.com/acm/contest/11166/I]题意：一个长为nnn的排列，有两个人轮流从中取数，每一轮中所取的数需要满足如下规则：取的数大于之前所有人取的数取的数的下标大于取数人之前取的数的下标如果有多种取数方案，则随机进行取数第一个人第一次取数随机如果有人没法再取数，游戏结束求最后期望能取数多少次。N≤5000N\leq 5000N≤5000Solution:期望DP，比赛时最后想到了做法但是没写完，晚上调了调就过了。首先
2021-08-18 14:53:10
191
原创 Codeforces 1542E Abnormal Permutation Pairs-DP
传送门题意给定n，modn，modn，mod，求有多少对(p,q)(p,q)(p,q)满足：1.p,qp,qp,q是长度为n的排列2.ppp的字典序大于qqq3.ppp的逆序对数小于qqq答案对modmodmod取模Case 1:n≤50Case \ 1:n\leq 50Case 1:n≤50Case 2:n≤500Case \ 2:n\leq 500Case 2:n≤500SolutionCase 1先考虑Case1，首先用f[i][j]f[
2021-07-04 17:45:13
259
原创 Codeforces 1485F-Copy or Prefix Sum-DP
Codeforces 1485F-Copy or Prefix Sum-DP题意给你一个n个数的序列bbb求有多少个序列aaa满足对于每个i(1≤i≤n)i(1\leq i\leq n)i(1≤i≤n)，至少满足以下两个条件之一：1.bi=aib_i=a_ibi=ai2.bi=∑j=1iajb_i=\sum_{j=1}^ia_jbi=∑j=1iajn≤2∗105n\leq 2*10^5n≤2∗105Solution最朴素的DP：dpi,jdp_{i,j}dpi,j表示前i个数和
2021-02-17 17:06:30
230
原创 Codeforces 1485E Move and Swap-DP
Codeforces 1485E Move and Swap-DP传送门题意：一棵n个节点的树，叶子节点的深度都相同，每个节点有一个权值aia_iai，有红蓝两个棋子，初始在根节点1，每轮进行三步操作：1.红棋子移动到当前所在节点的儿子上2.蓝棋子移动到当前节点层数+1的任意一个节点3.交换红蓝两个棋子（可选）移动到叶子节点后终止移动每轮移动后获得的分数为棋子所在位置的权值差的绝对值，求最大分数和。n≤2∗105n\leq 2*10^5n≤2∗105Solution：我们分层进行处理
2021-02-17 17:05:49
161
原创 hdu6899 CCPC2020网络赛 1012 Xor-数位DP
hdu6899 CCPC2020网络赛 1012 Xor-数位DP题意：T次询问，每次给出A,B,K,W，求满足下面条件的(x,y)对数：1.x,y是整数2.x∈[0,A],y∈[0,B]x \in [0,A],y\in[0,B]x∈[0,A],y∈[0,B]3.∣x−y∣≤K|x-y|\leq K∣x−y∣≤K4.x xor y≤Wx~ xor~ y\leq Wx xor y≤WA,B,K,W≤109,T≤2000A,B,K,W\leq10^9,T\l
2020-09-29 17:56:26
321
原创 牛客第7场I-Valuable Forests prufer序列+DP
传送门题意：定义一个无根树的权值为所有点的度数的和，求有标号的n个点形成的所有森林的权值的和。T≤5000,N≤5000T\leq 5000,N \leq 5000T≤5000,N≤5000Solution:比赛时脑抽，考完五分钟后过了…由prufer序列的结论可得，对于n个点的无根树，可以形成nn−2n^{n-2}nn−2个不同的树，我们记他的值为stnst_nstn,那么对于n个点的森林的个数fnf_nfn，我们可以求得DP式子：f(n)=∑i=0n−1Cn−1if(n−i−1)∗st
2020-08-01 21:31:56
376
2
原创 CF888G&牛客多校第五场B-异或最小生成树
先看CF的这道题：题意：传送门有n个点，每个点有一个权值aia_iai，任意两点之间边的权值是这两点权值的异或和，求最小生成树n≤2e5,ai<230n \leq 2e5, a_i< 2^{30}n≤2e5,ai<230Solution:首先需要先介绍一种叫做Boruvka的最小生成树算法，算法流程类似Kruskal，对于每个连通块，在他和其他连通块之间找一个最小的边相连，因为每次都会合并一半的连通块，所以复杂度为O（mlogn）O（m \log n）O（mlogn）那
2020-07-26 19:11:42
257
1
原创 Codeforces1295F Good Contest-DP
##题目大意：传送门长度为 nnn 的数列，第 iii 个数可能的值为[li,ri][l_i,r_i][li,ri]，求数列为不严格单调递减数列的期望。（2≤n≤50,0≤li≤ri≤1e9）（2\leq n \leq 50,0 \leq l_i \leq r_i \leq 1e9）（2≤n≤50,0≤li≤ri≤1e9）##Solution:我们把这些区间分割成两两之间不互相覆盖...
2020-01-30 23:13:37
440
3
原创 退役啦~~~
本来给了13个D类名额，我排12，但是由于一个学校最多只能有两个D所以被卡了学校名额QAQ退役后就去搞文化课了，明年高考完可能会再继续更新博客翘了一年文化课不知道从何补起QAQ人生不如意十之八九你好，文化课生活。...
2018-06-13 18:36:19
687
4
原创 洛谷P3830 [SHOI2012]随机树-期望DP
传送门题意：一棵含有n个叶子节点的二叉树通过如下方式生成：每次等概率的随机选择一个叶子节点，将这个节点加上左右两个子节点求：1.叶子节点平均深度的期望2.树深度的期望n≤100n≤100n\leq 100Solution:第一问很好处理：设fxfxf_x表示有x个叶子节点的树的叶子节点平均深度我们考虑在一个有x-1个叶子节点的树里随机选择一个叶子节点展开...
2018-06-07 13:06:03
700
原创 BZOJ5068: 友好的生物-枚举
传送门题意：n种生物，每种生物i有k个属性ai,jai,ja_{i,j}，两种生物之间的友好程度为Friendliness=(∑k−1i=1Ci∗di)−CK∗dKFriendliness=(∑i=1k−1Ci∗di)−CK∗dKFriendliness=(\sum_{i=1}^{k-1} C_i*d_i)-C_K*d_K其中 CiCiC_i是非负常数， didid_i是属性 i ...
2018-06-07 13:05:06
438
原创 BZOJ2727: [HNOI2012]双十字-树状数组
传送门题意：给定一个R∗CR∗CR*C的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。双十字由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制：1.两条水平的线段不能在相邻的两行。2.竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。3.竖直线段必须将两条水平线段严格划分成相等的两半。4.上方的水平线段必须严格短于下方的水平线段。...
2018-06-05 11:25:36
421
原创 BZOJ4565: [Haoi2016]字符合并-区间DP+状压DP
传送门题意：有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。1≤n≤300,0≤ci≤1,1≤wi≤109,k≤81≤n≤300,0≤ci≤1,1≤wi≤109,k≤81\leq n\leq 300,0\leq ci\leq 1,1\leq wi\leq 10^9,...
2018-06-04 08:33:34
278
原创 BZOJ2734: [HNOI2012]集合选数-状压DP
传送门题意：给出n，求出{1,...,n}{1,...,n}\{1,...,n\}的所有满足以 下条件的子集数量：若 x 在该子集中，则 2x 和 3x 不能在该子集中。 n≤100000n≤100000n\leq 100000Solution:没见过类似做法的人见到这道题真的是毫无思路啊…构造矩阵形如 ⎛⎝⎜⎜⎜⎜⎜⎜1248...361224...9183672.....
2018-06-02 23:23:54
271
原创 BZOJ2669: [cqoi2012]局部极小值-状压DP+容斥
传送门题意:有一个n行m列的整数矩阵，其中1到n∗mn∗mn*m之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，判断有多少个可能的矩阵。 (1≤n≤4,1≤m≤7)(1≤n≤4,1≤m≤7)(1\leq n\leq 4, 1\leq m\leq 7)Solution:显然我们把矩...
2018-06-02 21:48:35
256
原创 BZOJ 3925:[Zjoi2015]地震后的幻想乡-状压DP
传送门题意：给定一个n点m边的无向图，没有重边和自环，每条边的权值为[0,1][0,1][0,1]之间的随机变量，求最小生成树中最大边的期望权值。 n≤10,m≤n(n−1)2n≤10,m≤n(n−1)2n≤10,m≤\frac {n(n−1)}2Solution:题意其实可以转化为选前k小的那些边使图恰好联通，求k的期望答案即为k(m+1)k(m+1)\frac k{...
2018-05-31 16:25:27
251
原创 BZOJ4197: [Noi2015]寿司晚宴-状压DP
传送门题意：n-1个数，分别为2~n，现从中取出若干数放入两个集合中，使A集合中所有数都和B集合中的所有数互质，求满足条件的方案数。n≤500n≤500n≤500Solution:根据题意，在一个集合中选择一个数相当于选择了这个数的质因子集合，所以说两个集合的质因子集合的交集必须为空。一个很简单的想法就是状压DPf[i][S][T]f[i][S][T]f[i][S]...
2018-05-30 20:49:13
226
原创 洛谷P4242 树上的毒瘤-树剖+虚树+点分治
传送门题意：这棵树上有 n 个节点，每个点的初始颜色为 cicic_i 。接下来进行 q 个操作：1.修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。2.对于给定的树上某个点集 S ，定义某个点集内的点的权值为：Wi=∑j∈ST(i,j)Wi=∑j∈ST(i,j)W_i=\sum_{j\in S}T(i,j)其中T(i,j)表示i到j的路径上的颜色的段数每次指...
2018-05-30 14:37:50
487
原创 洛谷P1846 游戏-DP
传送门题意：给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数k1k1k_1和k2k2k_2 ，并删除第一个数列的最后k1k1k_1个数，计算出它们的和s1s1s1；删除第二个数列的最后k2k2k2个数，计算出它们的和s2s2s2。这一次操作的得分就是(s2−k2)∗(s1−k1)(s2−k2)∗(s1−k1)(s_2-k_2 )*(s_1...
2018-05-29 19:04:58
341
原创 AGC24 E - Sequence Growing Hard-树形DP
传送门题意：给出n,k,m，问有多少个序列组(A0,A1,...,An)(A0,A1,...,An)(A_0,A_1,...,A_n)满足以下条件： 序列AiAiA_i的长度恰好为i 所有元素均在[1,k][1,k][1,k]的范围内 Ai−1Ai−1A_{i−1}是AiAiA_i的子序列 AiAiA_i的字典序大于Ai−1Ai−1A_{i−1} 答案模m输出。 n,...
2018-05-22 09:37:37
425
原创 BZOJ5340: [Ctsc2018]假面-期望DP
传送门题意：有 2 个技能：1.锁定：对一名指定的敌方单位使用，以 p 的概率对该单位造成 1 点伤害。2.结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。如果一个单位的生命值降至 0 或 0 以下，那么该单位就会死亡。 现在有 n 个敌方单位（编号从 1 至 n），编号为 i 的敌方单位有 mimim_i 点生命值。 按顺序施放 Q 个技能：1.对于锁...
2018-05-20 11:46:13
236
原创 BZOJ5339: [TJOI2018]教科书般的亵渎-组合数学
传送门题意：在炉石传说中有这样的一个场面：n个随从，血量为1~n，现在去除m个随从，然后开始释放“亵渎”。每使用一张“亵渎”会获得一定的分数，分数计算如下：在使用一张“亵渎”之后，每一个被亵渎造成伤害的怪会产生xkxkx^k的分数，其中x是造成伤害前怪的血量，k是需要杀死所有怪物所需的“亵渎”的张数。n≤1013m≤50n≤1013m≤50n≤10^{13} m≤50Solut...
2018-05-19 22:47:59
1027
原创 BZOJ 2448: 挖油-区间DP+单调队列
题意：[0,x]中全是1，判断[1,n]中的点i中是0还是1需要权值aiaia_i，最坏情况下求得到x的最小权值n<=2000n<=2000nf[i][j]f[i][j]f[i][j]表示只考虑[i,j]，最坏情况下求得到x的最小权值那么f[i][j]=minjk=i(max(f[i][k−1],f[k+1][j])+a[k])f[i][j]=mink=ij(max(f[i...
2018-05-04 12:50:48
487
原创 BZOJ4836: [Lydsy1704月赛]二元运算-分治FFT
传送门题意：定义二元运算 opt 满足x opt y={x+yx−y,,x<yx≥yx opt y={x+y,x<yx−y,x≥yx \ opt \ y =\left\{\begin{aligned}x+y&,&xai opt bj=cai opt bj=ca_i\ opt\ b_j=...
2018-05-02 19:22:05
297
原创 BZOJ4833: [Lydsy1704月赛]最小公倍佩尔数-数论
传送门题意：令(1+2–√)n=e(n)+f(n)∗2–√(1+2)n=e(n)+f(n)∗2(1+\sqrt2)^n=e(n)+f(n)*\sqrt2,其中e(n),f(n)e(n),f(n)e(n),f(n)都是整数。令g(n)g(n)g(n)表示f(1),f(2)…f(n)f(1),f(2)…f(n)f(1),f(2)…f(n)的最小公倍数.给定两个正整数n和p,其中p是...
2018-04-30 21:17:19
507
原创 BZOJ5093: [Lydsy1711月赛]图的价值-斯特林数+FFT
传送门题意：“简单无向图”是指无重边、无自环的无向图（不一定连通）。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大，请对998244353取模输出。1≤n≤109,1≤k≤2000001≤n≤109,1≤k≤2000001≤n≤10^9,1≤k≤200000Solution：易知每个点的...
2018-04-28 13:43:24
274
原创 BZOJ2159: Crash 的文明世界-树形DP+第二类斯特林数
传送门题意：给你k和一棵n个点的树，每个边边权为1，对每个点i求∑nj=1dis(i,j)k∑j=1ndis(i,j)k\sum_{j=1}^ndis(i,j)^kn≤50000 k≤150n≤50000 k≤150n ≤ 50000 \ k ≤ 150Solution:首先有一个结论：xn=∑ni=1Cix∗Sin∗i!xn=∑i=1nCxi∗Sni∗...
2018-04-13 08:05:11
231
原创 BZOJ1063: [Noi2008]道路设计-树形DP
传送门题意：Z国是一棵树，为了使Z国的交通更加便利顺畅，现决定在Z国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。我们定义每条规划路线为一个长度大于1的城市序列，每个城市在该序列中最多出现一次。任意两条规划路线不能有公共部分。一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城...
2018-04-11 11:36:41
229
原创 BZOJ3742: Painting-树形DP+费用流
权限题。题意：给出一颗n个节点的树，要给每一条边染一个1~n-1的颜色，染颜色i的代价为i，要求同一个节点连出的所有边所染颜色都互不相同，求一个为整棵树染色的方案，使得代价之和尽量小n<=150n<=150nf[x][i]f[x][i]f[x][i]表示节点x向其父亲连的边为i时x的子树所产生的最小贡献看似非常不好转移实际上就是非常不好转移所以说我们另辟蹊径——...
2018-04-10 20:50:21
235
原创 BZOJ2459:残缺的字符串-FFT
权限题题意：有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。这两个串已经老化了，每个串都有不同程度的残缺。你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?1<=m<=n<=3000001<=m<=n<=3000001∗∗*看...
2018-04-10 15:59:14
193
原创 BZOJ5250: [2018多省省队联测]秘密袭击-树形DP
传送门题意：给一棵n个点的树，每个点的点权在 1到 W之间求所有连通块的权值第k大的和模 64123k≤n≤1666,W≤1666Solution：正解貌似是线段树合并+FFT 但是我并不会写QAQ所以说我们考虑暴力碾标算：我们可以考虑每个点对于答案的贡献：我们把大于它的点看成1，小于它的点看成0，最后只要求包含它的和为k-1的联通块个数即可，这个可以用一个...
2018-04-10 11:42:27
435
原创 BZOJ5251: [2018多省省队联测]劈配-网络流
传送门题意：有n位选手和m位导师，每位导师战队有容量限制bibib_i。每位选手有一张志愿表。对于每位选手，导师之间允许并列（最多允许C位导师并列）。所有选手有一个排名，选手之间不允许并列。导师录取的规则可以简单概括为：对每位选手，在优先满足更高位选手的前提下，尽可能满足该选手最高位志愿。每位选手有一个理想的志愿s_i（梦想），表示他希望被s_i或更高位的志愿录取。求：...
2018-04-09 14:33:37
290
原创 BZOJ5249：[2018多省省队联测]IIIDX-线段树
传送门题意：你需要给给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目，每首曲目都会有一个难度d，游戏内第i首曲目会在玩家Pass第⌊ik⌋⌊ik⌋\lfloor\frac i k\rfloor首曲目后解锁。安排这些曲目的顺序，使得每次解锁出的子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个i满足di≥d⌊ik⌋di≥d⌊ik⌋d...
2018-04-09 11:53:41
258
原创 SDOI2018游记
第一次参加省选 好紧张QWQ简单的记录一下都发生了什么DAY-1学不进去PWP晚上开包出了张橙 很慌DAY0正逢假期 所以就顺路回了趟老家_(:з」∠)__(:з」∠)__(:з」∠)_在车上补完了京紫 并且得知了京紫要出续集的消息 激动得不行PWP violet天下第一下午到酒店 给房间的门锁坏了 给换了两个大单间hhh这波血赚晚上去试机的时候按照惯例...
2018-04-06 17:22:16
1780
5
原创 BZOJ4767-两双手-DP+容斥
传送门题意：棋盘上的一个棋子，给出他的两种移动方式：1.(u,v)−>(u+Ax,v+Ay)(u,v)−>(u+Ax,v+Ay)(u,v) -> (u+Ax,v+Ay)2.(u,v)−>(u+Bx,v+By)(u,v)−>(u+Bx,v+By)(u,v) -> (u+Bx,v+By)现给出一些不能走的障碍点n个，求(0,0)到(Ex,Ey)的方案数...
2018-03-22 19:18:49
345
原创 BZOJ4516: [Sdoi2016]生成魔咒-后缀数组+线段树+RMQ
传送门题意：给出一个字符串，分别求出前1~n位所含的不同的字符串个数n<=100000n<=100000nO(nlogn)O(nlogn)O(n\log n)代码：#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>...
2018-03-21 18:35:35
257
原创 BZOJ2407:探险/BZOJ4398:福慧双修-最短路+分治
两道都是权限题…题意：给出一张n个点，m条边的图，同一条边不能走两次，每条边正着走与反着走所需要的时间可能不同，求一个从1开始的大于一个点的最短环N<=10000,M<=200000,1<=W,V<=10000N<=10000,M<=200000,1<=W,V<=10000NO(nlog2n)O(nlog2n)O(n\log^2 n)...
2018-03-21 18:14:37
432
原创 洛谷P3911 最小公倍数之和-莫比乌斯反演
传送门题意：给出n个数aiaia_i，求∑ni=1∑nj=1lcm(ai,aj)∑i=1n∑j=1nlcm(ai,aj)\sum_{i=1}^n\sum_{j=1}^n lcm(a_i,a_j)1≤N≤50000;1≤ai≤500001≤N≤50000;1≤ai≤500001 \le N \le 50000; 1 \le a_i \le 50000Solution：再次...
2018-03-21 08:51:48
462
原创 BZOJ4515: [Sdoi2016]游戏-树链剖分+超哥线段树
传送门题意：Alice 和 Bob 在玩一个游戏。游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bo...
2018-03-18 19:25:34
296
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人