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

Author：我不会玩锐雯
发布时间：February 4, 2021
2355views
No comments
25957字数
Categories： ACM技能点

比赛地址：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)$表示$a$的$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;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/160/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：February 4th, 2021 at 09:36 pm

如果觉得我的文章对你有用，请随意赞赏

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

我不会玩锐雯 • 2021 年 02 月 04 日

比赛地址：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;
}

第三种：线性递推方程

注：上面的$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)$表示$a$的$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;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/160/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

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

A-串

B-括号

C-红和蓝

D-点一成零

E-三棱锥之刻

F-对答案一时爽

G-好玩的数字游戏

H-幂塔个位数的计算

I-限制不互素对的排列

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

Leave a Comment Cancel reply

【每日一题】4月7日树

handsome主题修改记录

链式前向星

红黑树入门

【每日一题】4月6日数码

计蒜客 2020 蓝桥杯大学 B 组省赛模拟赛（一）

建造者模式

【每日一题】4月3日 Shortest Path

简单工厂模式

Codeforces Round #764 (Div. 3)

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

A-串

B-括号

C-红和蓝

D-点一成零

E-三棱锥之刻

F-对答案一时爽

G-好玩的数字游戏

H-幂塔个位数的计算

I-限制不互素对的排列

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