2018年3月

BZOJ 4919: [Lydsy1706月赛]大根堆

Solution本质上树上问题和链上的最长子序列区别不大,只需要将数组启发式合并就可以了,用 set 就可以。Description给定一棵n个节点的有根树,编号依次为1到n,其中1号点为根节点。每个点有一个权值v_i。你需要将这棵树转化成一个大根堆。确切地说,你需要选择尽可能多的节点,满足大根堆的性质:对于任意两个点i,j,如果i在树上是j的祖先,那么v_i>v_j。请计算可选的最多的点数,注意这些点不必形成这棵树的一个连通子树。Input第一行包含一个正整数n(1<=n<=200000),表示节点的个数。接下来n行,每行两个整数v_i,p_i(0<- 阅读剩余部分 -

BZOJ 4878: [Lydsy1705月赛]挑战NP-Hard

Solution对整个无向图求一个 DFS 树,如果最大深度 > k,就可以输出一条路径,如果 <= k,就可以以深度作为染色方案。有一点点卡常,数组不要开太大。Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> using namespace std; const int N = 1001; const int M = 20001; inline ch- 阅读剩余部分 -

BZOJ 1345: [Baltic2007]序列问题Sequence

Solution单调栈水过。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 2000000; int stack[N], top; int main() { int n; scanf("%d", &n); long long ans = 0; for(int i=1; i<=n; i++) { int x; scanf(&- 阅读剩余部分 -

BZOJ 4657: tower

Solutionhttps://blog.csdn.net/qq_33229466/article/details/70159372Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 100000; const int INF = 0x3f3f3f3f; int n, m, s, t; int a[100][100]; int go[5][2] = {{- 阅读剩余部分 -

POJ 2135: Farm Tour

Solution题目大意:给定一个无向图,求 1-n-1 来回的最短路径,每条边只能走一次。用费用流求解一个流量为 2 的流就可以了。Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 20000; const int M = 200000; int n, m; int head[N], nex[M], to[M], c[M], w[M], ce = 1- 阅读剩余部分 -

BZOJ 2565: 最长双回文串

Solution记录下以每个字符开头/结尾的回文串的最大长度即可。Code#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 300000; char t[N]; char s[N]; void init() { scanf("%s", t); int len = strlen(t); for(int i=0; i<len; i++) { s- 阅读剩余部分 -

BZOJ 1818: [Cqoi2010]内部白点

Solution网上的做法大多是扫描线 + 树状数组,我的做法也差不多,只不过写的是线段树(没他们的短)。首先可以证明的是不存在永不终止的情况,所以输出 -1 是没分的(垃圾出题人),进一步考虑下可以发现最多变色一次就会把所有点染完色了,如果我们把两个同一行或同一列的两个点看成一个线段,那么染色的点一定就是行列两条线端的交点。我们只要求线段交点个数就可以了,我们可以用线段树来完成这个问题,遇到横向的边就区间更新 +1,遇到纵向的边就单点查询。看起来有点问题是吧?由于纵向的边是一个线段,我们只能要一定纵坐标范围内的横向边,线段树是无法直接维护这个东西的,所以我们离线所有纵向的- 阅读剩余部分 -

BZOJ 2330: [SCOI2011]糖果

Solution差分约束模板题Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 101000; const int M = 500000; int n, m; int head[N], nex[M], to[M], val[M], ce; void add(int u, int v, int w) { to[++ce] = v; nex[ce]- 阅读剩余部分 -

BZOJ 1054: [HAOI2008]移动玩具

Solution直接搜索就可以了。可以状压一下方便判重。Code#include <cstdio> #include <algorithm> #include <queue> using namespace std; int s, t; int a[10][10]; int toNum() { int x = 0; for(int i=1; i<=4; i++) for(int j=1; j<=4; j++) { x <<= 1; x |= a[i][j]; - 阅读剩余部分 -

BZOJ 4663: Hack

Solution一句话题意,求一个不能割同一条路径两个边的最小割。我们直接先按照题意建图,然后每条边都加个流量为 INF 的反向边,通过画图和简单思考可以知道,如果割了一条路径的两条边,一定会割掉一个反向边,如果割了反向边就不可能是最小割了,所以加了反向边就可以保证答案的正确性。还有就是要特判一下如果 1 号点不能到达一个点,如果加了反向边它们就可能联通的,这时候不需要加反向边。别忘记开 long longCode#include <cstdio> #include <algorithm> #include <queue> #inclu- 阅读剩余部分 -

BZOJ 1085: [SCOI2005]骑士精神

Solution迭代加深搜索Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> using namespace std; int a[5][5], now[5][5]; int go[8][2] = { {2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {-1, -2}, {-2, -1}, {2, 1}, {1, 2} }; int target[5][5] =- 阅读剩余部分 -

BZOJ 3109: [cqoi2013]新数独

Solution按照题意搜索就行了。Code#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std; const int N = 30; int a[N][N][5]; int bel[N][N]; int l1[N][N]; int l2[N][N]; int used[N][N]; int ans[N][N]; void dfs(int x, int y) { if(y >- 阅读剩余部分 -

BZOJ 1295: [SCOI2009]最长距离

Solution可以直接求下任意两点的最短路,把障碍看做是权值为 1 的点,其他点权值为 0,这样最短路的意义就是两点间拆至少多少个障碍才能联通。之后枚举任意两个点更新答案就可以了Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <cmath> using namespace std; const int N = 32; int n, m, t; int a[N][N]; char s[N]- 阅读剩余部分 -