Codeforces Round 640 (Div. 4)

简介: Codeforces Round 640 (Div. 4)A~G

A. Sum of Round Numbers

得到每个数位上的数是几,在记录后面零的个数
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int x;
    cin >> x;
    vector<int> a;
    int n = 5;
    int p = 1;
    while(n -- )
    {
        int t = x % 10;
        x /= 10;
        if(t) a.push_back(t * p);
        p *= 10;
    }
    cout << a.size() << endl;
    for(auto t : a)
        cout << t << " ";
    cout << 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. Same Parity Summands

给定两个整数n, k。构建一个k个奇偶性相同的数列,使得和是n。

构造题,两种方式

如果前k-1个数写成1,最后留一个n-k+1也是奇数,就构造成功

如果前k-2个数为2,最后一个n - 2 * (k - 1) 也是偶数,就构造成功

否则就不能构造出来

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n, k;
    cin >> n >> k;
    int n1 = n - (k - 1);
    if(n1 > 0 && n1 % 2 == 1)
    {
        cout << "YES" << endl;
        for(int i = 0; i < k - 1; i ++ )
            cout << "1 ";
        cout << n1 << endl;
        return;
    }

    int n2 = n - 2 * (k - 1);
    if(n2 > 0 && n2 % 2 == 0)
    {
        cout << "YES" << endl;
        for(int i = 0; i < k - 1; i ++ )
            cout << "2 ";
        cout << n2 << 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;
}

C. K-th Not Divisible by n

题意很简单, 输出第 K 个不能被 n 整除的数
#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n, k;
    cin >> n >> k;
    long long a = k / (n - 1);
    long long b = k % (n - 1);
    if(b == 0) b = -1;
    cout << (long long)a * n + b << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    int tt;
    cin >> tt;
    while(tt -- )
    {
        solve();
    }
    return 0;
}

D. Alice, Bob and Candies

模拟
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
void solve()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
        cin >> a[i];
    
    int ans1 = 0, ans2 = 0;
    int res1 = 0, res2 = 0;
    int l = 0, r = n - 1;
    int cnt = 0;
    while(l <= r)
    {
        if(res1 <= res2)
        {
            res1 = 0;
            while(res1 <= res2 && l <= r)
            {
                res1 += a[l];
                ans1 += a[l];
                l ++ ;
            }
            cnt ++ ;
        }
        else if(res1 >= res2)
        {
            res2 = 0;
            while(res2 <= res1 && l <= r)
            {
                res2 += a[r];
                ans2 += a[r];
                r -- ;
            }
            cnt ++ ;
        }
    }
    cout << cnt << " " << ans1 << " " << ans2 << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    int tt;
    cin >> tt;
    while(tt -- )
    {
        solve();
    }
    return 0;
}

E. Special Elements

定义一种特殊元素,只要有连续区间和等于它,它就是特殊元素,问有多少个特殊元素

先用cnt记录每个数字出先的次数,然后n^2遍历所有区间,算出区间和t,ans += cnt[t];

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef long long LL;
int s[N];
int cnt[N];
bool st[N];
void solve()
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        cnt[s[i]] ++ ;
        s[i] += s[i - 1];
    }
    LL ans = 0;
    for(int len = 2; len <= n; len ++ )
        for(int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            LL t = s[r] - s[l - 1];
            if(t < N && !st[t])
            {
                ans += cnt[t];
                st[t] = true;
            }
        }
    cout << ans << endl;
}
int main()
{
    freopen("test.in", "r", stdin);
    int tt;
    cin >> tt;
    while(tt -- )
    {
        solve();
    }
    return 0;
}

F. Binary String Reconstruction

构造,特殊情况特判
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    bool f = false;
    string s;
    if(a == b && a == 0)
    {
        a = -1;
        c ++ ;
    }
    if(b > 0 && b % 2 == 0)
    {
        b -- ;
        f = true;
    }

    for(int i = 1; i <= a + 1; i ++ )
        s += '0';
    
    for(int i = 1; i <= b; i ++ )
    {
        s += (char)('0' + (i & 1));
    }

    for(int i = 1; i <= c; i ++ )
        s += '1';
    if(f) s += '0';
    cout << s << "\n";
}
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. Special Permutation

如果n小于4,肯定不存在

剩下的先从大到小输出奇数,在输出4和2,在从6开始从小到大输出偶数

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    if(n < 4)
    {
        cout << -1 << endl;
        return;
    }
    int t = n;
    if(t % 2 == 0) t -- ;
    for(int i = t; i > 0; i -= 2)
        cout << i << " ";
    
    cout << 4 << " " << 2 << " ";
    for(int i = 6; i <= n; i += 2)
        cout << i << " ";
    
    cout << 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;
}
目录
相关文章
|
机器学习/深度学习
Codeforces Round #742 (Div. 2)
Codeforces Round #742 (Div. 2)
52 0
Codeforces Round 849 (Div. 4)
Codeforces Round 849 (Div. 4)A~G2题解
114 0
Codeforces Round #675 (Div. 2) A~D
Codeforces Round #675 (Div. 2) A~D
154 0