Codeforces Round#640(Div4)解题报告

Codeforces Round#640(Div4)解题报告

活久见,Codeforces出了Div4,晚上睡早了后来虚拟参赛的。题目较为简单,构造,思维为主
image.png

A.Sum of Round Numbers

题意

一开始题意理解错了,以为是数字中不能出现,大于五的数字,又看了一眼题目,把一个数拆成若干个除首位都是 $0$ 的数字的和

题解

模拟就行了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 1e5 + 7;
const int INF = 0x7fffffff;

void solve(){
    int n, k;
    cin >> n >> k;
    if(n > 2*(k-1) && n % 2 == 0){
        cout << "YES" << endl;
        for(int i = 1;i <= k-1;i++)
            cout << 2 << " ";
        cout << n - 2*(k-1) << endl;
    } else if(n % 2 == 0 && k % 2 == 0 && n >= k){
        cout << "YES" << endl;
        for(int i = 0;i < k-1;i++)
            cout << 1 << " ";
        cout << n - (k-1) << endl;
    } else if(n % 2 == 1 && k % 2 == 1 && n >= k){
        cout << "YES" << endl;
        for(int i = 0;i < k-1;i++)
            cout << 1 << " ";
        cout << n - (k-1) << endl;
    } else {
        cout << "NO" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--){
        solve();
    }

    return 0;
}

B.Same Parity Summands

题意

构造一个有 $k$ 项的组合,$k$ 项相加为 $n$,且奇偶行相同.

题解

奇数 X 奇数 = 奇数, 奇数 X 偶数 = 偶数, 偶数 X 偶数 = 偶数

  • 当 $n$ 为偶数时
    • 如果 $n\geq 2\ast \left( k-1\right)$,可以构造一个长度为 $k-1$ 的 $2$ 序列,最后一个$n - 2*(k-1)$,
  • 当 $n,k$ 奇性相同时,并且$n\geq k$,直接构造全 $1$ 序列然后 $n - (k - 1)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 1e5 + 7;
const int INF = 0x7fffffff;

void solve(){
    int n, k;
    cin >> n >> k;
    if(n > 2*(k-1) && n % 2 == 0){
        cout << "YES" << endl;
        for(int i = 1;i <= k-1;i++)
            cout << 2 << " ";
        cout << n - 2*(k-1) << endl;
    } else if(n % 2 == 0 && k % 2 == 0 && n >= k){
        cout << "YES" << endl;
        for(int i = 0;i < k-1;i++)
            cout << 1 << " ";
        cout << n - (k-1) << endl;
    } else if(n % 2 == 1 && k % 2 == 1 && n >= k){
        cout << "YES" << endl;
        for(int i = 0;i < k-1;i++)
            cout << 1 << " ";
        cout << n - (k-1) << endl;
    } else {
        cout << "NO" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--){
        solve();
    }

    return 0;
}

C.K-th Not Divisible by n

题意

询问找到从 $1$ 开始第 $k$ 个不能被 $n$ 整除的数字

题解

数学规律题,发现例如能被 $3$ 整除 的第 $7$ 个数字,
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
可以发现,以3的倍数为分界,可以划分为 1,2,3 | 4,5,6|,7,8,9| ....,,每一部分有$n-1$个数字可以被选择,那么最多可以有 $cnt = k / (n-1)$个部分,能到达的边界为 $cntn$, 能过跳过的数字有$cnt(n-1)$,然后看往右需要过几个即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 1e5 + 7;
const int INF = 0x7fffffff;

void solve(){
    int n, k;
    cin >> n >> k;
    int cnt = k/(n-1);
    int r = cnt*n;
    cnt *= (n-1);
	if(k == cnt)
		cout << r-1 << endl;
	else
		cout << r + (k - cnt) << endl;   
//    int l = 1,r = n;
//    for(int i = 1;;i++){
//        if(r - l >= k){
//            cout << l+k-1 << endl;
//            break;
//        } else {
//            k -= (r - l);
//        }
//        l = i*n+1, r = (i+1)*n;
//    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--){
        solve();
    }

    return 0;
}

D.Alice, Bob and Candies

题意

两个人吃糖果,一个人从左边吃,一个人从右边开始吃,轮流开吃,每个人吃的糖果数量都要比上一个人吃的糖果的数量要多,如不过满足则游戏结束。

题解

双指针,一个从左一个从右,暴力去扫就好了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 1e5 + 7;
const int INF = 0x7fffffff;
int a[MAXN], b[MAXN], c[MAXN];
void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = n,cnt = 0,suml = 0, sumr = 0,last = 0;
    while(l <= r){
        int now = 0;
        while(l <= r && now <= last){
            now += a[l];
            l++;
        }
        cnt++;
        last = now;
        suml += now;
        now = 0;
        if(l > r)
            break;
        while(l <= r && now <= last){
            now += a[r];
            r--;
        }
        cnt++;
        last = now;
        sumr += now;
        now = 0;
        if(l > r)
            break;
    }
    cout << cnt << " " << suml << " " << sumr << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }

    return 0;
}

E.Special Elements

题意

判断输入的$a_i$是否为某一段整个数组某一段的和

题解

暴力前缀和桶排,由于$a_i \leq n$所以桶内元素只要 $\leq n$ 即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 3e5 + 7;
const int INF = 0x7fffffff;
int a[MAXN], b[MAXN], c[MAXN];
void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++){
        b[i] = b[i-1] + a[i];
        for(int j = 1;j < i;j++){
            if(b[i] - b[j-1] <= n)
                c[b[i] - b[j-1]] = 1;
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++)
        ans += c[a[i]];
    cout << ans << endl;
    memset(c,0,sizeof(c));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

F.Binary String Reconstruction

题意

构造一个序列满足有 $n_0$个00,有 $n_1$ 个01/10,有 $n_2$ 个11的序列

题解

先构造00,再构造11,然后10即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 3e5 + 7;
const int INF = 0x7fffffff;
int a[MAXN], b[MAXN], c[MAXN];
void solve() {
    int n0,n1,n2;
    cin >> n0 >> n1 >> n2;
    if(n1 == 0){
    	if(n0 == 0){
    		for(int i = 0;i < n2+1;i++)
            	cout << 1;
		} else {
			for(int i = 0;i < n0+1;i++)
            	cout << 0;
		}
        cout << endl;
        return ;
    }
    for(int i = 0;i < n0+1;i++)
        cout << 0;
    for(int i = 0;i < n2+1;i++)
        cout << 1;
    n1--;
    int cnt = 1;
    while(n1 > 0){
        if(cnt % 2 == 1)
            cout << 0;
        else
            cout << 1;
        cnt++;
        n1--;
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

G.Binary String Reconstruction

题意

构造序列满足任意相邻数字之差的绝对值在区间 $[2,4]$ 中。

题解

$2n+1,2n−1,…,5,3,1,4,2,6,8,…2n−2,2n$ .注意1,2,3无解

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MAXN = 3e5 + 7;
const int INF = 0x7fffffff;
int a[MAXN], b[MAXN], c[MAXN];
void solve() {
    int n;
    cin >> n;
    if(n < 4){
        cout << -1 << endl;
        return ;
    }
    for(int i = n;i >= 1;i--)
        if(i % 2)
            cout << i << " ";
    cout << "4 2 ";
    for(int i = 6;i <= n;i+=2)
        cout << i << " ";
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}