BraketBN-CSDN博客

原创【BZOJ3659】Which Dreamed It【有向图欧拉回路计数】【matrix tree定理】【BEST定理】【高斯消元】

【题目链接】定理题.../* Think Thank Thunk */#include #include #include using namespace std;typedef long long LL;const int maxn = 105, p = 1000003;int n, fact[200005], A[maxn][maxn], du[maxn];

2016-07-18 15:19:12 2352

原创【BZOJ2055】80人环游世界【有上下界的最小费用最大流】

【题目链接】随便建.../* Think Thank Thunk */#include #include #include using namespace std;const int maxn = 205, maxm = 250005, maxq = 100005, inf = 0x3f3f3f3f;int n, m, head[maxn], cnt, bg, ed,

2016-07-16 17:02:52 1225

原创【BZOJ2039】[2009国家集训队]employ人员雇佣【最小割】

【题目链接】【POPOQQQ的题解】被卡题意了。。/* Think Thank Thunk */#include #include #include using namespace std;typedef long long LL;const int maxn = 1005, maxm = 5000005, maxq = maxn;const LL linf =

2016-07-15 18:12:47 843

原创【BZOJ1968】[Ahoi2005]COMMON 约数研究【数论】

【题目链接】对于数字i，在1到n中，一共有n / i个数是i的倍数。/* Think Thank Thunk */#include #include #include using namespace std;inline int iread() { int f = 1, x = 0; char ch = getchar(); for(; ch '9'; ch = g

2016-07-15 11:31:08 684

原创【BZOJ1930】[Shoi2003]pacman 吃豆豆【最大费用最大流】

【题目链接】被卡的不要不要的= =hzwer的建图似乎是错的，按照这个过了【jiangyuze831的题解】/* Think Thank Thunk */#include #include #include using namespace std;const int maxn = 4005, maxm = 4100005, maxq = 100000, i

2016-07-14 17:48:17 1093

原创【BZOJ1834】[ZJOI2010]network 网络扩容【最大流】【最小费用最大流】【残量网络】

【题目链接】先跑最大流，然后在残量网络上跑最小费用最大流。/* Think Thank Thunk */#include #include #include using namespace std;const int maxn = 1005, maxm = 20005, maxq = 100000, inf = 0x3f3f3f3f;int n, m, k, cur[ma

2016-07-14 16:44:59 889

原创【BZOJ2795】[Poi2012]A Horrible Poem【Hash】【GCD】【暴力】

【题目链接】【POPOQQQ的题解】跑了倒数rk5.../* Think Thank Thunk */#include #include #include using namespace std;typedef long long LL;typedef unsigned long long ULL;const int maxn = 500005;int n,

2016-07-14 12:12:20 731

原创【BZOJ1907】树的路径覆盖【贪心】

【题目链接】清空时候忘把边清空了= =RE无数发另外计算的时候还得算根节点...【ydc的题解】/* Think Thank Thunk */#include #include #include using namespace std;const int maxn = 10005;int n, head[maxn], cnt, q[maxn], dp[ma

2016-07-12 08:04:00 626

原创【BZOJ1927】[Sdoi2010]星际竞速【最小费用最大流】

【题目链接】有点神...【BLADEVIL的题解】/* Think Thank Thunk */#include #include #include using namespace std;const int maxn = 1605, maxm = 300005, maxq = 500000, inf = 0x3f3f3f3f;int n, m, head[m

2016-07-11 16:37:37 767

原创【BZOJ1806】[Ioi2007]Miners 矿工配餐【DP】

【题目链接】设dp[i][a1][a2][b1][b2]表示，前i个食物，第一个矿场最后两次的食物分别为a1、a2，b1、b2同理，所得到的最大煤炭数。/* Think Thank Thunk */#include #include #include #define rec(i, x, y) for(int i = x; i <= y; i++)using namespac

2016-07-09 18:39:46 696

原创【BZOJ1867】[Noi1999]钉子和小球【DP】

【题目链接】简单DP。。注意输出不能有换行。/* Think Thank Thunk */#include #include #include using namespace std;typedef long long LL;const int maxn = 55;int n, m;bool g[maxn][maxn];inline LL gcd(LL a,

2016-07-09 17:46:58 833

