4 BraketBN

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

【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

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

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

2016-06-10 10:10:42

【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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!