- 博客(219)
- 收藏
- 关注
RSS订阅原创 2019ICPC南昌题解
B-A Funny Bipartite Graph题意：给出每一边的点数都不超过n≤18n\leq18n≤18的二分图，对左边的点标号iii从111到nnn，对右边的点标号jjj从111到nnn，数据保证不会出现iii到jjj的连边(i>j)(i>j)(i>j)，保证左边的每个点的度数都在111到333之间。并且给出一个矩阵AAA，在这个矩阵中，如果Ai,j=1A_{i,j}=...
2019-12-10 22:10:01
1417
原创 [2019CCPC哈尔滨] L LRU Algorithm 模拟
给一个n≤5e3n\leq5e3n≤5e3的序列，这个序列从左往右表示每次都往里面插入一个元素，如果这个元素不在里面，那么会插入在头部，否则就删除掉在原来的位置并且重新插入到头部。然后如果插入的元素超过容量，那么就会将尾部的弹出。并且给出q≤2e3q\leq2e3q≤2e3次询问。对于每次询问，给定一个容量，然后和一个序列，现在要判断这个序列是否在整个插入的过程中出现过，忽略后缀000。显然对...
2019-11-15 11:41:06
379
原创 [2019CCPC哈尔滨] B Binary Numbers dp
题意比较复杂。给出m≤17m\leq17m≤17 表示我现在有[0,2m−1][0,2^{m}-1][0,2m−1]这样的一个区间，然后现在有0≤N≤2m0\leq N \leq 2^{m}0≤N≤2m表示我将会把这个区间分为NNN段区间，这NNN段是覆盖所有的区间并且严格不相交的。然后在每个区间里面都选一个数Ai∈[Li,Ri]A_{i}\in[L_{i},R_{i}]Ai∈[Li,Ri...
2019-11-15 11:24:41
351
原创 [2019CCPC哈尔滨] A Artful Paintings 二分+差分约束
有N≤3e3N\leq3e3N≤3e3个格子，你可以任意给每个格子染色，但是要满足M≤3e3M\leq3e3M≤3e3限制条件，限制条件有两种类型：1.1.1. 区间[l,r][l,r][l,r]中被染色的格子数量不少于KKK。2.2.2. 区间[l,r][l,r][l,r]外被染色的格子数量不少于KKK。在满足所有限制条件下求染色格子数量的最小值。显然染色格子数量越多，越容易满足。因此二...
2019-11-15 11:06:02
770
原创 [2019CCPC哈尔滨] E Exchanging Gifts 拓扑排序
给出n≤1e6n\leq1e6n≤1e6个数字串，数字串的总和不会超过1e61e61e6，但是会有一个将两个数字串连接的操作，总数字串的长度会比较大，最大会有1e181e181e18。然后求问你可以通过若干次交换，使得最多的数字自己的位置上和原来的数字不同，求这个最大值。可以发现不同的数字不会超过1e61e61e6个，所以可以考虑基于值然后统计每个值的次数。对于每个被生成的串，由它向合成它的两个...
2019-11-14 10:31:10
500
原创 [2019CCPC哈尔滨] I Interesting Permutation 组合数学
对于一个序列，定义fif_{i}fi表示它的前缀最大值，gig_{i}gi表示它的前缀最小值，hi=fi−gih_{i}=f_{i}-g_{i}hi=fi−gi。现在给出一个hhh数组，求问合法的原序列的个数。注意到hih_{i}hi是单调不降的，并且h1=0h_{1}=0h1=0且hn≤n−1h_{n}\leq n-1hn≤n−1。首先先判断对于hih_{i}hi都是合法的，...
2019-11-13 21:22:16
576
原创 BZOJ4883 棋盘上的守卫 最小基环树
给一个N×M≤1e5N×M\leq1e5N×M≤1e5的棋盘，然后每个棋盘都可以放一个守卫，你可以选择是让它保护横向的也可以让他保护纵向的。然后一个位置最多只能放一个守卫，放置在(i,j)(i,j)(i,j)这个位置的代价是wi,jw_{i,j}wi,j。然后求使得所有的位置都被守护的最小代价。完全不太会做的题。一种费用流/最大权匹配的做法是左边放N+MN+MN+M个点分别表示行/列，右边是...
2019-11-12 14:36:28
135
原创 BZOJ2654 tree 二分+最小生成树
给出N≤5e4,M≤1e5N\leq5e4,M\leq1e5N≤5e4,M≤1e5的无向连通图，一些边是白色，一些边是黑色的。然后求问满足恰好的KKK条边是白色的最小生成树的值是多少。是有一个比较新奇的思路，有博主把这个称为凸优化，具体做法是先...
2019-11-12 13:33:53
129
原创 BZOJ3714 Kuglarz 最小生成树
给出n≤2e3n\leq2e3n≤2e3个小球，并且你可以花费cl,rc_{l,r}cl,r查询[l,r][l,r][l,r]这一段小球的奇偶性，现在求问你要确定每个位置是否有小球的最小花费是多少。确定每个位置是否有小球等价于确定所有的前缀的奇偶性。对于前缀iii和前缀i+1i+1i+1：1.1.1.奇偶相同，iii不存在小球。2.2.2.奇偶不同，iii存在小球。对于区间[l,r][...
2019-11-12 11:11:09
114
原创 洛谷P2245 星际导航 最小生成树+lca
给出一个N≤1e5,M≤3e5N\leq1e5,M\leq3e5N≤1e5,M≤3e5的无向图，无向图的图上有边权。然后给出q≤1e5q\leq1e5q≤1e5次询问，每次询问给出两个点u,vu,vu,v，求u,vu,vu,v路径上最大边的最小值。应该是一个挺常规的问题：容易想到这样的路径是最小生成树上的路径。先求出最小生成树，然后可以预处理出lcalcalca，在倍增的过程中可以维护每个结点...
2019-11-12 10:49:59
158
原创 洛谷P3225 [HNOI2012]矿场搭建 割点
给出n≤1e3n\leq1e3n≤1e3个点的无向图，你可以在每个点选择放置避难所。然后求问所有的方案满足：1.对于任何一点被破坏，剩下的点能都走到避难所。2.放置避难所的数目最少。...
2019-11-11 20:35:30
120
原创 洛谷P3119 草鉴定Grass Cownoisseur 强连通分量+最长路
给出一个有向图，然后从111号点出发，有一次可以逆行的机会，求最终走回到111号点一共走过的点数是多少。显然可以先把环上的点走完，所以先对原图缩点，每个点的点权为强连通分量的大小。然后考虑把图分为两层，对上一层的点连反边到下一层。然后求最长路。d...
2019-11-11 18:41:51
150
原创 洛谷P2764 校园网Network of Schools 强连通分量
给出n≤100n\leq100n≤100个点，每个点都有若干个出边表示可以传递到下一个点。然后有两个问题，分别是求最少的点使得信息全部被传递以及需要在列表里面增加多少信息才能使得任何一点开始使得信息能够全部被传递。先缩点变成一个DAGDAGDAG。对于问题111，答案显然是入度为000点的个数。对于问题222，答案为入度为000的个数和出度为000的个数的较大值。因为只需要对入度为000和出...
2019-11-11 16:55:59
94
原创 洛谷P3469 BLO-Blockade 割点
给出一个无向图，然后求问对于每个点iii，如果去掉这个点iii，那么有多少个有序对(x,y)(x,y)(x,y)将无法到达。显然分两类情形：1.iii不是割点，那么去除iii对连通性没有影响，所以答案即为2(n−1)2(n-1)2(n−1)2.iii是割点，那么去除iii会把图分成若干块，除了2(n−1)2(n-1)2(n−1)以外，还要加上所有的不同块中的点对。这个只要在求割点的时候统计...
2019-11-11 15:10:18
181
原创 洛谷P1345 奶牛的电信Telecowmunication 最小割
给出n≤1500n\leq1500n≤1500个点，然后有两个点c1,c2c_{1},c_{2}c1,c2会通过某些通路相连，然后你可以去除掉某些点，如果某个点被去掉。那么和这个点相连接的边也会被去除。然后求问去掉最少的点，使得两个点不连通。拆点，中间连接一条容量为111的边，然后点与点的连接从下面的点连接到上面的点。求最小割。对于那些认为不能拆开的点，一般连infinfinf的流量。#...
2019-11-11 14:23:21
95
原创 洛谷P2055 假期的宿舍 二分图匹配
给出n≤50n\leq50n≤50个人，然后一部分是在校学生，其中一部分要回家，另一部分留校。然后另外一部分是外来学生。然后每个人可以睡到和自己认识的人的床位上。然后求问是否存在一种方案可以满足所有的人都有睡觉的床位。对于所有的留校学生和外来学生都建边连到自己可以睡的床位。然后做二分图最大匹配，如果可以完全匹配，那么满足条件。#include<bits/stdc++.h>usi...
2019-11-11 13:18:25
117
原创 洛谷P1726 上白泽慧音 强连通分量
给出n≤5e3n\leq5e3n≤5e3并且m≤5e4m\leq5e4m≤5e4的有向图，求最大强连通分量，对于大小相同的输出字典序最小的。裸的tarjan缩点，复习一下tarjan求强连通分量：直接对有向图某处开始dfs，...
2019-11-11 12:53:05
93
原创 洛谷P1993 小K的农场 差分约束
对于nnn个物品，给出mmm个限制关系，分别是：1.aaa比bbb至少多种ccc单位的作物。2.aaa比bbb至多多种ccc单位的作物。3.aaa和bbb的作物数相等。求问是否满足这样的一种情形，符合所有的限制关系。不妨记f(∗)f(*)f(∗)表示∗*∗的作物数，显然各条件等价于：1.f(a)−f(b)≥cf(a)-f(b)\geq cf(a)−f(b)≥c2.f(b)−f(a)≥...
2019-11-07 12:31:46
95
原创 [2016CCPC-final] H Engineer Assignment 状压dp
给出n,m≤10n,m\leq10n,m≤10分别代表有nnn个工程以及mmm个工程师，然后给出每个工程所需要能力以及每个工程师所具备的能力，求问如果分配工程师使得能够完成的工程最多。因为数据范围很小，可以直接预处理对于每个工程iii，所有2m2^m2m种状态的工程师是否可以完成。那么fi,Sf_{i,S}fi,S表示到前iii个工程，当前工程师的状态是SSS能够完成的最多的工程数。然后暴力...
2019-10-21 10:55:58
232
原创 [2016CCPC-final] B Wash 贪心
给出l≤1e6l\leq1e6l≤1e6件衣服，然后给出n≤1e5n\leq1e5n≤1e5台洗衣机以及m≤1e5m\leq1e5m≤1e5台烘干机，每台洗衣机有一个洗衣服的时间wiw_iwi，每台烘干机有一个烘干的时间did_idi，然后求问最少的把所有的衣服烘干的时间。首先，应该让每一件衣服尽早洗完。优先队列维护下每台洗衣机结束的时间，直接模拟。然后贪心把洗完时间最晚的衣服优先用更快的烘...
2019-10-21 10:46:14
264
原创 [2017ICPC-EC上海] B Scapegoat 贪心
给出n≤2e5n\leq2e5n≤2e5个数，并且给出m≥nm\geq nm≥n，你要将这nnn个数均分为mmm组，然后使得这些数的值的方差最小，求问最小的方差是多少。分成了mmm组，其实最终的平均值是不变的，即∑i=1nai/m\sum_{i=1}^{n}a_i/m∑i=1nai/m，而且每个数至少要分到一组里面。接下来就是每次贪心把一个数多划分一组，选择那个多划分一组之后对答案的贡献下降...
2019-10-13 20:53:30
265
原创 [洛谷P2992] 三角形计数 几何
平面上给出n≤1e5n\leq1e5n≤1e5的点，然后求有多少个三角形满足这个三角形包含原点(0,0)(0,0)(0,0)。直接考虑包含原点的三角形比较难计算。考虑算不包含原点的三角形的个数，固定一个点，那么所有不包含原点的三角形的另外两个端点一定在该点与原点连线直线的同一个半平面中。对每个点只选取逆时针的半平面避免出现重复的情形。这样对所有的点先极角排序，然后双指针维护左半平面点的个数。...
2019-10-11 14:55:58
200
原创 [2018ICPC焦作] K Counting Failures on a Trie 哈希+倍增
给出一个n≤1e5n\leq1e5n≤1e5的字典树，并且给出n≤1e5n\leq1e5n≤1e5的字符串sss，每次询问给出一个区间[l,r][l,r][l,r]，然后让这个子串在字典树上沿边匹配。每次如果失配就会重新回到根的位置重新匹配。对于每次查询，求出失配的次数以及最终匹配到位置。先考虑如何快速求出第一次失配的位置，对于每个后缀的开头，一定满足当前这个前缀如果不失配，那么更小的前缀也不会...
2019-10-11 01:21:46
252
原创 [2018ICPC焦作] H Can You Solve the Harder Problem? 后缀数组+线段树
一句话题意：给出n≤1e5n\leq1e5n≤1e5个数，求所有本质不同的连续子序列最大值和。如果没有本质不同的条件限定：对于每个左端点iii，记录fif_ifi是iii作为左端点答案。fi=(j−i)+fjf_i=(j-i)+f_jfi=(j−i)+fj，jjj是第一个值不小于iii的位置。求每个位置向右第一个不小于...
2019-10-10 20:16:02
247
原创 [2019CCPC秦皇岛] G Game on Chessboard 状压dp
给出一个最大12×1212×1212×12的棋盘，然后棋盘上有黑色或者白色的棋子。每个棋子都有一个权值。现在你要把所有的棋子全部拿走，你有两种取法：1.任意取走一个棋子，付出这个棋子权值的代价。2.取走一对棋子，付出两个棋子权值绝对值的代价，但是必须要满足的条件是你如果想拿走现在这个棋子，你必须要保证这个棋子作为右上端点的矩形里面没有其它的棋子。求问拿完所有的棋子最小的权值是多少。首先，单取一个...
2019-10-10 19:53:50
867
原创 [2018ICPC沈阳] L Machining Disc Rotors 几何
给出一个圆心在(0,0)(0,0)(0,0)半径为RRR的圆，以及n≤100n\leq100n≤100个圆，这些圆和大圆的重合部分会被切割掉。数据保证任何两个切割的部分都不会有交点，也不会出现切割部分就是一整个圆的情形。对于内含的这一部分情形，对答案不会产生影响。只考虑相交的情形，答案有两种可能。要么是原来的圆的某条直径，要么是两个端点的距离。判断是否存在某条直径有一个简单的做法，枚举每个端...
2019-10-09 23:57:31
233
原创 [2018ICPC沈阳] G Best ACMer Solves the Hardest Problem map+set
给出一个6000∗60006000*60006000∗6000大小的平面，平面上初始的时候有若干个点，点上有权值。然后支持四种操作：1.插入权值为www的点。2.删除某个位置的点。3.给距离某个位置为k\sqrt kk距离的点都加上www的权值。4.对距离某个位置k\sqrt kk距离的点权求和。点的范围不大。可以预处理出来所有距离为k\sqrt kk在两个方向上可以分解为哪些长度。插入和...
2019-10-09 20:38:23
150
原创 [2018ICPC沈阳] C Insertion Sort 组合数学
给出一个长度n≤50,k≤50n\leq50,k\leq50n≤50,k≤50的排列，然后对前kkk个排序之后满足序列的最长上升子序列长度为n−1n-1n−1的方案数有多少种。前kkk个数最终会排序，所以不考虑顺序，一共有k!k!k!种可能。若前kkk个数是111...
2019-10-09 10:28:45
365
原创 [2019CCPC秦皇岛] E Escape 最大流
给出一个n×mn×mn×m的矩阵，n,m≤100n,m\leq100n,m≤100。给出aaa个入口，表示有aaa个机器人从这些入口进来。给出bbb个出口，表示机器人可以从这bbb个出口出去。一些格子是障碍点表示无法通行，然后你可以在每个格子最多设置一个转向机关让机器人转向。转向分别可以转化左下，右下，左上，右上。求问是否最终aaa个机器人都能走出去。因为无论是转向或者是不转向。如果两个机器人的...
2019-10-08 11:21:23
187
原创 [2019CCPC秦皇岛] K MUV LUV UNLIMITED 树上博弈
给出n≤1e6n\leq1e6n≤1e6的树，然后两个人玩博弈游戏，每次可以选择若干的叶子结点把它删掉。如果只有一条链的情形，取决于奇偶性。如果某一条链的链底的父亲有超过两个儿子，那么此时相当于可以改变一次奇偶性，所以这样的状态是必胜态。否则就判断所有的叶子节点到最近的出度大于2的祖先的链长，当且仅当所有链长均为偶数的时候是必败的。#include<bits/stdc++.h>...
2019-10-08 11:00:03
246
原创 [2019CCPC秦皇岛] A Angle Beats 极角排序
给出n≤2e3n\leq2e3n≤2e3个点，以及q≤2e3q\leq2e3q≤2e3个点，保证所有的点都互不相同，对于每次询问的这个点，求问有多少对(u,v)(u,v)(u,v)，和当前这个点构成一个直角三角形。分成两种情形：1.询问的点是直角的顶点：对n个点以询问点为中心极角排序。然后枚举每个点，二分出逆时针90°的点有多少个，只考虑一个方向就不会重复计算。2.询问的点是不是直角的顶点：...
2019-10-08 10:36:22
309
2
原创 [2019CCPC秦皇岛] J MUV LUV EXTRA KMP
给出一个字符串，并且给出参数a,ba,ba,b。然后对于这个字符串的一个可以通过在后面增补字符而构成循环节的一个子串。它的长度为lll，它的整个循环在当前串中出现的长度为ppp，求最大的ap−blap-blap−bl。事实上对于从iii这个后缀选择的任何前缀，ppp的值是固定的一定是后缀的长度，所以对于后缀选定的情形下，自然是lll尽量小。所以要求一个后缀的最小循环节，考虑将串倒置，求前缀的最...
2019-10-08 10:13:45
150
原创 [2019CCPC秦皇岛] F Forest Program 点双连通分量
给出一个n≤3e5n\leq3e5n≤3e5的仙人掌，然后求问有多少种删边的方案，使得这个仙人掌变成一个森林，仙人掌保证一条边不会被两个简单环共用。找出所有的环，那么环中的边只要至少删掉一条即可满足，而剩下所有的非环的边则可删可不删，直接求出所有的点双连通分量，计算出答案。...
2019-10-07 22:33:16
141
原创 [2019HNCPC] D Modulo Nine dp
给出一个n≤50n\leq50n≤50的允许有前导0的数字串，以及m≤50m\leq50m≤50个区间[l,r][l,r][l,r]求满足所有的区间的数字乘积是9的倍数的方案数。满足乘积是9的倍数即这个区间有超过2个9的质因子也就是3的个数要超过2个。显然3,6各有一个，9有两个，而0只要出现就一定是9的倍数，这里也可以认为是两个。记录下两个最近的因子的位置fi,j,kf_{i,j,k}fi,j...
2019-10-06 11:00:51
170
原创 [2018HNCPC] G 排列 状压dp
给出n≤20n\leq20n≤20的数pip_ipi以及mmm个二元组(ai,aj)(a_i,a_j)(ai,aj)，然后要求重新排列这个数列，使得∑i=1m∣api−apj∣\sum_{i=1}^{m}|a_{p_i}-a_{p_j}|∑i=1m∣api−apj∣最小。先对数组排序，然后从小到大填入每个数，这样就不用考虑绝对值的影响。同时记录下位置所在的二元组的状态以及二元组的...
2019-10-05 21:51:40
164
原创 [2018HNCPC] E Grid 线段树
给出一个n×mn×mn×m，n,m≤1e9n,m\leq1e9n,m≤1e9的矩形。一开始，矩形中的每个点都不连通。然后有q≤1e5q\leq1e5q≤1e5的操作，每次操作都会把[l,r][l,r][l,r]行或者[l,r][l,r][l,r]列全部连接起来，求问对于每一次操作之后的连通块的个数是多少。对于每次询问，如果只连接了行或者列的话。以连接了xxx行为例，那么总共有nm−x(m−1)n...
2019-10-05 20:25:57
188
1
原创 [2017HNCPC] Strange Optimization 简单数论
给出正整数n,m≤1e9n,m\leq1e9n,m≤1e9，并且定义函数f(t)=mini,j∈Z∣in−jm+t∣f(t)=\min_{i,j\in Z}|\frac{i}{n}-\frac{j}{m}+t|f(t)=mini,j∈Z∣ni−mj+t∣，求一实数α\alphaα使得f(12+α)f(\frac{1}{2}+\alpha)f(21+α)最大，求出值。由于α\alphaα...
2019-10-04 20:37:12
218
原创 [2018HNCPC] J 买一送一 树形dp
给出一个根为111，n≤1e5n\leq1e5n≤1e5有点权的树，定义每个结点f(i)f(i)f(i)为从根结点到这个结点上任选两个点u,vu,vu,v的点权构成的不同的<w(u),w(v)><w(u),w(v)><w(u),w(v)>的个数。求∀i∈[2,n]\forall i\in [2,n]∀i∈[2,n]的f(i)f(i)f(i)。遍历树时候如果vv...
2019-10-03 23:45:43
122
原创 [2018HNCPC] H 千万别用树套树 线段树
给出q≤1e5q\leq1e5q≤1e5次操作，每次向集合SSS插入一个线段或者查询对于当前线段，SSS中有多少个线段完全覆盖它。保证端点最大值不超过1e51e51e5，并且被查询的线段的长度最多为222。求出有多少个线段的右端点小于当前线段的右端点，有多少个线段的左端点大于当前线段的左端点，用总数减掉这些线段的个数。只有左右端点都被包含的线段被多见...
2019-10-03 23:35:27
168
原创 [2018JSCPC] HDU 6279 Circular Coloring dp
给出nnn个黑球，mmm个白球，并且m,n≤5000m,n\leq5000m,n≤5000。然后呈环状排列，相同的颜色看作连续的一段，答案是这些段的长度之积。求问所有可能的排列答案之和是多少。最终构成环状的形态一定是白球和黑球都分成了iii段，i≤min(n,m)i\leq min(n,m)i≤min(n,m)。枚举最终分成了多少段，预处理出白球和黑球分成iii段的答案。那么ans=(n+m)∑...
2019-10-02 22:11:58
163
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人