CR1SceNT-CSDN博客

原创 2018-2019 ACM-ICPC, Asia Jiaozuo H - Can You Solve the Harder Problem?

Portal：GYM-102028H题意：求所有本质不同子序列的最大值的和。思路：参考本质不同的子串做法处理本质不同子序列：后缀数组，heightheightheight部分的子串就是没有贡献的子串。考虑以位置 iii 为左端点的所有子串答案的求法，找到 iii 后第一个大于 a[i]a[i]a[i] 的位置 PosPosPos 。 sum[i]=a[i]∗(Pos−i)+sum[...

2019-04-03 11:25:08 838

原创老年（已退役）选手复习计划 PART2

放上来有些符号产生了一点偏差。。不知道怎么变成了问号。。比较懒懒得改了。。意会，意会。。2017.7.4：概率与期望： 1.BZOJ1415：预处理p[x][y]表示，猫在x，鼠在y时猫下一步走哪里。然后记忆化搜索。 2.BZOJ3450：再求一个期望长度就好解决了。斜率优化： 1.BZOJ1010：推式子。 2.BZOJ1096：同上。 3.BZOJ3156：同上。 4.BZOJ3

2017-07-25 15:53:51 609

原创老年（已退役）选手复习计划 PART1

HN集训的时候电脑坏了。。。回来以后拿去修结果去NOINOI都没能带自己的电脑。。也没来得及发这个东西了。。妈耶能拿分的题知识点我没复习到，果然NOINOI全程血妈崩哦。退役选手还是散发一点点的光和热吧QAQQAQ。一篇放不下。。分两篇放。2017.6.29: 网络流: 1.BZOJ1391：shabi题，中间连租用费用即可。 2.BZOJ2132：相邻不取不同的获得额外收益，那么将矩阵黑

2017-07-25 15:48:59 707

原创 BZOJ4028: [HEOI2015]公约数数列

BZOJ4028看着这么神的题，最后发现是个“聪明人”打的暴力。。首先进行分块，维护每一块内的Gcd和XorGcd和Xor，每个块内存下二元组x,Xorx,Xor表示位置和当前位置的亦或值，按照亦或值为第一关键字排序。对于一次修改就将块内信息重新维护，每次O(n√logn√)O(\sqrt{n}log_{\sqrt{n}}) 对于一次询问，记LastGcd,LastXorLastGcd,L

2017-06-16 11:16:35 525

原创 BZOJ3994: [SDOI2015]约数个数和

BZOJ3994d(x)为x的约数个数d(x)为x的约数个数求∑ni=1∑mj=1d(i,j)\sum_{i=1}^n\sum_{j=1}^m d(i,j) 有个很神奇的结论。。上式=∑i=1n∑j=1m[gcd(i,j)==1]ni∗mj上式=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==1] {\frac{n}{i}*\frac{m}{j}} QnQQnQ像我这样

2017-06-16 10:34:08 775

原创 BZOJ4177: Mike的农场

BZOJ4177MDMD考的时候还想半天，这TMTM不就是文理分科吗。真的sbsb了。赶紧退役算了。。 SS向nn个点连边（S,i,ai）（S,i,a_i） nn个点向TT连边（i,T,bi）（i,T,b_i）对于mm每条规则(i,j,k)(i,j,k)，连边(i,j,k)(i,j,k)和(j,i,k)(j,i,k) kk个额外收益，如果是都取aa获得收益，就建新点，SS连向新点，然后该点

2017-06-16 10:06:34 659

原创 BZOJ4170: 极光

BZOJ4170对于graze(x,y)=|x−y|+|a[x]−a[y]|<=kgraze(x,y)=|x-y|+|a[x]-a[y]|<=k 将位置看做xx坐标，aa值看做yy坐标。就是求和某个点的曼哈顿距离小于等于kk的点数个数。发现这个范围是一个菱形。将坐标系旋转一下。(x,y)(x,y)变成(x−y,x+y)(x-y,x+y)，从曼哈顿距离变成切比雪夫距离。也就变成了求某个正方形内点

2017-06-16 09:57:42 538

原创 BZOJ4169: Lmc的游戏

