2021牛客寒假算法基础集训营1

比赛地址：https://ac.nowcoder.com/acm/contest/9981

出题人题解：https://ac.nowcoder.com/discuss/593200

A-串

知识点： $dp$

第一种：定义状态 $dp[i][0/1][0/1]$ 表示前 $i$ 个字符是否包含字母 $u$ 和 $s$ 。

$dp[i][0][0]$ 表示前 $i$ 个字符没有 $u$ ，也没有 $s$ 。
$dp[i][0][1]$ 表示前 $i$ 个字符没有 $u$ ，但是有 $s$ 。
$dp[i][1][0]$ 表示前 $i$ 个字符有 $u$ ，但 $u$ 后面没有 $s$ 。
$dp[i][1][1]$ 表示前 $i$ 个字符有 $u$ ，且 $u$ 后面有 $s$ 。

则有状态转移方程：

$dp[i+1][0][0]=dp[i][0][0] * 24;$
前 $i$ 个字符没有 $u$ 和 $s$ ，第 $i+1$ 个位置有24个字母(除了 $u,s$ )可选。
$dp[i+1][0][1]=dp[i][0][0] + dp[i][0][1] * 25;$
前 $i$ 个字符没有 $u$ 和 $s$ ，第 $i+1$ 个位置只能选 $s$ ；
前 $i$ 个字符有 $s$ ，第 $i+1$ 个位置有25个字母(除了 $u$ )可选。
$dp[i+1][1][0] = dp[i][0][0] + dp[i][0][1] + dp[i][1][0] * 25;$
前 $i$ 个字符没有 $u$ 和 $s$ ，第 $i+1$ 个位置只能选 $u$ ；
前 $i$ 个字符有 $s$ ，第 $i+1$ 个位置也可以选 $u$ ；
前 $i$ 个字符有 $u$ ，第 $i+1$ 个位置有25个字母(除了 $s$ )可选。
$dp[i+1][1][1] = dp[i][1][0] + dp[i][1][1] * 26;$
前 $i$ 个字符有 $u$ ，第 $i+1$ 个位置只能选 $s$ ；
前 $i$ 个字符有 $u$ 和 $s$ ，第 $i+1$ 个位置有26个字母可选。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL dp[MAXN][2][2];
LL ans;
int main() {
    scanf("%d", &n);
    dp[1][0][0] = 24; //没有u，没有s
    dp[1][0][1] = 1; //没有u，但有s
    dp[1][1][0] = 1; //有u，但后面没有s
    dp[1][1][1] = 0; //有u，且后面有s
    for(int i = 2; i <= n; i++) {
        dp[i][0][0] = dp[i - 1][0][0] * 24;
        dp[i][0][0] %= mod;

        dp[i][0][1] = dp[i - 1][0][0] + dp[i - 1][0][1] * 25;
        dp[i][0][1] %= mod;

        dp[i][1][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][1][0] * 25;
        dp[i][1][0] %= mod;

        dp[i][1][1] = dp[i - 1][1][0] + dp[i - 1][1][1] * 26;
        dp[i][1][1] %= mod;

        ans = (ans + dp[i][1][1]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

第二种(出题人解法)：定义状态 $dp[i]$ 表示前 $i$ 个字符是否包含子序列 $us$ 。

则有状态转移方程： $dp[i+1]=26^i-25^i+25*dp[i];$
对于长度为 $i+1$ 的字符串包含子序列 $us$ 有两种情况：

前 $i$ 个字符包含子序列 $us$ ，第 $i+1$ 个位置有26个字母可选，数量为 $26*dp[i]$ 。
前 $i$ 个字符包含 $u$ 但 $u$ 后面没有 $s$ ，第 $i+1$ 个位置只能选 $s$ ，数量为 $26^i(任意选)-25^i(没有u)-dp[i](us)$ 。

将两种情况合并即为 $dp[i+1]$ 。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL ans;
LL dp[MAXN];
LL po[MAXN][2];
int main() {
    scanf("%d", &n);
    ans = dp[2] = 1;
    po[2][0] = 26 * 26;
    po[2][1] = 25 * 25;
    for(int i = 3; i <= n; i++) {
        po[i][0] = po[i - 1][0] * 26 % mod;
        po[i][1] = po[i - 1][1] * 25 % mod;
        dp[i] = (po[i - 1][0] - po[i - 1][1] + 25 * dp[i - 1]) % mod;
        dp[i] = (dp[i] + mod) % mod;
        ans = (ans + dp[i]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

第三种：线性递推方程

四糸智乃在出题人题解的评论区补充了线性递推方程：A题补充一个线性递推方程，这个方式是用高斯消元解线性递推的方式生成的，你不需要对这个方程式做解释或者去理解它，只是说这个式子能够和题目完美匹配。 $dp[1]=0,dp[2]=1,dp[3]=77$
$dp[i]=76*dp[i-1]-1925*dp[i-2]+16250*dp[i-3]+1$

注：上面的 $dp[i]$ 是最终答案，不需要求和。感兴趣的可搜索BM算法求线性递推式。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL dp[MAXN] = {0, 0, 1, 77};
int main() {
    scanf("%d", &n);
    for(int i = 4; i <= n; i++) {
        dp[i] = (76 * dp[i - 1] - 1925 * dp[i - 2] + 16250 * dp[i - 3] + 1) % mod;
        dp[i] = (dp[i] + mod) % mod;
    }
    printf("%lld\n", dp[n]);
    return 0;
}

B-括号

知识点：构造

考虑这样去构造：先放 $l$ 个 $($ ，再放 $r$ 个 $)$ ，合法的括号对数量为 $l*r$ 。
找到最小的 $x$ 满足 $x * x \geq K$ ，使得 $l=x$ ，再找最大的 $r$ 满足 $l * r \leq k$ 。注意这里 $r$ 不一定为 $x-1$ ，例如当 $k=5$ 时 $2*2=4<5<3*2=6<3*3=9$ 。
计算还需要的合法括号对数 $cnt=k-l*r$ 。
最后方案为左边 $l$ 个 $($ ，并在 $cnt$ 的位置插入一个 $)$ ，然后右边 $r$ 个 $)$ 。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int k;
int findr(int l) {
    for(int r = l; r >= 0; r--) {
        if(l * r <= k) return r;
    }
    return -1;
}
void solve(int x) {
    int l = x, r = findr(x);
    int cnt = k - l * r;

    for(int i = 1; i <= l; i++) {
        putchar('(');
        if(i == cnt) putchar(')');
    }
    for(int i = 1; i <= r; i++) putchar(')');
    putchar(10);
}
int main() {
    scanf("%d", &k);
    if(k) {
        int x = 0;
        while(++x) {
            if(x * x >= k) {
                solve(x);
                break;
            }
        }
    } else puts(")");
    return 0;
}
/*
0
)
1
()
2
(()
 3
 ()()
 4
 (())
 5
 (()()
9
((()))
*/

C-红和蓝

知识点：树形 $dp$

定义状态 $dp[i]$ ：

$dp[i]=-1$ 表示以 $i$ 为根结点的子树无解。
$dp[i]=0$ 表示以 $i$ 为根结点的子树可以刚好构造合法解。
$dp[i]=1$ 表示以 $i$ 为根结点的子树除掉根结点后可以构造合法解。

对于结点 $i$ 有以下情况：

有子树无解， $dp[i]=-1$ 。
有大于一棵子树除掉根结点后可以构造合法解， $dp[i]=-1$ 。
有且恰有一棵子树除掉根结点后可以构造合法解，则该子树的根与结点 $i$ 配对是合法解， $dp[i]=0$ 。
所有的子树都已合法，则以 $i$ 为根结点的子树剩下根结点 $i$ ， $dp[i]=1$ 。

判断是否有解之后，只需要遍历一遍树使得 $dp[i]=0$ 的结点和根结点颜色不同， $dp[i]=1$ 的结点和根结点颜色相同即可。

注：荷塘涟漪的博客写了从叶子往根和从根往叶子两种思路。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int ans[MAXN];

///建树
int u, v;
int head[MAXN];
int edge[MAXN], ne[MAXN];
void addedge(int i, int u, int v) {
    edge[i] = v;
    ne[i] = head[u];
    head[u] = i;
}

///判断是否存在解
int dp[MAXN];
//dp[i] = -1 表示当前子树无合法解
//dp[i] = 0 表示当前子树已经合法
//dp[i] = 1 表示当前子树剩根节点
void build(int id, int root) {
    int cnt = 0;
    for(int i = head[id]; i != -1; i = ne[i]) {
        int v = edge[i];
        if(v == root) continue;
        build(v, id);
        if(dp[v] == -1) {
            dp[id] = -1;
            return;
        }
        if(dp[v] == 1) cnt++;
    }
    if(cnt == 0) dp[id] = 1;//子树全部合法，剩根节点
    if(cnt > 1) dp[id] = -1;//剩根节点的子树大于1，无解
    if(cnt == 1) dp[id] = 0;//剩根节点的子树等于1，合法解
}

///输出
void dfs(int id, int root, int x) {
    ans[id] = x;
    for(int i = head[id]; i != -1; i = ne[i]) {
        int v = edge[i];
        if(v == root) continue;
        if(dp[v] == 0) dfs(v, id, x ^ 1);
        else dfs(v, id, x);
    }
}
int main() {
    scanf("%d", &n);

    ///建树
    memset(head, -1, sizeof(head));
    for(int i = 0; i < n - 1; i++) {
        scanf("%d%d", &u, &v);
        addedge(i * 2, u, v);
        addedge(i * 2 + 1, v, u);
    }

    ///判断是否存在解
    build(1, -1);

    ///输出
    if(dp[1] == 0) {
        dfs(1, -1, 0);
        for(int i = 1; i <= n; i++) putchar(ans[i] ? 'B' : 'R');
        putchar(10);
    } else puts("-1");
    return 0;
}

D-点一成零

知识点：并查集

总方案数是 $n!* \prod(每个连通块的大小)$ ，其中 $n$ 是连通块的数量。
用并查集维护连通块的数量、大小和总方案数。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
int cnt;//集合个数
LL ans;//方案数
char s[507][507];
LL inv(LL a) {
    if(a < 1) return 1;
    if(a == 1) return 1;
    return inv(mod % a) * (mod - mod / a) % mod;
}

LL f[250577];
bool vis[507][507];//标记访问
int jishu[250577];//集合大小
int dx[4] = { -1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
bool check(int i, int j) {
    if(i < 1 || i > n) return false;
    if(j < 1 || j > n) return false;
    if(s[i][j] != '1') return false;
    if(vis[i][j]) return false;
    return true;
}
void dfs(int i, int j, int root) {
    if(!check(i, j)) return;
    jishu[root]++;
    vis[i][j] = true;
    f[i * 500 + j] = root;
    for(int k = 0; k < 4; k++) dfs(i + dx[k], j + dy[k], root);
}
void init() {
    cnt = 0, ans = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(s[i][j] == '1' && !vis[i][j]) {
                dfs(i, j, i * 500 + j);
                cnt++;
                ans = ans * cnt % mod;
                ans = ans * jishu[i * 500 + j] % mod;
            }
        }
    }
}
int findfa(int x) {
    if(f[x] == x) return x;
    return f[x] = findfa(f[x]);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);

    init();

    scanf("%d", &k);
    int x, y, root1, root2;
    while(k--) {
        scanf("%d%d", &x, &y);
        x++, y++;
        if(s[x][y] == '0') {
            s[x][y] = '1';
            root1 = x * 500 + y;
            f[root1] = root1;
            jishu[root1] = 1;
            for(int k = 0; k < 4; k++) {
                int i = x + dx[k], j = y + dy[k];
                if(s[i][j] == '1') {
                    root2 = findfa(i * 500 + j);
                    if(root1 == root2) continue;

                    ans = ans * inv(cnt--) % mod;
                    ans = ans * inv(jishu[root2]) % mod;

                    f[root2] = root1;
                    jishu[root1] += jishu[root2];
                }
            }
            cnt++;
            ans = ans * cnt % mod;
            ans = ans * jishu[root1] % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E-三棱锥之刻

知识点：计算几何

设正三棱锥棱长为 $a$ ，有关数学结论：

正三棱锥到 4 个顶点距离都相等的点为外接球的球心。
正三棱锥外接球半径为 $\frac{\sqrt{6}a}{4}$ 。
正三棱锥外接球球心到某一个面的距离为 $\frac{\sqrt{6}a}{12}$ 。
正三棱锥外接球球心投影到面上到边的距离为 $\frac{\sqrt{3}a}{6}$ 。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

double a, r;
double maxr, minr;
double solve() {
    if(r <= minr) return 0;//小于最小距离，全部都染不到
    if(r >= maxr) return sqrt(3) * a * a;//大于最大距离，全部都可染色

    //投影到面上是一个圆
    double R = sqrt(r * r - minr * minr);//与面相交圆的半径
    double area = pi * R * R;//圆的面积
    double d = sqrt(3) * a / 6;//圆心到边的距离
    if(R <= d) return 4 * area;//完整的圆

    double length = sqrt(R * R - d * d) * 2;//弦长
    double angle = 2 * acos(d / R);//角度
    double hu = angle * R;//弧长
    double shan = hu * R / 2;//扇形面积
    return 4 * (area - shan * 3 + length * d / 2 * 3);
}
int main() {
    cin >> a >> r;
    maxr = sqrt(6) * a / 4;//外接球半径
    minr = sqrt(6) * a / 12;//外接球球心到面的距离
    printf("%.6f\n", solve());
    return 0;
}

F-对答案一时爽

知识点：贪心

最大值：两个相同则都对，不同至少对一个。
最小值：一定可以使两个人都错，最小值恒为0。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
string s, t;
int ans;
int main() {
    cin >> n;
    getchar();
    getline(cin, s);
    getline(cin, t);
    n = s.length();
    for(int i = 0; i < n; i += 2) {
        if(s[i] == t[i]) ans += 2;
        else ans += 1;
    }
    printf("%d 0\n", ans);
    return 0;
}

G-好玩的数字游戏

知识点：模拟

存在0或者相邻的两个数相同，则游戏没有结束。
随机数不合法以及使用过之后都需要更新。
可以移动也算有效操作，并不一定需要合并。
仔细阅读合并规则，选择合适的策略。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

LL x;
int p, q;
int grade;
int a[7][7];
char s[MAXN];
void pra() {///调试输出用
    putchar(10);
    for(int i = 1; i <= 4; i++) {
        for(int j = 1; j <= 4; j++) {
            printf("%d ", a[i][j]);
        }
        putchar(10);
    }
}
bool checkIsDie() {///判断游戏是否结束
    for(int i = 1; i <= 4; i++) {
        for(int j = 1; j <= 4; j++) {
            ///任意相邻两个数相同或存在0，则没有结束
            if(a[i][j] == 0) return false;
            if(a[i][j] == a[i][j + 1]) return false;
            if(a[i][j] == a[i + 1][j]) return false;
        }
    }
    ///找不到相邻两数相同和0，游戏结束
    return true;
}
bool up(int j) { ///j列向上
    bool ret = false;
    ///先合并
    for(int i = 1; i <= 4; i++) {
        if(a[i][j] == 0) continue;
        for(int k = i + 1; k <= 4; k++) {
            if(a[k][j] == 0) continue;
            if(a[k][j] != a[i][j]) break;
            a[i][j] *= 2;
            a[k][j] = 0;
            grade += a[i][j];
            ret = true;
            break;
        }
    }
    ///再移动
    for(int i = 1; i <= 4; i++) {
        if(a[i][j] != 0) continue;
        for(int k = i + 1; k <= 4; k++) {
            if(a[k][j] == 0) continue;
            swap(a[i][j], a[k][j]);
            ret = true;
            break;
        }
    }

    return ret;
}
bool left(int i) { ///i行向左
    bool ret = false;
    ///先合并
    for(int j = 1; j <= 4; j++) {
        if(a[i][j] == 0) continue;
        for(int k = j + 1; k <= 4; k++) {
            if(a[i][k] == 0) continue;
            if(a[i][k] != a[i][j]) break;
            a[i][j] *= 2;
            a[i][k] = 0;
            grade += a[i][j];
            ret = true;
            break;
        }
    }
    ///再移动
    for(int j = 1; j <= 4; j++) {
        if(a[i][j] != 0) continue;
        for(int k = j + 1; k <= 4; k++) {
            if(a[i][k] == 0) continue;
            swap(a[i][j], a[i][k]);
            ret = true;
            break;
        }
    }

    return ret;
}
bool down(int j) { ///j列向下
    bool ret = false;
    ///先合并
    for(int i = 4; i >= 1; i--) {
        if(a[i][j] == 0) continue;
        for(int k = i - 1; k >= 1; k--) {
            if(a[k][j] == 0) continue;
            if(a[k][j] != a[i][j]) break;
            a[i][j] *= 2;
            a[k][j] = 0;
            grade += a[i][j];
            ret = true;
            break;
        }
    }
    ///再移动
    for(int i = 4; i >= 1; i--) {
        if(a[i][j] != 0) continue;
        for(int k = i - 1; k >= 1; k--) {
            if(a[k][j] == 0) continue;
            swap(a[i][j], a[k][j]);
            ret = true;
            break;
        }
    }

    return ret;
}
bool right(int i) { ///i行向右
    bool ret = false;
    ///先合并
    for(int j = 4; j >= 1; j--) {
        if(a[i][j] == 0) continue;
        for(int k = j - 1; k >= 1; k--) {
            if(a[i][k] == 0) continue;
            if(a[i][k] != a[i][j]) break;
            a[i][j] *= 2;
            a[i][k] = 0;
            grade += a[i][j];
            ret = true;
            break;
        }
    }
    ///再移动
    for(int j = 4; j >= 1; j--) {
        if(a[i][j] != 0) continue;
        for(int k = j - 1; k >= 1; k--) {
            if(a[i][k] == 0) continue;
            swap(a[i][j], a[i][k]);
            ret = true;
            break;
        }
    }

    return ret;
}
bool option(char ch, int i) {///选择是哪种操作
    if(ch == 'W') return up(i); ///i列向上
    if(ch == 'A') return left(i); ///i行向左
    if(ch == 'S') return down(i); ///i列向下
    if(ch == 'D') return right(i); ///i行向右
    return false;
}
long long f(long long x, int p) {///生成下一个随机数
    long long r = (x % p) * (x % p) / 10 % p;
    return (r ^ (1LL << 17) ^ (1LL << 57)) % p;
}
void change() {///合法操作后把一个0变为2
    while(true) {
        int tmp = x % 16;
        int i = tmp / 4 + 1, j = tmp % 4 + 1;
        if(a[i][j] == 0) {
            a[i][j] = 2;
            x = f(x, p);
            break;
        }
        x = f(x, p);
    }
}
void solve() {
    for(int i = 0; i < q; i++) {
        if(option(s[i * 2], s[i * 2 + 1] - '0')) {
            ///如果操作合法则生成随机数
            //pra();
            change();
        }
        if(checkIsDie()) {
            ///如果无法操作，结束
            printf("%d\n%d", grade, i + 1);
            return ;
        }
    }
    printf("%d\nnever die!\n", grade);
}
int main() {
    cin >> x >> p >> q;
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 4; j++)
            cin >> a[i][j];
    cin >> s;
    //pra();
    //cout << s << endl;
    solve();
    return 0;
}

H-幂塔个位数的计算

知识点：找规律、欧拉降幂

第一种：找规律

人找晕了，TAT。

第二种：欧拉降幂
$ $a^b \equiv\begin{cases} a^{b \; mod \; \phi(p)}, & gcd(a,p) = 1 \\ a^b, & gcd(a,p) \ne 1,b < \phi(p)\\ a^{b \; mod \; \phi(p)+\phi(p)}, & gcd(a,p) \ne 1,b \geq \phi(p)\end{cases}\;(mod \; p)$ $

以第三条公式为例： $99^{10000} \% 6 = 99^{10000 \% \phi(6) + \phi(6)} \% 6 = 99^{10000 \% 3 + 3} \% 6 = 99^4 \% 6 = 3$ ，其中 $\phi(p)$ 是欧拉函数。
在数论中，对正整数 $n$ ，欧拉函数是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。
定义表示的层幂塔，则有以下递推：
- $a(n) \% 10 = a^{a(n-1) \% \phi(10) + \phi(10)} \% 10 = a^{a(n-1) \% 4 + 4} \% 10$ 。
- $a(n-1) \% 4 = a^{a(n-2) \% \phi(4) + \phi(4)} \% 4 = a^{a(n-2) \% 2 + 2} \% 4$ 。
- $a(n-2) \% 2 = a^{a(n-3) \% \phi(2) + \phi(2)} \% 2 = a^{a(n-2) \% 1 + 1} \% 2$ 。
- $a(n-2) \% 1 + 1 = 1$ 。

注：下面的代码虽然AC了，但存在问题，例如 $11^b \% 10$ 应该使用第一个公式。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 4e6 + 117;
const int MAXM = 1e6 + 117;

string s, t;
int phi(int x) {
    if(x == 10) return 4;
    if(x == 4) return 2;
    if(x == 2) return 1;
    return -1;
}
int getnum(string s, int mod) {
    int ret = 0, len = s.length();
    for(int i = 0; i < len; i++) ret = (ret * 10 + s[i] - '0') % mod;
    return ret;
}
int mypow(string s, int n, int mod) {///s^n%mod
    int a = getnum(s, mod), ret = 1;
    while(n--) ret = ret * a % mod;
    return ret;
}
int solve(string s, int n, int mod) {///s的n层%mod+mod
    int a = getnum(s, mod);
    if(mod == 1) return 1;
    if(n == 1) return a % mod + mod;
    int mi = solve(s, n - 1, phi(mod));
    return mypow(s, mi, mod) + mod;
}
int main() {
    cin >> s >> t;
    if(s == "1" || t == "1") {
        cout << s[s.length() - 1] << endl;
    } else {
        int n;
        if(t.length() > 2) n = 100;
        else n = getnum(t, 100);
        int mi = solve(s, n - 1, phi(10));
        cout << mypow(s, mi, 10) << endl;
    }
    return 0;
}
/*
1056122113
932597604
3
*/

I-限制不互素对的排列

知识点：构造、数学

结论： $gcd(n,n+1)=1$ ，若 $n$ 是奇数有 $gcd(n,n+2)=1$ 。
当 $k<\frac{n}{2}$ 时，取前 $k+1$ 个偶数排在前面，剩下的数顺序排列。
当 $k= \frac{n}{2}$ 时，前面放偶数且6放在最后，然后接3和奇数，形如： $2 \quad 4 \quad 8\ldots \frac{n}{2} \quad 6 \quad 3 \quad 1 \quad 5 \ldots$

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
bool f[MAXN];
int main() {
    scanf("%d%d", &n, &k);
    int ou = n / 2;
    if(ou > k || (k == ou && n >= 6)) {
        for(int i = 2; i <= n; i += 2) {
            if(i / 2 > k + 1) break;//输出前k+1个偶数
            if(k == ou && i == 6) continue;//特判
            printf("%d ", i);
            f[i] = true;
        }
        if(k == ou) {//特判
            printf("6 3 ");
            f[6] = f[3] = true;
        }

        for(int i = 1; i <= n; i ++) {//顺序输出剩下的数
            if(!f[i]) printf("%d ", i);
        }
        putchar(10);
    } else puts("-1");
    return 0;
}

J-一群小青蛙呱蹦呱蹦呱

知识点：数论

剩下来的数一定有两种以上的质因子。
两个数 $p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n}$ 和 $p_1^{b_1} p_2^{b_2} \ldots p_n^{b_n}$ 的最小公倍数为 $p_1^{max(a_1,b_1)} p_2^{max(a_2,b_2)}\ldots p_n^{max(a_n,b_n)}$ 。
对每个质因子，求出满足条件的最高次幂。当 $p=2$ 时，满足 $3*2^k \leq n$ ；当 $p>2$ 时，满足 $2*p^k \leq n$ 。
至少有两个质因子， $p \leq \frac{n}{2}$ 。

参考荷塘涟漪的博客，担心精度丢失的也可以参考出题人的写法。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL ans;
int prime[80000000 + 117];
LL fast_pow(LL a, LL n) {
    LL ret = 1, temp = a % mod;
    while(n) {
        if(n & 1) ret = ret * temp % mod;
        temp = temp * temp % mod;
        n >>= 1;
    }
    return ret;
}
void solve(int x) {
    if(x == 2) ans = ans * fast_pow(2, floor(log(n / 3) / log(2))) % mod;
    else ans = ans * fast_pow(x, floor(log(n / 2) / log(x))) % mod;
}
int main() {
    scanf("%d", &n);
    ans = 1;
    for(int i = 2; i <= n / 2; i++) {
        if(!prime[i]) {
            solve(i);
            prime[++prime[0]] = i;
        }
        for(int j = 1; j <= prime[0] && prime[j] <= n / 2 / i; j++) {
            prime[prime[j]*i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    if(ans == 1) puts("empty");
    else printf("%lld\n", ans);
    return 0;
}