Educational Codeforces Round 161 (Rated for Div. 2)

Educational Codeforces Round 161 (Rated for Div. 2)

A. Tricky Template

題意：開(kāi)始沒(méi)看懂。。。給出長(zhǎng)度均為n的三個(gè)字符串a(chǎn)bc，字符串s與模板t匹配的條件為：當(dāng)模板位置字符為小寫(xiě)時(shí)，$s_i$與$t_i$必須相同，大寫(xiě)時(shí)二者必須不同。這里注意，字符匹配過(guò)程是不區(qū)分大小寫(xiě)的，’C‘與’c’是相同的。
現(xiàn)在需要找出一個(gè)模板t，使得t與字符串a(chǎn)和b匹配，且與c不匹配，是否能找到。

思路：只要字符串c存在一個(gè)位置的字符與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根棍，任取三根組成三角形，有多少種可能，現(xiàn)給出n個(gè)整數(shù)$a_i$，第i根棍的長(zhǎng)度為(2^$a_i$)。

思路：組成的三角形一定是等腰三角形，才能滿(mǎn)足任意兩邊之和大于第三邊這樣的三角形定理：

• 三條邊相等：長(zhǎng)度相同的棍，任取仨
• 兩條邊相等，長(zhǎng)度相同的棍，任取倆，注意，第三條邊只能去找比當(dāng)前相同的兩根棍嚴(yán)格小的邊才能組成三角形

AC code：文章來(lái)源地址http://www.zghlxwxcb.cn/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座城市，按順序給出每個(gè)城市的坐標(biāo)$a_i$，我們定義一個(gè)城市到另一個(gè)最近城市的距離為兩城市坐標(biāo)差的絕對(duì)值，最近城市有且只有一個(gè)。一個(gè)城市到最近城市花費(fèi)為一枚硬幣，否則花費(fèi)硬幣數(shù)為兩城市的距離。
給出t個(gè)查詢(xún)，每次查詢(xún)城市A->B的最小花費(fèi)。

思路：

• 首先給出城市是按照坐標(biāo)大小排列的，意味著一個(gè)城市的最近城市有且只有一個(gè)并且相鄰；

• 當(dāng)我們的路徑上存在最近城市這條路時(shí)，我們的硬幣花費(fèi)就為1，假設(shè)路徑不存在最近城市，那么我們的花費(fèi)直接就是兩城市的距離?，F(xiàn)在每當(dāng)路徑上存在一段最近城市距離，我們的花費(fèi)就會(huì)減少(這兩個(gè)最近城市的距離再-1)枚硬幣。

• 然后一個(gè)城市到達(dá)另一個(gè)城市可以分兩種情況去討論，我們定義城市A<城市B：

  • A->B：一個(gè)前綴和，計(jì)算可以省去的硬幣數(shù)；
  • B->A：一個(gè)后綴和，計(jì)算可以省去的硬幣數(shù)；

• 則兩城市間的最小花費(fèi)為，兩城市的距離 - 可以省去的硬幣數(shù)

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

到了這里，關(guān)于Educational Codeforces Round 161 (Rated for Div. 2)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！