BZOJ416930分的暴力，当n<=10n<=10时，还是很好做的辣、就是给每个叶子节点固定权值。然后树形dpdp就可以了，因为一个点被先手或是被后手取是确定的，就很好写了。n<=200000n<=200000时肯定就不能枚举了。。既然无法确定叶节点权值，那么转化一下，dpdp不求具体值是多少，改为求第几大。 fxf_x表示当前点取最大的是第几大，gxg_x表示当前点取最小的是第几小。

2017-06-16 09:24:38 413

原创 BZOJ4027: [HEOI2015]兔子与樱花

BZOJ4027一开始想的都是二维的dpdp。。数据这么大怎么转移啊QAQQAQ。后来发现原来贪心就行辣。。。直接记ansi=soni+cians_i=son_i+c_i，那么将这个点删除对应着其父节点+=ansi−1+=ans_i-1 那么对于某个点xx，将儿子的ansans值从小到大排徐，然后依次删直到不能删为止。然后删下面的比删上面的优。因为删某个点xx的儿子节点，有影响的只

2017-06-16 08:39:59 456

原创 BZOJ4517: [Sdoi2016]排列计数

BZOJ4517对于一组数据n,mn,m。ans=Cmn∗dp[n−m]ans=C_n^m*dp[n-m] dp[i]dp[i]表示ii的错排数。那就是考虑如何求dpdp数组了。求dpndp_n： 1.将第nn个数放入前n−1n-1个任意一个中，有n−1n-1种，记放的位子为kk. 2.kk若放在位置nn，那就相当于剩下n−2n-2个错排，也就是dp[n−2]dp[n-2]种方案。kk若不

2017-06-12 17:03:00 427

原创 BZOJ4516: [Sdoi2016]生成魔咒

BZOJ4516每次在结尾添加一个数，相当于添加一个前缀。那么倒过来看，变成每次在开头添加一个数，也就是添加一个后缀。假若新的后缀长为xx，那么相当于在原有的基础上增加了xx个串,假设其中有yy个串已经出现过。那么ansi=ansi−1+x−yans_i=ans_{i-1}+x-y 考虑如何求这个yy 考虑新加入的串和已有串的冲突。假设新串s=aadds=aadd，原有串ss=add

2017-06-12 16:47:19 311

原创 BZOJ4514: [Sdoi2016]数字配对

