A. 和猫猫一起起舞！

By Hetmes Askalana *

题意分析

存在两个字符集 $\{U, D\}, \{L, R\}$ ，给定任意UDLR中的字符，输出两个字符集中不和该字符处在同一字符集的任意字符。不计大小写。

题解

直接按上文所述判断即可。

代码

C++:

void solve(){
    char c;
    cin >> c;
    if(c == 'U' or c == 'D') cout << 'L';
    else cout << 'U';
    cout << endl;
    return;
}

Python:

print("L" if input() in list("UD") else "U")

B. 冒险猫猫参上！！

By Hetmes Askalana *

题意分析

构造一个长度为 $n$ 的数组 $a$ ，保证 $\forall i, j \in [1, n] \land j - i = 1, a_i, a_j \neq 0, |a_i - a_j| = 1$ 同时 $\sum_{i=1}^n a_i \leq 3n$

题解

总和还是给多了。

我们首先构造一个基础数组 $\{1, 1, 1, 1, ...\}$ ，如果我们间隔 $1$ 将其 $+1$ ，那么数组就会变成 $\{1, 2, 1, 2, ...\}$ ， $\sum_{i=1}^n a_i \leq \frac {3n} 2$ ，所以我们只需要输出这个数组的前 $n$ 项即可。

不难看需要 $+1$ 的位置和奇偶性有关，于是：

代码

void solve(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){ // ++i是在循环里一个常数优化，可以不管
        cout << i % 2 + 1 << " ";
    }
    cout << endl;
}

C. 泉神，启动！！！

By Hetmes Askalana *

题意分析

题目中说的很明白了，找到一个 $1 \leq y \leq 10^{18}$ ，使得 $x \times y$ 的数集是 $x$ 数集的子集，也就是所有在 $x \times y$ 中的数字都被包含在 $x$ 内。

题解

不难看出，例如 $x = 2233$ ， $22330$ 一定可以被 $x$ 整除， $223300, 2233000, 22330000$ 肯定也行，因为它们都是 $2233 \times 10^k, k \in Z^+$

此时可以观察出， $22330000$ 正好空出了四个位置供 $x$ 直接填入末尾，得出 $z = 22332233, \frac z x = 100001$ ，而且这种形式对于任意 $x$ 都可以试用，于是得出一个通式：

$y = 1 \times 10^{\lfloor\log_{10}x\rfloor + 1} + 1$

由于我们是打ACM的，所以可以转化为：

$y = 1 \times 10^{len(str(x))} + 1$

且因为 $x \leq 10^9$ ，故 ${\log_{10}x} \leq 9$ ，所以 ${\log_{10}y} \leq 10$ ，满足 $y \leq 10^{18}$ 。

代码

void solve(){
    string s; cin >> s;
    cout << (LL)(pow(10, s.length()) + 1) << endl;
    return;
}

for _ in range(int(input())):
    print(10 ** (len(input())) + 1)

D. 大预言家！！！！

By Hetmes Askalana *

题意分析

在平面直角坐标系中有一虫绕原点以特定规则螺旋状爬行，求 $t$ 秒后甲虫所在位置。

题解

本题的正解和 $t_i$ 有序并没有一点关系。

我们把题目中的图缺失的部分填满，可以看出当 $i = j \land i, j >= 0$ 的时候，抵达该点的时间是 $(2i + 1)^2$ ，所以我们可以选择以该点为基准点，确定一个边长为 $i * 2$ 的正方形，于是我们可以选择一条边即可确定一个 $x$ 或者 $y$ ，它一定等于 $\pm i$ 。之后进行回溯，即可 $O(1)$ 算出结果。

之后就纯模拟了，叙述起来实在麻烦，可以看看代码。其中 // 等价于 C++ 中的整形除法。

记得开LL。

代码

