WorldWide_D-CSDN博客

原创留的一些坑（有空和有能力时填掉）

鼓足干劲，力争上游持续更新。Matrix-Tree定理和模意义下的矩阵行列式例题：bzoj 4031 bzoj 4596斯坦纳树广义后缀自动机例题：bzoj 3926treap

2016-09-03 10:23:56 1293

原创 GDOI2018 记

day0达成成就：在中山住酒店晚上去远洋喝东西，顺便看同行的两个人玩沙雕游戏将近1h 回去开个会就差不多睡了day1我上去抄个密码，回头有个兄弟做我位上帮我把密码输了。。拿到题目，t1似乎是个签到题，t2有点眼熟但是不太会，t3是个一眼题，t4又是有点眼熟。。先把t1写了，发现自己是约数个数*n的做法。1e6之内似乎约数个数最大是200多，但是我感觉由于ai≤10，应该跑不满，就没有管

2018-05-03 22:46:54 1192

原创 [codeforces955F] Heaps

题目大意我们称一个有根树的节点u是 k-ary heap of depth m 的，当且仅当其满足以下条件之一： 1. m=1 2. m>1，u有至少k个儿子是至少 k-ary heap of depth m-1的（即儿子可以是 k-ary heap of depth n的，n≥m）给定一个n个节点的有根树（1是树根）。设dp[k][u]表示一个最大的m，满足u为根的子树中存在节点是 k-a

2018-03-26 21:47:52 703

原创 [codeforces 917D]Stranger Trees

题目大意给定一棵n个节点的树。对于k=0到n-1，输出有多少棵n个节点的带标号无根树恰好与给定的树有k条公共边。答案模109+710^9+7 n≤100分析我们从prufer序的角度考虑这道题。选择了若干条原树的边后，我们得到一些联通块。把这些联通块都缩在一起，假设剩下m个点，接下来我们要去连接这些联通块，得到一棵树，然后考虑这棵树的prufer序是怎样的。由于当前叶子的父亲所表示的联通块

2018-03-01 20:32:05 779

原创 [codeforces 938G]Shortest Path Queries

题目大意给定一个n个点m条边的无向联通简单图，边有边权。接下来有q次操作，操作有三种： 1. 添加一条边，保证添加后仍是简单图 2. 删除一条边，保证删除后仍是联通图 3. 给定x,y，求所有x到y的路径中所有边权异或和最小值（一条边经过多次算多次） n,m,q≤200000 边权<230<2^{30}分析首先我们联想到CF另一道题845G，这题没有前两个操作，只询问1到n的答案。那道

2018-03-01 15:27:56 787

原创 [arc061F] Card Game for Three

题目大意A,B,C三个人玩游戏，最初每个人分别有n,m,k张牌，每张牌上有字母a,b,c之一，但是不知道每张牌具体是什么。由A先操作，每轮操作者翻出自己牌堆顶的一张牌并弃置，下一轮的操作者是该牌上字母对应的人。不能操作的人赢。问有多少种初始牌的情况能使A胜利。答案模1,000,000,0071≤n,m,K≤300,000分析考虑枚举翻牌序列有x个b，有y个c，那么序列长度应该是n+x+y。由于最后一

2018-02-27 15:53:31 654

原创 [agc013E]Placing Squares

题目大意给定一个n和m个数（升序给定，满足1≤s1 < s2 < … < sm ＜ n）你有无限个边长为正整数的正方形。你在数轴正半轴用正方形放在上面覆盖它。需满足：正方形恰好把0到n的区域覆盖完；不能翻转或叠置，且相邻两个正方形之间的缝隙坐标不能是m个数中任意一个。一个方案的贡献为所有正方形面积乘积。求贡献和模109+710^9+7n≤10910^9 m≤10510^5分析这题的思路在之前打

2018-02-22 18:30:56 526

原创 [agc016F] Games on DAG

题目大意给定一个n个点m条边DAG，每条有向边(x,y)满足x < y。现在有一个博弈：有两个棋子分别在节点1、2，两人轮流做以下操作：选择一个棋子，由其所在节点的出边移动到另一个节点。不能操作算输。假设两人绝顶，现在问有多少种边的子集满足：保留这些边之后先手必胜。方案数模109+710^9+7n≤15，没有重边分析可以考虑按照sg给图分层。同时容易发现，两个棋子是两个独立的游戏，为了方便，只需

2018-02-15 12:00:48 739 1

原创 GDKOI游记