原创【BZOJ4078】[Wf2014]Metal Processing Plant【2-SAT】【二分】【二分图】【并查集】

【题目链接】考虑比较暴力的方法，我们枚举两个集合的最大值S1, S2，那么我们可以用2-SAT来判断合法不合法（如果i, j之间的值大于S1，那么如果i在第一个集合，j只能在第二个集合，其他类似）。我们将边权从大到小排序，依次枚举S1，发现S2是单调的（S2越大，越可能合法），于是可以二分S2了。另外还有个优化，把枚举S1的过程看成加边的过程，我们发现当这个图不是二分图的时候就可以

2016-07-09 09:46:47 1825

原创【BZOJ4636】蒟蒻的数列【扫描线】【set】

【题目链接】从Claris那里学来的扫描线做法。/* Think Thank Thunk */#include #include #include #include using namespace std;typedef long long LL;const int maxn = 80005;int n, m;LL ans;struct data

2016-07-08 18:10:53 628

原创【BZOJ4631】踩气球【暴力】【线段树优化】

【题目链接】记录每个盒子被哪些熊孩子的区间覆盖，用链表存起来。又因为熊孩子的区间是连续的，所以用线段树优化一下就行了。注意空间大小，不然容易RE WA/* Think Thank Thunk */#include #include #include using namespace std;typedef long long LL;const int max

2016-07-08 17:46:57 1261 1

原创【BZOJ2121】字符串游戏【区间DP】

