Tag_king-CSDN博客

原创 HN集训比赛总结

天天被虐傻哦。。不写点总结就要废掉了。。Day1 T1应该是回文自动机的题，按照我的水平期望应该是40分。。然而我爆0了，因为少打了一对括号而挂在位运算上。。看到这种给几种变换的题如果不是搜索的话就要往DP想，就是状态转移嘛，但是我还是花了一点时间才想到。。时间多就看一看manacher吧。。 T2是LCT，看到题被吓傻，连暴力都不想写。。考场上期望应该是25-40分，看到要子树又不知道怎么

2015-07-05 19:08:05 923

原创 [BZOJ3926]ZJOI2015诸神眷顾的幻想乡|后缀自动机

注意到非常关键的条件，只与一个空地相邻的空地数量不超过20个，也就是叶子不超过20个，这意味着啥？考虑u到v的路径，一定存在某个叶子，当以这个叶子为根的时候u是v的祖先，也就是说所有的序列都是某个叶子为根的树的一条直链，把一棵树看出一个trie那么我们要做的就是统计这最多20个trie拼成的大trie的不重复子串数量啦！陈老师是厉害呀… 窝只会SAM做法。。按大trie建出SAM，然后可以像3

2015-06-20 22:19:09 1003

原创 [BZOJ3998]TJOI2015弦论|后缀自动机

对SAM不太熟做这题想了很久才想清楚。。大爷们的博客都写的好简（我太弱）首先对原串建SAM。。如果能求出f[i]表示以root走到状态i的路径为开头往后能得到的串的数量，我们就可以像线段树那样的查询了（26分？）。。设num[i]为已确定的一条root到i的路径对应的子串数量，当T=0的时候，显然num[i]=1，num[root]=0；对于T=1，root到i的路径对应的串还可以作为另一个

2015-06-20 22:15:19 787

原创 [CODEVS3160]最长公共子串|后缀数组|后缀自动机

第一种做法是把两个字符串接起来，中间放一个奇怪的字符，然后建这个串的后缀数组，求出h数组，对于h[i]表示lcp（sa[i],sa[i-1]），如果sa[i]和sa[i-1]分布在奇怪的字符的两边就用h[i]更新答案。。然后补了一下后缀自动机，就是裸题了，对一个串建SAM，另一个串在上面匹配即可。。 SA:#include<cstdio>#include<iostream>#inclu

2015-06-20 22:05:25 630

首先最少数量显然大于1，那么考虑炸掉一个点，如果它不是割点并没有什么影响，如果是割点的话必须要满足炸开之后的每个联通块都有至少一个救援点。如果这个图没有割点的话选两个点放就行了，答案是C（n，2），否则求出每一个割点，把这个图按割点分割成若干个联通块，把这些联通块缩点就是一个树结构，要使树上任何一条边断掉之后分成的两块都有救援点，就一定要在每一个叶子块上放一个救援点。把所有叶子块的size乘起来就行

2015-06-20 22:00:17 1150

原创 [BZOJ4002]JLOI2015有意义的字符串|矩阵乘法

题目和字符串有啥关系吗。。。熟悉特征方程就容易发现这其实是一个a[n]=c1∗a[n−1]+c2∗a[n−2]a[n]=c_1*a[n-1]+c_2*a[n-2]这样的数列的通项的一部分，a[n]=(b+d√2)n+(b−d√2)na[n]=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n，其中c1=b,c2=d−b24c_1=b,c_2=\

2015-06-20 21:58:14 609

原创 [BZOJ3991]SDOI2015寻宝游戏|set|虚树

询问就是求包含所有宝藏点的最小子图（貌似叫虚树？按dfs序用set维护宝藏点的序列，并把set中相邻点（头和尾也算相邻）在树中路径的距离累加记为sum，删除序列中第i个点时，设前面为l[i]（l[1]=n），后面为ri，把l[i]到i和到r[i]的距离在sum中减去，并加上l[i]到r[i]的距离，插入是也是类似的。。

2015-06-20 21:43:27 1257

原创 [BZOJ2875]NOI2012随机数生成器|矩阵乘法

一开始想用等比数列公式搞，但是模数可能为合数。。然后裸上矩乘，注意要用快速乘要不然会爆long long。#include<cstdio>#include<iostream>#include<cmath>#include<memory.h>#define ll long longusing namespace std;ll m,a,c,x0,n,g,an;struct ju{