day0又到了写游记的时候了~ 这次koi摆到了冬令营之前，还设置了一个讲课日，很悠闲啊。然而之前一个月都在做5h3题的模拟赛，可能会对4h4题不适应day1早上出门，感到凉凉。集体迟到了15min…结果试机的时间也没有了。只得匆匆应战。看完所有题，第一题马上有了思路，但是发现自己写出来是两个log的。计算一下感觉有点虚。但是评测时开O2，我就大胆写了。结果样例调了挺久，一对拍又是错。。很

2018-01-28 22:00:28 605

原创 [codeforces896E] Welcome home, Chtholly

题目大意给定一个n个数的序列。m次操作：1. 给区间[l,r]中所有大于x的数减x 2. 询问区间[l,r]中数值为x的数个数。n,m≤100000 1≤a[i],x≤100000分析这题？循环展开然后optimize一下就过了这是由乃题，我们应该考虑分块。值域范围比较小，我们可以直接记录cnt[i][j]表示块i中数值为j的数个数。然后再用并查集把同一块中数值相同的元素缩在一起。对于

2018-01-19 20:31:10 556

原创 [bzoj5011][Jx2017]颜色

题目大意给定n个数的序列，你需要选出一个数字集（可以为空集），使得原序列中所有未被选的数字恰好是一个非空的区间。n≤300000，1≤ai≤n分析题目等价于被选的数字恰好是一个非空的区间。对于所有可行的极小区间，它们之间的关系只有两种：包含和没有交集。那么可以考虑扫一遍这个序列，用单调栈按第一次出现时间维护当前未被扫完的数值。如果栈顶的数值被扫完了，那么一直退栈直到栈空或栈顶元素未被扫完。这

2018-01-19 10:43:27 404

原创 [Codeforces860E]Arkady and a Nobody-men

题目大意给定一个n个节点的有根树。设r(a,b)r(a,b)，其中b是a的祖先，这表示b的后代中除a以外深度不大于a的节点个数。设z(a)=∑r(a,b)z(a)=\sum r(a,b)。求每个z(a)z(a)n≤500000分析答案等于：∑dep(b)≤dep(a)dep(lca(a,b))−dep(a)\sum_{dep(b)≤dep(a)}dep(lca(a,b))-dep(a) 这等价于z

2018-01-16 20:22:03 519

原创 [codeforces856C]Eleventh Birthday

题目大意给定n个正整数，你需要把它们按任意顺序拼接，得到一个大数。问有多少种方案使得最终得到11的倍数。如果两个数相同，它们交换位置也算不同方案。答案对998244353取模n≤2000 数字≤10910^9分析找突破口。我们发现，一个数的奇数位每加1，对模11的余数的贡献是1，偶数为每加1，贡献是-1。证明？10≡−1(mod11)10≡-1(mod 11) 我们跟着这个思路走下去。对

2018-01-12 22:22:26 718

原创 [codeforces 891E]Lust

题目大意给定大小为n的数组，还有一个变量res（初始为0）。进行k次操作，每次随机选择一个数ai，然后给res加上∏j≠iaj\prod_{j≠i}aj，然后ai-1 问最终res的期望值模1e9+71e9+7的值。n≤5000，0≤ai,k≤10910^9分析首先转化题意：每一次加的数可以看成操作前所有数的乘积减操作后所有数的乘积。那么只需求最终序列累乘的期望值，然后用初始的值减去它即可。接

2018-01-11 17:41:14 734

原创 [codeforces 886F]Symmetric Projections

题目大意给定二维平面上n个点。问有多少条直线满足：所有点在它上面投影得到的点集是对称的。有无限条输出-1n≤2000分析首先：对称中心一定是原点集的重心在其上面的投影。接下来：如果两个点关于重心对称，那么它们在任意直线上的投影点都关于重心在其上的投影点对称。可以将这对点删去。接下来枚举两个点，令它们对称，容易发现对应的直线是唯一的。那么我们可以得到n2n^2条直线，一条直线出现过不小于n次才

2018-01-11 10:56:23 564

原创 [codeforces827F] Dirty Arkady's Kitchen

题目大意给定n个点m条无向边，边权为1.每条边还有一个出现时间区间。从1出发，每个时刻必须沿着一条边走到另一个点。问你最早什么时候到达n。无解输出-1 n,m≤500000分析我们不妨把每个点拆成两个点，表示时刻为奇数和偶数。边也按照奇偶拆开，再拆成两条有向边。然后用小根堆以加入时间为关键字维护每条边。设Late[u][p]表示当前奇偶性为p的点u，最晚可以逗留到什么时候。加入一条边时，如

2018-01-10 16:56:36 420

原创 [codeforces848D] Shake It!

