Educational Codeforces Round 161 (Div. 2)

mostimali / 2024-01-30 / 原文

A - Tricky Template

难度: ⭐⭐

题目大意

给定三个字符串a, b, c; 现在有一个模板串t, 如果字符串s和t匹配需要满足两个条件;
1- 如果 t_i 是小写字母, 那么 s_i 和 t_i 相同;
2- 如果 t_i 是大写字母, 那么 s_i 不能 t_i 的小写形式相同;
问是否存在一个模板串t使得a, b都和t匹配, 而c不匹配;

解题思路

本题要从a, b串下手, 根据a, b当前字符的形式来判断 t_i 的类型, 然后再用 t_i 去约束c;
当a_i == b_i时, 如果a_i是小写, 那么此时 t_i 大小写都可以, 如果是小写, 只要c_i不等于a_i就匹配失败; 如果是大写, 那么t_i的小写形式肯定不是a_i, 所以还是只要c_i不等于a_i就匹配失败; 如果a_i是大写, 那么此时t_i只能是大写, 并且只要此时c_i是小写就匹配失败;
当a_i != b_i时, 那么此时t_i只能是大写, 么t_i的小写形式肯定不是a_i 或者b_i, 所以还是只要c_i不等于a_i和b_i就匹配失败;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, m;
signed main() {
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        string a, b, c;
        cin >> a >> b >> c;
        bool f = false;
        for(int i = 0; i < n; i++){
            if(a[i] == b[i] && islower(a[i])){
                if(c[i] != a[i]){
                    f = true;
                    break;
                }
            }
            else if(a[i] != b[i]){
                if(islower(c[i]) && c[i] != a[i] && c[i] != b[i]){
                    f = true;
                    break;
                }
                
            }
        }
        if(f) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

B - A Balanced Problemset?

难度: ⭐⭐

题目大意

给定n条边a_i, 每条边的长度是2^ai; 问这n条边能组成多少个三角形, 不去重;

解题思路

本题因为是二进制所以难度大大降低; 当三条边都不一样时, 第三边一定小于两边之和, 也一定小于等于两边之差, 所以一定不行; 所以要考虑等腰和等边就可以了, 等腰只要第三边比腰短就行, 而等边更是用组合数就可以搞定; 我这里为了方便都对multiset和set来解决去重的问题;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, m;
int p[N];
signed main() {
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        multiset<int> s1;
        set<int> s2;
        for(int i = 1; i <= n; i++){
            int a;
            cin >> a;
            s1.insert(a);
            s2.insert(a);
        }
        int idx = 0, res = 0;
        for(auto t : s2){
            int num = s1.count(t);
            if(num >= 2){
                res += idx * num * (num - 1) / 2;
                if(num >= 3){
                    res += num * (num - 1) * (num - 2) / 6;
                }
            }
            idx += num;
        }
        cout << res << endl;
    }
    return 0;
}

C - Closest Cities

难度: ⭐⭐⭐

题目大意

有n个城市a_i位于横轴上, 每个城市的距离是|a_i - a_j|; 而对于a_i而言, 离其最近的城市称为友好城市, 题目保证每个城市都只能有一个友好城市; 从a_i到其友好城市只需要花费一块钱, 而去别的城市需要花费|a_i - a_j|; 现在有m组询问, 给定起点和终点, 请问从起点到终点最少需要花费多少钱;

解题思路

看似是个图论, 但是因为都在横轴上, 所以不需要考虑路径问题, 就单向从起点到终点即可, 预处理出友好城市以及前缀和和后缀和既可以了; 要注意的是前缀和和后缀和是路径的和, 不是城市的和, 要注意求解时的下标;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, m;
int p[N], nx[N];
int u[N], du[N];
signed main() {
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> p[i];
        for(int i = 1; i <= n; i++){
            if(i - 1 >= 1 && i + 1 <= n){
                if(abs(p[i] - p[i - 1]) < abs(p[i] - p[i + 1])){
                    nx[i] = i - 1;
                }
                else nx[i] = i + 1;
            }
            else if(i - 1 >= 1) nx[i] = i - 1;
            else if(i + 1 <= n) nx[i] = i + 1;
        }
        for(int i = 2; i <= n; i++){
            if(nx[i - 1] == i) u[i] = u[i - 1] + 1;
            else u[i] = u[i - 1] + p[i] - p[i - 1];
        }
        for(int i = n - 1; i >= 1; i--){
            if(nx[i + 1] == i) du[i] = du[i + 1] + 1;
            else du[i] = du[i + 1] + p[i + 1] - p[i];
        }
        cin >> m;
        while(m--){
            int a, b;
            cin >> a >> b;
            if(a < b){
                cout << u[b] - u[a] << endl;
            }
            else {
                cout << du[b] - du[a] << endl;
            }
        }
    }
    return 0;
}

D - Berserk Monsters

难度: ⭐⭐⭐⭐

题目大意

现在有n个怪兽, 他们都有各自的攻击力和防御力, 当遇到大于防御力的攻击时会被击败, 防御力不会因受到攻击而被削减; 总共有n轮攻击, 每轮攻击怪兽都会向当前左边离自己最近的和右边离自己最近的怪兽发起攻击; 输出每一轮都有多少怪兽被击败;

解题思路

暴力模拟的复杂度是O(n²)需要优化; 模拟一下过程会发现, 当有怪兽被击败时, 只有相邻的两个怪兽受到影响; 如果某一轮没有怪兽被击败, 那么往后的轮次也不会有怪兽被击败; 我们可以用双向链表来表示怪兽之间相邻的关系; 用一个集合来装当前轮次被击败的怪兽, 然后通过检查其相邻的怪兽来得到下一轮被击败的怪兽; 由于每一轮被击败的怪兽都不一样, 所以这是O(n)的;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, m;
int a[N], d[N];
bool st[N];
struct {
    int l, r;
}p[N];
signed main() {
    IOS;
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        set<int> s1, s2;
        for(int i = 1; i <= n; i++) st[i] =false;
        st[0] = true, st[n + 1] = true;
        a[0] = 0, a[n + 1] = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> d[i];
        for(int i = 1; i <= n; i++){
            p[i].l = i - 1;
            p[i].r = i + 1;
            if(i == n) {
                if(a[i - 1] > d[i]) s1.insert(i);
            }
            else if(a[i - 1] + a[i + 1] > d[i]){
                s1.insert(i);
            }
        }
        for(int i = 1; i <= n; i++){
            cout << s1.size() << ' ';
            for(auto t : s1){
                st[t] = true;
                int l = p[t].l, r = p[t].r;
                p[l].r = r;
                p[r].l = l;
            }
            for(auto t : s1){
                int l = p[t].l, r = p[t].r;
                if(!st[l] && a[p[l].l] + a[p[l].r] > d[l]) s2.insert(l);
                if(!st[r] && a[p[r].l] + a[p[r].r] > d[r]) s2.insert(r);
            }
            s1.swap(s2);
            s2.clear();
        }
        cout << endl;
    }
    return 0;
}