- 博客(85)
- 收藏
- 关注
RSS订阅原创 Inverse
题意给出一个1~N的排列P，进行K次操作，每次等概率的选取一段区间（从所有n(n+1)2\frac{n(n+1)}{2}2n(n+1)中选）翻转求K次操作后的逆序对期望个数题解定义d(i,j,k)为k次操作后，Pi>PjP_i>P_jPi>Pj的概率那么最终的答案就是∑i=1n∑j=i+1nd(i,j,K)\sum_{i=1}^n\sum_{j=i...
2019-01-16 08:13:43
249
原创 matrix
题意定义一个矩阵价值为它的不相同的行的个数给出n*m大小的矩阵，求它的所有子矩阵的价值题解这个问题相当于对于每个(p,S)（p为左端点所在列，S为一个字符串（em…这里跳了一步，我们可以把数字序列看成字符串））在多少个(x,y)中满足∃z∈[x,y]\exist z ∈[x,y]∃z∈[x,y]，从z行p列开始的字符串和S相同对于p=1，我们可以这样，将这N行看做是N个字符串，然后插入一...
2019-01-12 07:27:42
198
原创 sequence
题意定义一个序列是K好的，当且仅当其所有元素的按位与的值能被K整除给出一个长度为N的序列A和K，每次询问[L,R]中有多少个连续子序列是K好的题解由于按位与运算是不增的，我们可以把相同的后缀与值分段存下来，显然不会有超过30个段这就很有意思了我们可以离线处理，按询问的右端点排序，然后我们从左往右枚举以当前位置为右端点的...
2019-01-11 21:56:31
380
原创 bzoj 3809 Gty的二逼妹子序列
题目一个n个元素的数组，元素大小∈[1,n]，每次询问[l,r]中，数值[s,t]中出现了多少种n<=1e5,m<=1e6题解比较容易发现的做法是莫队然后用树状数组维护这样复杂度就是O(nmlogn)O(n\sqrt mlogn)O(nmlogn)的于是应该就T了其实我还专门交了发试试，确实T了…关注到n和m不同我们分析一下需要的操作1.插入&删除 O(n...
2019-01-10 19:37:54
163
原创 BZOJ3222 Hotel&BZOJ4543 Hotel加强版
题目一棵树，找到三个点他们两两之间距离相同题解O(N2)O(N^2)O(N2)定义f(u,d)表示以u为根的子树中，与u距离为d的节点数g(u,d)表示以i为根的子树中，已经找到了两个点，如果在u子树外找到一个距u为d的点就能成为一个合法方案的这两个点的无序点对数可有转移方程f[u][i]+=f[v][i−1]f[u][i]+=f[v][i-1]f[u][i]+=f[v][i−1]...
2019-01-08 08:13:42
185
原创 BZOJ2555 SubString
题意要求你在线支持下面几个操作：1.在当前字符串末尾插入一个字符串2.查询一个字符串作为子串在当前字符串中出现了多少次题解后缀自动机显然出现次数就是对应节点right大小对吧那么动态维护怎么做呢？LCT再详细的讲讲怎么用LCT维护fail树（好像也叫parent树来着）吧（此处注意LCT并不完全是正常的LCT）简单的讲，就是正常的SAM新建节点时在LCT新建节点，更新后缀链接时...
2019-01-07 11:12:10
120
原创 BZOJ2806 Cheat
BZOJ数据爆水！可以试试这两组1 10100011ans:11 1000111ans:0题目有M个01串作为“作文库”，N次询问，每次询问给出一个01串S，你可以在S中取出成若干个不相交的长度大于等于L的子串，若这些子串都在那m个串中的任意一个作为子串出现过，且这些子串长度的和>=0.9*原长，那么这个L就是合法的，问你最大的合法的L是多少题解在后面的工作之前...
2019-01-06 20:50:32
163
原创 BZOJ 2946 [Poi2000]公共串
题意给出几个字符串，求他们的最长公共子串题解其实我们只需要能够对于两个串求出它们的最长公共子串，这道题就差不多解决了我们对第一个串构建后缀自动机，之后的跟它匹配就可以了对于每个结点，每次匹配时维护当前匹配长度的最大值，再对全局维护一个最小值（因为要公共），然后最终答案就是所有点最小值的最大值但是需要注意的是，当我们匹配了某个节点后，我们要更新它的fa的最大值，因为这个点能匹配就意味着f...
2019-01-06 20:23:57
211
原创 BZOJ 3238 差异
题意给出一个长度为n的字符串S，令TiT_iTi表示它从第i个字符开始的后缀。求（其中len(a)len(a)len(a)表示字符串a的长度，lcp(a,b)表示字符串a和字符串b的最长公共前缀）ans=∑1≤i&amp;amp;amp;lt;j≤nlen(Ti)+len(Tj)−2∗lcp(Ti,Tj)ans=\sum_{1\leq i&amp;amp;amp;lt;j \leq n}len(T_i)+len(T_j)...
2019-01-06 16:00:22
185
原创 东非大裂谷
题意给出一棵树每个点上有权值你需要把这些树分成若干条链，每条链都必须满足上面的点深度互不相同（也就是说不会存在某个点有两个儿子都在链上），每条链的收益是该链上的最大值减去最小值。问最大的总收益题解可以发现，由于收益只跟最大值和最小值有关，所以链的两端一定分别是最大值和最小值也就是说每条链都一定是从上到下单增或单减的，而且这样的话，我们就可以通过把相邻的差值加起来就得到最大减最小了我们...
2019-01-05 16:39:24
386
原创 地中海气候
题意有一个包含 N 个正整数的序列，序列元素不大于 N。紧接着，他们维护了一个可重集合 S，包含序列中的前 P 个元素。Alice 先手，二人轮流进行下面的一系列操作：从集合 S 中拿走一个元素，加到玩家的总分上面；将序列中的下一个数字(如果存在)添加到集合 S 中；假使二人都尽力使自己的总分最大，设游戏的结果为 Alice 的总分与 Bob 的总分之差，那么请你在给定序列和集合元...
2019-01-05 16:32:16
331
原创 光线追踪
题意有两种操作1.插入一个每条边与坐标轴平行的矩形（）2.从原点射出一个光，问他最先碰到那个矩形（所有点都在x轴正半轴或y轴正半轴或第一象限中）题解离线处理啦我们通过极坐标排序，我们可以离散化，每个矩形我们就可以看做是覆盖了一段极角坐标显然我们可以把一个矩形简化成左边和下边那两条线段然后我们可以用两棵线段树来维护线段（真·线段树）我们分开处理横的和纵的然后分别更新啦，可以由于...
2019-01-04 20:31:19
218
原创 AGC019F Yes or No
题意有N+M个问题，其中N个答案是YES，M个是NO每次你可以回答YES或NO，问答对个数的期望当然还有个条件，当你回答了某个问题后，你会得知这道题的正确答案。所以问你采取最优方案时的期望题解我们先考虑假如不会知道答案当N&gt;M时，显然我们就应该一直答Yes，这样我们答对的期望就是(N+M)NN+M=N(N+M)\frac{N}{N+M}=N(N+M)N+MN=N反之亦然，所以...
2019-01-04 16:36:39
176
原创 bzoj4518 征途
题意Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。帮助Pine求出最小方差是多少。设方差是v，可以证明，v×m2v×m^2v×m2是一个整数。为...
2019-01-04 08:49:09
253
1
原创 Codeforces 804F Fake bullions
题意有N个帮派，每个帮派有Si个人，其中一些人有真金条给出一张竞赛图，若图上存在一条边u->v,那么如果u中一人i，v中一人j，满足i mod Su=j mod Svi\ mod \ S_u=j\ mod \ S_vi mod Su=j mod Sv且i有金条（无论真假）且j无金条，i就会给j一个假金条...
2018-12-27 13:44:19
405
原创 CodeForces553E Kyoya and Train
题意n个火车站，m条单向铁路，你要从1到n。每条铁路有一个费用，然后通过的时间是[1,t]中的，会给出通过某条边用每个时间的概率。如果你到n的时间大于t,就会被罚x。当你到达一个火车站的时候，你可以根据当前的情况改变方案。问从1到N的最小期望花费n<=50,m<=100,t<=20000题解可以先有一个dp，d[i][j]表示从i出发，当前为j时刻时的最小花费d(u,t...
2018-12-27 08:22:36
164
原创 bzoj 2302 [HAOI2011]Problem c
题意给n个人安排座位，先给每个人一个1~n的编号，设第i个人的编号为ai（不同人的编号可以相同），接着从第一个人开始，大家依次入座，第i个人来了以后尝试坐到ai，如果ai被占据了，就尝试ai+1，ai+1也被占据了的话就尝试ai+2，……，如果一直尝试到第n个都不行，该安排方案就不合法。然而有m个人的编号已经钦定了，你只能安排剩下的人的编号，求有多少种合法的安排方案。对M取模100%的数据满足...
2018-12-26 19:44:25
925
原创 bzoj 2091 [Poi2010]The Minima Game
题意给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。题解首先，我们把数组按从小到大排序每个人取数时，一定是取的最后的连续的一段证明吗…显然？我们可以定义d[i]为最前面的i个，先手最多多拿多少分那么要么就先...
2018-12-26 18:55:35
148
原创 bzoj 2216 [Poi2011]Lightning Conductor
题解给出一个长度为n的序列a，你需要对于每个i，找到最小的整数p满足对于∀j,aj≤ai+p−∣i−j∣\forall j,a_j\leq a_i+p- \sqrt{|i-j|}∀j,aj≤ai+p−∣i−j∣题意移项，有p≥a[j]−a[i]+∣i−j∣p\geq a[j]-a[i]+\sqrt{|i-j|}p≥a[j]−a[i]+∣i−j∣也即是说p=max(a[j]+∣i−j...
2018-12-26 17:22:57
218
原创 bzoj 3864 Hero meet devil
题意一个脱氧核苷酸链只由AGCT组成，以下讨论的串都只有AGCT现在给出一个串S，问你对于i∈[0,|S|]有多少个长度为m的串T满足LCS(S,T)=i|S|<=15 m<=1000题解直观的想法是dp套kmp?反正下面讲的是dp套dp内层的dp是个显然的LCS盗个图我们观察这个转移式，可以发现只会用到两行的信息，而且同一行相邻两个之间相差不超过1那就很好办了，...
2018-12-26 12:20:37
314
原创 bzoj 4726 [POI2017]Sabota?
题意题解二分答案x，然后用树形dp check即可具体一点，d[i]表示i为根的子树下最多有多少个叛徒放个代码void dp(int u){ if(sz[u]==1){ d[u]=1; return ; } d[u]=1; for(int i=head[u];i;i=edge[i].nxt){ int v=...
2018-12-26 09:52:23
147
原创 bzoj 4922 Karp-de-Chant Number
题意给出n个括号序列，你从中选出若干个并以任意方式拼接得到的合法括号序列最长是多少n,|S|<=300题解先把输入的括号序列简化成一个三元组（r,l,len）表示最后左边剩下了r个右括号，右边剩下了l个左括号，原长为len （很绞是不是？）于是我们可以很轻易的得到一个N^3的dp，d[j]表示还剩j个左括号未匹配的最大长度，然后依次枚举，如果j>=r那么，d[j-r+l]=m...
2018-12-26 08:45:31
195
原创 THUSC2017 座位
题解把每个位置上的人都看做是一个节点，然后如果我们能把这种换位置的关系表示出来，我们就可以把每个点拆成两个x，一个从S流进1，一个流出1到T那么这么表示出这种关系呢首先对于一个环上的移动，我们可以把相邻的两个点之间连一条费用1的双向边那么桌子之间的关系呢...
2018-12-25 21:17:55
344
原创 Manacher算法小结
文章目录算法介绍例题例题1 HDU 3068 最长回文题意题解例题2 bzoj2565 最长双回文串题意题解例题3 Codeforces 17E Palisection题意题解例题4 The Number of Palindromes题意题解例题5 codeforces 1080e Sonya and Matrix Beauty题意题解Manacher，又称马拉车算法，是解决字符串中回文的意大利...
2018-12-25 20:55:08
154
原创 PKUSC 2018 最大前缀和
题意给出一个序列，把他随机打乱，然后求最大前缀和的期望n<=20题解定义f(S)为S为最大前缀和的方案数，g(S)为S中的元素，最大前缀和<0的方案数,sum(S)为S中元素的和那么答案就是（设T为全集）∑S=1Tf[S]g[TxorS]sum[S]\sum_{S=1}^Tf[S]g[TxorS]sum[S]S=1∑Tf[S]g[TxorS]sum[S]下面就是f和g怎...
2018-12-24 17:25:52
484
原创 Coeforces 611H New Year and Forgotten Tree
题意给出一张无向图，但是所有数字都由?代替（也即是说，你只知道每条边连接的两个点的标号的位数）问你这可不可能是棵树n<=200000题解我们将每个位数相同的点中挑一个点出来称为关键点那么一个显而易见的结论是，所有树，都可以在不改变那个所有数字都由?代替后的结果的前提下，转变成一个关键树然后加一大堆叶子的形式（即去掉关键点，连通块大小都是1）然后我们考虑这个怎么实现首先爆搜关键...
2018-12-24 16:09:48
291
原创 Codefoces 793G Oleg and chess
目录题意题解题意给出一个n*n的棋盘，其中有q个矩形区域不能放棋子（但是不会隔开攻击），问最多能摆放多少个互不攻击的车n,q&amp;lt;=10000（时限6.5s，而且是cf）题解首先考虑如果已经知道了一些可以放的单个位置，该怎么做就一个正常的二分图建模网络流对吧如果是知道了一些可以放的矩形区域呢？我们可以用线段树来优化建图，用两个线段树分别代表连续的x或y的一段那么现在的问题就是怎么...
2018-12-24 08:16:26
237
原创 点亮
题意题解对于40%的数据，O(2nn2)O(2^nn^2)O(2nn2)乱整题目中多次强调：随机得到的树来来来直接上性质众所周知？不存在的综上，题解的意思是：随机一般是用来暴力骗分，但是这道题就是正解下面是性质的证明（突然发现自己在疯狂粘题解）由于这个深度很小，所以我们可以状压把所有的输入处理到LCA上然后就可以dp了，d(i,j,k)表示i子树，状态为j，点亮...
2018-10-24 20:08:22
473
原创 1017考试
流水账先看题第一题数论，第二题博弈，第三题dp+优化？第一题推了一小会没啥性质，开始打表打表打出来了一个子任务3规律，但是还是没出正解8:40还是先把子任务1、3写了然后又继续找规律，感觉第二题没啥大思路，还是回来想第一题开始考虑思考方法，由于是位运算，考虑把二进制数打出来看9:40左右，突然发觉可以按每位求和然后再推一下，就是0的个数*1的个数然后10:10写完，然后开始对拍...
2018-10-17 13:02:39
217
原创 1015考试总结
流水账先通览一遍题面第一题估计是数论，第二题估计是dp或者区间操作，第三题估计是数据结构首先第一题最关键的性质是nn-&amp;gt;nm，也即是说可以一列一列的转移，每隔n列个数相同然后一开始想错了，想成之后都是第一行个数8:30码完第一题第一个版本（方法有问题）8:40码完第一题第二个版本（暴力）对拍，发现问题，反应过来应该是对应的个数，而不是都是第一个8:55第一题第三个版本（验证...
2018-10-15 19:14:45
100
原创 AGC011 E Increasing Numbers
题意定义一个数是上升的，当其每个数位上的数不小于比它数位高的数比如11233然后给你一个数N（N&amp;amp;lt;=10500000N&amp;amp;lt;=10^{500000}N&amp;lt;=10500000）求它最少能拆成几个上升的数的和题解首先有几个性质需要发现第一个是对于一个上升的数，它一定可以写成不超过9个1111111…结构的数的和也即是说，他一定能写成恰好9个结构为10p−19...
2018-09-26 21:53:06
164
原创 AGC011 D Half Reflector
题意有N个机器排成一排，有两种状态A：会把球反弹（即让球反方向滚动）B：让球自由通过（即让球沿原方向滚动）然后每有一个球撞上机器，这个机器就会改变状态现在给你N个机器的初始状态，然后你将一个球滚进去K次，问K次后机器状态题解打表找规律想办法从小到大归纳模型首先，如果第一个是A，那么球就弹回去了，第一个变成B如果第一个是B，那么球就会如下动o-&gt;BABA&lt;-oBB...
2018-09-26 20:29:08
519
原创 AGC011 C Squared Graph
题意定义两个图的乘法是：点数为它们的乘积，新图中(x,y)到(z,w)有边，当且仅当第一个图(x,z)有边，第二个图(y,w)有边给出一个无向图G，求它的平方的连通分量个数题解我们考虑相对一般点的情形：图A乘上图B首先考虑那些孤点（即度数为0），设AB孤点个数为I由于孤点不和任何点有连接，所以在新图中，它所对应的那一行（列）就肯定是独立的也就是说，跟孤点有关的就是IAIB+IA(NB...
2018-09-26 18:28:14
142
原创 AGC010 F Tree Game
题意有一颗 n 个节点的树。现在第 i 个节点放有 ai 个石子。A和B 想要用这棵树玩一个游戏。首先,A选择一个节点并放一个木块在上面。然后从A开始，他们轮流进行如下操作：1.从木块所在的节点移除一个石子2.然后把木块向相邻的一个节点移动若当某个人进行操作的时候当前木块所在节点没有石子，那么他就不能进行这轮操作并输掉游戏。请找出所有能让 A赢得游戏的放置木块的初始节点，在两人都采用最...
2018-09-25 21:15:50
188
原创 AGC010 D Decrementing
题意有 n 个整数，其中第 i 个数为 Ai。这些数字的 gcd 为 1。两人轮流操作，每次操作把一个大于 1 的数减 1，并把所有数除以所有数的最大公约数，最后无法操作者输，求是否先手必胜题解特判n=1定义3个状态：1.有奇数个偶数，至少一个奇数2.有偶数个偶数，至少两个奇数3.有偶数个偶数，有一个奇数首先呢，由于初始值gcd为1，所以1.2.3.一定已经涵盖了所有开始和中途可能...
2018-09-25 19:57:26
154
原创 AGC010 C cleaning
题意这棵树有n个节点,节点i有ai个石头每次操作选择两个叶子节点(u,v)(u不能等于v),移除u到v路径上的每一个节点的一块石头(包括u,v).注意:如果这条路径上有一个节点没有石头,则不能进行操作.能否通过上述操作将树上的石头移完此处的叶子节点为度数为1的节点.题解对于非叶子节点，可以发现如果我们计算直接相连的边上经过的次数，这些次数加起来应该恰好是2*ai；而叶子结点，则是ai...
2018-09-25 17:04:24
122
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人