天天看点

Codeforces Round #572 (Div. 2) A,B,C,D1题解

总的来说这一场还是比较顺利的,很快出了4题,Rating + 108.

A. Keanu Reeves

思维题,如果01个数不等就不用拆,直接输出就ok,否则就先把第一个数输出,那么剩下的数01就肯定不会相等了

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,one = 0,zero = 0;
    string s;
    cin >> n >> s;
    for(int i = 0;i < s.length(); i++)
    {
        if(s[i] == '1')
            one++;
        else
            zero++;
    }
    if(one != zero)
        cout << 1 << endl << s << endl;
    else
    {
        cout << 2 << endl << s[0] << " ";
        for(int i = 1;i < s.length(); i++)
            cout << s[i];
        cout << endl;
    }
    return 0;
}
           

B. Number Circle

一开始看到这个,首先想到素数环,但是看了一眼数据范围就不可以了。然后就想着递增排一下,然后检测一下首尾,就OK了

#include<bits/stdc++.h>
typedef long long ll;
const int MAXN = 200011;
using namespace std;
ll a[MAXN], n;
int main() 
{
    cin >> n;
    for (ll i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    if (a[1] >= a[2] + a[3])
        cout << "NO";
    else 
    {
        cout << "YES" << endl;
        if (n & 1) 
        {
            for (ll i = 1; i <= n; i += 2)
                cout << a[i] << " ";
            for (ll i = n - 1; i > 0; i -= 2)
                cout << a[i] << " ";
        } else {
            for (ll i = 1; i <= n; i += 2)
                cout << a[i] << " ";
            for (ll i = n; i > 0; i -= 2)
                cout << a[i] << " ";
        }
    }
    return 0;
}
           

C. Candies!

这个题的出题人想的是让用dp的做法来做,但是我理解了一波题意后觉得在过程中取模和加一起对结果取模没什么两样,然后就这样写的,然后就pp了,最后还AC了,真的是很神奇啊。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int x[maxn],sum[maxn];
int main()
{
    int n,q,l,r;
    cin >> n;
    for(int i = 1;i <= n; i++)
    {
        cin >> x[i];
        sum[i] = sum[i - 1] + x[i];
    }
    cin >> q;
    while (q--)
    {
        cin >> l >> r;
        int ans = sum[r] - sum[l - 1];
        cout << ans / 10 << endl;
    }
    return 0;
}
           

D1. Add on a Tree

一开始在题意上卡了半天,然后好久才明白了。题意是给你一个树,问你能不能通过更改一对叶子结点的路径上的权值把树上任意的边权变为任意值,是就yes,不是就no。

然后又研究了好久的样例,然后猜了一个如果有度数为2的点就no,否则就yes,怀着忐忑的心情交了上去,然后,然后,然后居然过了,了,。

虽然有度数为2的点肯定不行,这个是可以证明的,但是没有为什么就可以呢???

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int vis[maxn];
int main()
{
    int n,u,v;
    cin >> n;
    n--;
    while(n--)
    {
        cin >> u >> v;
        vis[u]++;
        vis[v]++;
    }
    int flag = 1;
    for(int i = 1;i < maxn; i++)
    {
        if(vis[i] == 2)
        {
            flag = 0;
            break;
        }
    }
    if(flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}