Contestant. Rank 1837. Rating +17.

开局天崩场

A. Typical Interview Problem

题意

对于一个数字，如果它是 \(3\) 的倍数，那么它映射到字符串 \(F\)，如果它是 \(5\) 的倍数，那么映射到 \(B\)，如果是 \(15\) 的倍数，那么映射到 \(FB\)，否则映射到空字符串。给定一个字符串，输出它是否是一段连续区间内对应数字映射后拼接而成的。

思路

显然，\(15\) 一循环，且给定的字符串长度只有 \(10\)，所以我们只需暴力匹配即可。

有趣的是，\(FB\) 拆开不影响答案。

时间复杂度：\(O(n)\)

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0) {
            int n = console.nextInt();
            String s = "FBFFFBFFBFFBFBFFBFFBBFFBFBFFBFFB";
            String x = console.next();
            console.print(s.contains(x) ? "YES\n" : "NO\n");
        }
        console.close();
    }

    //快读模板 此处略去
    //public static class Console implements Closeable {}
}

s开小了，倒大霉了属于是

B. Asterisk-Minor Template

题意

给定两个字符串，构造出一个模板，模板由 '*' 和字母组成，通配符 '*' 可以匹配自然数个任意字母。输出是否存在一种模板，使通配符的数量小于等于字母的数量。若存在，输出这个模板。

思路

要满足题给条件，那么模板一定需要存在两个连续的字母。考虑到可以任意匹配，我们不妨只找出一对字母，在两个字符串中均出现，如 \(ab\) 在 \(aabc, xxxabz\) 中均出现，那么就可以在两边加上通配符，如构建为 *\(ab\)*。

当然，只要开头或结尾一样，一个字母加上一个通配符即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        string a, b;
        cin >> a >> b;
        if(a[0] == b[0]) cout << "YES\n" << a[0] << '*' << '\n';
        else if(a[a.size() - 1] == b[b.size() - 1]) cout << "YES\n" << '*' << a[a.size() - 1] << '\n';
        else{
            bool f = false;
            for(int i=0;i<a.size() - 1;i++){
                for(int j=0;j<b.size() - 1;j++){
                    if(a[i] == b[j] && a[i + 1] == b[j  + 1]){
                        cout << "YES\n" << '*' << a[i] << a[i + 1] << '*' << '\n';
                        f = true;
                        break;
                    }
                }
                if(f) break;
            }
            if(!f) cout << "NO\n";
        }
    }
}

贪心一下~

C. Maximum Set

题意

给定两个整数 \(l, r\)，在 \([l, r]\) 内找一个递增不重复序列，满足相邻数可整除。输出序列的最大数量，以及该数量的方案数。方案数 \(\mod 998244353\)。

思路

首先，要让数量最多，且能整除，那么我们不妨将左端点循环乘二，得到一个不超过右端点的最大数，此时乘二的数量就是序列的最大数量 \(- 1\)。

更简洁地看，我们将上述过程转化为一个表达式：\(l \times 2 \times 2 \times \ldots \times 2 = x\leq r\)。

那么，显然 \(\frac{r}{x}\) 是小于 \(2\) 的，所以若要让某个倍数变大，即选择一个 \(2\) 将其变大，那么我们只能将其改成 \(3\)。

那么，整道题就可以变为遍历所有满足上述表达式的 \(l\)，判断 \(\frac{r}{x}\) 和 \(1.5\) 的大小关系，若前者大，那么对于这个左边界，我们可以得到 \(cnt_2\) 个方案，否则只有一个方案。

上述思路的复杂度较高，考虑到推算较为简单，我们不妨直接推导式子：

设 \(\frac{x}{l} = p\)，那么 \(l'p \leq r\) 即 \(l \leq l' \leq \frac{r}{p}\)。

同理，\(l \leq l'' \leq \frac{2r}{3p}\)

那么，答案即为 \((l'' - l + 1) \times cnt + (l' - l'')\)

当然，我们也可以二分，问题不大（（

时间复杂度：一般般

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception{
        Console console = new Console();
        long mod = 998244353;
        long t = console.nextInt();
        nxt:
        while(t -- > 0) {
            long n = console.nextInt(), m = console.nextInt();
            long x = n, ans1 = 1, p = 1;
            while(true){
                if(x * 2 > m) break;
                x *= 2;
                ans1 ++;
                p = (p * 2) % mod;
            }
            boolean ok = false;
            long l1 = (long) Math.max(n - 1, (double) m * 2 / 3 / p), l2 = Math.max(l1 - 1, m / p);
            long ans2 = (((l1 - n + 1) * ans1 % mod) + (l2 - l1) % mod) % mod;
            console.print(ans1 + " " + ans2 + "\n");
        }
        console.close();
    }

    //快读模板 此处略去
    //public static class Console implements Closeable {}
}

暴力枚举左端点的铸币竟是我自己