题目大意给定n,m，最开始一个无向图中只有两个点s,t和连接它们的一条边。你需要进行n次操作，每次选择图中一条边(u,v)，加入一个点i，并且添加两条边(u,i)，(i,v)。问最终有多少种不同构的图，满足其s-t最小割为m。模10^9+7输出n,m≤50分析设f[i][j]表示i次操作，s-t最小割为j的方案数。接下来你需要枚举五个数a,b,c,d,x（其中四元组(a,b

2018-01-09 22:21:04 630

原创 [codeforces 718E]Matvey's Birthday

题目大意给定一个长度为n的字符串，字符集大小为8。两个点i,j之间有权值为1的边当且仅当满足以下条件之一 1. |i-j|=1 2. si=sj求图的直径和多少个有序点对之间的最短路长度等于直径2≤n≤100000分析好题设dist(i,j)dist(i,j)表示点i到点j的最短距离，Dist(i,c)Dist(i,c)表示点i到字符c的最短距离。易得dist(i,j)=min(|i−j

2018-01-03 17:29:08 559

原创 [codeforces884F]Anti-Palindromize

题目大意定义“反回文串”为一个字符串S[1..|S|]，对于任意1≤i≤|S|都满足S[i]≠S[|S|-i+1]。很显然长度为奇数的字符串不可能是反回文串。现给定字符串S，保证其长度为偶数。你需要把S的字符顺序打乱得到字符串T，满足它是反回文串，并且最大化其价值。价值定义为：所有满足S[i]=T[i]的位置i的b[i]之和（b数组给定）|S|≤100 字符集为小写字母分析这种问题一般考虑网络

2017-12-29 21:39:06 463

原创 [codeforces840E] In a Trap

题目大意有一个n个节点的有根树，边权为1，点权给定，第i个点的点权是ai。q次询问，每次给定u,v，并保证u是v的祖先。问对于u到v路径上的所有i（包括u,v），最大的ai xor dist(i,v)。其中dist(i,v)是i到v的距离n≤50000 0≤ai≤n q≤150000分析这题的做法很有趣。我们把v到u的路径每256个节点分成一段（最后一段可能不够256个，可以单独枚举

2017-12-27 15:13:23 561

原创 [bzoj5101] [POI2018]Powód

题目大意有一个n*m的网格图，给定相邻的格子之间墙的高度，并且默认边界的墙的高度是无穷大的。再给定水位上限H，问有多少种可能的水位。n*m≤500000 H≤1,000,000,000分析可以把每个格子看成一个点，相邻的点之间有边权为墙高度的边，然后求一次最小生成树。在克鲁斯卡尔算法过程中，当两个点在一个联通块时，水位一定是一样的。那么再设Ans[x]表示联通块x当前的答案。新加入一条

2017-12-24 16:01:02 564

原创 [codeforces903G]Yet Another Maxflow Problem

题目大意给定一个2n个节点的图，其中n个点在A集，n个点在B集。且称A集第i个点为ai（B集类似）。每个ai（i < n）向ai+1连一条给定容量的边（B也一样），还有m条边从ax连到ay，容量给定。有q次操作，每次修改一条ax连向ax+1的边的容量（x和容量给定）。你需要对每次操作以及操作前输出以a1为源点，bn为汇点的最大流。n,m,q≤200000分析首先最大流=最小割考虑没有修改怎么

2017-12-18 19:25:11 452

原创 NOIP2017游记

day0今年跑到了郊区考场…晚饭吃得比较早，所以到那里时又叫了夜宵。晚上也没怎么腐，和平时差不多的时间就睡了。day1坐进了考场后，今年连试机的时间也没有。。坐在那干等了15min开场。待到8点半比赛开始，解压了文件后，发现今年只有example_data和题目。没有注意事项、没有要求写什么自我介绍txt不过没有太在意。首先看完所有题。第一题竟然不会，第二题感觉就是个模拟，第三题大概是拓扑序

2017-11-18 11:07:42 1118

原创 [arc076F]Exhausted?

题目大意有m个椅子，第i个在位置i，每个椅子只能坐一个人。有n个人，第i个人能坐的椅子的位置j需满足j≤Li或j≥Ri。现在你可以添加若干个椅子，可以放在任意实数位置。问最少加多少个n,m≤200000分析题目就是问你最多坐多少个人… 首先考虑只有L或R的限制。以只有L为例，可以按位置从小到大枚举椅子，在Li处决定i坐在哪。很显然的贪心是：枚举每往后一个椅子就多一个位置放人，然后已知Lj=

2017-11-04 21:33:06 702

原创 [codeforces870F] Paths

题目大意对于一个n个节点的图，节点编号为1到n，对于两个节点u,v，如果它们的gcd大于1，那么u与v之间有一条长度为1的边。给定n，求节点两两之间距离之和（不连通则距离视为0）n≤10710^7分析首先容易发现，两个端点如果有一个编号为1或为大于n2\frac{n}{2}的质数的点，那么这两点间一定没有路径。接着两两间有路径的点对分以下几种情况： 1. 编号相同，距离为0 2. gcd

2017-10-30 15:59:11 592

原创 [bzoj2131] 免费的馅饼

题目大意你在一个1*W的格子图上，最开始可以在任意位置。每一个时刻你可以向左右移动1或2格，也可以不动。第i个馅饼在ti时刻落在位置pi上，价值为vi。问你可以获得的最大价值和是多少。n≤100000 W,pi,ti≤10810^8分析设f[i]表示最后一个拿到的馅饼是i的答案。 i能转移到j，需要满足的条件是|wi−wj|≤2(tj−ti)|wi-wj|≤2(tj-ti) 可以把绝对值拆开，

2017-10-25 20:38:11 462

原创 [bzoj5017/Snoi2017]炸弹

题目大意在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足： Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。对于i等于1到n，求把第i个炸弹引爆会导致多少个炸弹爆炸。n≤500000，|Xi|≤101810^{18}，0≤Ri≤2⋅10182·10^{18}，保证Xi严格递增分析首先引爆的炸弹肯定是一个区间。

2017-10-23 20:36:45 670

原创 [agc017F]Zigzag

题目大意有一个n行的三角形，第i行有i个格子。第i行第j个格子用(i,j)表示。从(i,j)可以到达(i+1,j)和(i+1,j+1)。现在要确定m条从(1,1)出发到第n行的路径。设第a条路径走到的第b个格子是(b,X[a,b])，对于任意a < b，不能存在i，使得X[a,i]>X[b,i]。同时还有K条形如(a,b,c)的限制，表示第a条路径第b个点到第b+1个点必须往方向c走。求合法的方

2017-10-22 14:50:49 867

原创 [jzoj3865/JSOI2014]士兵部署

题目大意给定平面上n个整点。m次询问，每次给出一个整点P，问n个点加上P之后形成的凸包面积为多少。n,m≤100000分析首先可以给n个点求个凸包，然后就是计算加上P之后凸包增加的面积。先判掉凸包是一个点或线段的情况。接下来讲一般情况。如果能找到过点P的两个切线就可以求增加的面积了。假设P在凸包外面，那么可以考虑先随便在凸包上确定一个点Q，然后直线PQ和凸包有两个交点（如果这条直线恰好是

2017-10-19 16:40:35 408

原创 [codeforces850D]Tournament Construction

题目大意给定m个数的一个非负整数集合，不超过30。你需要构造一个竞赛图，满足：所有点的出度去重后等于该集合。 m≤31分析做这题需要用到兰道定理(Landau’s Theorem)。设点i的出度为d[i]，那么对于任意1≤i≤n1≤i≤n,有∑ij=1d[i]≥i(i−1)2\sum_{j=1}^{i}d[i]≥\frac{i(i-1)}{2}。且当i=n时是等于。那么可以考虑构造一个合法

2017-10-14 12:51:44 540

原创 [codeforces873E]Awards For Contestants

题目大意给定n个正整数，要把它们放进三个组（分别为1号组，2号，3号），也可以不放。每组至少要有一个数。同时对于对于1,2,3号组，两两直接必须满足cnt[p]≤2*cnt[q]，其中cnt[x]表示x号组有多少个数。对于两个数x,y，如果x < y，那么y不能放在编号比x大的组。定义c[x]表示x号组的最大数，d[x]是x号组的最小数。特殊地，c[-1]表示没有放的数的最大值，d[-1]同理。

2017-10-14 09:58:46 660

原创 [codeforces864F]Cities Excursions

题目大意给定n个点m条边的有向图。q次询问，每次给定x,y,k，求x到y的字典序最小的路径的第k个节点。路径是可以无限长的（1到2到1到2…，前提是能到达目标节点）。如果字典序最小的路径无限长或者x无法到达y或者路径没有k个点就输出-1.n,m≤3000，q≤400000分析考虑一个询问怎么做。首先预处理出每个点能到达的所有点。然后从x出发，每次枚举当前点出边，在所有能到达y的点中找一个编号最小

2017-09-28 19:34:44 530

原创 [bzoj5043]密码破译

题目大意有一个n个数的数组a和一个非负整数k（a[],k未知），但是你知道数组b，对于任意i满足bi=ai^k。你还知道∑ai=m\sum ai=m求可能最小的k，无解输出-1 n≤100000，bi≤2602^{60}分析其实这种题都是套路题。首先可以预处理cnt[i]表示b数组有几个数二进制第i位为1，p[i]表示m的二进制第i位是否为1。然后从高到低逐位确定k。设f[i][j]表示确定到

2017-09-23 22:01:06 1227

原创博弈

题目大意给定一棵n个节点的树。两个人进行博弈，后手的人最初在节点b上，还给定一个目标节点t。对于后手的人，如果有至少一条未被标记的边连着它所在的节点，那么它必须选择其中一条走过去，并标记下这条边。否则不用动。对于先手的人，每次可以：1. 删除一条边 2. 删除一条边的标记 3. 不操作。现在先手者想以最少的操作次数把后手者赶到目标节点（不操作不计算次数），后手者则想最大化这个答案。两个人

2017-09-23 17:25:17 312

原创 [codeforces856D]Masha and Cactus

题目大意给定n个点的树，接下来给出m条非树边，每条非树边有一个价值。现在你可以添加一些非树边，在保证每个点最多在一个简单环的情况下，求价值和最大值。n,m≤200000分析首先考虑dp，设f[i]表示以i为根的子树的答案。把每条非树边挂在lca上。求f[i]时，首先处理不选择一条lca为i的情况。接下来枚举一条lca=i的非树边，加上其它儿子的f值、该边所覆盖的路径的答案。难点就在于求一条路

2017-09-16 09:15:43 714

原创 [bzoj4811] [Ynoi2017]由乃的OJ

题目大意给定一棵树，n个节点，问有多少个三元组(x,y,z)(x < y < z)，满足这三个点在树上距离两两相等。 n≤100000分析你可以想到一个n方的dp：设f[i][j]表示i为根的子树中，与i距离为j的节点有多少个。g[i][j]表示i为根的子树中，有多少个二元组(x,y)(x < y)满足：设d表示它们到lca的距离都为d，它们的lca到i的距离为d-j。那么做到i节点时，先递归

2017-09-14 18:49:59 599

原创 [bzoj4543] [POI2014]Hotel加强版

题目大意给定一棵树，n个节点，问有多少个三元组(x,y,z)(x < y < z)，满足这三个点在树上距离两两相等。 n≤100000分析你可以想到一个n方的dp：设f[i][j]表示i为根的子树中，与i距离为j的节点有多少个。g[i][j]表示i为根的子树中，有多少个二元组(x,y)(x < y)满足：设d表示它们到lca的距离都为d，它们的lca到i的距离为d-j。那么做到i节点时，先递归

2017-09-13 21:37:57 810

原创 [bzoj4867] [Ynoi2017]舌尖上的由乃

题目大意给定一棵n个节点的树，边有边权。m个操作：1. 给一条边边权加k；2.询问一棵子树第k小的深度。修改操作的k和最初的边权不超过一个给定的常数lenn,m≤100000 len≤10分析首先可以求出dfs序，转化到序列上。用数据结构似乎无从下手，于是考虑分块。首先查询是可以二分答案的，对于询问区间完全包含掉的块，预处理一个以权值为下标的数组的前缀和，可以O(1)查询。那么对

2017-09-02 22:13:20 802 1

原创 [bzoj4977]跳伞求生

题目大意有n个队友和m个敌人，每个队友有一个攻击力ai，每个敌人有攻击力bi和价值ci。你可以选择若干个队友，每个队友i去怼一个敌人j（i,j两两不同），当ai>bj时，你的队友可以对答案造成ai-bj+cj的贡献。问答案最大可以是多少。n,m≤100000分析我首先往贪心方面想。考虑把队友按a升序排序，敌人按b升序排序。然后枚举攻击力，开一个优先队列维护可以怼的敌人的c-b。然后对于一个对友，

2017-08-24 22:31:09 1360

原创 [bzoj4976]宝石镶嵌

题目大意给定n个数以及k，要求将n个数去掉k个，剩下的值or起来最大。n≤100000 k≤100 每个数是不大于100000的正整数分析假设所有数中总共sum个二进制位出现过1，那么当n-k≥sum时，每个1都一定可以出现。当n-k < sum时，n最大只有116，可以设f[i][j]表示前i个数，or和为j最多可以去掉多少个数，转移很简单。#include <cstdio>#include

2017-08-24 20:55:51 706

空空如也

空空如也