2021-02-02 18:22 已编辑浙江大学 C++

关注

2021 牛客寒假多校1 神崎兰子构造思维

串

DP。雨神的博客讲得很清楚。
我也做了一点注释。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
ll dp[N][3];
int n;
int main() {
    cin >> n;
    dp[1][0] = 25;
    // dp[i][0]表示长度i无u的串数量
    dp[1][1] = 1;
    // dp[i][1]表示长度i有u无us的串数量
    dp[1][2] = 0;
    // dp[i][2]表示长度i有us的串
    ll ans = 0;
    rep(i, 2, n) {
        dp[i][0] = (dp[i - 1][0] * 25) % mod;
        //在前串尾缀除u以外的字符即可
        dp[i][1] = (dp[i - 1][1] * 25 + dp[i - 1][0]) % mod;
        //有u串尾缀非s + 无u串尾缀u
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 26) % mod;
        //无s串尾缀s + 符合串尾缀任意字符
        ans = (ans + dp[i][2]) % mod;
    }
    cout << ans;
    return 0;
}

括号

构造长度小于 ${10^5}$ 的有k个合法括号对的括号字符串。

首先考虑形如这样的括号字符串
```
(((()))))
```
它有n个左括号，m个右括号，当给定的k很大的时候，如果能将括号字符串表示成这种形式是最短的：由均值不等式，当n和m尽可能接近的时候，字符串会最短
k最大可达 ${10^9}$ ， ${\sqrt{k}}$ 可满足长度需求
考虑k为一个大质数，无法满足成两个数的乘积形式，如何解决？观察括号字符串，当在从左往右数第i个左括号后添加一个右括号，可以使得括号字符串的合法括号对增加i个。
```
(()(()))))
```
增加两个合法括号对。
综上，可以考虑转化成这样式子 ${k=n*m+i}$ ，且为了使得n*m尽可能接近，可令 ${n=\sqrt{k}}$

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5;
const int mod = 1e9 + 7;
int main() {
    ll n;
    sc(n);
    if (n == 0) return puts(")("), 0;
    ll m = sqrt(n);
    ll r = n / m, d = n % m;
    rep(i, 1, m) {
        putchar('(');
        if (i == d) putchar(')');
    }
    rep(i, 1, r) putchar(')');
    return 0;
}

红与蓝

叶子节点之与父亲有边相连，所以叶子节点必然与父亲同色。
而父亲节点已经和叶子节点同色，所以叶子节点必然与爷爷节点异色。
爷爷的颜色确定后，如果爷爷还与一条边相连，那么标记爷爷的相邻点颜色也确定。
所以统计位置信息然后再跑一边DFS染色即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
ll read() {
    ll a = 0;
    char b = 1, c;
    do
        if ((c = getchar()) == 45) b = -1;
    while (c < 48 || c > 57);
    do
        a = (a << 3) + (a << 1) + (c & 15);
    while ((c = getchar()) > 47 && c < 58);
    return a * b;
}
int head[N], nex[N << 1], to[N << 1];
int cnt;
int fri[N];
bitset<N> b;
void add(int u, int v) {
    nex[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}
void dfs1(int x, int f) {
    for (int i = head[x]; i; i = nex[i]) {
        int t = to[i];
        if (t == f) continue;
        dfs1(t, x);
        if (!fri[x] && !fri[t]) {
            fri[x] = t;
            fri[t] = x;
        }
    }
}
void dfs2(int x, int f) {
    for (int i = head[x]; i; i = nex[i]) {
        int t = to[i];
        if (t == f) continue;
        b[t] = t == fri[x] ? b[x] : !b[x];
        dfs2(t, x);
    }
}
int main() {
    int n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    if (!*min_element(fri + 1, fri + 1 + n)) {
        puts("-1");
        return 0;
    }
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i) putchar(b[i] ? 'R' : 'B');
}

点零成一

本题其实是一个比较简单的并查集，但是本菜鸡太久没写了以至于debug了很久。

数据量很小于是可以暴力合并，新加进来的数也可以实时合并或增加集合。

