牛客小白月赛 41 民间题解

A 小红的签到题

要让最多的人 AK，也就是每一道题都尽可能能多使一个人 AK。

所以一共 $cc$ 道题，每个人拿走 $aa$ 道题，最多就是 $\lfloor {\displaystyle \frac{c}{a}}\rfloor \backslash left\backslash lfloor\backslash dfrac\{c\}\{a\}\backslash right\backslash rfloor$ 个人 AK。

$bb$ 是用来检测数据合法性的，应满足 $a\times b\ge ca\backslash times\; b\backslash ge\; c$，原因显然。

B 小红的ABC

对于一个回文子串 $strstr$，若其长度 $\ge 4\backslash ge4$，则去掉首尾两个字符也一定是一个回文子串。

因此满足题目要求的回文子串长度非 $22$ 即 $33$，直接分类讨论，并枚举子串的起点判断一下就好。

时间复杂度 $O(n^2)O(n^2)$，结合哈希等算法可以做到 $O(n)O(n)$。

C 小红的口罩

一共 $nn$ 个口罩，每次选择最舒服的一个使用，使用完之后它的 $a_{i}a\_i$ 会翻倍。

这非常明显是类似于合并果子的优先队列，直接使用 Standard Template Library 中的 std::priority_queue 即可单次操作 $O(\log )O(\backslash log)$ 地插入、查询最值。

这个复杂度实际上是 $O(n\cdot \log n\cdot \log \text{值域})O(n\; \backslash cdot\backslash log\; n\backslash cdot\backslash log\backslash text\{值域\})$ 的，直接考虑构造 $a_i=1,k=10^{9}a\_i=1,k=10^9$ 就能卡到这个级别（每个 $a_{i}a\_i$ 共计进出优先队列 $\log \backslash log$ 次，每次 $O(\log )O(\backslash log)$ 复杂度）

另一种合理的严格 1log 高论：考虑二分答案 $ss$，表示不舒适度 $\le s\backslash le\; s$ 时的一个口罩我都会继续使用。

最后找到一个最优的阈值 $ss$，满足 $s+1s+1$ 的不舒适度就超过 $kk$。

最后统计答案并输出即可。

D 小红的375

首先根据 $a\cdot b\mathrm{\mid }c\iff a\mathrm{\mid }c\text{ and }b\mathrm{\mid }c(\gcd (a,b)=1)a\backslash cdot\; b|c\backslash Leftrightarrow\; a|c~\backslash text\{and\}~b|c(\backslash gcd(a,\; b)=1)$ 的性质可知：

能被 $375375$ 整除 $\iff \backslash Leftrightarrow$ 能被 $33$ 整除且能被 $125125$ 整除。

前者直接根据一个众所周知的结论：各位数字之和是 $33$ 的倍数判断一下。

后者的话，就考虑类似能被 $55$ 整除的判定手段，首先一个数字由于 $\mathrm{m}\mathrm{o}\mathrm{d}1000\backslash bmod1000$ 和自己后三位同余，也就是只用考虑后三位。

而这里我们只需要枚举后三位能不能是 $125,250,375,\cdots ,875,000125,250,375,\backslash cdots,875,000$ 即可（前 $88$ 个 $125125$ 的倍数）

为了方便检验，还可以写一个 work(a, b, c) 函数检验输入的正整数是否包含了 $aa$、$bb$、$cc$ 三个数位。

剩下的细节不多言了，详情可以参见代码。

E 小红的数组

读完题第一反应是给 $aa$ 数组排序并二分查找，复杂度 $O(n\log n)O(n\backslash log\; n)$。

实际上还可以设计一种双指针扫描的算法，除去排序的复杂度之外是严格 $O(n)O(n)$ 的。

设 $ll$ 表示第一个和 $a_{i}a\_i$ 相乘小于 k 的数字，$rr$ 表示最后的和 $a_{i}a\_i$ 相乘大于 k 的数字。

容易观察到随着 $a_{i}a\_i$ 增加，$l,rl,r$ 的值都是单调递减的，而最后查询贡献只需要建立一个 calc 函数：

calc(L, R, I) 表示到了 $II$ 位置之后区间 $[L,R][L,\; R]$ 的答案，这里我们需要去掉 $II$ 及其之前的答案，也就是：

int calc(int L, int R, int I){
    L = mx(L, I + 1);
    return mx(0, mn(n, R - L + 1));
}

剩下的都是双指针的常见套路了。

F 小红的rpg游戏

听说标算是指数级爆搜然后找联通快，这里给一个常见套路做法。

就是考虑给迷宫建立四联通的有向图，然后把怪物造成的血量值减少等效成第三维。

设 $\text{dis}(i,j,k)\backslash text\{dis\}(i,\; j,\; k)$ 表示到达地图的点 $(i,j)(i,\; j)$，剩余血量 $kk$ 的路径长度最小值。

这样直接 Dijkstra 转移（松弛）即可。

本质上也可以理解成一个 dp 的过程，怎么理解都行。

std

