Spy97

分类

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 计算几何(30) 贪心(2)

/ 注册

全部文章（共151篇）

2018 HNCPC 湖南省程序设计竞赛 CSU 2167 Grid

题意：初始有n*m的点，矩形排列。有2种操作，第一种是将第i行的所有点联通（a<=i<=b）,第二种是将第i列的所有点联通（a<=i<=b）。每次操作后输出有多少个联通块。题解：先说结论，若某次操作后有a行，b列联通，则联通块的个数为n*m-a*(m-1)-b*(...

2018-09-13

0 644

2018 HNCPC 湖南省程序设计竞赛 CSU 2168 Fixed Point

题意：一个序列长为n，初始为1......n，m种操作，每次翻转一个区间，问操作k次后满足a[i]==i的个数，当操作数大于m时，从第一种操作开始循环反复进行那m种操作，直到操作k次。题解： m最大只有10，我们将k分解成k=p*m+q 对于位置y，假设在操作q次后出现在位置x，那么位置...

2018-09-12

0 750

2018 ICPC 沈阳网络赛 The cake is a lie

题意：给出n个半径一致的圆，画一个圆至少完全包含其中的m个，求最小半径。题解：可化简为，n个点，求覆盖掉至少m个的最小的圆 O(n^2logn *logR）的解法：二分半径，然后判断这个半径下能覆盖的最多的点，若小于要求，半径变大，若大于要求，半径缩小。如何得知一个半径下能覆盖...

2018-09-11

0 417

2018 ICPC 徐州网络赛 K题 Morgana Net

题意：求第迭代t次后的矩阵卷积。题解：输入给出两个矩阵An，Bm 建立一个矩阵Cn*n，将矩阵A中的元素以此放到矩阵C的第一行我们将卷积的过程构造成一个转移矩阵，然后用矩阵快速幂解决构造方法：考虑点a，它周围的点a1,a2,a3,a4,a5......要参与卷积的计算中 ...

2018-09-10

0 692

南京网络赛 The Great Nim Game

题意：有n堆石子，从中选出k堆，使选出的石子进行nim游戏时先手必胜，求方案数。题解： nim游戏中，所有石子的异或和不为0，先手必胜，问题就化简为，n个数中的子集的异或和不为0的方案数。 dp[i][j]表示选前i个数，异或和为j的方案数。 dp方程： dp[i][j]=dp...

2018-09-06

0 448

2018 ICPC 南京网络赛 skr

题意：给出一个字符串，求它的所有回文子串转化成数字的和，对1e9+7取模。题解：先上Manacher，然后枚举每个点，按照半径从大到小的顺序枚举回文串，遇到出现过的就break，统计答案即可。注意的是，判重时只能用pb_ds中的gp_hash_table，unordered_map会...

2018-09-04

0 365

2017香港regional Black and White

题意：给一个n*n的矩阵，初始全是白色，进行m次操作，每次操作是让一个子矩阵的颜色翻转，求最后有几个黑色的方格。题解：每行分别处理，将一个子矩阵拆成两条线段，分别是上底和下底，然后按照线段的高度排序。每到一行，将所有高度等于该行的下底的线段加入线段树中，表示对这个线段进行翻转，更新答案...

2018-09-03

0 2806

查分约束系统

首先根据题目的要求进行不等式组的标准化。 (1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式，这样建立j->i的边，权值为k的边，如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k...

2018-08-28

0 462

codeforces 1019D Large Triangle

题意：给出n个点和一个面积s，问能否从n个点中选3个点组成s的三角形的面积为s。题解: 这题我思考了很久，因为确实方法不是很好懂。首先，原题是bzoj 3707，这道题是给出n个点，求3个点组成的最小面积。我们先从这题入手。解法一：分块+暴力将坐标系多...

2018-08-27

0 545

HDU 6442 GuGu Convolution CCPC 2018 网络赛

题意：给出两个生成函数，求他们的卷积的第n项的系数。要求输出形如的最简形式。题解：首先根据题意可以得出答案就是：可以如下化简：可以类比快速幂的求法：需要注意的是：由于模数p可能与2不互质，所以运算时对（p*2）取模，求出答案后除以2即可。由于要带根...

2018-08-26

0 347