A.Sum of Round Numbers

题意：

把一个数拆成若干个除首位都是0的数字的和

题解：

取出各位上的数判断是否为 $0$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    vector<int> v;
    v.clear();
    int n, base = 1;
    scanf("%d", &n);
    while (n)
    {
        if (n % 10)
            v.push_back(n % 10 * base);
        n /= 10;
        base *= 10;
    }
    printf("%d\n", v.size());
    for (auto i : v)
        printf("%d ", i);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Same Parity Summands

题意：

构造一个长度为 $k$ 的序列要求满足所有元素奇偶性相同且和为 $n$ 。

题解：

仅 $n$ 为偶数且 $n≥2k$ 或 $n,k$ 奇偶性相同且 $n≥k$ 时可以满足。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    if (!(n & 1) && (n >= (k << 1)))
    {
        puts("YES");
        for (int i = 1; i < k; i++)
            printf("2 ");
        printf("%d\n", n - 2 * (k - 1));
        return;
    }
    if (!((n - k) & 1) && (n >= k))
    {
        puts("YES");
        for (int i = 1; i < k; i++)
            printf("1 ");
        printf("%d\n", n - k + 1);
        return;
    }
    puts("NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.K-th Not Divisible by n

题意：

求第 $k$ 小个不能被 $n$ 整除的整数。

题解：

每个区间内为 $n−1$ 个数。除一下算出来是第几个区间的第几个数乘上原长度即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll a = k / (n - 1), b = k % (n - 1);
    printf("%lld\n", b ? a * n + b : a * n - 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Alice, Bob and Candies

题意：

A从左边取物，B从右边取物。要求当前人取物总和尽可能小，但要求至少大于另一个人上一次取物总和。最后不够时取完游戏结束。求取物次数以及A,B的取物总和。

题解：

用双指针模拟即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, a[maxn];
void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int l = 1, r = n, cnt = 0, suml = 0, sumr = 0, lst = 0;
    while (l <= r)
    {
        int now = 0;
        while (l <= r && now <= lst)
            now += a[l++];
        cnt++, suml += now, lst = now, now = 0;
        if (l > r)
            break;
        while (l <= r && now <= lst)
            now += a[r--];
        cnt++, sumr += now, lst = now, now = 0;
    }
    printf("%d %d %d\n", cnt, suml, sumr);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Special Elements

题意：

如果数组里的某个数等于该数组某一个连续区间内的所有数字之和，那么该数字即为特殊点。求整个数组的特殊点数量。 $(1 \leq a_i \leq n)$

题解：

用前缀和求出所有连续区间的和，遍历数组判断是否存在值相等的区间即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 8e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], pre[maxn], n;
bool check[maxn];
void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), check[i] = false;
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + a[i];
        for (int j = 0; j < i - 1; j++)
            if (pre[i] - pre[j] <= n)
                check[pre[i] - pre[j]] = true;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (check[a[i]])
            ans++;
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

F.Binary String Reconstruction

题意：

要求构造一个二进制串，使得所有长度为 $2$ 的子序列满足： $(0,0),(0,1 /1,0),(1,1)$ 的个数分别为 $n0$ , $n1$ , $n2$

题解：

因为没有限制二进制串的长度，所以可以先 $(0,0)$ 后 $(1,1)$ 最后 $(0,1)$ 。注意 $(0,0)$ 和 $(1,1)$ 以及 $(1,1)$ 和 $(0,1)$ 交界处会多出两个 $(0,1 /1,0)$ 序列。要注意特判 $n1$ 为 $0$ 的情况，由于题目保证一定有解，所以不用担心 $n1=0$ 时 $n0,n2$ 同时不为 $0$ 的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 8e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (b == 0)
    {
        if (a)
            for (int i = 0; i <= a; i++)
                putchar('0');
        if (c)
            for (int i = 0; i <= c; i++)
                putchar('1');
        puts("");
        return;
    }
    for (int i = 0; i <= a; i++)
        putchar('0');
    for (int i = 0; i <= c; i++)
        putchar('1');
    for (int i = 0; i < b - 1; i++)
        printf("%d", i % 2);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

G.Special Permutation

题意：

用 $1 \sim n$ 构造一个长度为 $n$ 的序列满足任意相邻数字之差的绝对值在区间 $[2,4]$ 中。

题解：

$2n+1,2n−1,…,5,3,1,4,2,6,8,…2n−2,2n$ 。其中当 $n=1,2,3$ 时无解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 8e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    scanf("%d", &n);
    if (n <= 3)
        puts("-1");
    else
    {
        for (int i = n; i >= 1; i--)
            if (i & 1)
                printf("%d ", i);
        printf("4 2 ");
        for (int i = 6; i <= n; i += 2)
            printf("%d ", i);
        puts("");
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #640 (Div. 4)