// A
#include<cstdio>
#include<cassert>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int mn(int x, int y){
    return x < y ? x : y;
}
int main(){
    int a = init(), b = init(), c = init();
    assert(5 <= a && a <= 10);
    assert(1 <= b && b <= 1000);
    assert(1 <= c && c <= 1000);
    assert(b * a >= c);
    /* 一共 b 个人至多写 b * a 道题 */
    print(c / a), putchar('\n');
}
// B
#include<cstdio>
#include<cstring>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e2 + 5;
char s[N];
bool check(int i, int j){
    for (; i <= j; ++i, --j)
        if (s[i] != s[j]) return 0;
    return 1;
}
int main(){
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            if (check(i, j)) {
                print(len); return 0;
            }
        }
    }
    print(-1), putchar('\n');
}
// C
#include<queue>
#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
std::priority_queue<int, std::vector<int>, std::greater<int> >Q;
signed main(){
    int n = init(), k = init();
    for (int i = 1; i <= n; ++i)
        Q.push(init());
    int limit = 0, times = 0;
    while (1) {
        int top = Q.top(); Q.pop();
        if (limit + top > k) {
            print(times), putchar('\n');
            return 0;
        }
        ++times;
        limit += top;
        Q.push(top << 1);
    }
}
// D
#include<cstdio>
#include<cstring>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 3e5 + 5;
char s[N]; int TOT[10], tot[10];
bool work(int a, int b, int c){
    if (tot[a] >= 1 && tot[b] >= 1 && tot[c] >= 1) {
        --tot[a], --tot[b], --tot[c];
        int sum = 0;
        for (int i = 9; i >= 0; --i) {
            sum += tot[i];
            while (tot[i]--) print(i);
        }
        if (!sum) {
            if (a == 3 && b == 7 && c == 5) {
                print(375); return 1;
            }
            if (a == 7 && b == 5 && c == 0) {
                print(750); return 1;
            }
            return 0;
        }
        print(a), print(b), print(c), putchar('\n');
        return 1;
    }
    return 0;
}
void Relax(){
    for (int i = 0; i < 10; ++i)
        tot[i] = TOT[i];
}
int main(){
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int sum = 0;
    for (int i = 1; i <= len; ++i) {
        ++TOT[s[i] - '0'];
        sum += s[i] - '0';
    }
    if (sum % 3) { print(-1); return 0; }
    Relax();
    if (work(1, 2, 5)) return 0;
    Relax();
    if (work(2, 5, 0)) return 0;
    Relax();
    if (work(3, 7, 5)) return 0;
    Relax();
    if (work(6, 2, 5)) return 0;
    Relax();
    if (work(7, 5, 0)) return 0;
    Relax();
    if (work(8, 7, 5)) return 0;
    Relax();
    if (tot[0] >= 2 && tot[5] >= 1) {
        --tot[0], --tot[0], --tot[5];
        int sum = 0;
        for (int i = 9; i >= 0; --i) {
            sum += tot[i];
            while (tot[i]--) print(i);
        }
        if (!sum) return 0;
        print(500); return 0;
    }
    Relax();
    if (tot[0] >= 3) {
        --tot[0], --tot[0], --tot[0];
        int sum = 0;
        for (int i = 9; i >= 0; --i) {
            sum += tot[i];
            while (tot[i]--) print(i);
        }
        if (!sum) return 0;
        int AAA = 3;
        while (AAA--) print(0);
        return 0;
    }
    print(-1), putchar('\n');
}
// E
#include<cstdio>
#include<algorithm>
#define int __int128
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 3e5 + 5;
int n, k, a[N];
int mx(int x, int y){
    return x > y ? x : y;
}
int mn(int x, int y){
    return x < y ? x : y;
}
int calc(int L, int R, int I){
    L = mx(L, I + 1);
    return mx(0, mn(n, R - L + 1));
}
signed main(){
    n = init(), k = init();
    for (int i = 1; i <= n; ++i)
        a[i] = init();
    std::stable_sort(a + 1, a + 1 + n);
    a[0] = 0, a[n + 1] = k;
    int l = n + 1, r = n + 1;
    // l : 第一个和 a[i] 相乘小于 k 的数字
    // r : 最后的和 a[i] 相乘大于 k 的数字
    int s1 = 0, s2 = 0, s3 = 0;
    for (int i = 1; i < n; ++i) {
        while (a[r - 1] * a[i] > k) --r;
        while (a[l] * a[i] >= k) --l;
        s1 += calc(r, n, i);
        s2 += calc(l + 1, r - 1, i);
        s3 += calc(1, l, i);
    }
    // O(n) : 考虑到取数的单调性，直接双指针去扫就行
    print(s1), putchar(' '), print(s2), putchar(' '), print(s3), putchar('\n');
}
// F
#include<map>
#include<queue>
#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 5e1 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
char s[N][N];
struct Node{
    int x, y, z;
    friend bool operator<(const Node&p, const Node&q){
        if (p.x != q.x) return p.x < q.x;
        if (p.y != q.y) return p.y < q.y;
        return p.z < q.z;
    }
};
std::map<Node, int>dis;
std::queue<Node>queue;
int main(){
    int n = init(), m = init(), h = init();
    dis[(Node){1, 1, h}] = 0;
    for (int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    queue.push((Node){1, 1, h});
    while (!queue.empty()) {
        Node u = queue.front(); queue.pop();
        int x = u.x, y = u.y, z = u.z;
        if (x == n && y == m) {
            print(dis[u]);
            return 0;
        }
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            int nz = z;
            if (s[nx][ny] >= '1' && s[nx][ny] <= '9')
                nz -= s[nx][ny] - '0';
            if (s[nx][ny] == '*')
                nz -= 9999999;
            if (nz <= 0) continue;
            Node v = (Node) {nx, ny, nz};
            if (!dis.count(v)) {
                dis[v] = dis[u] + 1;
                queue.push(v);
            }
        }
    }
    print(-1);
}