Codeforces Round 799 (Div. 4)

简介: Codeforces Round 799 (Div. 4)

A. Marathon

输入三个数字,判断有几个比第一个数字大
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a, b, cnt = 0;
    cin >> a;
    for(int i = 0; i < 3; i ++ )
    {
        cin >> b;
        if(b > a) cnt ++ ;
    }
    cout << cnt << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

B. All Distinct

用set存不同个数,如果要删除的个是偶数,就输出set.size();

否则,输出set.size() - 1;

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    set<int> se;
    for(int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        se.insert(x);
    }
    int res = se.size();
    cout << ((n - res) & 1 ? res - 1 : res) << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    int _t;
    cin >> _t;
    while(_t--)
    {
        solve();
    }
    return 0;
}

C. Where's the Bishop?

找主教的位置,题目说出主教的位置不在棋盘边缘

故统计每一行#的个数,如果当前行是1,而上下两行是2,就在当前行

遍历一遍寻找y坐标即可

#include<bits/stdc++.h>
using namespace std;

char g[8][8];

void solve()
{
    int cnt[8] = {0};
    for(int i = 0; i < 8; i ++ )
    {
        cin >> g[i];
        for(int j = 0; j < 8; j ++ )
        {
            if(g[i][j] == '#')
                cnt[i] ++ ;
        }
    }
    for(int i = 0; i < 8; i ++ )
    {
        if(i == 0 || i == 7) continue;
        if(cnt[i] == 1 && cnt[i - 1] == 2 && cnt[i + 1] == 2)
        {
            for(int j = 0; j < 8; j ++ )
            {
                if(g[i][j] == '#')
                    cout << i + 1 << " " << j + 1 << endl;
            }
        }
    }
}

int main()
{
    freopen("test.in", "r", stdin);
    int _t;
    cin >> _t;
    while(_t--)
    {
        solve();
    }
    return 0;
}

D. The Clock

直接模拟这个过程
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int h, m, t;
    scanf("%d:%d %d", &h, &m, &t);
    int h1 = h, m1 = m;

    int x = t / 60, y = t % 60;
    int cnt = 0;

    do
    {
        if(h % 10 == m / 10 && m % 10 == h / 10)
            cnt ++ ;
        
        if(m + y >= 60)
        {
            h = (h + x + 1) % 24;
            m = (m + y) % 60;
        }
        else
        {
            h = (h + x) % 24;
            m = (m + y) % 60;
        }
        // cout << h << " " << m << endl;

    } while (h != h1 || m != m1);
    cout << cnt << endl;
}

int main()
{
    freopen("test.in", "r", stdin);
    int _t;
    cin >> _t;
    while(_t--)
    {
        solve();
    }
    return 0;
}

E. Binary Deque

删去最少的数,使得数组和为k

先找到如果左区间定为0,和为k的话,右区间在哪,如果大于数组长度了,说明无解

找到左右区间,进行双指针更新答案

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n, k;
    cin >> n >> k;
    int a[n];
    int sum = 0;
    int res = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int l = 0, r = -1;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
        if (sum == k)
        {
            r = i;
        }
        if (sum > k)
            break;
    }
    if (r == -1)
    {
        cout << -1 << endl;
        return;
    }
    res = max(res, r - l + 1);
    while (r >= l && r < n)
    {
        r++;
        sum += a[r];
        while (sum > k)
        {
            sum -= a[l];
            l++;
        }
        res = max(res, r - l + 1);
    }
    cout << n - res << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    int _t;
    cin >> _t;
    while (_t--)
    {
        solve();
    }
    return 0;
}

F. 3SUM

因为题目只在乎模十后的数,我们就只用模十后的数,模十后相同的数我们最多存3个

这样数组中最多也就30个数,直接n^3暴力求解

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a;
    vector<int> cnt(10, 0);
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (cnt[x % 10] < 3)
        {
            a.push_back(x % 10);
            cnt[x % 10] ++ ;
        }
    }
    n = a.size();
    for(int i = 0; i < n; i ++ )
        for(int j = i + 1; j < n; j ++ )
            for(int k = j + 1; k < n; k ++ )
                if((a[i] + a[j] + a[k]) % 10 == 3)
                {
                    cout << "YES" << endl;
                    return;
                }
    cout << "NO" << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while (_t--)
    {
        solve();
    }
    return 0;
}

G. 2^Sort

找到一个长度为k+1的子数组,满足每个元素小于下一个元素的两倍
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i ++ ) cin >> a[i];

    int cur = 1, cnt = 0;
    for(int i = 0; i < n - 1; i ++ )
    {
        if(a[i] < a[i + 1] * 2)
        {
            cur ++ ;
            cnt += (cur >= k + 1);
        }
        else cur = 1;
    }
    cout << cnt << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}

H. Gambling

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    map<int, vector<int>> mp;
    for(int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        mp[x].push_back(i);
    }

    int l, r, ans, maxv = 0;
    for(auto [x, a] : mp)
    {
        int t = -2e9, pos;
        for(int i = 0; i < a.size(); i ++ )
        {
            if(a[i] - 2 * i > t)
            {
                t = a[i] - 2 * i;
                pos = a[i];
            }
            int now = 2 * i - a[i] + t + 1;
            if(now > maxv)
            {
                maxv = now;
                ans = x;
                l = pos;
                r = a[i];
            }
        }
    }
    cout << ans << " " << l << " " << r << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _t = 1;
    cin >> _t;
    while(_t -- ){
        solve();
    }
    return 0;
}
目录
相关文章
|
27天前
|
人工智能 测试技术 BI
Codeforces Round 942 (Div. 2)
Codeforces Round 942 (Div. 2)
|
5月前
Codeforces Round #729 (Div. 2)
【6月更文挑战第4天】在这两个编程问题中,B. Plus and Multiply 要求判断通过加法和乘法操作数组是否能形成目标数 `n`。思路是形如 `x^a + yb = n` 的表达式,如果满足则能构造。C. Strange Function 关注的是找到最小正整数 `x` 使得 `x` 不是 `i` 的因子,计算这些值的和模 `10^9+7`。对于每个 `i`,偶数时 `f(i)` 是 3,奇数时是 2,利用因子与最大公约数计算周期性求和。
30 1
|
人工智能 算法 BI
Codeforces Round #179 (Div. 2)A、B、C、D
我们每次加进来的点相当于k,首先需要进行一个双重循环找到k点和所有点之间的最短路径;然后就以k点位判断节点更新之前的k-1个点,时间复杂度降到O(n^3),而暴力解法每次都要进行floyd,时间复杂度为O(n^4);相比之下前述解法考虑到了floyd算法的性质,更好了运用了算法的内质。
54 0
Codeforces Round #192 (Div. 2) (329A)C.Purification
Codeforces Round #192 (Div. 2) (329A)C.Purification
41 0
|
机器学习/深度学习
Codeforces Round #742 (Div. 2)
Codeforces Round #742 (Div. 2)
49 0
|
人工智能
Codeforces Round #786 (Div. 3)(A-D)
Codeforces Round #786 (Div. 3)(A-D)
70 0
|
人工智能 索引
Codeforces Round 806 (Div. 4)
Codeforces Round 806 (Div. 4)A~G
110 0
Codeforces Round 640 (Div. 4)
Codeforces Round 640 (Div. 4)A~G
92 0
|
索引
Codeforces Round 817 (Div. 4)
Codeforces Round 817 (Div. 4)A~G题解
106 0