1、前言
正式开始的第一周的任务——把NOIP2010至NOIP2015的所有D1/2的T2/3写出暴力。共22题。
暴力顾名思义，用简单粗暴的方式解题，不以正常的思路思考。能够较好的保证正确性，但是最大的问题在于效率。搞OI这么久，每次考试也经常纠结于暴力与正解之间，其实这两者概念上本来就没有明显的界限，是一组相对概念。
下面尽可能的不提到正解，但是如果正解容易到我都能够轻松秒的话就还是说一下了。
普通的DFS/BFS搜索是暴力，但暴力不局限于此。根据向总的话，记忆化搜索亦属于暴力，名字逼格这么高分数肯定也高一些。什么是记忆化搜索呢？
记忆化搜索就是把我们之前搜索过的状态保存下来，在之后搜索再遇到这种状态时就可以避免重复搜索，直接调用上次搜索的结果即可。记忆化搜索适用于重复子结构较多的题目。
这样看上去貌似好熟悉。。。是啊很像动态规划。。。
我姑且把它理解为以DFS的形式来实现的动态规划吧，，，虽然向总始终说他不是动态规划。
Tips:（我写的/暴力最佳方式/正解）
2、NOIP2010
② tourist 乌龟棋（?/记忆化搜索/动态规划）
思路：30分暴力直接强行DFS跑所有情况不多说了。考虑本题有一个特别的地方——重叠子结构很多，经常可能出现使用卡片个数相同但是顺序不同的情况。如果直接DFS的话，会浪费大量时间。由于总状态比较少，4张卡片每张只有至多40张，故可以把所有状态存入一个四维数组，f[a][b][c][d]表示在剩下a张1，b张2，c张3，d张4时可以获得的最大分数。在DFS时如果遇到之前已经遇到过的状态，进行比对，选取较大值转移。这样可以省去大量时间，也就是所谓的记忆化搜索。然而一旦你把f[a][b][c][d]的状态转移方程写出来就会发现。。和动态规划有什么区别呢。
代码：
#include <cstdio>
#include <cstring>
#define MAXN 355
#define MAXM 45 int n, m, w[MAXN], x, t[], f[MAXM][MAXM][MAXM][MAXM]; int max(int a, int b) {
return a > b ? a : b;
} int DFS(int o, int a, int b, int c, int d) {
if (f[a][b][c][d] != -) return f[a][b][c][d];
f[a][b][c][d] = ;
if (a) f[a][b][c][d] = max(DFS(o + , a - , b, c, d), f[a][b][c][d]);
if (b) f[a][b][c][d] = max(DFS(o + , a, b - , c, d), f[a][b][c][d]);
if (c) f[a][b][c][d] = max(DFS(o + , a, b, c - , d), f[a][b][c][d]);
if (d) f[a][b][c][d] = max(DFS(o + , a, b, c, d - ), f[a][b][c][d]);
f[a][b][c][d] += w[o];
return f[a][b][c][d];
} int main() {
freopen("tortoise.in", "r", stdin);
freopen("tortoise.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &w[i]);
for (int i = ; i <= m; i++) scanf("%d", &x), t[x]++;
memset(f, -, sizeof(f));
printf("%d", DFS(, t[], t[], t[], t[]));
return ;
}
④ water 引水入城（?/BFS+枚举/BFS+动态规划）
思路：对于30分，题目明确是不能满足要求。。（我竟然没意识到这个的重要性）
3、NOIP2011
② hotel 选择客栈（动态规划/枚举+前缀和/搜索+优化？？）
代码：
#include <cstdio>
#define MAXN 200005
#define MAXK 65 int n, k, p, s, c, v, a[MAXN], f[MAXK][MAXN]; int main() {
freopen("hotel.in", "r", stdin);
freopen("hotel.out", "w", stdout);
scanf("%d %d %d", &n, &k, &p);
for (int i = ; i <= n; i++) {
scanf("%d %d", &c, &v);
for (int j = ; j < k; j++) f[j][i] = f[j][i - ] + (j == c);
s += (v <= p ? f[c][a[i] = i] - : f[c][a[i] = a[i - ]]);
}
printf("%d\n", s);
return ;
}
③ mayan Mayan游戏（搜索/搜索/搜索）
思路：太长不写。恶心死了。
⑤ qc 聪明的质检员（？/二分答案/二分答案）
思路：
代码：
⑥ bus 观光公交（？/最短路/贪心或网络流）
思路：
代码：
4、NOIP2012
② game 国王游戏（贪心/贪心/贪心）
思路：这个贪心到底是如何证明的还是不清楚啊，以前做过所以知道怎么贪心。但是我还是耿直的写了直接根据一只手来贪心50分。感觉题目好鬼。对了记得写高精度。
50分代码：
#include <cstdio>
#include <algorithm>
using namespace std; #define MAXN 1005 typedef long long ll; #ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif ll n, x0, y0, o, ans; struct Mst {
ll x, y;
} a[MAXN]; struct Cmp {
bool operator () (Mst a, Mst b) {
return a.y < b.y;
}
} x; int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf(lld lld lld, &n, &x0, &y0), o = x0;
for (int i = ; i <= n; i++) scanf(lld lld, &a[i].x, &a[i].y);
sort(a + , a + n + , x);
for (int i = ; i <= n; i++) ans = max(ans, o / a[i].y), o *= a[i].x;
printf(lld, ans);
return ;
}
③ drive 开车旅行（？/枚举/倍增+set）
思路：就枚举吧。
⑤ classroom 借教室（线段树/线段树/二分答案+差分）
思路：30分模拟。可以很明显的看出来线段树是很适合这道题的，只要常数不是很大，100分到手（我也不知道怎么才会把常数写大）。
代码：
#include <cstdio>
#define MAXN 1000005 int n, m, c[MAXN], d[MAXN], x[MAXN], y[MAXN], get; struct Tree {
int v, f;
} t[MAXN * ]; int min(int a, int b) {
return a < b ? a : b;
} void build(int o, int l, int r) {
if (l == r) {
t[o].v = c[l];
return;
}
int mid = (l + r) >> ;
build(o << , l, mid), build(o << | , mid + , r);
t[o].v = min(t[o << ].v, t[o << | ].v);
} void pushDown(int o) {
t[o << ].v -= t[o].f, t[o << | ].v -= t[o].f;
t[o << ].f += t[o].f, t[o << | ].f += t[o].f;
t[o].f = ;
} void dec(int o, int l, int r, int ql, int qr, int v) {
if (get) return;
if (t[o].f) pushDown(o);
if (l == ql && r == qr) {
t[o].v -= v, t[o].f += v;
if (t[o].v < ) get = ;
return;
}
int mid = (l + r) >> ;
if (qr <= mid) dec(o << , l, mid, ql, qr, v);
else if (ql >= mid + ) dec(o << | , mid + , r, ql, qr, v);
else dec(o << , l, mid, ql, mid, v), dec(o << | , mid + , r, mid + , qr, v);
t[o].v = min(t[o << ].v, t[o << | ].v);
} int main() {
freopen("classroom.in", "r", stdin);
freopen("classroom.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &c[i]);
build(, , n);
for (int i = ; i <= m; i++) {
scanf("%d %d %d", &d[i], &x[i], &y[i]);
dec(, , n, x[i], y[i], d[i]);
if (get) {
printf("-1\n%d", i);
return ;
}
}
printf("");
return ;
}
⑥ blockade 疫情控制（枚举/枚举/二分答案+贪心+倍增）
思路：20分枚举。
代码：
#include <cstdio>
#include <algorithm>
using namespace std; #define MAXN 10005 int n, u, v, w, m, a[MAXN];
int o, h[MAXN], vis[MAXN], res, b[MAXN], c[MAXN], btot, ctot; struct Edge {
int v, next, w;
} e[MAXN]; void addEdge(int u, int v, int w) {
o++, e[o] = (Edge) {v, h[u], w}, h[u] = o;
} void DFS(int o, int fa) {
for (int x = h[o]; x; x = e[x].next) {
int v = e[x].v;
if (v == fa) continue;
if (a[v]) res += a[v];
DFS(v, o);
}
} int work() {
for (int x = h[]; x; x = e[x].next) {
int v = e[x].v;
res = a[v], DFS(v, );
if (!res) b[++btot] = e[x].w;
else if (res != ) c[++ctot] = e[x].w * (res - );
}
sort(b + , b + btot + ), sort(c + , c + ctot + );
return b[] + c[ctot];
} int main() {
freopen("blockade.in", "r", stdin);
freopen("blockade.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i <= n - ; i++)
scanf("%d %d %d", &u, &v, &w), addEdge(u, v, w), addEdge(v, u, w);
scanf("%d", &m);
for (int i = ; i <= m; i++) scanf("%d", &o), a[o]++;
printf("%d", work());
return ;
}
5、NOIP2013
② match 火柴排队（树状数组+逆序对/枚举/树状数组或归并排序+逆序对）
思路：考虑给出的式子在什么情况下可以获得最小值？两列数组分别最大对最大，次大对次大……最小对最小。为了达到这一局面，求逆序对就行了！（就行了。哦。）这个点确实考的非常偏啊，如果没有提前看过的话怎么做？
这个插下逆序对的概念：
对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[i] > A[j]，则称(A[i] , A[j])为数组A中的一个逆序对。
代码：
#include <cstdio>
#include <algorithm> #define MAXN 100005
#define MOD 99999997
using namespace std; int n, a[MAXN], b[MAXN], ta[MAXN], tb[MAXN], c[MAXN], ans, tot[MAXN]; struct cmpa {
bool operator () (int a,int b) {
return (ta[a]<ta[b]);
}
} xa; struct cmpb {
bool operator () (int a, int b) {
return (tb[a] < tb[b]);
}
} xb; int lowbit(int o) {
return o & -o;
} void update(int o) {
while (o <= n) tot[o]++, o += lowbit(o);
} int getSum(int o) {
int ans = ;
while (o) ans += tot[o], o -= lowbit(o);
return ans;
} int main() {
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &ta[i]), a[i] = i;
for (int i = ; i <= n; i++) scanf("%d", &tb[i]), b[i] = i;
sort(a + , a + n + , xa), sort(b + , b + n + , xb);
for (int i = ; i <= n; i++) c[b[i]] = a[i];
for (int i = ; i <= n; i++) update(c[i]), (ans += (i - getSum(c[i]))) %= MOD;
printf("%d", ans);
return ;
}
③ truck 货车运输（最大生成树/SPFA+优化/最大生成树+倍增）
思路：30分算法直接SPFA维护最长路，我用的30分是Kruskal维护最大生成树，一条边一条边加进去进行判断。。。然而这道题做到60分的暴力也不难——就是把这两种30分算法综合一下（what...）。当且仅当所选择的边在最大生成树上的时候，可以得到最优解。故可以事先求出最大生成树，在最大生成树上进行SPFA！蠢的想不到啊卧槽。100分的话，感觉不是很难吧暂时没写，最大生成树+树上倍增LCA。
30分代码：
#include <cstdio>
#include <algorithm> #define MAXN 10005
#define MAXM 50005
#define INF 1 << 30 using namespace std; int n, u, v, w, q, o;
int s, t, set[MAXN], m; struct Edge {
int u, v, w;
}; Edge e[MAXN * ]; struct Cmp {
bool operator () (Edge a, Edge b) {
return (a.w > b.w);
}
} x; void addEdge(int u, int v, int w) {
o++, e[o] = (Edge) {u, v, w};
} int check(int x) {
return (set[x] == x ? x : set[x] = check(set[x]));
} int work() {
int ans, get = ;
for (int i = ; i <= m; i++) {
if (check(s) == check(t)) {
get = ;
break;
}
int c1 = check(e[i].u), c2 = check(e[i].v);
if (c1 != c2) set[c1] = c2, ans = e[i].w;
}
return get ? ans : -;
} int main() {
freopen("truck.in", "r", stdin);
freopen("truck.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) scanf("%d %d %d", &u, &v, &w), addEdge(u, v, w);
sort(e + , e + m + , x);
scanf("%d", &q);
while (q--) {
scanf("%d %d", &s, &t);
for (int i = ; i <= n; i++) set[i] = i;
printf("%d\n", work());
}
return ;
}
60分代码：
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std; #define MAXN 10005
#define MAXM 50005
#define INF 1 << 30 struct Tmp {
int u, v, w;
} te[MAXM]; struct Edge {
int v, next, w;
} e[MAXN]; struct Cmp {
bool operator () (Tmp a, Tmp b) {
return a.w > b.w;
}
} x; int n, m, t, u, v, w, o, head[MAXN], vis[MAXN], dis[MAXN], q[MAXN * ], set[MAXN]; int check(int o) {
return o == set[o] ? o : set[o] = check(set[o]);
} void addEdge(int u, int v, int w) {
o++, e[o] = (Edge) {v, head[u], w}, head[u] = o;
} int SPFA(int x, int y) {
int h = , t = ;
memset(vis, , sizeof(vis)), memset(dis, -, sizeof(dis));
q[] = x, vis[x] = , dis[x] = INF;
while (h != t) {
int o = q[h];
for (int x = head[o]; x; x = e[x].next) {
int v = e[x].v;
if (dis[v] < min(dis[o], e[x].w)) {
dis[v] = min(dis[o], e[x].w);
if (!vis[v]) vis[v] = , q[t] = v, t++;
}
}
vis[o] = , h++;
}
return dis[y];
} int main() {
freopen("truck.in", "r", stdin);
freopen("truck.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
te[i] = (Tmp) {u, v, w};
}
sort(te + , te + m + , x);
for (int i = ; i <= n; i++) set[i] = i;
for (int i = ; i <= m; i++) {
int u = te[i].u, v = te[i].v, w = te[i].w;
int c1 = check(u), c2 = check(v);
if (c1 != c2) set[c1] = c2, addEdge(u, v, w), addEdge(v, u, w);
}
scanf("%d", &t);
for (int i = ; i <= t; i++) scanf("%d %d", &u, &v), printf("%d\n", SPFA(u, v));
return ;
}
⑤ flower 花匠（贪心/贪心/动态规划+优化）
思路：最想吐槽的一道题，。为什么正解会想到动态规划。。不是说不可做，这摆明了的可以贪心啊！虽然两年前甚至是一年前都无法很快的想到，但是一年之后的我把这道题当做新题再看一次的时候，实在是想不通为什么要去动态规划的路线。。所以我写了一个代码量极短的贪心。
代码：
#include <cstdio>
#define MAXN 100005 int n, h[MAXN], t[], o; int max(int a, int b) {
return a > b ? a : b;
} int main() {
freopen("flower.in", "r", stdin);
freopen("flower.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &h[i]);
for (int j = ; j <= ; j++, o = j)
for (int i = ; i <= n; i++)
if (o ? (h[i] > h[i - ]) : (h[i] < h[i - ])) o ^= , t[o]++;
printf("%d", max(t[], t[]) + );
return ;
}
⑥ puzzle 华容道（BFS+少量优化？/BFS/BFS+SPFA）
思路：直接写了BFS，据说是60分，但是最后得了70分。
70分代码：
#include <cstdio>
#include <cstring>
#define MAXN 35 const int vx[] = {, , , -}, vy[] = {, -, , }; int n, m, t, a[MAXN][MAXN], vis[MAXN][MAXN][MAXN][MAXN];
int ex, ey, sx, sy, tx, ty; struct Queue {
int x, y, ox, oy, d;
} q[MAXN * MAXN * MAXN * MAXN]; int BFS() {
int h = , t = ;
q[] = (Queue) {ex, ey, sx, sy, };
while (h != t) {
for (int i = ; i <= ; i++) {
int nx = q[h].x + vx[i], ny = q[h].y + vy[i];
if (nx == q[h].ox && ny == q[h].oy) {
q[t].ox = q[h].x, q[t].oy = q[h].y;
if (q[t].ox == tx && q[t].oy == ty) return q[h].d + ;
}
else q[t].ox = q[h].ox, q[t].oy = q[h].oy;
if (!a[nx][ny] || vis[nx][ny][q[t].ox][q[t].oy]) continue;
vis[nx][ny][q[t].ox][q[t].oy] = ;
q[t].x = nx, q[t].y = ny, q[t].d = q[h].d + ;
t++;
}
h++;
}
return -;
} int main() {
freopen("puzzle.in", "r", stdin);
freopen("puzzle.out", "w", stdout);
scanf("%d %d %d", &n, &m, &t);
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++) scanf("%d", &a[i][j]);
for (int i = ; i <= t; i++) {
memset(vis, , sizeof(vis));
scanf("%d %d %d %d %d %d", &ex, &ey, &sx, &sy, &tx, &ty);
vis[ex][ey][sx][sy] = ;
printf("%d\n", sx == tx && sy == ty ? :BFS());
}
return ;
}
6、NOIP2014
② link 联合权值（BFS/BFS/树形动态规划）
思路：现在来看还是NOIP2014的题最良心。。。直接根据点与点之间的关系找出所有距离为2的点对，最后再统计权值即可。记得开long long。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define MAXN 200005
#define MOD 10007 #ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif typedef long long ll; ll h[MAXN], w[MAXN], tot[MAXN], n, u, v, o, ans, maxv; struct edge {
ll v, next;
} e[MAXN * ]; void add(ll u, ll v) {
o++, e[o] = (edge) {v, h[u]}, h[u] = o;
} void work(ll x, ll fa) {
ll sonv = , tmax = , vmax;
for (ll o = h[x]; o; o = e[o].next) {
ll v = e[o].v;
sonv += w[v];
if (tmax < w[v]) tmax = w[v], vmax = v;
}
for (ll o = h[x]; o; o = e[o].next) {
ll v = e[o].v;
if (v == fa) continue;
if (v != vmax) maxv = max(maxv, tmax * w[v]);
tot[v] += w[fa] + sonv - w[v], work(v, x);
maxv = max(maxv, w[v] * w[fa]);
}
} int main() {
freopen("link.in", "r", stdin);
freopen("link.out", "w", stdout);
scanf(lld, &n);
for (ll i = ; i < n; i++) scanf(lld " " lld, &u, &v), add(u, v), add(v, u);
for (ll i = ; i <= n; i++) scanf(lld, &w[i]);
work(, );
for (ll i = ; i <= n; i++) (ans += w[i] * tot[i]) %= MOD;
printf(lld " " lld, maxv, ans);
return ;
}
③ bird 飞扬的小鸟（动态规划/记忆化搜索/动态规划）
思路：这个题搜索分高的有点过分啊（当然我也是受益者之一）。其实题目本身没有太多难度，无论是搜索还是记忆化搜索还是动态规划，最要注意的部分就是上界的特判。
代码：
#include <cstdio> #define MAXN 10005
#define MAXM 1005
#define INF 0x3f3f3f3f int n, m, k, x[MAXN], y[MAXN], u[MAXN], d[MAXN], f[MAXN][MAXM], ans = INF, cnt; int min(int a, int b) {
return a < b ? a : b;
} int main() {
freopen("bird.in", "r", stdin);
freopen("bird.out", "w", stdout);
scanf("%d %d %d", &n, &m, &k);
for (int i = ; i < n; i++) scanf("%d %d", &x[i], &y[i]);
for (int i = ; i <= n; i++) u[i] = m + ;
for (int i = ; i <= k; i++) {
int o;
scanf("%d", &o), scanf("%d %d", &d[o], &u[o]);
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
f[i][j] = INF;
if (j > x[i - ]) f[i][j] = min(f[i][j], min(f[i - ][j - x[i - ]], f[i][j - x[i - ]]) + );
}
for (int j = m - x[i - ]; j <= m; j++) f[i][m] = min(f[i][m], min(f[i - ][j], f[i][j]) + );
for (int j = d[i] + ; j <= u[i] - ; j++)
if (j + y[i - ] <= m) f[i][j] = min(f[i][j], f[i - ][j + y[i - ]]);
for (int j = ; j <= d[i]; j++) f[i][j] = INF;
for (int j = u[i]; j <= m; j++) f[i][j] = INF;
int get = ;
for (int j = ; j <= m ; j++)
if (f[i][j] != INF) {
get = ;
break;
}
if (!get) {
printf("0\n%d", cnt);
return ;
}
else if (u[i] != m + ) cnt++;
}
for (int i = ; i <= m; i++) ans = min(ans, f[n][i]);
printf("1\n%d", ans);
return ;
}
⑤ road 寻找道路（搜索/搜索/搜索）
思路：来自day2的水题。正序逆序各对图进行一次扫描，用DFS/BFS/SPFA均可。
代码：
#include <cstdio>
#include <cstring> #define MAXN 10005
#define MAXM 200005
#define INF 0x3f3f3f3f int n, m, u, v, st, en, head[][MAXN], o[], dep[MAXN], vis[MAXN]; struct edge {
int v, next;
} e[][MAXM]; void add(int u, int v, int x) {
o[x]++, e[x][o[x]] = (edge) {v, head[x][u]}, head[x][u] = o[x];
} void init() {
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) scanf("%d %d", &u, &v), add(u, v, ), add(v, u, );
scanf("%d %d", &st, &en);
memset(dep, INF, sizeof(dep));
} void BFS1() {
int q[MAXN], h = , t = ;
q[] = en, vis[en] = ;
while (h != t) {
int o = q[h];
for (int x = head[][o]; x; x = e[][x].next) {
int v = e[][x].v;
if (vis[v]) continue;
vis[v] = , q[t] = v, t++;
}
h++;
}
} void BFS2() {
int q[MAXN], h = , t = ;
q[] = st, dep[st] = ;
while (h != t) {
int o = q[h], no = ;
for (int x = head[][o]; x; x = e[][x].next) {
int v = e[][x].v;
if (!vis[v]) {
no = ;
break;
}
}
if (!no)
for (int x = head[][o]; x; x = e[][x].next) {
int v = e[][x].v;
if (dep[v] > dep[q[h]] + ) q[t] = v, t++, dep[v] = dep[q[h]] + ;
}
h++;
}
} int main() {
init(), BFS1(), BFS2();
if (dep[en] != INF) printf("%d", dep[en]); else printf("-1");
return ;
}
⑥ equation 解方程（搜索/搜索/搜索+Hash+取模）
思路：30分从头搜到尾。。。50分是高精度吧，没时间写就没有写了。据说搜索+取模可以省去高精度直接AC？现在应该不是研究这个的时候了。。。我只写了30分的。
30分代码：
#include <cstdio>
#define MAXN 105 int n, m, a[MAXN], tot = , ans[MAXN]; int main() {
freopen("equation.in", "r", stdin);
freopen("equation.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= m; i++) {
int x = , o = ;
for (int j = ; j <= n; j++) o += a[j] * x, x *= i;
if (o == ) ans[tot++] = i;
}
printf("%d\n", tot);
for (int i = ; i < tot; i++) printf("%d\n", ans[i]);
return ;
}
7、NOIP2015
呵呵哒。你敢信我对这一年的题目什么印象都没有。。他们在那里讲信息传递的时候我一脸懵逼。确实一点都不想回忆这个，所以15年的我一道题都没有去做。
② message 信息传递
③ landlords 斗地主
⑤ substring 子串
⑥ transport 运输计划