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篇）

CCPC 2018 秦皇岛 I题 Riddle

题意：给出n数字，每个数字可能有以下2中含义之一，1：表示物品的重量，2：表示一个袋子的重量，要求如果是袋子，其重量必须某些个表示物品的重量之和，问有多少种合法的可能性。题解：状压dp 对每个数字用0、1表示，其中1表示考虑当前数字，0表示不考虑当前数字，如二进制数（10110）表示只...

2018-10-03

0 614

牛客国庆集训派对Day2 魔法阵

题意：给出3个点，确定一个正三角形，每个三角形的顶点一一对应一个给出的点，使对应的最大距离最小。题解：官方的给出最优解的样子代码： #include<bits/stdc++.h> #define N 1010 #define INF 0x3f3f3...

2018-10-02

0 399

牛客练习赛27 计数

题意： n个数字一个环，每个数字只能是3或7，要求所有相邻的m个数中，7的个数大于等于3的个数，求方案数。题解：由于m<=5，用一个数字表示最后m个数的状态，转移方程很好写： dp[i]->dp[j](j和i都合法，并且二进制下i的后m-1位和j的前m-1位相同）然后构造...

2018-09-23

0 453

2018 北京网络赛 G题 The Mole

题意：二维平面给出n条线段，每次提问一个点，输出到这个点距离最短的线段的编号。题解：数据随机，就暴力+RP了。。。坐标范围是2^16，将坐标每2^8一个分块，总共有2^16个块。读入一条线段时，将这条线段经过的所有块都加上当前线段的编号。读入一个询问，找到他属于第几块，然后枚举...

2018-09-22

0 451

2018 焦作网络赛 H String and Times

题意：给出一个字符串，和一个上下界，求所有子串中出现次数恰好介于上下界的个数。题解：假设上下界为x、y，我们计算出出现次数大于k的数目cal（k），那么cal（x）-cal（y+1）就是答案。先上后缀数组板子求出rank、sa和height数组我们按rank从小到大排序，相邻k个...

2018-09-19

0 391

2018 牛客多校第二场 C message

题意：给出n条直线，询问m次，每次询问给出一条直线，问这条直线与那n条直线的在y轴右侧交点的横坐标的最大值。题解：设交点为，则要使x最大，我将一条直线的两个系数a、b看做点（a，b），那么答案就是n个点中到询问点的斜率的最小值。为了方便和便于理解，我们将x坐标取反，转为求...

2018-09-19

0 431

2018 ICPC 青岛网络赛 Couleur

题意：给出一个长度为n的序列，每次将某个子序列分成两段，输出所有段中逆序对最大的数目。题解：假设从x位置断开，找到x最左边的断点l，和最右边的断点r，那么就是把区间(l,r)分解为(l,x)和(x,r)，如何维护两段的逆序对个数呢？启发式分解假设断点更靠近r，我们暴力求解出(x,...

2018-09-17

0 505

codeforces 886F 889D 890F Symmetric Projections

这题我写吐了，交了31发，最后一发AC，尝试了各种写法以及各种假优化，最后从别人的代码片段中获得灵感，感慨还是自己太蠢了。。。题意： n个点，有一条过原点的直线，如果所有点在这条直线上的投影点是关于某个点对称的，那么这条直线就是GOOD，问这样直线的个数。题解：首先要求出所有点的...

codeforces 886F 889D 890F

2018-09-14

0 451

Kruskal重构树

建树方法在Kruskal求最小/最大生成树的基础上，假设要加入的u、v两点，边权为w，设u、v两点的father为fu、fv，新建一个点（从n+1开始标号）p，father[fu]=father[fv]=p，将点p的点权设为w。使用方法：最小生成树的任意两点的最大值：将边从小到...

Kruskal重构树

2018-09-13

0 444

离散化后线段树

正常的线段树是这样的 [1,10]->[1,5]+[6,10]; 我们统计区间和的时候也很方便每个区间的r-l+1就是区间长度现在的问题是如果数据范围太大，维护一段区间的和就不简单了例如以下对应关系 1 2 3 4 5 6 10 20 30...

2018-09-13

0 307