def solve():
    t = int(input())
    n = int(math.ceil(math.sqrt(t)))
    n += 1 if n % 2 == 0 else 0 # 右上角定位，强制取大于等于t秒的第一个抵达秒数是一个奇数的平方的位置
    tmp = n * n - t
    if tmp < n: # 上边
        y = n // 2
        x = (n // 2) - tmp
    elif tmp < (2 * n - 1): # 左边
        tmp -= n
        x = -(n // 2)
        y = (n // 2 - 1) - tmp
    elif tmp < (3 * n - 2): # 下边
        tmp -= (2 * n - 1)
        y = -(n // 2)
        x = -(n // 2 - 1) + tmp
    else: # 只剩下右边
        base = (n - 2) * (n - 2)
        tmp = t - base
        x = (n // 2)
        y = (n // 2) - tmp
    print(x, y)
    return

E. 全都要！！！！！

By Hetmes Askalana *

题意分析

有一条长度为 $n$ 的路径，移动 $k$ 次，每次移动可以选择前进 $[1, 6]$ 格子，并获取该格的金币（也可能损失），求抵达目标点时可以获得的最多金币（可能亏）。

题解

ALL!!!!!ALL OR NOTHING!!!!!

好得不能再好了，[数据删除]方圆一米最家喻户晓，最权威的投资导师Askalana的猫猫教您日赚百亿！不要998，更不要9998，更更不要99998！只要V我50，请猫猫吃肯德基（bushi）

以上为胡话。

我们可以定义二维动态规划数组 $f_{ij}$ ，表示在抵达第 $i$ 格总共移动了 $j$ 次的状态，遍历所有可能的骰子（6个值）为 $dc$ ，即可得到状态转移方程：

$f_{ij} = \max\{f_{ij}, f_{i - dc, j - 1} + a_i\}$

最后取 $R = \max\{f_{ik}\}, i \in [1, n]$ 即为答案。

DP 数组的最小值需要满足 $f_{ij} < -2 \times 10^{9+5}$ 才不会被负数卡爆。

ps：这道题的数据被限制为最多有 $k - 1$ 个格子是可以获取金币的，其余包亏，所以那些读成最多 $k$ 次的全被卡爆了。

代码

void solve(){
    int n, k; cin >> n >> k;
    vector<LL> a(n + 5);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    vector<vector<LL>> f(n + 5, vector<LL>(k + 5, -1145141919810)); // 魔法的数字，助您日入百亿
    LL R = -1145141919810;
    f[0][0] = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= min(i, k); ++j){
            for(int p = max(0, i - 6); p <= i - 1; ++p){
                f[i][j] = max(f[i][j], f[p][j - 1] + a[i]);
            }
        }
        R = max(R, f[i][k]);
    }
    cout << R << endl;
}

F. 水题！！！！！！

By Hetmes Askalana *

题意分析

给定一个垂直迷宫，在 * 的位置召唤一个无限水源，求按题目所述的规则扩散多久后可以使水流任意末端抵达 %。

题解

首先明确一个性质，除了垂直下来的有 创造新路径 能力的水流外，其余的在到达一个空点时一定是最快的。那么也可以推广出：同一维度的水流在抵达一个同维度的流体未抵达过的点的时候一定最快。

由于每次扩散时间一定会增加，我们可以使用 广度优先搜索 的方式，用 大根堆 以时间自小到大存储所有需要处理的扩散端点。在处理破坏破坏障碍物时，根据如上规律我们可以直接假定这一格的障碍物已损，令水流进入这段空间即可。

如果不愿意开三维vis，在vis判定时忽略竖向水流，检查下方需要进入的障碍物是否vis过也是可以的。

代码

struct Node{
    int x, y, nowT, abi;
    bool operator<(const Node& y) const{
        return y.nowT < nowT;
    }
};

void solve(){
    int n, m, t;
    cin >> n >> m >> t;
    ++t; // 我们默认水流直接进入新节点，所以t自增比较方便。
    vector<vector<char>> G(n + 5, vector<char>(m + 5, '^'));
    pair<int, int> stp, enp;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> G[i][j];
            if(G[i][j] == '*') stp = {i, j};
            if(G[i][j] == '%') enp = {i, j};
        }
    }
    priority_queue<Node> q;
    q.push({stp.first, stp.second, 0, 1});
    vector<vector<bool>> vis(n + 5, vector<bool>(m + 5, 0));
    while(!q.empty()){
        auto [x, y, nowT, can] = q.top();
        q.pop();
        if(can != 1) if(vis[x][y]) continue;
        vis[x][y] = true;
        if(G[x][y] == '%'){ // 搜到了就直接强制终止，因为堆和模型的性质，一定是最优的之一。
            cout << nowT << endl;
            return;
        }
        if(G[x + 1][y] == '#'){
            if(can and !vis[x + 1][y]) q.push({x + 1, y, nowT + t, 1}); // 塞
            if(y + 1 <= m and G[x][y + 1] != '#') q.push({x, y + 1, nowT + 1, 0}); // 左右扩散判定
            if(y - 1 >= 1 and G[x][y - 1] != '#') q.push({x, y - 1, nowT + 1, 0});
        }else{
            if(x + 1 <= n) q.push({x + 1, y, nowT + 1, 1}); // 垂直扩散判定
        }
    }
    cout << -1 << endl;
    return;
}

牛客周赛83 - 题解

A. 和猫猫一起起舞！

题意分析

题解

代码

B. 冒险猫猫参上！！

题意分析

题解

代码

C. 泉神，启动！！！

题意分析

题解

代码

D. 大预言家！！！！

题意分析

题解

代码

E. 全都要！！！！！

题意分析

题解

代码

F. 水题！！！！！！

题意分析

题解

代码