Miao_zc-CSDN博客

原创新博客？

我就放个链接：https://mioam.github.io/

2018-01-22 15:27:51 721

原创 noip2017滚粗记

啊，蒟蒻noi盘滚粗了啊我可能除了T1全GG了啊。。。。。。。。

2017-11-12 18:44:56 813

原创快速沃尔什变换FWT

大概在做CC月赛的时候看到了这样一道题：https://www.codechef.com/OCT17/problems/XORTREEH 题意是要你做一个%330301441的类似FWT的东西。定义数组A，B，C。定义一个操作A⊕B=CA\oplus B=C C[i]=∑u∑vA[u]B[v] | u,v在k进制下不进位的和为i 其中k=2,3,4,...,9,10C[i]=\sum_u

2017-10-17 20:29:58 850 3

原创 bzoj4964: 加长的咒语

求区间最长括号序列子串。很有意思的括号，但是我有些细节没处理好，导致代码长，算法复杂。。如果有更好的算法我也很想知道啊>.考虑一个括号序列A=(B1)(B2)(B3)…，其中与某个括号匹配的相对的括号唯一。证明显然。有一个显然的算法：用栈判断一个字符串是否为括号序列。考虑拓展这个结论：对任意括号串的某个括号序列子串，某个括号匹配的相对的括号唯一。证明显然。既然这样就随

2017-08-11 10:51:41 701

原创可持久化treap

平衡树是一个有用的结构，但是常用的splay等由于均摊复杂度和旋转操作，无法方便的可持久化。这时候跳出一个treap，他可以可持久化！treap是一种笛卡尔树，有两个值：位置与权。这样构建出来的treap满足两个性质：1、左儿子位置小于当前节点小于右儿子，2、儿子的权值小于父亲。容易猜想，若权值随机，则树高是O(logn)。使用类似二叉堆的旋转操作可以很方便的维护treap，但是还有一

2017-08-06 16:15:33 713

原创多校联合自爆记

今年的多校联合lych不来AK，没办法蒟蒻也要来鏼题了。。顺便摸dalao@wzf2000@wanglichao1121多校联合1：比赛开始还不知道账号密码，睡午觉被叫起来，A了签到题就跑了。。大概是全场最菜了。。多校联合2：终于好好打了，开场做签到，直接过了5T排名达到了前5。然后各自开了题，大概同时写着4道题，就3h过去了。然后我直接开1010，贡献13发WA（RE）。

2017-07-29 19:51:47 523

原创 NOI2017游记

蒟蒻去NOI啦~DAY-1报到日和lych_cys吔了饭。回到寝室发现另外两位绍一的dalao都没来(结果好像住在了别的寝室QAQ)，都不能膜了啊。。晚上被（po）鄙（ge）视（mo），感觉自己萌萌哒，听说有nzdl。。DAY0开幕式+笔试看了一些并没有看懂但觉得很棒的舞蹈，然后就是dzd讲话，绝不作弊！之后背了2h的笔试，结果差点睡着。。晚上和lych_c

2017-07-26 16:21:17 1506

原创 bzoj3242: [Noi2013]快餐店

——来自一个失去梦想的咸鱼miaom考虑海蜇基环树的一般套路，在确定快餐店位置的情况下，最优解中环上必有一条边是废的。思考枚举这条边，我们需要在最快的时间求剩余部分的直径。当前答案就是直径/2，证明非常简单，就离快餐店最远的点一定是直径端点。这个东西可以通过双指针单调队列维护，达到O(n)复杂度。然后我就失去了梦想，直接线段树水过了。线段树做法如下：先搞出那个环，重复一遍变成序列问题，询问

2017-07-04 21:09:18 578

原创 loj#6169. 相似序列

最近口胡了一个随机的idea，结果在loj上连出3道类似的题。。我的思路是这样的：给每个数一个随机权值，如果两个序列的数的随机权值异或和相等可以认为这两个序列排序后相同。考虑主席树，对于两个区间l~r的数，如果递归不同的部分，直到两半都相同。然后就能得到那两个不同的数，再判断一下即可。#include#define ll long long#define N 100005#defin

2017-06-23 21:35:03 739 1

原创 codeforces 379G. New Year Cactus

题目大意：给一颗2500点的仙人掌，每个点可以染黑色，白色，不染色。同一条边两端点不能为黑白，求对于所有黑点个数的白点个数的最大值。我直接想到了把他的dfs树建出来，直接dp节点x的儿子有y个黑点，当前染a，子树的返祖边染b的最大值。但是我以为他是O(n^3)的。但实际上他是O(n^2)，然后就没有然后了。dp写的超长。。。#include#define N 2505using n

2017-06-15 08:08:15 638 3

原创 codeforces 794G. Replace All

