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 {}
}

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