- 博客(609)
- 资源 (8)
- 收藏
- 关注
RSS订阅
原创 博客收藏
容斥原理讲解：http://www.cppblog.com/vici/archive/2011/09/05/155103.aspx AC自动机：http://hihocoder.com/problemset/problem/1036 AC自动机算法：http://blog.csdn.net/niushuai666/article/details/7002823 从头到尾彻底理解KMP：htt...
2016-10-26 17:40:41
1912
原创 *Codeforces Round #202 (Div. 1)*
发烧了，烧了五天，吓死我了，还以为要挂了呢。幸好又活过来了。A. Mafia题意：n个人玩一个游戏，每次要选出来一个主持的,剩下n-1个人玩这个游戏。第i个人想玩ai轮游戏，问最少玩多少轮可以满足所有人的要求。思路：我的思路是二分搜索，先排个序，这样第一个人就是要玩轮数最少的，末尾的就是要玩轮数最多的。对于搜索的每个值，我的策略是先满足要玩轮数最少的那个人，这些轮都是由需要轮数最多的人那个人作为主持
2017-12-13 19:06:15
481
原创 *Codeforces Round #201 (Div. 1)*
在出题人看到岛娘了，膜一下。感觉这场的题比上一场难了太多了。可能我太菜吧。A Alice and Bob思路：连懵带猜做出来的。求出n个数字的gcd，每个数字都除以gcd，然后得到一个新的集合。集合中最大的数字即最终集合中数字的个数。减掉已有数字的个数，即游戏能玩几回合。根据奇偶性判断胜负即可。看了tutorial，才想到思路。假设有两个数字a，b，假设a>b，令d=gcd(a,b)，a=xd，b=
2017-11-30 20:55:23
451
原创 Codeforces Round #200 (Div. 1)
A Rational Resistance思路：因为每个电阻的电阻是1，这就很好算了，比如要求的电阻是a/b，假设a>b，则要求电阻个数就是a/b + b/(a%b) + (a%b)/(b%(a%b))…，直到某一步的模运算那里能够整除。我也不知道为啥这样，找了俩数据，算了算是这个规律，那就这样算了。#include <bits/stdc++.h>using namespace std;type
2017-11-25 20:39:35
488
原创 SGU 106 The equation（扩展欧几里德）
没想起来怎么做 参考：https://www.cnblogs.com/zjbztianya/archive/2013/03/12/2956835.html思路还是很简单的，ax+by=c, gcd(a,b)=d,则x = x0+(b/d) * t,y = y0 - (a/d) * t，每个t确定一对解，现在已经知道x1<=x<=x2,y1<=y<=y2,代换一下，求出来t的范围即可，有多少个t的整
2017-11-14 19:19:30
387
原创 poj 2891 Strange Way to Express Integers（一元线性同余方程组）
迭代求解方程组，拿板子就好了#include <stdio.h>typedef long long LL;const int N = 11110;LL M[N], R[N];LL gcd(LL a, LL b){ return !b ? a : gcd(b, a%b);}LL extgcd(LL a, LL b, LL &x, LL &y){ LL d = a;
2017-11-13 20:34:21
323
原创 poj 2396 Budget(有源汇上下界可行流)
这题的建图真恶心。好不容易写完后结果还wa了，顿时生无可恋啊，看了下discuss，说不能输出负数，最后不能输出多余的空行，我把这俩都改了，就AC了，虽说那里说这是在zoj不能ac的原因，不过在poj也适用，哈哈。 思路：每行为一个点，每列为一个点，给出的限制就是行列之间连线的流的上下界，初始下届为0，上界为INF。然后建好图之后，建立一个虚拟源点和虚拟汇点，源点和边连线，流量上下界为行的和，列和
2017-11-13 13:57:05
372
原创 zoj 2314 reactor cooling（无源汇有上下界可行流）
初次接触，https://www.cnblogs.com/liu-runda/p/6262832.html，通过这个博客学习的建图方式。建好图后套板子即可。#include <bits/stdc++.h>using namespace std;const int MAXN = 300;const int INF = 0x7fffffff;struct edge{ edge(){}
2017-11-12 20:57:46
325
原创 hdu 3579 Hello Kiki（一元线性同余方程组）
和hdu 1573基本一样。注意不能输出0，是最小正整数解#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 110, INF = 0x3f3f3f3f;int M[N], R[N];int gcd(int a, int b){ return !b ? a : gcd(b, a%b)
2017-11-12 14:22:04
316
原创 hdu 1573 X问题（一元线性同余方程组）
当中国剩余定理中的那些模数不互质的时候怎么解？就像解普通方程组一样，迭代求解同余方程组。思路很简单。过两天重新写个，换掉这个抄来的模板。 代码是直接拿的模板，改都没改：http://blog.csdn.net/discreeter/article/details/70318677#include <bits/stdc++.h>using namespace std;typedef long lon
2017-11-11 19:28:03
357
原创 poj 2114 Boatherds（树分治）
点分治，和poj 1741 Tree基本一样，就是统计数量那里不一样。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int MAXN = 10010;const int MAXM = 20020;struct Edge{ int to,w,next;} edg
2017-11-11 12:47:49
286
原创 poj 1854 Evil Straw Warts Live(分治)
wa了好久，调了好久。。。。。 思路：先判断能否形成回文串，然后分治，先让整个串的两端字符相等，找出最少移动次数，然后去掉两端，得到新串，使新串两端相等，找出最小移动次数，这样不停缩小规模，直到搞完整个串。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int MAXN =
2017-11-09 23:15:20
482
原创 hdu 6143 Killer Names（第二类斯特林数）
生活总是那么操蛋，(a+b)%mod写成了(a+b%mod)，找错找了一个多小时。。 思路： m种字符，名字分两部分，都能放下n个字符。先取出名字的一部分，即n个位置。对于这n个位置，能放i种字符，i属于[1, min(m,n)]，就是n个元素放进k个盒子里，并且盒子不同，所以要乘阶乘，这对应第二类斯特林数，对于某个i，共Cim∗S[n][i]∗fac[i]C^{i}_{m}*S[n][i]*f
2017-11-09 21:04:46
285
原创 hdu 2643 Rank（第二类斯特林数）
n个人的名次，因为有并列排名的情况，所以共n种情况，只有1个名次(所有人并列第一)到一共n个名次。对于某种情况，假设现在有x个名次，每个名次不知道多少人，就是有x个盒子，每个盒子内至少分配一个人，即n个数的集合的划分为x个非空集合方法的数目，正好是第二类斯特林数，在这里还要计数不同的排列方式，即这x个集合的不同排列。#include <bits/stdc++.h>using namespace s
2017-11-09 13:16:17
314
原创 hdu 3625 Examining the Rooms（第一类斯特林数）
n个门，最多打爆k个门，也就是最多有k个环（第一类斯特林数）。把1个环到k个环的情况全加起来，每次加的时候还要减去1号自己成环的情况。 S[N][i]是n个元素i个环排列，S[N-1][i-1]就是1自己成环的情况。#include <bits/stdc++.h>using namespace std;typedef long long LL;LL fac[22];LL S[22][22];
2017-11-09 12:13:20
301
原创 hdu 4372 Count the Buildings（第一类斯特林数）
从前向后看可以看到F栋楼，去掉中间最高那栋楼，有F-1栋楼，看到的第一栋楼和看到的第二栋楼之间的楼，分给第一栋楼，属于同一组楼，后边的依次类推，共F-1组楼，对于每组楼，假设有X栋楼，去掉我们看到的这一栋楼固定在第一个位置（这一组最高的楼在最靠前的位置），剩下X-1栋楼随意排列，X-1栋楼的的排列就是X栋楼的环排列，这就分成了F-1个环排列，从后向前看的也是这样。这就是N栋楼形成了F+B-2个环排列
2017-11-08 21:40:04
276
原创 poj 3237 Tree（树链剖分）
wa了半天。。懒惰标记那里要用异或来修改，wa的时候突然想到，万一两次反转相同的区间，反转就取消了，然而我的懒惰标记那里一直col[rt]=1，这样反转就没有取消。。。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int MAXN = 1e5+10;const int IN
2017-11-07 23:12:13
214
原创 FZU 2082 过路费（树链剖分，边权）
树剖裸题#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int MAXN = 5e4+10;struct Edge{ int to,next;} edge[MAXN*2];int head[MAXN],tot;int top[MAXN];int fa[MAXN
2017-11-07 20:10:05
249
原创 poj 2763 Housewife Wind(树链剖分，边权)
树剖裸题，wa了好久，才发现线段树传错参数了。。。。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int MAXN = 1e5+10;struct Edge{ int to,next;} edge[MAXN*2];int head[MAXN],tot;int
2017-11-07 19:53:44
249
原创 LightOJ 1348 Aladdin and the Return Journey（树链剖分）
树剖裸题，套kuangbin大佬的模板#include <bits/stdc++.h>using namespace std;const int MAXN = 30010;struct Edge{ int to,next;} edge[MAXN*2];int head[MAXN],tot;int top[MAXN];int fa[MAXN];int deep[MAXN];i
2017-11-06 23:21:35
271
原创 Aoj - 1313 Intersection of Two Prisms（数值积分）
挑战程序设计竞赛例题。。。 我就抄了下代码。。。#include <bits/stdc++.h>using namespace std;const int INF = 0x7fffffff;const int MAXN = 110;int M,N;int X1[MAXN],Y1[MAXN];int X2[MAXN],Z2[MAXN];double width(int* X, int* Y
2017-11-06 20:06:38
356
原创 hdu 2227 Find the nondecreasing subsequences（树状数组+DP）
看到题目想到了逆序数。 首先是想：先离散化，对每个数字，统计在这之前有多少个数字比他小，再用BIT计算比他小的这些数字能组成多少序列，然后再加上一个单独的当前数字。试了下，对于升序数组是没问题，非升序的就不行，突然想到前边那些数字是有顺序的插进去的。。搜到：http://blog.csdn.net/u013582254/article/details/46334163 可以通过dp来更新啊。
2017-11-06 18:11:38
372
原创 hdu 2642 Stars（二维树状数组）
二维BIT裸题#include <bits/stdc++.h>using namespace std;const int MAXN = 1e3+3;#define lowbit(x) (x&(-x))int f[MAXN][MAXN],a[MAXN][MAXN];void add(int x, int y, int val){ for(int i = x; i < MAXN; i +
2017-11-06 16:20:18
245
原创 hdu 1892 See you~(二维树状数组)
二维BIT裸题#include <bits/stdc++.h>using namespace std;const int MAXN = 1e3+3;#define lowbit(x) (x&(-x))int f[MAXN][MAXN],a[MAXN][MAXN];void add(int x, int y, int val){ for(int i = x; i < MAXN; i +=
2017-11-06 16:00:07
172
原创 poj 3185 The Water Bowls（高斯消元）
每按一个位置，是一个状态，就是一个列向量，构造系数矩阵，上板子。。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;//对2取模的01方程组const int MAXN = 300;//有equ个方程， var个变元。增广矩阵行数为equ,列数为var+1,分别为0到varint e
2017-11-05 21:54:12
213
原创 poj 1753 Flip Game（高斯消元）
和 poj 1681 Painter’s Problem 完全一样，http://blog.csdn.net/gyhguoge01234/article/details/78428118#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;//对2取模的01方程组const int MAXN
2017-11-05 21:25:27
271
原创 poj 2065 SETI（高斯消元）
看懂就是水题，看不懂就是难题。我没看懂 题目意思在这里讲的很清楚 http://blog.csdn.net/u013486414/article/details/47005013 看懂题目后，直接上板子就过了。不过kuangbin的模板，求逆元那里要改成扩展欧几里德的模板。。。本来那个模板不适合用在这里。。#include <stdio.h>#include <string.h>#incl
2017-11-05 20:47:37
200
原创 poj 2947 Widget Factory（高斯消元）
根据样例列出来方程，解出来结果是1，3，实际结果是8，3。。懵逼了，一周最多七天，怎么会有8。搜了下题解才知道这中间可能隔着很多周，那这就是用高斯消元解线性同余方程组了，而且方程很好列，把kuangbin大佬板子拿来就是了。（板子就是这道题） 具体意思看这里：http://blog.csdn.net/qingshui23/article/details/52511894#include <stdi
2017-11-05 20:04:49
202
原创 Codeforces Round #363 (Div. 1) C. LRU(状态压缩dp)
这题在博客左上角放了好久了，一直不会做，看了半天题解，勉强看懂。。 参考：http://blog.csdn.net/squee_spoon/article/details/52040852 看看各个博客的讲解，看看代码，强行理解。。。我的理解写在注释里了。#include <bits/stdc++.h>using namespace std;double dp[1<<20];double p
2017-11-05 18:45:26
320
原创 Codeforces Round #368 (Div. 2) D. Persistent Bookcase（dfs）
想不到怎么去做，暴力模拟的时候发现那个回到之前的状态搞不定，然后参考了卿学姐代码：http://www.cnblogs.com/qscqesze/p/5791698.html还有题目意思的问题，英语不好啊，对着数据调了好几遍才搞懂题目意思，即操作4的意思，原来是回到过去的某个状态，然后从那里从新开始。。。 看过代码思路就清楚了，把这些操作建成一棵树，dfs一遍就完事了，思路很棒。操作4就是树枝分叉
2017-11-04 19:40:27
208
原创 Codeforces Round #368 (Div. 2) C. Pythagorean Triples
题解中就在评论中给了个公式，不过评论中有人给了一个证明连接：http://codeforces.com/blog/entry/46681看到毕达哥斯拉三元组，我想到一个题：poj 1305，这个题是枚举来做的，cf这题我也就枚举试了下，不行。。。 我的写法是看的别人结论： 当n被4整除时，结果是n/4 * 3和n/4 * 5 当n被2整除时，结果是((n/2) * (n/2)/2) * 2和(
2017-11-04 17:26:58
320
原创 poj 3422 Kaka's Matrix Travels（最小费用流）
题目在《挑战程序设计竞赛》的练习题的最小费用流分类里。看到后第一反应是dp，想到了 51Nod 1084 矩阵取数问题 V2 这个题，这个题是个多进程dp，从左上走到右下，走两次。然后就去搜了下这个题的题解：http://www.hankcs.com/program/algorithm/poj-3422-kakas-matrix-travels.html 主要是不怎么会建图，看了下题解的注释，然后
2017-11-03 19:30:21
251
原创 poj 2195 Going Home（最小费用流）
建立一个虚拟原点s和虚拟汇点t。s到每个H连接一个容量为1，花费为0的边。每个m到t连接一个容量为1，花费为0的边，然后每个H对每个m建边。 直接上板子。。#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std;struct edge{ int to
2017-11-03 13:30:23
241
原创 最小费用流模板(Bellman-Ford算法找最短路)
poj 3068#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std;struct edge{ int to,cap,cost,rev; edge(int _to = 0, int _cap = 0, int _cost = 0, int _
2017-11-03 12:46:20
460
原创 poj 3068 "Shortest" pair of paths（最小费用流）
两个东西不能在一块运输，说明路的容量是1，就运俩东西，流量就是2。流量为2的最小费用流。直接上板子。这个板子是通过bellman-ford算法来寻找最短路，进而沿最短路增广的。#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std;struct edge{
2017-11-03 12:43:14
347
原创 poj 1830 开关问题（高斯消元）
线代真是白学了 题解：http://blog.csdn.net/u011418307/article/details/52328759 只要构造出来方程，剩下就很简单了。。#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;//对2取模的01方程组const int MAXN = 40
2017-11-02 20:47:01
282
原创 poj 1681 Painter's Problem（高斯消元）
思路同poj 1222 EXTENDED LIGHTS OUT一样，只是多了个判断解的情况。 http://blog.csdn.net/shiren_Bod/article/details/5766907 这是poj 1222 的讲解，思路都是一样的。代码是kuangbin的模板。。#include <stdio.h>#include <string.h>#include <algorithm
2017-11-02 18:49:52
235
原创 poj 1222 EXTENDED LIGHTS OUT(高斯消元)
题解：http://blog.csdn.net/shiren_Bod/article/details/5766907 这题直接枚举第一行可行，因为第一行确定了，下边就都确定了。 但是是来练习高斯消元的，表示并不会构造方程。题解中讲的比较详细，看了几遍看懂了，感觉线代白学了。。模板是kuangbin大佬的模板。每次计算时选取绝对值最大的那一行来消元，是因为这样计算出结果会更精确。书上写的，不知道为
2017-11-02 17:39:06
182
原创 hdu 1222 Wolf and Rabbit（gcd）
兔子是否能活下来，就看狼能不能走遍所有的洞了。如果狼能走遍所有的洞，兔子就死定了。n是洞的个数，m是狼的步长。假设狼走了x步，走到了位置k，则位置k=x*m%n，则k =x * m - (x * m/n) * n，即k =x * m + y * n，当前洞口位置是m和n的线性组合，所以 gcd(n,m) | k。m和n的所有线性组合构成的集合与所有的gcd(n,m)构成的集合相同，即位置k的集合和g
2017-11-01 21:57:05
335
原创 zoj 2112 Dynamic Rankings（动态第k大，树状数组套主席树）
这个题在kuangbin大佬的模板里有。 http://www.cnblogs.com/kuangbin/p/3308118.html kuangbin大佬博客里有四个学习连接。#include <bits/stdc++.h>using namespace std;const int MAXN = 60010;struct node{ int l,r,sum;}T[MAXN*30
2017-11-01 20:21:06
406
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人