题目大意：给两个'A''B''？'组成的串XY，'？'可以是'A'或'B'，求所有'？'的情况下，将'A''B'换成两个长度小于n的01串的方案数和。这好像有一些奥妙重重的性质。先考虑一个简单的情况：第一个串有a个'A'，第二个串有b个'B'。设'A'=>A,'B'=>B。b*|A|=a*|B|，且AB串coprime（是官方题解中的说法，互质，就像辗转相除法一样的感觉）。由于这样的性质，

2017-06-12 16:45:41 1028

原创 codeforces 587F. Duff is Mad

蛮好的一道fail树的题目考虑fail树，对于询问l,r,k，相当于询问l~r的字符串在AC自动机上对应节点在fail树子树中是第k个串前缀的节点的个数和。发现k固定有一种O(n+Σ串长)的优秀做法，就不说了。同时对一些询问存在使用分块数据结构维护的离线O(Σ询问串长)的做法，就可以分块了，复杂度O(nsort(n))这个离线O(Σ询问串长)做法把询问挂在fail树上，dfs的同时维护

2017-06-09 10:42:05 667

原创 bzoj4827: [Hnoi2017]礼物

看到要求∑(xi − y i+k -c )2的最小值。首先将xi − y i+k看作整体，得到一个关于c的二次函数nc^2+pc+q=0。发现q的形式将y数组翻转类似一个卷积，然后又发现其中每个值小于998244353，然后一个NTT上去就能求出精确的最小值了。O(nlogn)#include#include#define P 998244353#define N 200005#def

2017-04-18 20:34:49 881

原创 ZJOI2017DAY1游记

DAY-2到温州，车上吐了，药丸。三国杀13血忠臣周泰被主公单杀，无限血八阵连胜。。。RP--DAY-1早上被闹钟叫醒，po了一天隔膜，啥都没干。DAY0早上忘记设闹钟，6:45被jlh的电话叫醒。讲课atcoder的题，然而lych全做过了，在一旁补笔记。手机被七主力玩没电了。。。晚上和wlc猜次日算法，我：T1数据结构，T2分治，T3FFT。。。（flag背

2017-03-23 20:58:16 1207

原创 bzoj4767: 两双手

注意一个条件，ax*by!=bx*ay，所以每个点所需的每只手的次数是固定的，于是就可以转换为网格图（注意这里|坐标|注意有一些无解的可能需要特判。//发现bzoj上使用cerr会返回RE 2333#include#include#include#define P 1000000007#define ll long longusing namespace std;int Ex,

2017-03-11 08:59:59 881 1

原创 cf755G. PolandBall and Many Other Balls

一个解法→一句话题意：给出1~n的序列，一个组的定义是1或2个相邻的数字，求每个数字最多属于1个组、共1~k个组分别的答案，对998244353取膜。//我语文差你来打我啊有一个SB的DP算法：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-2][j-1]。其中dp[i][j]表示前i个j组的方案。//lych：这还能不用FFT（NTT）哒把dp[i]看做多

2017-03-09 21:00:30 1093

原创 uoj#207. 共价大爷游长沙

miaom又来做LCT了！//lych：无敌由于不是很懂LCT子树信息维护的那套理论，想了好久（搞得树剖的子树维护就会了一样！）。首先是一个很巧妙的转化——将边在链上转化为这条边能将链的顶点分开。给每组顶赋一个随机权，每次可以把边断掉，查询每个联通块内权值异或和是否等于所有顶点权值异或和，就是子树异或和。然后发现动态树上子树不是dfs序连续那么简单，他应该是（当前点及沿偏爱边往下走得到

2017-03-07 20:51:07 840 2

原创 cf757G. Can Bash Save the Day?

简述题意：给一棵n个节点的数和一个n的数组（n的排列），支持两个操作：1 询问a[l]~a[r]的所有点到某个点的距离，2 交换a[x]与a[x+1]。一开始想到了这道题bzoj4012: [HNOI2015]开店，大概看了之后发现是开店的加强版。我想到像开店一样使用主席树处理，显然操作2很容易。然而他的时间是一个log。大概看了题解，感觉套路~ 毕竟开店的题解大多是log^2。。

2017-03-02 16:11:23 901

原创 uoj275. 【清华集训2016】组合数问题

智力孤危。。这道题可以根据lucas定理，把C(n,m)是k的倍数转换为n,m的k进制数，某一位的组合数是k的倍数，也就是n,m在k进制表示下n有一位比k小（大）。这样子的话就转换为一个数位DP，就能做了。题解貌似就把lucas推了一遍，嗯，差不多#include#include#define ll long long#define P 1000000007#define I2

2017-02-21 20:40:44 1432

原创 bzoj3926: [Zjoi2015]诸神眷顾的幻想乡

