526互联

Codeforces Round 886 (Div. 4)

发布时间 2023-07-22 09:41:02作者: PHarr

A. To My Critics

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    vector<int> a(3);
    for( auto & i : a )
        cin >> i;
    sort( a.begin(), a.end() );
    if( a[2] + a[1] >= 10 ) cout << "YES\n";
    else cout << "NO\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while( t -- )
        solve();
    return 0;
}

B. Ten Words of Wisdom

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1) , b(n+1);
    for( int i = 1 ; i <= n ; i ++ )
        cin >> a[i] >> b[i];
    int res = -1 , val = -1;
    for( int i = 1 ; i <= n ; i ++ ){
        if( a[i] > 10 ) continue;
        if( b[i] > val ) val = b[i] , res = i;
    }
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while( t -- )
        solve();
    return 0;
}

C. Word on the Paper

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    vector<string> g(8);
    for( auto & i : g )
        cin >> i;
    for( const auto & i : g )
        for( const auto & j : i )
            if( j != '.' ) cout << j;
    cout << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while( t -- )
        solve();
    return 0;
}

D. Balanced Round

#include <bits/stdc++.h>

using namespace std;


void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &i: a)
        cin >> i;
    sort(a.begin(), a.end());
    int res = 0;
    for( int i = 0 , last = INT_MIN , cnt = 0; i < n ; i ++ ){
        if( a[i] - last <= k ) cnt ++;
        else cnt = 1;
        res = max( res , cnt );
        last = a[i];
    }
    cout << n - res << "\n";


}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. Cardboard for Pictures

\[c=\sum(s+2w)^2=\sum(s^2+4sw+4w^2)\\ 4nw^2+4\sum (s)w+\sum(s^2)-c=0 \]

解一元二次方程

import math


def solve():
    n, c = map(int, input().split(' '))
    s = list(map(int, input().split(' ')))
    a = 4 * n
    b , c = 0 , - c
    for i in s :
        b += i
        c += i * i
    b = b * 4
    res = (math.sqrt(b * b - 4 * a * c) - b) // ( 2 * a )
    print(int(res))


T = int(input())
while T > 0:
    T -= 1
    solve()

F. We Were Both Children

枚举陷阱，枚举陷阱的因子统计答案

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        if (x > n) continue;
        a[x]++;
    }
    int res = 0;
    for (int i = 1, cnt = 0; i <= n; i++) {
        cnt = 0;
        for (int j = 1; j * j <= i; j++) {
            if (i % j != 0) continue;
            cnt += a[j];
            if (j != i / j)
                cnt += a[i / j];
        }
        res = max(res, cnt);
    }
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. The Morning Star

统计每一行、每一列、每一主对角线、每一负对角线上的点的数量，然后组合数即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    map<int,int> a , b , c , d;
    for( int x , y ; n ;  n -- ){
        cin >> x >> y;
        a[x] ++ , b[y] ++ , c[x+y] ++ , d[x-y] ++;
    }
    int res = 0;
    for( auto [k,v] : a )
        res += v * (v-1) ;
    for( auto [k,v] : b )
        res += v * (v-1);
    for( auto [k,v] : c )
        res += v * (v-1);
    for( auto [k,v] : d )
        res += v * (v-1);
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

H. The Third Letter

建无向图，然后任意确定一个点，按照图的顺序去确定其他点的位置，在确定点位置的过程中判断是否合法即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1, a, b, c; i <= m; i++) {
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, -c);
    }
    vector<int> d(n + 1, LLONG_MIN);
    for (int i = 1; i <= n; i++) {
        if( d[i] != LLONG_MIN ) continue;
        d[i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int a = q.front();
            q.pop();
            for (auto [b, c]: g[a]) {
                if (d[b] != LLONG_MIN) {
                    if (d[b] != d[a] + c) {
                        cout << "NO\n";
                        return;
                    }
                } else {
                    d[b] = d[a] + c;
                    q.push(b);
                }
            }
        }
    }
    cout << "YES\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}