【题目链接】int开成bool，调了半天...设ok[i][j]表示模板串[i, j]这段是否能被删除完，再设dp[i]表示模板串[1, i]删除之后最少剩多少字母，那么显然有dp[i] = dp[i - 1] + 1if(ok[j][i]) dp[i] = min(dp[i], dp[j - 1])现在考虑如何得到ok[i][j]。设f[i][j][k][

2016-06-27 09:14:45 560

原创【BZOJ1069】[SCOI2007]最大土地面积【凸包】

【题目链接】显然四个点都在凸包上，按逆时针设为i, a, j, b，枚举i和j，a和b都是单调的，复杂度为O(n^2)闲得无聊写了个暴力。。/* Forgive me Not */#include #include #include using namespace std;typedef long double LD;typedef double DB;

2016-06-12 22:39:18 591

原创【HDU4787】GRE Words Revenge【AC自动机】【AC自动机合并】

【题目链接】调了4个小时多.../* Forgive me Not */#include #include #include using namespace std;const int maxn = 100005, maxl = 5000005, maxq = maxn;int n, q[maxq];char str[maxl], tmp[maxl];struc

2016-06-12 22:28:52 775

原创【BZOJ4510】[Usaco2016 Jan]Radio Contact【DP】

【题目链接】看了半天题才看懂...题解：设dp[i][j]表示FJ走到第i步，Bessie走到第j步时，的最小花费。那么从dp[i][j]向dp[i + 1][j]，dp[i][j + 1]，dp[i + 1][j + 1]转移就完了。复杂度：时间复杂度O(nm)，空间复杂度O(nm)收获：要留意到无后效性/* Forgive me

2016-06-10 11:43:09 1025

原创【BZOJ4579】[Usaco2016 Open]Closing the Farm【并查集】【离线】

【题目链接】感觉和BZOJ1015差不多。。题解：倒着考虑操作，就变成了加边。记录当前时刻有多少个连通块，如果有一个，那么答案是YES，否则是NO。对于当前点，把当前点与已经添加进的点合并。每合并一次，连通块减一。（一开始连通块先++）复杂度：时间复杂度O(n+mα(n))空间复杂度O(n+m)收获：当两个点已经在一个并查集里的时

2016-06-10 10:10:42 1070

原创【BZOJ4580】[Usaco2016 Open]248【区间DP】【或贪心】

【题目链接】以为adjacent是不同的意思，结果是相邻23333，写了个贪心WA了一发。题解：设dp[l][r]表示将l和r合并之后，得到的最大的数，于是就可以转移了dp[l][r] = dp[l][k] + 1（dp[l][k] == dp[k + 1][r]）另外还有贪心写法，只不过太麻烦了...话说好像写记忆化搜索的会被卡。。复杂度：时间

2016-06-10 09:21:24 1289

原创 pkusc2016滚粗记

第一次写游记。Day0和yzx，hjs一块，早上7点飞机，上了飞机一直睡...醒来后差不多已经降落了。从机场坐地铁，到北大站。（原来圆明园和中关村都在北大旁边呀）先去了宾馆，结果前台告诉我们房间还没退出来，由于肚子有点饿，就去对面的KFC填了填肚子。到了13点房间才空下，把东西放好，睡了会。起来14点半，去北大报道。北大好大啊...腿都没劲了orz找到了理科

2016-06-08 22:40:36 4090 1

原创【BZOJ3011】[Usaco2012 Dec]Running Away From the Barn【可并堆】

【题目链接】pkusc时候做的题，现在发上来。每个节点维护一个大根堆，维护从根节点到当前节点以及当前节点的子节点的路径长度（即深度）。如果当前节点的堆的堆顶 - 当前节点的深度大于L，那么删除堆顶，直到满足条件为止。那么堆的size就是当前节点的答案。当一个节点处理完毕后，把当前节点的堆与当前节点的父亲的堆合并，就可以了。当一个节点的儿子都处理完后，那么就可以

2016-06-07 14:45:34 817

原创【BZOJ2348】[Baltic 2011]Plagiarism【二分】【或 Two Pointers】

【题目链接】大水题竟然WA了2发。。（1）二分找到位置后，贡献应该是id - l...（2）被卡精度了/* Forgive me Not */#include #include #include using namespace std;typedef long long LL;const int maxn = 100005;int n, num[max

2016-06-02 16:55:57 427

原创【BZOJ2654】tree【二分】【最小生成树】

【题目链接】奇怪的二分。考虑给白边的边权加上一个数，这个数越大，MST时选的白边就越少。注意排序时候，如果边权相等，要先选白边。/* Forgive me Not */#include #include #include using namespace std;const int maxn = 50005, maxm = 100005, inf = 0x3f3

2016-06-02 16:03:48 610

原创【BZOJ1300】[LLH邀请赛]大数计算器【快速幂】【姿势】

【题目链接】比较有意思...经典的组合数取模问题，我们用质因数分解解决。低位的计算就不说了，直接快速幂取模就可以。对于高位的计算，我们计算log10下的答案，即log10(p1^a1*p2^a2*...*pk^ak) = a1*log10(p1) + a2*log10(p2) + ... + ak*log10(pk)记上式为ans，那么答案应该为10^ans，但是我们只要最

2016-06-02 15:21:32 693

原创【BZOJ1742】[Usaco2005 nov]Grazing on the Run 边跑边吃草【区间DP】

【题目链接】算是比较经典的区间DP，比较重要的思路是，把未来的花费放到现在计算。一开始写了个空间O(n^2)的记忆化搜索，结果被卡内存了，最后换成循环了.../* Forgive me Not */#include #include #include using namespace std;const int maxn = 3001, inf = 0x3f3f3f

2016-06-01 17:46:41 916

原创【BZOJ1710】[Usaco2007 Open]Cheappal 廉价回文【区间DP】

【题目链接】经典区间DP。首先添加一个字符和删除一个字符是等价的，因为在一个位置添加一个字符，就等价与在对称回文的位置删除一个字符，删除同理。那么我们只需要考虑删除字符。设dp[l][r]表示将[l, r]改为回文串的最小代价，那么有（1）dp[l][r] = min(dp[l + 1][r] + cost[str[l]], dp[l][r - 1] + cost[str[r]

2016-05-31 18:49:52 731

原创【BZOJ1664】[Usaco2006 Open]County Fair Events 参加节日庆祝【线段覆盖】【贪心】

【题目链接】怎么选到了这么水的题.../* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 10005;int n;struct _data { int l, r; bool operator < (const _da

2016-05-31 18:45:34 870

原创【BZOJ1649】[Usaco2006 Dec]Cow Roller Coaster【背包DP】

【题目链接】设dp[i][j]，表示前i个位置，花费为j，的最大有趣指数。然后类似背包一样转移。/* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 1005, maxm = 10005;int L, n, m, dp[maxn][ma

2016-05-31 18:06:20 783

原创【BZOJ1643】[Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪【暴力】

【题目链接】n = a^2 + b^2 + c^2 + d^2。暴力枚举a，b，c，都是sqrt(n)级别的，然后判断d^2是否是完全平方数。/* Telekinetic Forest Guard */#include #include #include #include using namespace std;int n, m;inline int iread

2016-05-31 16:42:27 986

原创【BZOJ1638】[Usaco2007 Mar]Cow Traffic 奶牛交通【DAG】【拓扑排序】【DP】

【题目链接】对于一条边(u, v)，经过这条边的次数为(1到u的路径个数)*(v到n的路径个数)。正反跑两次拓扑序，然后枚举边，统计答案。一开始以为(1到u的路径个数)就是经过边(u, v)的次数，结果WA啦。/* Telekinetic Forest Guard */#include #include #include #include using names

2016-05-31 16:27:54 859

原创【BZOJ3522】[Poi2014]Hotel【DFS】

【题目链接】NOIP2014D1T2是从这个题改的吧。。题解：首先可以发现，满足条件的点对一定是“有一个中心点，三个点到中心点的距离相等，且三个点分别在不同子树中”这种情况。那么枚举中心点，然后遍历子树，统计答案。d[i]为临时数组，表示当前子树中深度为i的点有多少个。d1[i]表示，当前点已经遍历过的子树中，深度为i的点有多少个。d2[i]表示，当前点已经遍历过的子树

2016-05-31 16:05:57 910

原创【BZOJ1584】[Usaco2009 Mar]Cleaning Up 打扫卫生【DP】

【题目链接】【hzwer的题解】维护转移位置的数组有点神。。/* Telekinetic Forest Guard */#include #include #include #include using namespace std;const int maxn = 40005, inf = 0x3f3f3f3f;int n, m, num[maxn], dp[max

2016-05-31 15:31:29 652

原创【BZOJ1633】[Usaco2007 Feb]The Cow Lexicon 牛的词典【DP】

【题目链接】数据范围都特别小，直接暴力就可以搞了。/* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 605, maxl = 27, maxm = 305;int n, m, dp[maxm], wlen[maxn];char word

2016-05-31 11:48:25 926

原创【BZOJ1576】[Usaco2009 Jan]安全路经Travel【最短路树】【树链剖分】【线段树】

【题目链接】【hzwer的题解】orz倍增求lca，根节点的深度不能从0开始。线段树手滑打跪了orz，WA1发。/* Telekinetic Forest Guard */#include #include #include #include #include #include using namespace std;typedef pair pii;c

2016-05-31 10:46:35 789

原创【BZOJ1570】[JSOI2008]Blue Mary的旅行【最大流】

【题目链接】太神啦。【POPOQQQ的题解】/* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 6005, maxm = 300005, maxe = 2505, maxq = 10000, inf = 0x3f3f3f3f;int n,

2016-05-31 08:59:55 604

原创【BZOJ4145】[AMPPZ2014]The Prices【状压DP】【背包】

【题目链接】【tunix的题解】/* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 105, maxm = 18, maxs = 1 << 16, inf = 0x3f3f3f3f;int n, m, dp[maxn][maxs],

2016-05-30 17:07:21 451

原创【BZOJ3612】[Heoi2014]平衡【计数DP】【整数拆分】

【题目链接】【tunix的题解】枚举力矩和、拿走橡皮的个数，然后就变成整数拆分问题了。/* Telekinetic Forest Guard */#include #include #include using namespace std;const int maxn = 10005, maxk = 12;int n, k, p, dp[maxn * maxk][

2016-05-30 16:42:24 704

原创【BZOJ1857】[Scoi2010]传送带【三分套三分】

【题目链接】好像是比较经典的题了。第一次在考场上写三分orz。/* Telekinetic Forest Guard */#include #include #include #include #include using namespace std;typedef double DB;const DB eps = 1e-6;struct po {

2016-05-30 15:58:36 509

原创【BZOJ2445】最大团【推公式】【中国剩余定理】【扩展Lucas】

【题目链接】公式为：设 ans = ∑(n! / ((d!)^(n/d)*(n/d)!))则答案为m ^ ans证明：考虑现在有d * k个点，d代表每个团的点数，那么k就是个数了，记方案数为Ak。然后现在又来了d个点，记方案数为Ak+1。（即现在有n = d * (k + 1)个点）我们选择一个点，让这个点与其他的d - 1个点组成团，方案数为C(d *

2016-05-30 07:54:07 936

空空如也

空空如也