Educational Codeforces Round 161 (Rated for Div. 2)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Educational Codeforces Round 161 (Rated for Div. 2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Educational Codeforces Round 161 (Rated for Div. 2),算法,c++,数据结构,codeforces

Educational Codeforces Round 161 (Rated for Div. 2)

A. Tricky Template

题意：开始没看懂。。。给出长度均为n的三个字符串abc，字符串s与模板t匹配的条件为：当模板位置字符为小写时， $s_i$ 与 $t_i$ 必须相同，大写时二者必须不同。这里注意，字符匹配过程是不区分大小写的，’C‘与’c’是相同的。
现在需要找出一个模板t，使得t与字符串a和b匹配，且与c不匹配，是否能找到。

思路：只要字符串c存在一个位置的字符与a和b都不同即可。

AC code:

void solve() {
    cin >> n;
    string a, b, c; cin >> a >> b >> c;
    for (int i = 0; i < n; i ++) {
        if (a[i] != c[i] && b[i] != c[i]) {
            cout << "YES" << endl;
            return;
        }
    } cout << "NO" << endl;
}

B. Forming Triangles

题意：有n根棍，任取三根组成三角形，有多少种可能，现给出n个整数 $a_i$ ，第i根棍的长度为(2^ $a_i$ )。

思路：组成的三角形一定是等腰三角形，才能满足任意两边之和大于第三边这样的三角形定理：

三条边相等：长度相同的棍，任取仨
两条边相等，长度相同的棍，任取俩，注意，第三条边只能去找比当前相同的两根棍严格小的边才能组成三角形

AC code：文章来源地址https://www.toymoban.com/news/detail-803803.html

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb emplace_back
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
 
typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
int a[N];
 
int sum(int x) {
    if (x < 3) return 0;
    return x * (x - 1) * (x - 2) / 6;
}
int sum2(int x) {
    if (x < 2) return 0;
    return  x * (x - 1) / 2;
}
 
void solve() {
    map<int, int> mp;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        mp[x] ++;
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans += sum(y);//任取仨
    }
    int now = 0;
    for (auto [x, y] : mp) {
        ans += sum2(y) * now;//二带一
        now += y;
    }
    cout << ans << endl;
}
 
signed main() {
    fast();
    
    T = 1;
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

C. Closest Cities

题意：有n座城市，按顺序给出每个城市的坐标 $a_i$ ，我们定义一个城市到另一个最近城市的距离为两城市坐标差的绝对值，最近城市有且只有一个。一个城市到最近城市花费为一枚硬币，否则花费硬币数为两城市的距离。
给出t个查询，每次查询城市A->B的最小花费。

思路：

首先给出城市是按照坐标大小排列的，意味着一个城市的最近城市有且只有一个并且相邻；
当我们的路径上存在最近城市这条路时，我们的硬币花费就为1，假设路径不存在最近城市，那么我们的花费直接就是两城市的距离。现在每当路径上存在一段最近城市距离，我们的花费就会减少(这两个最近城市的距离再-1)枚硬币。
然后一个城市到达另一个城市可以分两种情况去讨论，我们定义城市A<城市B：
- A->B：一个前缀和，计算可以省去的硬币数；
- B->A：一个后缀和，计算可以省去的硬币数；
则两城市间的最小花费为，两城市的距离 - 可以省去的硬币数

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb emplace_back
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
 
typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
int a[N];
 
void solve() {
    cin >> n;
    vector<int> l(n + 1, 0), r(n + 1, 0);
    a[0] = -INF;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (i == 1) {
            continue;
        }
        l[i] = l[i - 1];
        if (a[i] - a[i - 1] < a[i - 1] - a[i - 2]) l[i] += (a[i] - a[i - 1]) - 1;
    }
    a[n + 1] = INF;
    for (int i = n - 1; i >= 1; i --) {
        r[i] = r[i + 1];
        if (a[i + 1] - a[i] < a[i + 2] - a[i + 1]) r[i] += (a[i + 1] - a[i]) - 1;
    }
    int t; cin >> t;
    while (t --) {
        int x, y; cin >> x >> y;
        if (x < y) {
            cout << a[y] - a[x] - (l[y] - l[x]) << endl;
        } else {
            cout << a[x] - a[y] - (r[y] - r[x]) << endl;
        }
    }
 
}
 
signed main() {
    fast();
    
    T = 1;
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

到了这里，关于Educational Codeforces Round 161 (Rated for Div. 2)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！