- 博客(152)
- 收藏
- 关注
RSS订阅
原创 简单平面几何模板（持续更新）
1. 向量基本操作struct Point { double x, y; };typedef Point Vector;Vector operator + (Vector a, Vector b) { return { a.x + b.x, a.y + b.y }; }Vector operator - (Vector a, Vector b) { return { a.x - b...
2019-03-11 22:07:40
544
2
原创 简单数据结构模板
1，树状数组int C[maxn<<4] , a[maxn] , n;int lowbit(int x){ return x&(-x);}int Sum(int pos){ int ans = 0; while(pos>0) ans += C[pos] , pos -= lowbit(pos); return ans ;}...
2018-08-01 16:08:51
423
原创 简单图论模板
#define ll long long#define MT(a,b) memset(a,b,sizeof(a));const int INF = 0x3f3f3f3f;const int ONF = -0x3f3f3f3f;1，拓扑排序dfsint way[N][N],topo[N],vis[N];int t, n ,m;bool dfs(int u){ ...
2018-07-25 18:17:22
352
原创 简单数学模板
快速幂LL quick_mod(LL a, LL b){ LL ans = 1; a %= mod; while (b) { if (b & 1) { ans = ans * a % mod; b--; } b >>= 1; a = a * a % mod; } return ans;}快速乘+快速幂long l...
2018-07-15 14:18:05
262
原创 中国剩余定理(CRT) && 扩展中国剩余定理(EX_CRT)
中国剩余定理（解决模数互质的同余方程组） 在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：找到三个数：从3和5的公倍数中找出被7除余2的最小数20，从3和7的公倍数中找出被5除余3的最小数63，最后从...
2020-01-03 22:37:14
1233
3
原创 EXTENDED LIGHTS OUT POJ - 1222 （高斯消元）
POJ - 1222DescriptionIn an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a butt...
2019-10-13 13:20:37
189
原创 Painter's Problem POJ - 1681（高斯消元）
POJ - 1681There is a square wall which is made of n*n small square bricks. Some bricks are white while some bricks are yellow. Bob is a painter and he wants to paint all the bricks yellow. But the...
2019-10-13 13:20:22
221
原创 Game HDU - 3389 (Nim)
Bob and Alice are playing a new game. There are n boxes which have been numbered from 1 to n. Each box is either empty or contains several cards. Bob and Alice move the cards in turn. In each turn the...
2019-09-27 19:46:52
176
原创 P2900 [USACO08MAR]土地征用Land Acquisition （斜率优化dp）
戳题目描述Farmer John is considering buying more land for the farm and has his eye on N (1 <= N <= 50,000) additional rectangular plots, each with integer dimensions (1 <= width_i <= 1,000,...
2019-09-22 15:21:14
189
原创 P3628 [APIO2010]特别行动队（斜率优化dp）
特别行动队题目描述你有一支由 n 名预备役士兵组成的部队，士兵从 1 到 n 编号，要将他们拆分 成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号 应该连续，即为形如(i, i + 1, ..., i + k)(i,i+1,...,i+k)的序列。 编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x 为队内 士兵初始战斗力之和，即x = x_i...
2019-08-17 16:52:25
222
原创 2019 Multi-University Training Contest 8 ：Andy and Maze 1008（color coding + 状压dp）
Andy and MazeTime Limit: 15000/15000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 566Accepted Submission(s): 195Problem DescriptionAndy is a famous ex...
2019-08-16 10:58:03
774
原创 2019 Multi-University Training Contest 8 ：Acesrc and Hunting 1004（暴搜）
Problem DescriptionAcesrc is a famous hunter at Nanjing University second to none. Recently, he setn×mtraps in Yangshan Park, a park near Nanjing University Xianlin Campus, arranged innrows and...
2019-08-15 15:57:43
445
原创 P2365 任务安排 （斜率优化dp）
P2365 任务安排题目描述N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，...
2019-08-10 21:20:40
248
原创 Broken robot CodeForces - 24D （特殊矩阵O(n)消元）
You received as a gift a very clever robot walking on a rectangular board. Unfortunately, you understood that it is broken and behaves rather strangely (randomly). The board consists ofNrows andMc...
2019-08-09 21:19:07
280
原创 First Knight UVA - 12177 （高斯消元）
题意：给出每个点向四方走的概率，保证和为1，并且向边界外走的概率为0，求从（0, 0）走到（n-1, m-1）的期望步数。题解：dp[i][j] 表示从 （i，j）走到终点的期望步数， 然后列n * m 个方程， 用高斯消元求解。注意精度问题，求解过程中可以构成一个下三角形式，然后直接得到在（0, 0）位置的期望步数，可以减少很多误差，并且eps需要开到1e-12。因为这是一个稀疏矩阵...
2019-08-09 11:25:48
385
原创 2019 Multi-University Training Contest 6：Snowy Smile （1005）线段树
Snowy SmileTime Limit: 4000/4000 MS (Java/Others)Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1543Accepted Submission(s): 459Problem DescriptionThere arenpirate che...
2019-08-08 17:14:23
172
原创 2019 Multi-University Training Contest 6 ：Faraway （1006）
题链接Problem Descriptionnsoldiers are dispatched to somewhere in Byteland. These soldiers are going to set off now, but the target location is not so clear.Assume the target location is at(xe,ye)...
2019-08-08 12:01:40
229
原创 3143: [Hnoi2013]游走 （高斯消元 + 期望dp）
3143: [Hnoi2013]游走Description一个无向连通图，顶点从1编号到N，边从1编号到M。小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。...
2019-08-01 20:59:34
229
1
原创 高斯消元模板
1.整形struct Matrix { void clear() { MT(a, 0); } int equ, var; // equ 表示等式个数，var 表示未知变量个数 int a[maxn][maxn], x[maxn], free_n; // a表示增广矩阵， x表示解 bool free_x[maxn]; // 自由变元 Matrix ...
2019-07-27 11:17:39
228
1
原创 Electric resistance （高斯消元）
Electric resistance题意：已知一个串并联电阻串有n个结点，m种连接关系（u, v, r）表示u结点到v结点存在一个电阻r，求1结点到n结点的等效电阻题解：高斯消元浮点型，分别设每个节点的电势为xi，我们假设流入1结点的电流为1，然后对每个结点列一个kcl方程，因为这种方式只能算出每两个结点的电势差，所以我们需要给任意一个结点的电势赋值，从而确定其它结点的电势。最后运用...
2019-07-26 10:57:04
226
原创 Keen On Everything But Triangle（可持续化线段树）
Keen On Everything But TriangleProblem DescriptionNsticks are arranged in a row, and their lengths area1,a2,...,aN.There areQquerys. Fori-th of them, you can only use sticks betweenli-th to...
2019-07-25 11:36:46
229
原创 Harmonious Army （网络流最小割）
Problem DescriptionNow, Bob is playing an interesting game in which he is a general of a harmonious army. There arensoldiers in this army. Each soldier should be in one of the two occupations, Mag...
2019-07-25 10:06:10
166
原创 Blank（dp）
BlankProblem DescriptionThere areNblanks arranged in a row. The blanks are numbered1,2,…,Nfrom left to right.Tom is filling each blank with one number in{0,1,2,3}. According to his thought, ...
2019-07-23 20:49:26
183
原创 2019 Multi-University Training Contest 1 ：1013 Code (计算几何-凸包)
CodeProblem DescriptionAfter returning with honour from ICPC(International Cat Programming Contest) World Finals, Tom decides to say goodbye to ICPC and start a new period of life. He quickly gets...
2019-07-23 19:11:47
142
原创 E. Tree Painting （树形dp）
E. Tree Paintingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a tree (an undirected connected acyclic graph) con...
2019-07-19 10:28:30
229
原创 C. Lieges of Legendre（SG函数）
C. Lieges of Legendretime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputKevin and Nicky Sun have invented a new game called Lieges ...
2019-07-17 21:02:00
322
原创 E. Furlo and Rublo and Game （SG函数）
E. Furlo and Rublo and Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputFurlo and Rublo play a game. The table hasnpiles of...
2019-07-17 20:54:20
452
原创 Calendar Game HDU - 1079 （博弈论）
Calendar GameHDU - 1079Adam and Eve enter this year’s ACM International Collegiate Programming Contest. Last night, they played the Calendar Game, in celebration of this contest. This game consi...
2019-07-16 10:56:40
182
原创 The 2019 ACM-ICPC Shannxi J. And And And （点分治模板题）
J. And And AndA tree is a connected graph without cycles. You are given a rooted tree withnnnodes, labeled from1ton1ton. The tree is rooted at node11. The parent of theii-th node isfaifai. T...
2019-07-12 10:59:57
365
3
原创 Query on a tree V （动态点分治预处理，LCA计算两点距离， 堆维护最短距离）
Query on a tree VYou are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from nod...
2019-07-11 15:00:43
217
原创 CDQ套树状数组解三维偏序
3262: 陌上花开三维偏序：给定N个有序三元组(a,b,c)，求对于每个三元组(a,b,c)，有多少个三元组(a2,b2,c2)满足a2<a且b2<b且c2<c。 不用CDQ分治的方法：先按照a元素排序，从左到右扫描。按照b元素构造权值树状数组，树状数组每个节点按照c元素构造平衡树。树套树的解法不仅常数大，而且代码量巨大，还容易写错。 类似二维偏序问题，先按...
2019-07-05 14:58:02
3465
原创 CDQ分治求二维偏序
Stars二维偏序问题 给定N个有序对(a,b)，求对于每个(a,b)，满足a2<a且b2<b的有序对(a2,b2)有多少个。 我们从归并排序求逆序对来引入二维偏序问题。 回忆一下归并排序求逆序对的过程，我们在合并两个子区间的时候，要考虑到左边区间的对右边区间的影响。即，我们每次从右边区间的有序序列中取出一个元素的时候，要把“以这个元素结尾的逆序对的个数”加上“左...
2019-07-04 22:23:01
999
原创 CDQ分治（归并排序）求逆序数
CDQ分治的基本思想十分简单。如下：我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间[L,R]表示。 分。递归处理左边区间[L,M]和右边区间[M+1,R]的问题。 治。合并两个子问题，同时考虑到[L,M]内的修改对[M+1,R]内的查询产生的影响。即，用左边的子问题帮助解决右边的子问题。 这就是CDQ分治的基本思想。和普通分治不同的地方在于...
2019-07-04 15:45:34
221
原创 洛谷P2634 [国家集训队]聪聪可可（点分治）
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来...
2019-07-03 16:04:28
170
原创 【模板】点分治1
题目描述给定一棵有n个点的树询问树上距离为k的点对是否存在。输入输出格式输入格式：n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K输出格式：对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)输入输出样例输入样例#1：复制2 11 2 22输出样例#1...
2019-06-21 19:32:28
227
2
原创 [国家集训队]聪聪可可（树形dp）
题目描述聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一...
2019-06-19 21:29:07
226
原创 哈希冲突（分块）
题目描述众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。B君会给定许多个p和x，询问在模p时，x这个池内数的总和。另外，B君会随时更改value[k]。每次更改立即生效。保...
2019-06-19 16:45:53
386
原创 超级钢琴 （堆 + RMQ）
题目描述小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级...
2019-06-17 19:37:00
348
原创 小Z的袜子 （莫队）
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色相...
2019-06-17 13:14:35
134
原创 BKDR & DJB & ELF & FNV
int bkdr_hash(string str) { const int seed = 131; int hash = 0; for (int i = 0; i < str.length(); i++) { hash = hash * seed + (int)str[i]; } return hash & 0x7FFFFFF...
2019-06-16 11:56:54
304
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人