2015-06-20 21:40:42 511

原创 [BZOJ3670]NOI2014动物园|KMP

其实这也是一道水题。。自已yy完之后思路乱的要死就挂了。。先求正常的next数组嘛，然后next[i]向i连边，容易发现新next在i到1的路径上，且i往下走，后面点新next也会往下走，然后我们从1 dfs下去，把路径上的点记录下来，然后维护一个新next指针作为参数，由于新next是不会往上爬的所以这是O（N）的，num[i]的话显然等于新next[i]在树上的深度+1，然后就做完了。。

2015-06-20 21:38:06 453

原创 [BZOJ3669]NOI2014魔法森林|LCT|最小生成树

这题证明我有多弱。。noip之前写了一发挂了由于noip不考这个我就没去调了，省选之前写了一发在火车上调了2h未果又弃了，第三次写不记得调了多久才过，最后发现后两次犯的一样的傻逼错误，以一个变量为参数调用两次同样void忘记这个变量在第一次调用时就变了。。不能再蠢。。把边按a升序排序，不断加边，LCT维护b的 MST，不断更新答案就行了。。#include<cstdio>#include<io

2015-06-20 21:36:13 764

原创 [BZOJ3668]NOI2014起床困难综合征|贪心

显然是可以按位做的。我们将二进制第i位初始时为0和1到最后的结果都求出来，扫一遍就行了，之后从高位向低位贪心，如果第i为初始为0能使最后为1这位就为0，否则如果初始为1可以且加上这位不超过m就为1，否则为0。#include<cstdio>#include<iostream>#define N 200005#define inf 0x7fffffffusing namespace std;

2015-06-20 21:34:33 582

原创 Codeforces Round #306 div 2 solution

这场总的来说打的还行吧，不过fst了一题很郁闷。。感觉从pkusc回来看CF的英文题面就和看中文一样。。出AB的速度我觉得还是不错的。。没什么难题完全可以AK的，但是构造题有细节理不清，要加强处理复杂的关系的能力。。A:给一个字符串，问你能不能找到不重复的”BA”和”AB”我的做法是先找AB再找BA和先找BA再找AB各做一次。#include<cstdio>#include<iostream>

2015-06-05 10:13:45 785

原创 FFT多项式乘法学习笔记

其实我不知道我是否真的理解了FFT，但是我会用FFT优化多项式乘法了QAQ。。（以下大多摘自算导前置知识1. 多项式在一个代数域F上，关于变量x的多项式定义为形式和形式表示的函数A(x)=∑j=0n−1ajxj，其中a0…an−1为多项式各项的系数 A(x)=\sum_{j=0}^{n-1}a_jx^j，其中a0…an-1为多项式各项的系数2. 多项式的次数界若多项式有非

2015-06-03 21:41:09 3765

原创 APIO2015 Skulptrues|贪心|DP

考场上这题爆0真是郁闷。。按二进制位从高位开始贪心，当A等于1的时候对每一位记录f[i]f[i]表示前ii个使当前位为0且不与更高位冲突最少分几组，枚举上一块的右端点进行转移；当A>1的时候记录f[i][j]f[i][j]为前ii个分jj组是否能达到，转移同前。。

2015-06-03 21:11:44 495

原创 [POJ1741]Tree |点分治

同样是点分治。。但是这题在合并的时候比较麻烦，假设重心为x，首先要从x向下求出子节点的深度，然后将子节点按深度排序，设排序后第ii个点过重心能到的最远的点为第r[i]r[i]个，那么显然r[i]r[i]是递减的，所以扫一遍就可以求出过重心的路径的贡献了。但是这里面还会用重复计算的，就是在重心的同一颗子树的两个点可能又被计算了，这个时候dfs每棵子树，按上面的方法把同一颗子树重复计算的去除就行了。#i

2015-06-03 21:01:56 470

原创 [BZOJ2152]聪聪可可|树的点分治

学了学点分治，主要思想就是找重心来防止树退化成链这样的东西，感觉写的不是很顺但是1A了。。找到一个部分的重心之后答案变成两部分，一是过重心的路径，二是不过重心的路径，二可以递归地得到，一的话可以对每个重心向下求出每个子节点的深度mod 3，然后记录下余0,1,2的数量，然后0和0组合，1和2组合，要注意排除来自同一颗子树的点对的重复计算，还要注意点对是有顺序的而且可以相同。。#include<ios