BZOJ4514看到题目很容易发现是最大费用最大流。关键点就是如何分成二分图。（QAQQAQ涨姿势了）把每个aa分解质因数： a=∏pixia=\prod {p_i}^{x_i} 记Numi=∑xNum_i=\sum x那么可以发现可以根据NumiNum_i的奇偶性构造二分图。然后正常建图。若NumiNum_i为奇数，连边(S,i,bi,0)(S,i,b_i,0),否则连边(i,

2017-06-10 16:22:23 786

原创 BZOJ4031: [HEOI2015]小Z的房间

BZOJ4031任意两点若都不是柱子，视为可连边。然后矩阵树定理就好。【代码】#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <queue>#define N 200005#define Mod 1000000000#define

2017-06-10 08:52:11 333

原创 BZOJ4596: [Shoi2016]黑暗前的幻想乡

BZOJ4596题意：有NN个城市，N−1N-1个公司，每个公司可以修建的路有mim_i条。让每个公司修一条路，使得NN个城市构成一棵树。求方案数。学习了一下高斯消元的辗转相除做法。QAQQAQ，伏地膜。那么这个题容斥一下，N−1N-1个人的方案数-N−2N-2个人的方案数+N−3N-3个人的方案数…… 分别用矩阵树定理算出答案。复杂度O(2n∗n3)O(2^n*n^3)【代码】#inc

2017-06-10 08:14:48 569

原创 BZOJ4597: [Shoi2016]随机序列

BZOJ4597一开始看题一脸不可做的样子。。肯定又有什么鬼畜的结论QAQQAQ。（看看题解之后）。。和加减没什么关系。。维护一下前缀积的和就好了。 QAQQAQ然后自己拿n=3n=3手写试了一发。。md为什么不自己想。。 ans=∑i=1n−1(2∗3n−i−1∗∏j=1iai)+∏j=1naians=\sum_{i=1}^{n-1}(2*3^{n-i-1}*\prod_{j=1}^ia_

2017-06-09 20:30:47 421

原创 BZOJ4592: [Shoi2015]脑洞治疗仪

BZOJ4592（吐槽一下dsydsy，我=这个数据=了一天我xxx！！xxx！！）一开始看到这个题。诶，区间连续最大和诶！把脑洞的值为1，正常的赋为−INF-INF 但是操作1怎么办。。发现就是先统计出l0到r0l0到r0区间内−INF-INF的个数tottot，然后区间赋为1. 然后统计l1到r1l1到r1区间内1的个数TotTot，如果tot>Tottot>Tot就直接区间赋值了嘛。

2017-06-09 20:20:02 534

原创 BZOJ4590: [Shoi2015]自动刷题机

BZOJ4590sbsb二分题我CTM-1打成-2！！？判无解的时候都要checkcheck一下。。不能=0就出-1.【代码】#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <queue>#define N 100005#defi

2017-06-08 18:25:11 369

原创 BZOJ1907: 树的路径覆盖

BZOJ1907其实挺sbsb的一个树形dpdp。。我这种sbsb都会的树形dpdp。。。。我的做法很鬼畜。 fx,0，fx,1f_{x,0}，f_{x,1}分别表示点xx作为转折点（也就是连成一个VV字形）/非转折点，覆盖该子树的最小路径数。记vv为xx的儿子节点，sum=∑min(fv,0,fv,1)sum=\sum min(f_{v,0},f_{v,1}). Mn,mnMn,mn为

2017-06-08 17:23:14 462

原创 BZOJ4598: [Sdoi2016]模式字符串

BZOJ4598求树上满足某些条件的点对，首先就可以想到点分治。然后又与什么字符串匹配有关。KMP,AC自动机……KMP,AC自动机……之类的好像不太好用。。那就哈希吧！添加答案的时候有两种情况：那么就分别维护从上到下的链和从下到上的链。不是所有链都存的，仅当“从该点到当前根的一段是若干个模式串的前缀或者后缀”时才存。发现当长度为aa时，不仅m−am-a可以更新答案，长度为km−ak

2017-06-08 15:56:17 541

原创 BZOJ4815: [Cqoi2017]小Q的表格

BZOJ4815b×f(a,a+b)=(a+b)∗f(a,b)b×f(a,a+b)=(a+b)*f(a,b)很像辗转相减法。。那么每次修改点(a,b)(a,b)的值，会修改所有满足gcd(i,j)==gcd(a,b)gcd(i,j)==gcd(a,b)的点(i,j)(i,j)的值。记d=gcd(a,b)d=gcd(a,b)，那么fi,j=x∗i/d∗j/df_{i,j}=x*i/d*j/d(

2017-06-08 15:25:04 623

原创 BZOJ4873: [Shoi2017]寿司餐厅

BZOJ4873。。感觉网络流题目做的也不少了。。可是拿到了还是不会QAQQAQ 一开始把mx2+cxmx^2+cx的xx看成了取的该种寿司的个数。。。所求答案是获得的美味度之和减去花费。可以联想到最大权闭合子图。然后考虑一下依赖关系。首先可以想到源向每个区间连边，边权为Di,jD_{i,j}，这是收益。在考虑花费，每一种寿司向汇连边，花费应该是mx2+cxmx^2+cx，可是这个

2017-06-08 14:16:02 791

原创 BZOJ4818: [Sdoi2017]序列计数

BZOJ4818容斥一下，变成任取不超过mm的nn个数且和为pp的倍数的方案数-任取不超过mm的nn个合数且和为pp的倍数的方案数。令fi,jf_{i,j}表示ii个数，模p=jp=j的方案数。容易写出方程： for(i=1……n)for(i=1……n) for(j=0……p−1)for(j=0……p-1) for(k=1……m)for(k=1……m) fi,(j+k)Mod

2017-06-06 19:57:52 608

原创 BZOJ4870: [Shoi2017]组合数问题

BZOJ4870。。估计大多数人都是看题推式子。。然后各种码逆元。。CRTCRT。。LucasLucas定理等奇奇怪怪的东西。。然后还发现拿不了满分。。最后看到题解，就各种憋住的**破口而出。。其实题目就是求nknk个数中，取得的数模kk为rr的方案数。。显然有fi,j=fi−1,j−1+fi−1,jf_{i,j}=f_{i-1,j-1}+f_{i-1,j}(fi,0=fi−1,0+fi−1

2017-06-06 19:25:35 480

原创 BZOJ4868: [Shoi2017]期末考试

BZOJ4868我的做法好像有点奇葩。。用的二分。说一下自己的思路。先将数组tt和bb排序，记mn=t1mn=t_1,mx=bmmx=b_m。分别表示最早的想知道成绩的时间，和最晚的发布成绩的时间。那么调整发布成绩的最晚时间只会在mnmn到mxmx之间。如果mx<=mnmx<=mn直接输出0. 假如确定了发布成绩的最晚时间tt。那么Ans=调整发布成绩的最晚时间到t的代价+

2017-06-06 19:13:07 617

原创 BZOJ4810: [Ynoi2017]由乃的玉米田

BZOJ4810巧妙地利用bitsetbitset。 QAQQAQ可能只是我弱没看出来。莫队还是很容易看出来的。然后就是统计一下每一个值出现的个数。用cntcnt数组记录。对于操作3乘法而言，直接枚举因数，暴力判断一下就可以了。用一个bitsetfbitset_f记录每个值是否出现过。那么对于操作1减法来说，就直接将ff左移xx位，然后且上原集ff，判断是否有交就可以了。这个应

2017-06-06 18:40:23 672

原创 BZOJ4850: [Jsoi2016]灯塔

BZOJ4850很容易发现sqrt(|i−j|)sqrt(|i-j|)很多情况下都是相等的。那么就可以考虑分块。(题目应该是hj≤hi+p−sqrt(|i−j|)hj≤hi+p-sqrt(|i-j|)) 当sqrt(|i−j|)=xsqrt(|i-j|)=x时，令MxMx为所有满足sqrt(|i−j|)=xsqrt(|i-j|)=x的jj中，最大的hjh_j值。那么p>=Mx+sqrt(|

2017-06-06 18:22:20 695

原创 BZOJ3670: [Noi2014]动物园

BZOJ3670一开始想O(n)O(n)的算法，打半天是错的。然后发现直接暴力翻就可以了。那这样的话就先正常做KMPKMP，然后求出“即是后缀又是前缀，且前缀与后缀可重叠的字符串数量NumiNum_i” 之后翻到一个最后的且长度为当前一半以内的位子jj。numi=Numjnum_i=Num_j【代码】#include <cstdio>#include <iostream>#includ

2017-06-06 18:06:19 263

原创 BZOJ2976: [Poi2002]出圈游戏

BZOJ2976QAQQAQ总算自己做出来一个题。第ii轮有n−i+1n-i+1个人，记为mim_i，nn只有20，暴力算出该轮出圈的是第几个，记为rir_i。那么就可以列出方程： Ans≡r1 mod m1Ans\equiv r_1\space mod \space m_1 Ans≡r2 mod m2Ans\equiv r_2\space mod \space m_2 ⋮

2017-06-02 14:24:56 725

原创 BZOJ3656: 异或

BZOJ3656据说这个题是Cmn mod PC_n^m\space mod \space P 就做了。。。一个位置pp写成了pcpcwa了不知道多少遍。。【代码】#include <cstdio>#include <iostream>#include <algorithm>#define N 100005#define INF 0x7fffffffusing namespace st

2017-06-02 08:41:37 496

原创 BZOJ2982: combination

BZOJ2982LucasLucas定理模板题【代码】#include <cstdio>#include <iostream>#include <algorithm>#define N 10007#define mod 10007#define INF 0x7fffffffusing namespace std;typedef long long ll;ll read(){

2017-06-01 19:10:41 326

原创 BZOJ3129: [Sdoi2013]方程

BZOJ3129挺好的一道题呀。其实pp只会有三个值10007,262203414,437367875 将三个值分解质因数最大的也只有1012101^2。数组可以开的下，不然就不可做了。首先考虑没有限制。每一个任取，那就是隔板法 ans=Cn−1m−1ans=C_{m-1}^{n-1} 对于xi>=aix_i>=a_i的限制，可以看做，第ii个预先放好ai−1a_i-1个，将mm减去ai

2017-06-01 18:41:35 484

原创 BZOJ1407: [Noi2002]Savage

BZOJ1407直接枚举mm，然后n2n^2判断。为了方便处理，将所有CiC_i先-1. 对于任意两个野人i,ji,j，令他们第xx天相遇则有(Ci+x∗pi)mod M=(Cj+x∗pj)mod M(C_i+x*p_i)mod \space M=(C_j+x*p_j)mod \space M (Ci−Cj)=x(pj−pi)mod M(C_i-C_j)=x(p_j-p_i) mod \

2017-06-01 14:44:41 307

原创 BZOJ1951: [Sdoi2010]古代猪文

BZOJ1951又是一个被卡了很久的题。。差点就对指数取模了QAQQAQ，然后突然发现有问题。。就傻掉了这该怎么做。 ans=G∑d|nCdnmodPans=G^{\sum_{d|n}C_{n}^{d}} mod P 根据费马小定理(G,P)互质(G,P)互质，一个数GG的P−1P-1次方在模PP意义下为1. 那么ans=G∑d|nCdnmod (P−1)mod P那么ans=G^{\su

2017-06-01 08:51:06 760

原创 BZOJ 2142: 礼物

BZOJ2142令sk=∑ki=1wis_k=\sum_{i=1}^k w_i ans=∏i=1mCwin−si−1ans=\prod_{i=1}^m C_{n-s_{i-1}}^{w_i} 展开一下。ans=n!∏mi=1wi!∗(n−sm)!ans=\frac{n!}{\prod_{i=1}^mw_i!*(n-s_m)!} 因为pp不是质数，将pp分解质因数后，对于每一个因子分别处理然后C

2017-05-31 17:18:21 305

原创 BZOJ2521: [Shoi2010]最小生成树

BZOJ2521QAQ一开始看到这个题就想到了BZOJ2561 然而瞬间否定，这两个题应该不太一样。神flag！flag！先说说一开始错的想法错在哪吧。。可以直接passpass：（一开始想的是类似次小生成树的做法，先做最小生成树，排序时若有多个边长与z[lab]相同的边，把lab放到最后，然后MST，如果边lab没出现，直接返回。然而发现这样还是有可能有其他解使得不考虑边lab，MS

2017-05-29 11:00:29 824

原创 POJ2891Strange Way to Express Integers

POJ2891mi不互质时解同余方程组存一发模板吧QAQ 讲解看看：这里那个为什么要mod (m2/d)还是想了很久。。大概就是最后要在mod（m2*m1/d）意义下，然后带入到x=m1∗t1+a1x=m1∗t1+a1中乘了m1m1，所以前面mod（m2∗m1/d）mod（m2*m1/d）就可以满足条件。【代码】#include <cstdio>#include <iostream>

2017-05-28 20:58:57 330

原创 POJ1006：Biorhythms

POJ1006有三个周期，分别为23,28,33天。一个周期中有一天为峰值。给出三个峰值日期，和当前日期，求最少要经过多少天，三个峰值同时出现。中国剩余定理模板题。【代码】#include <cstdio>#include <iostream>#include <algorithm>#define N 2335#define INF 0x7fffffffusing namespace

2017-05-28 11:43:19 351

原创 BZOJ4591: [Shoi2015]超能粒子炮·改

BZOJ4591根据LucasLucas定理推出ans=∑i=02332Cin mod 2333∗∑j=0k/2333−1Cjn/2333+Ck/2333n/2333∗∑i=0k mod 2333Cin mod 2333ans=\sum_{i=0}^{2332}C_{n \space mod\space 2333}^i*\sum_{j=0}^{k/2333-1}C_{n/2333}^j+C_{n/2

2017-05-27 18:42:44 470

原创 BZOJ2111: [ZJOI2010]Perm 排列计数

BZOJ2111根据题目所给信息，要求所有2<=i<=N2<=i<=N时，满足Pi>Pi/2P_i>P_{i/2} 列一下，就是：p2>p1p_2>p_1,p3>p1p_3>p_1,p4>p2p_4>p_2,p5>p2p_5>p_2,p6>p3p_6>p_3,p7>p3p_7>p_3 发现很像一颗二叉树！就是一颗二叉树。。满足根节点小于两个儿子节点。然后显然有子结构，可以dpdp 对于

2017-05-27 11:48:26 347

原创 BZOJ4403: 序列统计

BZOJ4403求非降序列可以考虑将每一个位置加上i，变成求严格上升序列。那么长度为ii，范围在l到rl到r之间的方案数为Cii+r−lC_{i+r-l}^i 令M=r−l+1M=r-l+1ans=∑i=1nCiM+i−1ans=\sum_{i=1}^n{C_{M+i-1}^{i}}=C1M+C2M+1+C3M+2+…+CNM+N−1=C_{M}^1+C_{M+1}^{2}+C_{M+2}^

2017-05-27 10:22:28 446

空空如也

空空如也