答案其实就是每个集合里面的点数累乘，最后乘一个集合数量的全排列即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define pos(x, y) ((x - 1) * n + (y))
#define out(x, y) ((x) < 1 || (x) > n || (y) < 1 || (y) > n)
using namespace std;
typedef long long ll;
const int N = 500 + 7;
const int mod = 1e9 + 7;
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); }  //求一个数的逆元
int sz[N * N];
int fa[N * N];
inline void init(int n) {
    for (int i = 0; i <= n; ++i) fa[i] = i, sz[i] = 1;
}
inline int Find(int x) {
    if (x != fa[x]) fa[x] = Find(fa[x]);  //路径压缩
    return fa[x];
}
void merge(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if (fx != fy) fa[fx] = y, sz[fy] += sz[fx];
}
int n;
char g[N][N];
bool vis[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void dfs(int x, int y, int fa) {
    if (out(x, y)) return;
    vis[x][y] = 1;
    if (pos(x, y) != fa) merge(pos(x, y), fa);
    rep(i, 0, 3) {
        if (g[x + dx[i]][y + dy[i]] == '1' && !vis[x + dx[i]][y + dy[i]])
            dfs(x + dx[i], y + dy[i], fa);
    }
}
ll ans = 1;
ll cnt = 0;  //集合数量
void chk(int x, int y) {
    if (g[x][y] == '1') return;
    g[x][y] = '1';
    ++cnt;
    ans = ans * cnt % mod;
    int now = pos(x, y);
    rep(i, 0, 3) {
        if (!out(x + dx[i], y + dy[i]) && g[x + dx[i]][y + dy[i]] == '1') {
            int nxt = pos(x + dx[i], y + dy[i]);
            int f1 = Find(now);
            int f2 = Find(nxt);
            if (f1 != f2) {
                ans = ans * getInv(cnt) % mod;
                ans = ans * getInv(sz[f1]) % mod;
                ans = ans * getInv(sz[f2]) % mod;
                ans = ans * (sz[f1] + sz[f2]) % mod;
                --cnt;
                merge(f1, f2);
            }
        }
    }
}
int main() {
    sc(n);
    init(n * n);
    rep(i, 1, n) scanf(" %s", g[i] + 1);
    rep(i, 1, n) rep(j, 1, n) {
        if (g[i][j] == '1') {
            int now = pos(i, j);
            rep(z, 0, 3) {
                int nxt = pos(i + dx[z], j + dy[z]);
                if (!out(i + dx[z], j + dy[z]) &&
                    g[i + dx[z]][j + dy[z]] == '1')
                    merge(now, nxt);
            }
        }
    }
    rep(i, 1, n) rep(j, 1, n) {
        int now = pos(i, j);
        if (g[i][j] == '1' && Find(now) == now)
            ++cnt, ans = (ans * sz[now]) % mod;
    }
    rep(i, 1, cnt) ans = ans * i % mod;
    int t, u, v;
    sc(t);
    while (t--) {
        sc(u), sc(v);
        chk(++u, ++v);
        pr(ans);
    }
    return 0;
}

三棱锥之刻

根据发射距离R的不同，可分为四种情况

碰不到
四个圆
圆和三角的交*4
正四面体的全部内表面

图片说明

具体来说就是计算小三角形的面积，再加上一个最小的扇形面积。

重合部分的面积等于 ${S\triangle DGK *3 +\frac{1}{2}S_{扇HDG}*r*6}$

from math import sqrt, acos, pi
a, R = map(float, input().split())
d = sqrt(6) * a / 12  #中心到面的距离
r = sqrt(R * R - d * d) if d < R else 0  #三角形上的圆的半径
if R <= d: ans = 0  #碰不到
elif r <= a / (sqrt(3) * 2):  #四个圆
    ans = 4 * pi * (R * R - d * d)
elif R >= a * sqrt(6) / 4:  #全覆盖
    ans = a * a * sqrt(3)
else:  #切掉
    DF = a / (2 * sqrt(3))
    GF = sqrt(r * r - DF * DF)  #求底面三角形 半底长
    deg = pi / 3 - acos(DF / r)  # 小扇形的弧度
    ans = GF * DF * 3
    shan = deg * 0.5 * r * r
    ans += 6 * shan
    ans *= 4  #就漏了这一句
print(ans)

对答案一时爽

两人成绩最大值：保证每题至少有一人做对
最小值：保证没有一人做对，因为两个人无法覆盖四个选项，直接就是0

n = int(input())
a = input()
b = input()
a = a.replace(' ', '')
b = b.replace(' ', '')
cnt = 0
for i in range(n):
    if a[i] == b[i]: cnt += 1
print(cnt + n, 0)

好玩的数字游戏

本题是一个大模拟，但是比赛的时候把时间分配给大模拟其实是一件很有风险的事情，尤其是在很有机会的题目还没有解决的时候。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
//refer : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46663438
ll x0, p, q, s = 0, ed = -1;
ll a[6][6];
char seq[N << 1];

inline ll f(const ll &x, const ll &p) {
    ll r = (x % p) * (x % p) / 10 % p;
    return (r ^ (1LL << 17) ^ (1LL << 57)) % p;
}

inline int mergeCol(const int &x, const int &d) {
    int res = 0;
    if (d > 0) {
        for (int i = 4, j; i >= 2; --i) {
            if (a[i][x]) {
                for (j = i - 1; j >= 1 && a[j][x] == 0; --j) ;
                if (a[j][x] == a[i][x]) {
                    a[i][x] <<= 1, a[j][x] = 0;
                    s += a[i][x], res = 1;
                }
            }
        }
        for (int i = 4, j; i >= 2; --i) {
            if (!a[i][x]) {
                for (j = i - 1; j >= 1 && a[j][x] == 0; --j) ;
                if (a[j][x]) a[i][x] = a[j][x], a[j][x] = 0, res = 1;
            }
        }
    } else {
        for (int i = 1, j; i <= 3; ++i) {
            if (a[i][x]) {
                for (j = i + 1; j <= 4 && a[j][x] == 0; ++j) ;
                if (a[j][x] == a[i][x]) {
                    a[i][x] <<= 1, a[j][x] = 0;
                    s += a[i][x], res = 1;
                }
            }
        }
        for (int i = 1, j; i <= 3; ++i) {
            if (!a[i][x]) {
                for (j = i + 1; j <= 4 && a[j][x] == 0; ++j) ;
                if (a[j][x]) a[i][x] = a[j][x], a[j][x] = 0, res = 1;
            }
        }
    }
    return res;
}

inline int mergeRow(const int &x, const int &d) {
    int res = 0;
    if (d > 0) {
        for (int i = 4, j; i >= 2; --i) {
            if (a[x][i]) {
                for (j = i - 1; j >= 1 && a[x][j] == 0; --j) ;
                if (a[x][j] == a[x][i]) {
                    a[x][i] <<= 1, a[x][j] = 0;
                    s += a[x][i], res = 1;
                }
            }
        }
        for (int i = 4, j; i >= 2; --i) {
            if (!a[x][i]) {
                for (j = i - 1; j >= 1 && a[x][j] == 0; --j) ;
                if (a[x][j]) a[x][i] = a[x][j], a[x][j] = 0, res = 1;
            }
        }
    } else {
        for (int i = 1, j; i <= 3; ++i) {
            if (a[x][i]) {
                for (j = i + 1; j <= 4 && a[x][j] == 0; ++j) ;
                if (a[x][j] == a[x][i]) {
                    a[x][i] <<= 1, a[x][j] = 0;
                    s += a[x][i], res = 1;
                }
            }
        }
        for (int i = 1, j; i <= 3; ++i) {
            if (!a[x][i]) {
                for (j = i + 1; j <= 4 && a[x][j] == 0; ++j) ;
                if (a[x][j]) a[x][i] = a[x][j], a[x][j] = 0, res = 1;
            }
        }
    }
    return res;
}

inline int move() {
    for (int i = 1, j; i <= 4; ++i)
        for (j = 1; j <= 4; ++j) {
            if (!a[i][j]) return 1;
            if (a[i][j] == a[i - 1][j]) return 1;
            if (a[i][j] == a[i][j - 1]) return 1;
        }
    return 0;
}

inline void update() {
    while (1) {
        int tmp = x0 % 16;
        x0 = f(x0, p);
        if (!a[tmp / 4 + 1][tmp % 4 + 1]) {
            a[tmp / 4 + 1][tmp % 4 + 1] = 2;
            break;
        }
    }
}

int main() {
    scanf("%lld%lld%lld", &x0, &p, &q);
    for (int i = 1, j; i <= 4; ++i)
        for (j = 1; j <= 4; ++j) scanf("%lld", &a[i][j]);
    scanf("%s", seq + 1);
    for (int i = 1, d, x; i <= q; ++i) {
        x = seq[2 * i] - '0';
        if (seq[2 * i - 1] == 'W' || seq[2 * i - 1] == 'S') {
            d = seq[2 * i - 1] == 'W' ? -1 : 1;
            if (mergeCol(x, d)) update();
        } else {
            d = seq[2 * i - 1] == 'A' ? -1 : 1;
            if (mergeRow(x, d)) update();
        }
        if (!move()) {
            ed = i;
            break;
        }
    }
    printf("%lld\n", s);
    if (ed == -1)
        puts("never die!");
    else
        printf("%lld\n", ed);
    return 0;
}

幂塔个位数的计算

本题可以找规律，但这里采用欧拉降幂的做法：

欧拉降幂的前置知识是欧拉函数

简单来说欧拉降幂其实就是一个公式

$\equiv$ 表示同余， $\phi(p)$ 表示p的欧拉函数

${a^b\equiv \left\{ \begin{aligned} a^{b\%\phi (p)}& &\dots & gcd(a,b)=1\\ a^b & &\dots & gcd(a,b)\ne 1,b<\phi (p)\\ a^{b\%\phi (p)+\phi (p)} & &\dots & gcd(a,b)\ne 1,b\geq \phi (p) \end{aligned} \right .}$

直接套公式就可以写了，Python的int是会处理大数的。

def phi(x):
    if x == 10:
        return 4
    if x == 4:
        return 2
    if x == 2:
        return 1
    if x == 1:
        return 1


def cal(a, n, mod):
    if (mod == 1):
        return 1
    if n == 1:
        return a % mod + mod
    return pow(a, cal(a, n - 1, phi(mod)), mod) + mod

a = int(input())
n = int(input())
if (n == 1):
    print(a % 10)
else:
    print(pow(a, cal(a, n - 1, phi(10)), 10))

下面这种做法则是直接找出循环节

a = int(input())
n = int(input())
if (n == 1): print(a % 10)  # n==1 直接输出个位数
elif (n == 2): print(pow(a % 10, a, 10))  # n==2 直接快速幂算
else:
    e = pow(a % 4, a % 2 + 2, 4)
    print(pow(a % 10, e + 4, 10))

限制不互素对的排列

由于保证了 ${k\leq \frac{n}{2}}$ ，于是当 ${k\leq \frac{n}{2}-1}$ 时，选择全部的偶数对顺序排列即可得到答案。而当{k= \frac{n}{2}}$时只需要将6和3放在一起即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d ", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
bool vis[N];
int ans[N], p = 1;
int main() {
    int n, k;
    sc(n), sc(k);
    ans[p++] = 2, vis[2] = 1;
    int cnt = 0;
    rep(i, 1, k) {
        int now = 2 * (i + 1);
        if (now > n) break;
        ans[p++] = now;
        vis[now] = 1;
        ++cnt;
    }
    if (n >= 6 and cnt < k)
        swap(ans[3], ans[p - 1]), ans[p++] = 3, vis[3] = 1, ++cnt;
    if (cnt < k)
        puts("-1");
    else {
        rep(i, 1, p - 1) pr(ans[i]);
        rep(i, 1, n) if (!vis[i]) pr(i);
    }
    return 0;
}

一群小青蛙呱蹦呱蹦呱

题意是求 $[1,n]$ 以内的所有非单因子数的最小公倍数。
仔细思考可以想到2贡献了 $\log_2 \lfloor \frac{n}{3} \rfloor$ 次，因为有它因子的，包括它的尽可能高的次幂的数就是 $\lfloor \frac{n}{3} \rfloor$ 了。
同理其他非2的质数x贡献了 $\log_x \lfloor \frac{n}{2} \rfloor$ 次。

看来还是我的埃筛常数优秀。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
const int N = 8e7 + 7;
const int mod = 1e9 + 7;
bool notprime[N];
int primes[N], pcnt = 0;
inline void pre() {
    notprime[1] = 1;
    for (int i = 2, n = sqrt(N) + 1; i <= n; ++i) {
        if (!notprime[i]) {
            for (int j = N / i; j >= i; --j) {
                if (!notprime[j]) notprime[i * j] = 1;
            }
        }
    }
    primes[++pcnt] = 2;
    for (int i = 3; i < N; ++i)
        if (!notprime[i]) primes[++pcnt] = i;
}
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); }  //求一个数的逆元
inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}
int main() {
    pre();
    ll n = read();
    ll tm = log2(n / 3);
    ll ans = qkpow(2, tm);
    for (int i = 2; i <= pcnt; ++i) {
        if (2 * primes[i] <= n) {
            tm = log(n / 2) / log(primes[i]);
            ans = (ans * qkpow(primes[i], tm)) % mod;
        } else
            break;
    }
    if (ans == 1)
        puts("empty");
    else
        pr(ans);
    return 0;
}