太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。这是一棵只有20个叶子的树，容易想到对每个叶子节点dfs一遍，然后拉板子。。

2017-02-20 10:09:26 1003

原创 bzoj3512: DZY Loves Math IV

2017-01-20 15:02:13 1164

原创 bzoj3216: 话旧2

大家好，我是SB这道题是在看3215时找不到题面点进来的（然而并没有一眼看出这两题的差别）。一开始想了一会，感觉就是一个组合数，然后最小值==0就有点像Catalan数，于是打开geogebra画图，得到了一个：Ans=Get(Y-X,Z)-Get(Y+X+1,Z-1)，反正证（gan）出（jue）他是对的，就狂WA。。。后来找的了→ ，发现自己傻了。。然后用lucas定理

2016-12-22 16:58:06 948

原创 uoj#228. 基础数据结构练习题

第一次看到这题大概在这里：2016多校联合反正当时也没什么想法，表示有区间加好难受。题解并不难，维护每个区间最值、和，当一个区间开根后所有值都一样就直接赋值，否则递归。存在一种特例：3 4 3 4 3 4 3 4 3，开根后1 2 1 2 1 2 1 2 1.，+2: 3 4 3 4 3 4 3 4 3,，成功卡到暴力，所以要特判，原因大概是取整吧。所以就有了：后来发现ad

2016-12-15 15:59:27 550

原创 bzoj3218: a + b Problem

题目名称是吸引我点进来的。首先这是一个最小割模型，对点i，连S->i:b[i]，i->T:w[i]，i->i':p[i]，i'->j(奇怪):inf，这样就有了一个TLE的算法。怎么办呢？然后vfk强行将n^2的边减少到nlogn。。。

2016-12-14 20:57:20 585

原创 bzoj3672: [Noi2014]购票

为什么我这么慢！！！这道题大概有两种思路，树分治和线段树。树分治：使用类似cdq的方式，1：找重心，分裂，2：work（根所在的树）3：用重心到根的点的答案更新重心的子树，4：work（重心的子树）。更新的时候维护一个下凸壳，在下凸壳上二分即可。(我写了这个)线段树：同样需要维护下凸壳，考虑在dfs时动态维护当前节点到根路径上的区间下凸壳，这个用线段树在每个节前维护一个支持回撤的单调栈

2016-12-12 15:15:26 625 1

原创 bzoj1194: [HNOI2006]潘多拉的盒子

一看这道题自动机就好慌，但是多想想并不难。S由于自动机的输出可以是无限的，因此不放压缩状态，用(x,y)表示在第一个自动机x点，第二个自动机y点可行，然后跑bfs，找是否存在(x,y)使x可以输出而y不行，若有则不符合。#include #include#include#define N 105using namespace std;int S,a[N],b[N],f[N][

2016-12-09 09:39:28 583

原创 bzoj1178: [Apio2009]CONVENTION会议中心

这题有点强，一句话题意：求字典序最小的线段覆盖（这里的字典序指选择的线段的编号排序后的字典序）。如果不要求字典序只需要对左（右）端点排序，然后贪心取即可。一开始我想到的是DP，但是字典序存在了不可避免的后效性，看了题解之后，才有了思路。先离散，要使字典序最小优先选序号小的，然后判断选取某一个之后最优解是否改变。接下来就是怎么O（logn）求区间内线段覆盖。（具体做法搜索ppt。。。

2016-12-08 16:46:19 1333

原创 bzoj1195: [HNOI2006]最短母串

一开始以为这是字符串好题，一看n范围，n！就炸了。考虑dp，dp[i][j] i表示每个子串有没有出现，j表示最后的串。看了lych的博客之后，自己还是naive！首先有可能出现一个串没有用，要预处理掉，另外字典序最小需要存更多的东西。复杂度O（2^n*n*n*跑得过）。#include#include#include#define N 13using namespace s

2016-12-07 15:31:11 607

原创 bzoj1588: [HNOI2002]营业额统计

切水。法一：用平衡树维护，nlogn，网上大多数题解都是这个法二：权值线段树，我写的是这个，nlog1e9法三：离线+离散化+权值线段树，没什么好说的，nlogn法四：离线排序+链表，从后往前扫一遍即可，nlogn+n，常数比较小#include#include#define N 1000005#define inf 200000000using namespace s

2016-12-01 14:24:24 486

原创 NOIP2016 酱油记

Day1：到了衢州，并没有带三国杀，浪了一个晚上，心里好虚。T2好难，一开始只想到了nlogn的线段树合并，gg。借教室没考虑=1的情况，biubiuDay2：买来一副杀三国，又浪了一个晚上，心里好虚。T2想了一个伪线性做法，感觉卡不掉。有暴力对拍随机数据，暴力20s，伪线性1s，不管他了。T3一眼看出dp，然而不知怎的就写了long long，最后开double，luog

