[NOIPTG2017] 小凯的疑惑
题意
小凯有两种面值的金币，每种金币有无数个，求在无法准确支付的物品中，最贵的价值是多少金币。
分析
设两种金币面值分别为 $a$ 和 $b \; (a<b)$ ，答案为 $x$，则有$$x \equiv ma \, (mod \; b) \; (1 \leq m \leq b-1)$$
即$$x=ma+nb \; (1 \leq m \leq b-1)$$
显然当 $n \geq 0$ 时 $x$ 可以用 $a,b$ 表示出来，不合题意
因此当 $n=-1$ 时 $x$ 取得最大值，此时 $x=ma-b$
显然当 $m=b-1$ 时 $x$ 最大，此时 $x=(b-1)a-b=ab-a-b$
因此 $a,b$ 所表示不出的最大的数是 $ab-a-b$
[NOIPPJ2017] 棋盘
题意
在一个棋盘上，棋盘上每一个格子可能是红色、黄色或没有颜色的。你可以向上下左右四个方向走，但所经过的格子必须是有颜色的。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1个金币。
另外， 你可以花费2个金币使用魔法让下一个无色格子暂时变为你指定的颜色。但如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而你离开了这个暂时有颜色的格子后，这个格子恢复为无色。
求从棋盘左上角到右下角（保证左上角格子有颜色），最少需要花费多少金币。
分析
这题有很多种做法，看完题后我最先想到了BFS
于是从左上角格子开始向四个方向尝试扩展，同时要记录当前到达任意一个格子所需的最少金币。若扩展时可以使该块的值更优，则将该块的坐标与所需金币数放入队列。扩展的过程只需要分几种情况模拟：有色块至有色块（是否同色），有色块至无色块，无色块至有色块（是否同色）。为了避免很多不必要的重复，我将队列改为了按金币数排序的小根堆。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x7fffffff
#define N 105 struct Point {
int x, y, z, c;
bool operator< (Point rhs) const{
return z > rhs.z;
}
} p, t; int n, m;
int g[N][N], f[N][N];
priority_queue<Point> q;
int nxt[][] = {, , , , , -, -, }; void bfs() {
memset(f, 0x3f, sizeof f);
p.x = ; p.y = ; p.z = ;
f[][] = ;
q.push(p);
while (!q.empty()) {
t = q.top(); q.pop();
if (t.z > f[t.x][t.y]) continue;
for (int i = ; i < ; i++) {
int dx = t.x + nxt[i][], dy = t.y + nxt[i][];
int nc = g[t.x][t.y], dc = g[dx][dy];
if (dx < || dx > n || dy < || dy > n) continue;
if (t.z > f[dx][dy]) continue;
if (nc) {
if (dc) {
if (nc == dc) {
if (t.z < f[dx][dy]){
p.x = dx; p.y = dy; p.z = t.z;
f[p.x][p.y] = p.z;
q.push(p);
}
}
else if (t.z + < f[dx][dy]) {
p.x = dx; p.y = dy; p.z = t.z + ;
f[p.x][p.y] = p.z;
q.push(p);
}
}
else if (t.z + <= f[dx][dy]) {
p.x = dx; p.y = dy; p.z = t.z + ; p.c = nc;
f[p.x][p.y] = p.z;
q.push(p);
}
}
else if (dc) {
if (t.c == dc) {
if (t.z < f[dx][dy]) {
p.x = dx; p.y = dy; p.z = t.z;
f[p.x][p.y] = p.z;
q.push(p);
}
}
else if (t.z + < f[dx][dy]) {
p.x = dx; p.y = dy; p.z = t.z + ;
f[p.x][p.y] = p.z;
q.push(p);
}
}
}
}
} int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= m; i++) {
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
if (c) g[x][y] = ;
else g[x][y] = ;
}
bfs();
if (f[n][n] < ) printf("%d\n", f[n][n]);
else printf("-1\n"); return ;
}
[NOIPPJ2017] 跳房子
题意
确定一个起点，在起点右侧画n个格子，这些格子与起点分别有一定的距离。每个格子内有一个数字，表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内，第二次再从当前位置继续向右跳，依此类推。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
小R研发了一款弹跳机器人来参加这个游戏。这个机器人每次向右弹跳的距离只能为固定的d。小R如果花g个金币改进他的机器人，那么他的机器人灵活性就能增加g，即他的机器人每次可以选择向右弹跳的距离为d-g, d-g+1, d-g+2, ···, d+g-2, d+g-1, d+g（最小为1）。
现在小R希望至少获得k分，求他至少要花多少金币来改造他的机器人。
分析
我们可以看出得分对于g是单调的，所以考虑二分查找最小符合要求的g。然后对与每个g，我们只需要DP算出到达每个格子可以得到的最高分，然后判断是否存在大于等于k的分数
关于二分g的范围，最小值是0，最大值是离起点最远的格子的距离。由于这个算法不是很优秀，为了不超时得到50分，我把最大值设为1e6，没想到AC了，看来数据比较水，每个测试点的答案都不是很大...
然而正解是单调队列优化，将DP的二维降至了一维
下面是我写的代码（非正解的AC代码）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
//#define inf 0x7fffffff
#define N 500005 inline ll read() {
ll x = , f = ; char ch = getchar();
while (ch < '' || ch > '') {if ( ch == '-') f = -; ch = getchar();}
while (ch >= '' && ch <= '') {x = (x << ) + (x << ) + ch - ''; ch = getchar();}
return x *= f;
} int n;
ll sum, m, d, l = , r = , mid, ans;
ll x[N], s[N], f[N]; ll maxx(ll a, ll b) {
if (a > b) return a;
return b;
} bool check(ll g) {
memset(f, , sizeof f);
f[] = ;
for (int i = ; i < n; i++)
for (int j = i + ; j <= n; j++) {
if (x[j] - x[i] > d + g) break;
if (x[j] - x[i] < maxx(d - g, )) continue;
f[j] = maxx(f[j], f[i] + s[j]);
if (f[j] >= m) return true;
}
return false;
} int main() {
scanf("%d%lld%lld", &n, &d, &m);
for (int i = ; i <= n; i++) {
x[i] = read(); s[i] = read();
if (s[i] > ) sum += s[i];
}
if (sum < m) {
printf("-1\n");
return ;
}
while (l <= r) {
mid = (l + r) >> ;
check(mid) ? ans = mid, r = mid - : l = mid + ;
}
printf("%lld\n", ans); return ;
}
