Codeforces Round #640 (Div. 4)
A.Sum of Round Numbers
题意：
把一个数拆成若干个除首位都是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
题意：
构造一个长度为的序列要求满足所有元素奇偶性相同且和为
。
题解：
仅为偶数且
或
奇偶性相同且
时可以满足。
#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
题意：
求第小个不能被
整除的整数。
题解：
每个区间内为个数。除一下算出来是第几个区间的第几个数乘上原长度即可。
#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
题意：
如果数组里的某个数等于该数组某一个连续区间内的所有数字之和，那么该数字即为特殊点。求整个数组的特殊点数量。
题解：
用前缀和求出所有连续区间的和，遍历数组判断是否存在值相等的区间即可
#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
题意：
要求构造一个二进制串，使得所有长度为的子序列满足：
的个数分别为
,
,
题解：
因为没有限制二进制串的长度，所以可以先后
最后
。注意
和
以及
和
交界处会多出两个
序列。要注意特判
为
的情况，由于题目保证一定有解，所以不用担心
时
同时不为
的情况。
#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
题意：
用构造一个长度为
的序列满足任意相邻数字之差的绝对值在区间
中。
题解：
。其中当
时无解
#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();
}