2015-06-03 20:52:53 930

原创 [BZOJ3969]WF2013 Low Power|二分答案|贪心

先排序，二分能量差，显然同个机器的两个芯片的电池的最小值是连续的，否则交换之后可以得到更优的解，那么贪心地选取2*n对连续的电池，如果能选出且它们的后面都可以放2*（k-1）个电池的这是一个可行答案。。#include<cstdio>#include<iostream>#include<algorithm>#include<memory.h>#define N 1000005using n

2015-06-03 20:52:39 958

原创 [BZOJ3932]CQOI2015任务查询系统|主席树

CQOI好良心，都是裸题。。把任务差分裸上主席树就行了。。#include<iostream>#include<cstdio>#include<algorithm>#define ll long long #define N 100005#define M 4000010using namespace std;struct task{ int l,r,p;}t[N];st

2015-06-03 20:49:21 883

原创 [BZOJ3997]TJOI2015组合数学|DP

这题的方法感觉比较巧妙，对于(i,j)(i,j)和（i′,j′）（i',j'），当且仅当i>i′i>i’且j<j′j<j’的时候（也就是(i,j)(i,j)在(i′,j′)(i’,j’)的左下方）这两点不可能出现在一条路径上，所以求出一个点集使其中任意两点满足上述条件，这个点集的最大权值和就是答案，那么可以把每一行翻转，做DP，f[i][j]=max(max(f[i−1][j],f[i][j−1]

2015-06-03 20:45:43 801

原创 [BZOJ3931]CQOI2015网络吞吐量|最短路|最大流

网络流大裸题。。把在最短路上的边拉出来建图就行了。。#include<cstdio>#include<iostream>#define N 505#define M 100005#define inf 0x7fffffff#define INF 0x3f3f3f3f3f3f3f3fll#define ll long longusing namespace std;struct ed

2015-06-03 20:40:07 853

原创 [BZOJ3996]TJOI2015线性代数|最小割

一开始没看到是01矩阵。。化简之后发现，D=∑i=1n∑j=1na[i]∗a[j]∗b[i][j]−∑i=1na[i]∗c[i]D=\sum_{i=1}^{n} \sum_{j=1}^{n}a[i]*a[j]*b[i][j]-\sum_{i=1}^{n}a[i]*c[i]那么也就是相当于有n个物品，选了i和j可以得到b[i][j]的收益，但是选i要付出c[i]的代价，经典的最大权闭合子图模型。

2015-06-03 20:37:33 559

原创 [BZOJ4003]JLOI2015城池占领|可并堆

一开始用倍增做，后来发现不但会MLE精度也会炸掉。。学了一下左偏树，然后就是对每个点建一个可并小根堆，然后dfs的时候向上合并，向上的时候要像线段树之类的一样打lazy标记，由于乘的数都是正的所以相对大小不会变，并上去之后不停弹堆顶然后做做记录就行了。。#include<iostream>#include<cstdio>#define ll long long#define N 300005

2015-06-03 20:23:54 921

原创新的征程......

本来以为要退役了呢。。不过运气不错，又可以继续下去。。还是先要吐槽一下JXOI，太坑了，JX出题人是有多懒，连续两年搬CTSC原题上来（虽然我都没做过。。。），据说今年T1是OIBH上的题，呵呵。。第一题不能多说，题意不能再模糊了，又不告诉我什么叫剪成一个图案，又不告诉我什么叫本质相同的图案，问出题人还说题目已经说的很清楚了，wtf！！大概这是JX一直是弱省的很重要一个原因吧，题目出成这样，

2015-05-21 21:21:07 475

原创 [BZOJ4027]HEOI2015兔子与樱花|贪心

删点这个过程是与顺序无关的，我们不妨从叶子开始删。。考虑一个点x，删去任意孩子对答案贡献是一样的，所以肯定是从负重小的开始删，从root开始dfs，离开一个点时维护一个删完它的子树上的点时的最终负重c[i]，那么把x的孩子按c排序贪心地删就可以了。。（为啥n=2000000这样搞不会T掉。。#include#include#include#define N 2000005using n

2015-05-14 09:21:18 584

原创 [BZOJ4011]HNOI2015落叶枫音|拓扑序DP

窝不会做啊QAQ。。看了题解发现一个DAG每个点选一条入边就是一颗有根树（森林），所以DAG的生成有根树的数量就是所有入度不为0的点的入度积。那么在DAG上加了一条边之后还是这样算就可能会有一些不合法的情况（成环）了，假设加进来的是s->t的边，那么环中一定包含了一条t->s的路径，所以我们的任务就是找出原DAG上包含t->s的路径的生成有根树的数量然后减掉就行了。。如果有t->x这条边，那么考虑

2015-05-14 09:19:39 799

原创 [BZOJ3529]SDOI2014数表|莫比乌斯反演|树状数组

要求的是的约数和。。惯用思路，转过来枚举，则有，现在要求的就是，那么如果能处理出的前缀和就可以分块计算辣。。这两个都是积性的可以线性筛出来（我嫌麻烦暴力算的）。。但是还要处理a的限制，把所有询问按a升序排序，i按升序排序，用树状数组维护前缀和，每次把小于当前询问的a的东西加进去就行啦。。（Orz PoPoQQQ）#include#include#include#define N 10

2015-05-14 09:15:16 518

原创 [BZOJ3504]CQOI2014危桥|最大流

源向a1和b1连流量为2*an，2*bn的边，a2和b2向汇连流量为2*an，2*bn的边，其他边非危桥连inf，危桥连2的边，跑最大流，但是这时满流不一定有解，因为可能有a1流到b2的流这样，所以把b1，b2反过来重构图再跑一次最大流，若能满流则有解。证明：假设第一次a1流了x的流到b2，第二次的时候由于是无向图，a1到a2流还是2*an-x，那么a1到b1是x，所以有x的流是b1-a1-b2，

2015-05-14 09:12:47 421

原创 [BZOJ3531]SDOI2014旅行

先树链剖分，然后为每一个教开一颗线段树，动态开点，没了。#include#include#include#define N 100005#define M 4000005using namespace std;struct edge{ int e,next;}ed[N*2];int n,Q,i,x,y,q,s,e,ne=0,nd=0,cnt,a[N],w[N],c[N],to

2015-05-14 09:11:44 413

原创 [BZOJ3631]JLOI2014松鼠的新家|树上差分

看起来是一个裸的树链剖分，其实不用那么麻烦。。给每个点一个标记表示它到root上所有点权值+多少，把每一次将一条链上权值+1的操作差分就相当于把L,R标记+1，把lca和fa[lca]标记-1，最后把标记往上传就行了。。#include#include#define N 300005using namespace std;struct edge{ int e,xu,next;}ed

2015-05-14 09:09:49 785

原创 [BZOJ3506]CQOI2014排序机械臂

挺有意思的。。看到区间翻转好像很容易想到splay，想到之后就没什么难度了。。每个节点维护一个子树最小值，没次删去一个点，该打标记打标记就是。。为了处理同大小的数要以初始序号为第二关键字。。#include#include#define N 100005#define lc c[x][0]#define rc c[x][1]#define inf 2000000005using n

2015-05-13 22:01:16 718

原创 [BZOJ3573]HNOI2017米特运输|贪心

语文题。。我一开始以为可以只从一部分子节点获取然后就不会做了。。看懂题之后发现确定了一个点就确定了一颗树，那我们计算当i点不变时根节点的值，那么这些值的众数就是不变节点的最大数量了。。但是这个数可能很大，所以要hash一下，多取几个数模一下就安全了。。#include#include#include#define N 500005#define ll long long

2015-05-13 21:58:23 628

原创 [BZOJ1143]CTSC2008祭祀|最长反链|floyd|二分图匹配

据说这只有第一问才会这么水。。这东西好像叫做最长反链。。我的理解就是先一遍floyd找出每个点能到的所有点（好像这东西叫传递闭包？），然后对于一对可达的点A,B只能选取一个，这就是匹配了，拆点二分图，把可达的点对连边，n-匹配数就是答案。#include#include#include#define N 105#define inf 0x3fffffffusing namespace

2015-05-13 21:57:07 638

原创 [BZOJ1787]AHOI2008 紧急集合|LCA

仔细想想就是水题，找出三个点两两之间的LCA，必然会出现至少有两个LCA相同，因为肯定要有两个人先走到一起再往上走嘛，或者就是三个都相同了。。那么走到不同的LCA就是要走到的点，因为这个LCA只会使一个点走远路嘛。。#include#define N 500005#includeusing namespace std;struct edge{ int e,next;} ed[N*2

2015-05-13 21:56:10 411

原创 [BZOJ1018]SHOI2008堵塞的交通|线段树

好神的线段树题，以前只会维护区间什么数值信息的，竟然还可以维护联通性，好题啊，涨姿势了。。由于只有两行嘛，要保证线段树节点有可加性，我们维护六个信息，分别是右上到右下，右上到左上，右上到左下，右下到左上，右下到左下，左上到左下的联通性，合并的时候自己YY一下，还是很好想的。一点要注意的，父节点的左上到左下不能简单的直接把左儿子的值赋上去，还有可能是左走到右再走回来，右上右下的同理。

2015-05-13 21:55:23 730

原创 [BZOJ2618]CQOI2006凸多边形|扫描线

凸多边形的面积并好像有很多搞法，网上有O(N^2logN)的算法，窝只会O(N^3logN)的扫描线暴力（好像能做到O(N^3)是么求解。。把所有三角形的端点和交点放在一起排序，这样所有图像就被分成了若干个区间，每个区间内的面积都是若干个梯形（三角形也可以当做梯形来做），然后求中位线的总长累计面积就行了。求中位线长的时候就用X=mid去得到所有交点，然后排个序，记录经过某个交点是进一个三角形还是出

2015-05-13 21:53:26 607

原创 [BZOJ4008]HNOI2015亚瑟王|期望DP

不会这种题啊好弱啊啊啊。。 f[i][j]表示前i张牌剩下j个机会，那么转移有两种，一是i-1利用了一个机会，二是i-1没有利用机会，也就是这样f[i][j]=f[i-1][j]*pow[i-1][j]+f[i-1][j+1]*(1-pow[i-1][j+1])，然后总的答案就是sigma f[i][j]*(1-pow[i][j])*d[i]，(1-pow[i][j])就表示i利用到

2015-05-13 21:53:26 1736

原创 [BZOJ4010]HNOI2015菜肴制作|拓扑排序+堆

一开始看成字典序最小。。后来想到不对又YY了一种奇怪的方法，不过还是错的。。正解是倒着来，边都倒着加，然后求一个字典序最大的拓扑序，反过来就是答案了。。一开始想不通为什么是这样，仔细想想应该没错。。如果没有选最大的，就让一个更小的放在了后面，而它本可以在更前的，所以一定要选最大的。。感觉和NOI2009变换序列的思路有点像，倒过来把要先满足的放到后面它自然就会满足了。。#inclu

2015-05-13 21:52:29 727

原创 [BZOJ1038]ZJOI2008瞭望塔|半平面交

考虑某个村庄可以被看见的区域，发现一条线段的上方就是可以看见端点的区域，那就把所有线段扔进去做半平面交，不要忘记了要加上两条左右边界。。求出来之后发现答案要么是某个村庄往上到半平面交的一段距离，要么是半平面交的某个点向下到轮廓线的一段距离，两个都是线性函数嘛。。根据这两种情况枚举更新答案即可。。#include#include#include#include#include#incl

2015-05-13 21:50:40 538

原创 [BZOJ1069]SCOI2007最大土地面积|凸包|旋转卡壳

这大概才是真正的第一题计算几何了。。首先这四个点肯定在凸包上，所以求出凸包，之后枚举四边形的对角线AB，凸包求出来之后点是按逆时针排序的，不妨设B在A的逆时针方向，那么就在A逆时针转到B的点之间取一个C点使三角形ABC面积最大，这个用叉积很方便，再在B逆时针转到A的点之间曲一个D使三角形ABD面积最大，现在ABCD就是以AB为对角线面积的最大值。。当A固定B逆时针转的时候C,D都是逆时

2015-05-13 21:46:27 888

原创 [BZOJ2242]SDOI2011计算器|快速幂|扩展欧几里得|BSGS

第一问快速幂，第二问扩欧，第三问BSBG，注意特判。。BSGS戳这里#include#include#include#include#define ll long longusing namespace std;map mp;int T,i,k;ll y,z,p,ans;ll pow(ll a,ll t,ll p){ if (t==0) return 1ll;

2015-05-13 21:44:00 465

空空如也

空空如也