Codeforces Round 957 (Div. 3)

题目链接：Codeforces Round 957 (Div. 3)

总结：E不懂，F差一个set去重

A. Only Pluses

fag：枚举

B. Angry Monk

fag：模拟

Solution：分裂的花费为\(a_i - 1\)，添加的花费为\(a_i\)。

C. Gorilla and Permutation

fag：思维

Solution：大于等于\(k\)的数，逆序放在最前面，小于等于\(m\)的数，从最后面开始从大到小放，中间的位置任意放剩下的数。

void solve(){
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    int i, l, r;
    
    for (i = n, l = 1; i >= k; i --, l ++)
        a[l] = i;
    
    for (i = m, r = n; i >= 1; i --, r --)
        a[r] = i;
    
    for (int i = l; i <= r; i ++){
        a[i] = ++ m;
    }
    
    for (int i = 1; i <= n; i ++)
        cout << a[i] << " \n"[i == n];
}

D. Test of Love

fag：DP

Solution：考虑如何从上一步转移，跳过来或者游过来。

• 注意\(m\)的范围，可以直接枚举前\(m\)个格子（赛时没看到范围，用单调队列优化DP做的）
• 游过来的前提，上一格是水。

void solve(){
    cin >> n >> m >> k;
    string s;
    cin >> s;
    s = "$" + s;
    deque<int> qu;
    vector<int> f(n + 2, INF);

    f[0] = 0;
    qu.push_back(0);
    for (int i = 1; i <= n + 1; i ++){
        if (s[i] == 'C')
            continue;
        while (qu.size() && qu.front() + m < i){  // 存储原木的坐标
            qu.pop_front();
        }

        if (qu.size())
            f[i] = f[qu.front()];
        if (s[i - 1] == 'W')
            f[i] = min(f[i], f[i - 1] + 1);

        if (s[i] == 'L'){
            while (qu.size() && f[qu.back()] >= f[i])
                qu.pop_back();
            qu.push_back(i);
        }
    }

    if (f[n + 1] > k){
        cout << "NO\n";
    }
    else{
        cout << "YES\n";
    }
}

E. Novice's Mistake

fag：思维

Desription：给定一个\(n\)，求出所有满足条件的\(a, b\)组合。

• \(1 <= a <= 1e4， 1 <= n <= 100\)
• \(n * a - b\)等于将\(a\)个字符串\(n\)然后删去末尾\(b\)个字符之后代表的整数
• \(n * a - b > 0\)

Solution：注意到字符串的操作会影响答案的位数，但是数值计算\(n * a\)最多为\(1e6\)所以最大只有\(6\)位。

• 我们枚举\(a\)，然后枚举答案的位数\(k\)，对于每个\(k\)求出一个\(b\)，判断当前\(a, b\)是否满足条件

Competing：赛场根本没想到位数的关系

void solve(){
    string n;
    cin >> n;
    vector<pii> ans;

    for (int a = 1; a <= 10000; a ++){
        int len = to_string(stoi(n) * a).size();  // 当前位数
        // if (a == 1262)
        //     debug(len);
        for (int k = len; k; k --){
            int b = a * n.size() - k;
            if (!b) 
                continue;
            int t = 0;
            for (int i = 1, j = 0; i <= k; i ++){
                if (j == n.size())
                    j = 0;
                t = t * 10 + (n[j ++] - '0');
            }
            if (t == stoi(n) * a - b){
                ans.push_back({a, b});
            }
            // if (a == 1262 && b == 2519){
            //     debug(t, stoi(n) * a - b);
            // }
        }
    }
    cout << ans.size() << endl;
    for (auto [a, b] : ans){
        cout << a << " " << b << endl;
    }
}

F. Test of Love

fag：思维

Description：有\(n\)个数，给定一个\(x\)，将\(n\)个数分为\(k\)个连续区间，每个区间满足任意一个子集的乘积不等于\(x\)。

1 <= n <= 1e5 2 <= x <= 1e5
1 <= a_i <= 2e5

Solution：从前往后模拟当前区间能够得到那些因数（使用set去重），因为因数的个数很少，所以可做

Competing：没考虑到使用\(set\)去重

void solve(){
    int x;
    cin >> n >> x;
    vector<int> a(n);
    set<int> v; // 记录当前区间所有可能出现的x的约数
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    int ans = 1;
    for (int i = 0; i < n; i ++){
        if (x % a[i])
            continue;
        set<int> tmp;
        for (auto j : v){
            tmp.ep(a[i] * j); // 记录能够构造出来的数
        }
        for (auto j : tmp){
            if (x % j)
                continue;
            v.ep(j);
        }
        if (v.find(x) != v.end()){
            ans ++;
            v.clear();
        }
        v.ep(a[i]);
    }
    cout << ans << endl;
}