嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
EelAndRabbit
关键词：离散化，暴力
算法简述
实际上, 我们只需要考虑所有形如 以及 的时刻 就可以了. 如果我们抓鱼的时间不能表示成这两种形式之一的话, 我们可以通过改变时间 调整到这两种形式.
因此我们不妨枚举两次抓鱼的时刻 和 , 然后统计有多少条鱼能被抓上来, 并求出鱼的数量的最大值.
一点点小代码
vector<int> v;
bitset<51> flag[101]; //表示在第i个关键点抓能抓到的集合
class EelAndRabbit {
public:
int getmax(vector<int> l, vector<int> t) {
int n = l.size();
v.clear();
REP(i, 0, n - 1) v.PB(t[i]), v.PB(t[i] + l[i]); //先离散化 找出关键点
int ans = 0;
REP(i, 0, v.size() - 1) {
flag[i].reset();
REP(k, 0, n - 1)
if (t[k] <= v[i] && v[i] <= t[k] + l[k]) flag[i][k] = 1; // 找到能抓到的集合
}
REP(i, 0, v.size() - 1)
REP(j, i, v.size() - 1) get_max(&ans, (int)(flag[i] | flag[j]).count()); //枚举两个时间点
return ans;
}
};
ShoutterDiv1
关键词：贪心， 图论
算法简述
设 为 最小的元素, 为 最大的元素, 那么 的消息被看到当且仅当这则消息被 和 都看到了.
这样的话我们可以从 开始 BFS, 找到 到 和 的最短传播距离, 然后用 来更新 .
注意, 这里有一种特殊情况: 到 的路径与 到 的路径可能有交. 但是我们可以发现, 这种情况一定是先由 传到 (), 再由 传到 和 , 也就是说传播路径可能是 Y 字形. 因此我们还要枚举所有可能的 , 并用 更新 .
一点点小代码
const int N = 2600;
int f[N];
PII a[N];
int l[N], r[N];
bool el[N], er[N];
int n;
bool cmp(const PII &A, const PII &B) {
return A.SC - A.FR > B.SC - B.FR;
}
bool intersect(int x, int y) {
return a[x].SC <= a[y].SC && a[x].SC >= a[y].FR;
}
int calcL(int x) {
int res = 0;
while (!el[x]) {
if (x == l[x]) return -1;
x = l[x]; ++res;
}
return res;
}
int calcR(int x) {
int res = 0;
while (!er[x]) {
if (x == r[x]) return -1;
x = r[x]; ++res;
}
return res;
}
class ShoutterDiv1 {
public:
int count(vector<string> s1000, vector<string> s100, vector<string> s10, vector<string> s1, vector<string> t1000, vector<string> t100, vector<string> t10, vector<string> t1) {
CL(el, 1); CL(er, 1);
CL(l, 0); CL(r, 0);
REP(i, 1, s1.size() - 1) s1000[0] += s1000[i], s100[0] += s100[i], s10[0] += s10[i], s1[0] += s1[i];
REP(i, 1, s1.size() - 1) t1000[0] += t1000[i], t100[0] += t100[i], t10[0] += t10[i], t1[0] += t1[i];
n = s1[0].size();
REP(i, 1, n) a[i].FR = (s1000[0][i - 1] - 0) * 1000 + (s100[0][i - 1] - '0') * 100 + (s10[0][i - 1] - '0') * 10
+ s1[0][i - 1] - '0';
REP(i, 1, n) a[i].SC = (t1000[0][i - 1] - 0) * 1000 + (t100[0][i - 1] - '0') * 100 + (t10[0][i - 1] - '0') * 10
+ t1[0][i - 1] - '0';
sort(a + 1, a + n + 1, cmp);
REP(i, 1, n)
REP(j, 1, n) {
if (a[j].FR > a[i].SC) er[i] = 0;
if (a[j].SC < a[i].FR) el[i] = 0;
}
REP(i, 1, n) {
l[i] = r[i] = i;
REP(j, 1, n) if (a[j].FR <= a[i].SC && a[j].SC > a[r[i]].SC) r[i] = j;
REP(j, 1, n) if (a[j].SC >= a[i].FR && a[j].FR < a[l[i]].FR) l[i] = j;
}
int ans = 0;
REP(i, 1, n) {
f[i] = 1e9;
REP(j, 1, i - 1) if (a[j].FR <= a[i].FR && a[j].SC >= a[i].SC) getmin(&f[i], f[j] + 1);
int fl = calcL(i), fr = calcR(i);
if (fl == -1 || fr == -1) return -1;
getmin(&f[i], fl + fr);
ans += f[i];
}
return ans;
}
};
WallGameDiv1
关键词：博弈, 动态规划, 记忆化搜索
题目简述
Rabbit 和 Eel 在玩一个游戏. 游戏在一个 的棋盘上进行, 在这个游戏中, 玩家需要操作一个棋子, 将它从第一行移动到最后一行(当棋子被移动到最后一行时, 游戏立刻结束). 在第 行第 列有一个数字 , 表示经过这个格子的代价.
游戏由若干轮组成. 每一轮由 Rabbit 先操作. 在第一轮, Rabbit 会把一个棋子放在第一行的某一列上, 并付出相应的费用. 在接下来的每一轮中, Rabbit 先把棋子向左, 向右, 或向下移动一步, 然后付出相应的费用. 然后由 Eel 操作. Eel 可以选取一对 , 其中 并且 , 然后在 和 之间修建一堵墙. Eel 每次操作可以修建任意多的墙, 但是在任意时刻, Eel 修建的墙都不能够使游戏无法结束(也就是说, Eel 修建的墙不能阻止棋子从当前的位置移动到最后一行).
Rabbit 的目标是最小化花费, 而 Eel 的目标是最大化 Rabbit 的花费. 现在假设双方都绝顶聪明, 你需要求出最后的花费.
注意: 多次经过同一个位置的花费算多次.
算法简述
首先注意到两个结论:
- Eel 一定是等 Rabbit 走到某个位置下面, 再决定是否放墙;
- 如果 Eel 没有在 Rabbit 的下面放墙, 那么 Rabbit 一定要走下去.
于是我们可以得到一个推论: 每一行的墙的位置一定是连续的.
接下来我们可以设 表示当前在第 行, 表示有墙的列的编号为, 当前棋子的位置是 ; 表示有墙的列的编号为, 当前棋子的位置是 .
转移时只需要枚举 Eel 是否要在当前位置下面修墙, 如果修墙的话 Rabbit 是从当前位置走到 更好还是走到 更好, 就可以了.
