- 博客(178)
- 收藏
- 关注
RSS订阅
原创 link cut tree 学习小结【NOI2014】魔法森林
题目Description为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为1,2,3, … , n，边标号为 1,2,3, … , m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪
2017-12-04 22:15:40
491
原创 后缀数组
sa终于学习了一波sa sa的大概思想其实就是先把每一个i开头，长度为1的字符串排序，再通过前面的结果，用倍增的方法求出每一个i开头，长度为2k2^k的字符串的排名 设sa[i]表示排名第i的后缀开头的位置，rank[i]为以i开头的后缀的排名，height[i]表示sa[i]和sa[i-1]的lcp（最长公共前缀） 假设现在我们在对以i开头，长度为k的字符串排序，那么我们是已经知道长度为k/
2017-06-17 09:33:43
361
原创 splay学习小结＆常用基本操作模板
1这几天没有什么题目做，然后就开始乱看题解33，然后看到一题的题解有用到平衡树，但是我太弱了不会，所以决定趁这段时间比较闲学一波splay2平衡树是一种每一个叶子节点深度差的绝对值不超过1的二叉搜索树，而二叉搜索树满足对于每一个非叶子节点，ta的左子树中的节点权值比这个节点权值要小，而右子树中的节点权值比ta要大。splay就是一个通过玄学方法来维护这棵二叉搜索树的算法3首先平衡树有几种基本操作，假
2017-02-22 20:48:01
1059
3
原创 2019牛客暑期多校训练营（第一场）H-XOR
题意：给n个数，对某一个数的子集，如果这个子集的抑或和为0，就给ans加上这个子集大小，求ans范围：链接：https://ac.nowcoder.com/acm/contest/881/H题解：观察题目注意到①：对于每一个合法的子集，我们要加的是这个子集的大小而不是1，这启示我们可以统计每一个数都计算一次这个数在多少个合法的子集（也就是抑或和为0的子集）中出现的次数我们可以先把这n...
2020-01-13 17:27:22
195
原创 【杜教筛】【GDOI2018Day1模拟4.17】呼吸决定
题意求∑ni=1μ(i)∗im∑i=1nμ(i)∗im\sum_{i=1}^n μ(i)*i^m m<=2e5 n<=1e9题解设pi=μ(i)∗im|si=∑ni=1pipi=μ(i)∗im|si=∑i=1npipi= μ(i)*i^m |si=\sum_{i=1}^n pi，现在尝试让p卷一个g（狄利克雷卷积）∑ni=1(s∗g)(i)=∑ni=1∑d|ip(i...
2018-04-18 21:48:30
480
原创 HNOI2018D1T2 转盘
题意可以选定一个初始位置，每一个时间可以往后走一步（是一个圆）或者不走，每一个位置有一个出现物品的时间点，如果当前所在位置的物品已经出现则可以将其拿走，求最少要多久可以拿走所有的物品题解首先对于一个固定的起点，一定有一种方法使得往下一个点走的次数恰好为n-1 我们可以先任意选择一个最大值Ti，然后我们可以随便选择一个起点，依次处理每一个位置，这样肯定是最优解之一，如果有一个更优的...
2018-04-16 17:10:44
653
原创 jzoj5643【NOI2018模拟4.10】最小代价
题目给你一个n个点m条边无向图，每一个点有两个权a，b，现在要你选出恰好k个点，其中这k个点可以形成恰好1个联通块，对于每一个这样的选取方案，代价是max{a}+max{b}，问最小的代价 其中n<=3e5,m<=5e5题解大概的思路就是把每一条边都赋一个边权，把问题转化成选k-1条边，然后就可以lct（快速的求子树的大小）了需要注意的是lct中不应该连的边不要乱...
2018-04-10 21:21:01
577
原创 JSOI2018 DAY 2 T2 林克卡特树
题意自己去找吧 转化之后大概就是给你一个有n个点的值，有边权，然后要你选出k+1条不相交的链，问选择的所有边的和的最大值题解先考虑一下60分，k是<=100的，那么我们不妨设f[i][j][0/1/2]表示当前我已经做完了i的子树，点i的度数是0/1/2，对于这一颗子树我们最多能选择的边权和是多少 现在题目的关键是要恰好选择k+1条不相交的链，而选多了选少了答案都可能会变...
2018-04-09 22:38:49
419
原创 min_25 JZOJ5594 最大真因数
Time Limits: 2000 ms Memory Limits: 524288 KB Detailed Limits DownloadsDescription一个合数的真因数是指这个数不包括其本身的所有因数，例如6 的正因数有 1; 2; 3; 6，其中真因数有1; 2; 3。一个合数的最大真因数则是这个数的所有真因数中最大 的一个，例如6 的最大真因数为3。 给...
2018-03-26 22:33:22
758
原创 【NOI2018模拟3.11】派对
题目Time Limits: 2000 ms Memory Limits: 262144 KB Description你想举行一场派对，有m个朋友会来参加。 你有n个房间，由n-1条道路连接，形成一个树结构。你需要给每个朋友安排一个房间，满足以下条件： 每个朋友住在一个单独的房间； 存在一个房间(不一定要有人)，使得每个朋友到它的距离不超过k。求方案数对998244353取模的结...
2018-03-12 22:41:43
382
原创 agc009d
题目大意类似点分治过程，只不过分治中心任意选择。 求点分树最小深度。题解首先有一个很简单的东西：两个在点分树里深度相等的点的路径之间一定有一个在点分树中深度更小的点，并且只要有就是一个可行的方案 那么我们直接设一个f[x]，这是一个二进制，表示当前x的子树中有多少种深度，某一个拥有这个深度的点到x的路径中没有深度更小的点，如果有对应位置就是1 因为我们不知道最终有多少层，所...
2018-03-01 22:30:06
391
原创 arc074f
题目大意给你一个n*m网格图，有起点荷叶和终点荷叶，有中转荷叶，其他的格子没东西，一个荷叶可以跳到同一行或者列的另一个荷叶。问最多删掉几个中转荷叶能让起点终点不连通。如果不行输出-1. n,m<=100题解中出了一个叛徒题目？？？ 裸的最小割？？？ 考虑到是删点我们直接把一个点拆成两个点，中间连一条流量为1的单向边就好了#include<iostream...
2018-03-01 17:24:39
253
原创 border [arc077f]
题目大意定义一个f(s)为将字符串s后面加上长度最小的串，使得新串仍时一个形如AA的串。在操作10^18次后求[L,R]中各个字母出现的次数。保证原串形如AA。题解首先操作可以看做是操作无限次 我们考虑每一次后面新添加的字符串T满足什么样的条件 一开始的S是形如s1s2s3...sns1s2s3...sns1s2s3...sns1s2s3...sns_1s_2s_3...s_n...
2018-03-01 16:25:50
314
原创 agc018d
题目大意给你一棵树，然后你需要找到一个n的排列，使得 相邻两个数在树中的距离和最大，输出这个距离题解不妨先单独的去考虑一条边，它把这一颗树分成了两个部分，我们经过这条边最多的次数就是其中点数较小的那一个部分 假设树只有一个重心，如果我们把起点放到重心处，每一次我们到的点都跨过重心，那么我们惊喜的发现除了重心到终点的路径少走了一次其他的点都走满了，而如果我们从其他的点开始一定不...
2018-03-01 14:59:51
331
原创 agc016d
题目大意现在一共有n个数，每一次你可以把其中一个数换成整个序列的抑或和，有一个目标序列，问最少多少步可以转化成目标序列，若无解输出-1题解这一题的操作本质上就是一开始序列中有n个数，然后你手上有这n个数的抑或和，每一次你可以把手上的数和序列中的一个数交换那么我们实际上就是要求有多少个置换，答案就是置换个数加上每一个置换的大小，如果某一个置换的其中一个目标值为一开始的抑或和，那么答案...
2018-02-28 22:20:03
342
原创 agc009e
题目大意给你n个0，m个1，和一个k。每次操作你选择k个数，擦去这k个数并加入他们的平均数（1个），问最后会有多少种不同的实数。 n,m,k<=2000题解这题感觉好难啊。。。 首先要进行一波神奇的转换，可以想象现在有一颗k叉树，然后一共有n+m个叶子节点，其中有n个为1，m个为0，每一个非叶子节点的值为所有儿子的平均数，问最后根节点有多少种不同的取值方案这两者显然是本...
2018-02-28 21:03:00
420
原创 arc064f
题目大意给出n,m.问有多少个长度为n的序列a满足:1<=a[i]<=m,并且序列a经过若干次循环左移能变成回文. i.e:1,1,2,2 左移一次-> 1,2,2,1. n,m<=1e9题解先考虑如果没有旋转的限制的情况 显然就是(n/2)m(n/2)m(n/2)^m，旋转的话理论上是乘n，但是显然会算重 算重的原因就是因为几个回文串可以通过题目...
2018-02-27 21:12:36
347
原创 arc068f
题目大意现在有一个1-n的序列，我们将它依次加入一个双端的序列，加完之后我们再每一次选择双端序列中的左端点/右端点，选择一个将对应的数删除并加入一个删除序列中，问最后有多少个合法的删除序列满足第k个是1题解好像和很多dalao的解法有一些出入观察一下一开始的序列，发现是一个v型的东西，并且1就是v的中间最低那一个点 那么我们的删除序列的1-k位就是一个可以分解为1个或者2个单...
2018-02-27 17:20:18
444
原创 arc072e
题目大意 有一个人要去直线上lm远处的地方，他会依次给他的机器发出n个指令。第i个指令为di。他的机器收到一个指令x后，如果向目的地方向前进xm后比当前离目的地更近，就会向前移动xm，否则什么都不会做。现在，给你q个询问，每一次给出一个x，问你能不能改变dx，使得这个人不能到达目的地。你可以决定把dx改成什么数。题解第一次看这一道题的时候一直在想一些猎奇做法，什么都想不出来，然后就...
2018-02-27 15:58:51
272
原创 arc072f
题目大意你有一个大小为L的容器，每天早上都会有一个已知温度，已知体积的水到容器里面，但是这个容器是会爆的，为了不让他爆，每一天的晚上你都可以放一些水，求第n天时，在容器满容量的前提下，可以达到的最高温度是多少（每一天给你的水必须照单全收） 温度变化的公式t1∗v1+t2∗v2v1+v2t1∗v1+t2∗v2v1+v2\frac{t1*v1+t2*v2}{v1+v2}题解观察一下这个温...
2018-02-27 15:30:19
332
原创 agc017f
题目大意现在你要写出m个长度为n的二进制序列，有一些形如“第i个的第j位必须为x”的限制 对于后面的二进制要>=前面的任意一个二进制题解每一个二进制只和和前面的一个二进制有关系，所以有一个很暴力的做法，就是状压前面的一个二进制然后枚举当前的二进制再判断是否合法，这样是22n22n2^{2n}级别的如何更进一步我们考虑从本质上思考如何判断两个二进制哪一个大哪一个小前面...
2018-02-27 11:19:48
267
原创 agc013d
题目大意一开始有一个盒子，里面有n个球（黑或白，但是具体的数量我们并不清楚）然后进行m轮这样的操作1：拿一个球，放到序列中 2：放一个黑球，一个白球 3：拿一个球，放到序列中问最后的序列的情况数题解那么每一次就有00,01,10,11四种情况，并且四种情况都对当前盒子里面的球的数量都有限制 一个困扰我们的问题是一开始盒子里面球的数量是不清楚的，但是发现我们要求的东西和...
2018-02-27 08:27:00
278
原创 arc075f
题目大意定义rev(n)为n翻转后的那个数，比如123变成321 现在给出一个d(d<=1e9)，求n+d=rev(n)的数的个数题解一个关键的问题是n似乎是可以无限大的，所以肯定要先确定一个n的上界观察原式： n−rev(n)=dn−rev(n)=dn-rev(n)=d 设其位数为s，n的第i位为p[i]（第一位是个位） 那么原式等于 ∑s−1i=0(p[i]...
2018-02-26 21:32:09
297
原创 agc010d
题目大意有一个有n个数（n<=1e5）的序列a，满足所有数的gcd为1 现在有a，b两个人轮流操作 每一次其中的一个人把一个大于1的数-1，然后所有数除当前序列的gcd 不能操作输题解初始gcd为1，说明至少有一个数是奇数 如果此时有奇数个偶数的话那么先手就有必胜的策略先手可以把一个偶数-1 然后就有偶数个偶数 然后可以每两个偶数捆绑成一对，后手选择一个就选择另...
2018-02-25 22:04:05
227
原创 送你一朵圣诞树
题目大意有一个无限长的数轴，每一个点的值是0/1，现在给你每一个是1的点的位置（不超过100个），每次可以把一段奇素数长度的值都抑或1，求最少多少步可以把整个序列都变成0题解直接做好像很难，完全没有思路看了一下题解发现是把这个东西差分了一下，就是设一个bi=aixorai−1bi=aixorai−1b_i=a_i xor a_{i-1} 这样做有什么好处呢？ 可以发现...
2018-02-25 21:22:11
588
原创 回文树（回文自动机）学习小结
基本的功能首先十分重要的一点是一个长度为|S|的字符串最多只有|S|个本质不同的回文串 http://blog.csdn.net/u013368721/article/details/42100363 这篇配图文章写得很清晰写一写里面没有的吧首先回文串很多时候都是以其奇偶性来恶心人的，而回文树通过构造两个根（对应的是偶数长度的回文串以及奇数长度的回文串，并且把对应长度为奇数的树根的
2018-01-20 22:08:11
293
原创 送你一朵圣诞树
#include#include#include#include#include#include#define fo(i,a,b) for(i=a;i#define db double#define max(x,y) ((x)>(y)?(x):(y))#define ll long longusing namespace std;const int maxn=30005;
2018-01-11 08:11:05
525
原创 第二类斯特林数【清华冬令营2018模拟】送你一个DAG
题目1.1 Description 送你一个n 个点m 条边的DAG 和参数k, 定义一条经过l 条边的路径的权值为l^k. 对于i=1…n, 求出所有1 到i 的路径的权值之和, 对998244353 取模. 1.2 Input Format 第一行三个整数n; m; k, 分别表示DAG 的点数, 边数和参数. 接下来m 行, 每行两个整数ui; vi, 表示一条从ui 到vi ...
2018-01-08 17:15:05
1067
原创 【清华冬令营2018模拟】距离
题解Description Input Output Sample Input输入1： 1 1 输入2： 2 2Sample Output输出1： 2 输出2： 40Data Constraint题解由题意可列出：ans=∑ki=1i∗∑kj=1Cjk∗(2∗i−1)k−j∗2jans=\sum_{i=1}^{k}i*\sum_{j=1}^{k}C_{k}^{j}*(2*i-1)^
2018-01-03 22:35:50
445
原创 51nod1223 分数等式的数量
【清华冬令营模拟12.28】和与积 (Standard IO) Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits DescriptionInputOutput Sample Input2 2 15Sample Output0 4Data ConstraintHint题解题目要我们求的是 a< b< n 且 a
2017-12-29 17:07:41
253
原创 【2011集训队出题】happiness
题目Description 高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。 作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。Input 第一行两个正整数n，m。 接下来是六
2017-12-27 22:33:57
307
原创 【JSOI2014】支线剧情
题解事实上就是一个上下界最小费用最小流，每一条边为（1,1<<30,c）表示最少流1，最多无限流，每流1就要c的花费那么问题就变成了怎么把这个东西跑出来新建源汇点 S，T对于每一条边a–>b 费用c，转化为：从S向T连一条(1,c)的边，表示我这一条边最少流1次 a–>b：(1<<30,c)，表示这一条边没有流的上限 a–>T连接一条(1,0)的边 然后每一个点向点1（原来的原点连一条(1<<
2017-12-27 17:15:28
339
1
原创 CTSC2008totem 【WC2016模拟】Picture
Description （2） InputOutputSample Input样例输入1： 5 1 5 3 2 4 样例输入2： 4 1 2 4 3Sample Output样例输出1： 0 样例输出2： 16777215Data Constraint 题目问的其实就是 1324-1432-1243 =(1x2x-1423)-(14xx-1423)-(12xx-
2017-12-25 21:42:54
371
原创 【WC2016模拟】打击目标
DescriptionInputOutput Sample Input3 0 xyz xy x 1 2 2 1 3 xyz 2 3 zzzzxySample Output3 2Data Constraint 题解这一题在比赛的时候我已经想到了和题解基本一样的做法，然而因为不会树剖（雾，所以只打了50point，结果数据超级水，要不是开小了数组就AC了QvQ 下午赶紧学习了一下树剖，
2017-12-25 21:12:19
461
原创 【AHOI2009】最小割
题目Description A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限
2017-12-22 20:49:50
375
原创 【JLOI2015】通道连接
题目Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits DescriptionInputOutputSample Input输入1： 5 8 4 1 2 3 1 3 2 1 5 1 2 4 2 2 5 1 3 4 3 3 5 1 4 5 1 1 1 1 2 2 3 2 4 输入2： 5 8 4
2017-12-21 15:27:16
504
原创 【清华集训2017模拟12.09】Tree
Description InputOutput一行一个整数, 表示最小的距离和。Sample Input10 7 1 2 35129 2 3 42976 3 4 24497 2 5 83165 1 6 4748 5 7 38311 4 8 70052 3 9 3561 8 10 80238Sample Output184524Data Constraint 题解设g[i][j]
2017-12-19 16:59:11
307
原创 【CEOI2013】Adriatic
Description“千岛之国”在20 世纪90 年代中期是克罗地亚旅游的官方宣传口号。虽然这个口号在技术上是不正确的（克罗地亚拥有略超过一千座岛屿），但是作为一个事实，环岛游（从一个岛航行到另一个岛）是一个流行的夏季活动。为了这个任务的目标，亚得里亚海的地图被视为一个由正方形格子组成的、2500 行2500 列的网格。行号从1 到2500，从北到南编号；列从1 到2500，从西到东编号。海中有N
2017-12-19 16:36:07
439
原创 jzoj【NOIP2017提高A组集训10.28】图
题目Time Limits: 2500 ms Memory Limits: 524288 KB Detailed Limits Description有一个n个点A+B条边的无向连通图，有一变量x，每条边的权值都是一个关于x的简单多项式，其中有A条边的权值是k+x，另外B条边的权值是k-x，如果只保留权值形如k+x的边，那么这个图仍是一个连通图，如果只保留权值形如k-x的边，这个图也依然是一个
2017-12-08 22:20:10
324
原创 JZOJ 5387【GDOI2018模拟9.23】动态图
题目Time Limits: 1000 ms Memory Limits: 262144 KB Description InputOutput Sample Input5 3 0 1 4 5 1 2 4 3 1 2Sample Output3Data Constraint 题解鸟（雀）题一道。。。做法：函数式线段树+lct在每一次加入一条边i的时候，我们记录一个last[i] 如
2017-12-06 22:27:37
701
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人