2016-11-24 14:19:56 770 1

原创 NOIP RP++

NOIP RP++

2016-11-18 11:51:48 668

原创 bzoj4574: [Zjoi2016]线段树

好久没写题解了。。。这道题拖了好久，终于把常数卡进去了。首先发现数据随机，肯定不是正常算法，不妨离散。考虑DP，用dp[q][i][j]k]表示q轮后i~j最后变成k的情况。比较难转移。参考大神的blog：用dp[q][i][j][k]表示表示q轮后i~j最后变成每个数都小于等于k的情况，这样可以转移。//不要问我怎么转，好久以前推得式子然后每个值k只影响一段i~j的dp值

2016-10-10 21:00:33 660

原创 bzoj3316: JC loves Mkk

首先看到环，考虑变成链上询问。由于题目要求平均值最大，所以无法直接使用线段树维护。先二分平均值，问题就能转化为能否找到L~R的一列数和大于等于零。这个很像单调队列，只要对奇偶分别维护单调队列就可以了。#include#include#define N 200005#define ll long longusing namespace std;ll n,m,L,R,a[N],q[2][

2016-08-23 12:00:46 527

原创 bzoj2338: [HNOI2011]数矩形

这是一道SB题，然而我是大SB。。。发现N注意精度问题，中点请将坐标*2，面积请用叉积。连cmath都不用！P.S.:某同（da）学（ye）说可以留一个矩形，其他点坐标相同，可以卡到n^4然而去（bing）重（mei）就（you）行（chong）了（he）。#include#include#include#include#define ll long longusing

2016-08-05 17:06:31 523

原创 bzoj4035: [HAOI2015]T3

发现翻转相当于增加一个白格对于一个白格子，它的SG值只与它还能跳的次数有关，如长度10，SG[4]=SG[5]。于是不同的状态只有sqrt(n)个。只要求出还能跳k步的位置的SG就能得到答案。暴力DP即可，貌似O(n)能过#include#include#include#include#define N 100005using namespace std;int n,k,s

2016-08-03 21:07:30 989

原创 bzoj4650: [Noi2016]优秀的拆分

此题有95分暴力。。。发现AABB的统计相当于对AA的统计。于是可以计算出每个点左侧为AA的方案数。枚举|A|，将字符串分成长度为|A|的小段，当AA中点在小段中的情况可以利用SA+rmq，O(1)求。于是就能在O（n/1+n/2+...+n/n）=O(nlogn)内求解。#include#include#include#define N 80005using namespace

2016-08-03 21:01:31 867

原创 bzoj3159: 决战

这道题真是让我对LCT有了新的认识啊！题意大概就是实现一颗树，支持路径翻转！然后我一脸懵逼地想到了splay，然后不会。其实只要一个LCT就可以了，额外开一颗splay记录prefer路径上的值，然后翻转就是MakeRoot+splay+reverLCt+reverSplay，然后就好了。。。LCt真是神奇啊。。。#include#include#define N 50005

2016-07-19 20:11:11 1046

原创 bzoj3813: 奇数国

该村子在财产上的求和运算等同于我们的乘法运算该村子在财产上的求和运算等同于我们的乘法运算该村子在财产上的求和运算等同于我们的乘法运算一开始直接把它忽略了。。。导致题意都没看懂，直接看题解一句话题意，听说是最简单的一道。。。考虑phi(x)=x*∏(pi-1)/pi，维护区间和，区间每个质数是否存在(long long)，即可得到答案。#include#include

2016-07-19 09:22:53 660

原创 bzoj4383: [POI2015]Pustynia

既然讲了线段树就做一道裸题吧。。。于是卡死。。。考虑暴力，有点像差分约束的建边，然后发现k比较小，k个数把l~r分成k+1个区间于是用线段树建图，然后就好饿我用了dfs跑拓扑，因为并不需要排序。。今天听lbn讲splay+LCT+KDTree，生（ting）无（bu）可（dong）恋（a）。。。#include#include#include#define N 400005

2016-07-13 13:37:45 831 2

原创 bzoj3440: 传球游戏

这不傻逼题吗！一开始连题目都被读懂。。。第1类人，顺着传来的方向传给下一个人。第2类人，逆着传来的方向传给上一个人。第3类人，顺着传来的方向传给下面第二个人。第4类人，逆着传来的方向传给上面第二个人。现不知是从哪个人开始传，及开始传的方向，求有哪些人无论如何，最多只能碰到一次球然后很容易想到拆点，然后找环，可是不止有这种情况，可以从1号顺时针走到2号顺时针再走到1号

2016-07-12 15:40:36 902 1

空空如也

空空如也