almost 2 years ago

嘟噜噜... 还有一个月就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 的花费. 现在假设双方都绝顶聪明, 你需要求出最后的花费.

注意: 多次经过同一个位置的花费算多次.

算法简述

首先注意到两个结论:

  1. Eel 一定是等 Rabbit 走到某个位置下面, 再决定是否放墙;
  2. 如果 Eel 没有在 Rabbit 的下面放墙, 那么 Rabbit 一定要走下去.

于是我们可以得到一个推论: 每一行的墙的位置一定是连续的.

接下来我们可以设 表示当前在第 行, 表示有墙的列的编号为, 当前棋子的位置是 ; 表示有墙的列的编号为, 当前棋子的位置是 .

转移时只需要枚举 Eel 是否要在当前位置下面修墙, 如果修墙的话 Rabbit 是从当前位置走到 更好还是走到 更好, 就可以了.

← SRM 591 弱鸡题解 SRM 576 弱鸡题解 →
 
comments powered by Disqus