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上海大都会赛 E题 Thinking-Bear's necklace

题意：一个字符串的环，可以任意断开，使的子串的最大回文串最长，输出长度。但是你有两次将一个字符修改成任意字符的机会。题解：字符串Hash 将串延长1倍，枚举回文串的中间点，看看在最多修改2次的前提下最多有多长。具体方法：首先二分出可以向两侧扩展的最大长度，然后跳过一个...

2018-08-08

0 357

2018上海大都会赛 C题 Rescue

补完题后忙着补其他的了，就光把代码贴出来了，突然发现有人看，赶忙把题解发出来。题意：求两条线段的最近距离。题解：首先求空间中两条异面直线的距离为d，求的方法是板子。。。然后分两种情况：一是，首先我们定义两条直线的距离的方向为v，也就是说，一条直线沿方向v平移，会与另一条直线相交。...

2018-08-05

0 419

pb_ds

pb_ds库包括：优先队列平衡二叉树 Hash 准则：需要合并时用pairing_heap_tag 使用时需要的库： #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tr...

2018-08-02

0 492

HDU 6333

题意： n个苹果最多取m个，求方案数。题解：令表示n个苹果最多取m个的方案数，很容易想到根据杨辉三角也很容易推出我们将m-n当作一条线段，那么就是这条线段的函数值，而根据上面的两个公式，又可以在O(1)的时间内实现到、、、的转移。利用莫队算法离线处理即可。代码： #inclu...

2018-08-02

0 381

HDU 6326

题意：一棵结点数为n的树，除1号结点外都有一个怪兽，消灭第i个结点上的怪兽会消耗ai的HP，但消灭完之后会恢复bi的HP。现在从结点1出发去打怪，最少初始时含有多少HP才能保证能打完所有的怪，而且任何时候的HP都不为负。题解：以1为根，将无根树变为有根树。要想消灭结点x的怪兽，必须先消灭x的...

2018-07-31

0 487

HDU 6331

题意：给一张有向图，q个询问，询问s到t至少经过k条路的最近距离。题解： f[k][i][j]表示从i到j经过k条路的最短路，则f[k][i][j]=min{f[k-1][i][t]+map[t][j]},(1<=t<=n),这个方程很好理解，从i到j经过k条路，我们枚举中间点t...

2018-07-31

0 375

codeforces 698D

题意：给出m个射击位置，和n个静止的射击目标，在每个射击位置只能开一枪，问有多少位置是可能被射击到的。题解：对每个目标单独独立判断是否可能被射击到即可，判断方法是dfs，关键是dfs的方法。找到合适高效的dfs是关键，我就在这里跪倒了，太菜了，最后学习了codeforces里大佬的...

2018-07-30

0 508

codeforces 933C

题意：给出三个点，求将二维平面划分成几部分。题解：感谢quailty的出题以及题解。首先是常规的欧拉公式：其中,表示划分成的平面数，为边数（edge），为顶点数（vertices）。这里，将其进行变形。表示整个图形的圆弧数，对单个圆来说，等于圆的上的交点数，求和即可求出，表...

2018-07-28

0 422

codeforces 982E

题解：先单独处理水平和竖直走的情况，在分析斜着走的情况。每次我们遇到边界，不反弹，而是接着走，理解为地图向前进的两个方向翻转扩展，直到走到了四个角落之一，算出两个方向各自扩展的数量，在根据奇偶来确定坐标。利用扩展欧几里得来算出是否有解。代码： #include<bits...

2018-07-28

0 457

HDU 6304

题解：先把数列a打表找一下规律，发现（除了第一项1以外）：出现1次：1，3，5，7，9，11，13，15...... 出现2次：2，6，10，14，18，22，26...... 出现3次：4，12，20，28，36，44...... 出现4次：8，24，40，56，72，88...

2018-07-24

0 584