[Codeforces Round #640 (Div. 4)]A,B,C,D,E,F,G题解
[Codeforces Round #640 (Div. 4)]题解
第一次出现div4去凑凑热闹玩玩，下面是题解。
A-Sum of Round Numbers
题意：给定n，判断n由几个Round Number（除了数字第一位其他都是0的数字）构成，输出个数和这几个Round Numbers
思路：从后往前一位一位拆就ok了 当然你想从前往后也可以
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
long long ans[500];
int main(void) {
long long t;
scanf("%lld", &t);
while (t--) {
long long cnt = 0;
long long n;
long long c = 0;
scanf("%lld", &n);
while (n) {
if (n % 10 != 0) {
ans[cnt++]=(n % 10)*pow(10,c);
}
c++;
n /= 10;
}
printf("%lld\n", cnt);
for (int i = 0; i < cnt - 1; i++) {
printf("%lld ", ans[i]);
}
printf("%lld\n", ans[cnt - 1]);
}
return 0;
}B-Same Parity Summands
题意：给一个数字n和k，求这个数字能不能由k个奇数或者k个偶数构成。
思路：先填k-1个1或2，再看最后剩下的数是否大于零且为同奇/偶数就可。
代码：
#include<cstdio>
int main(void) {
int t;
scanf("%d", &t);
while (t--)
{
int n, k;
scanf("%d%d", &n, &k);
int temp = n - k + 1;
if (temp > 0&&temp&1) {
printf("YES\n");
for (int i = 0; i < k - 1; i++) {
printf("1 ");
}
printf("%d\n", temp);
continue;
}
temp = n - (k - 1) *2;
if (temp > 0 && temp % 2 == 0) {
printf("YES\n");
for (int i = 0; i < k - 1; i++) {
printf("2 ");
}
printf("%d\n", temp);
}
else {
printf("NO\n");
}
}
return 0;
}C-K-th Not Divisible by n
题意：给定n和k，输出第k个不能被n整除的数字
思路：视n为一个周期，每个周期内必定有n-1个数字不能被n整除，跳过前面的整个k/n-1周期，然后开始加上余数即可，注意，如果余数为零，则答案为(k/n-1)*n-1，需要回退一步
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
int main(void) {
long long t;
scanf("%lld", &t);
while (t--) {
long long n,k;
scanf("%lld %lld", &n,&k);
long long c = n - 1;
long long be = (k / c)*n;
long long mo = k % c;
if (!mo) {
be--;
}
printf("%lld\n", mo + be);
}
return 0;
}D-Alice, Bob and Candies
题意：长度为n的糖果数列，每个糖果有不同的sweet值。Alice从左边开始吃，Bob从右边开始吃，Alice先吃，两人的规则就是本回合吃的要比上个回合（即对方）吃的sweet要多，最后吃完为止。输出回合数和每人吃到的sweet值即可。
思路：模拟即可
代码：
#include<cstdio>
#include<cstring>
typedef long long ll;
ll can[1005];
int main(void) {
ll t;
scanf("%lld", &t);
while (t--) {
ll n;
scanf("%lld", &n);
for (ll i = 0; i < n; i++) {
scanf("%lld", &can[i]);
}
ll a = 0, b = 0, l = 0,r=n-1,last=0,s1=0,s2=0;
ll cnt = 0;
for (; l <= r;) {
if (cnt & 1) {
//Bob
if (s2 <= last) {
s2 += can[r--];
}
else {
last = s2;
b += s2;
s2 = 0;
cnt++;
}
}
else {
//Alice
if (s1 <= last) {
s1 += can[l++];
}
else {
last = s1;
a += s1;
s1 = 0;
cnt++;
}
}
}
//Update last move
if (cnt & 1) {
b += s2;
cnt++;
}
else {
a += s1;
cnt++;
}
printf("%lld %lld %lld\n", cnt, a, b);
}
return 0;
}E-Special Elements
题意：给定n长度的数组，定义如果在数组内存在[l,r]（l!=r)区间使得
∑ i = l r a i = a k \sum^{r}_{i=l}a_i=a_k i=l∑rai=ak
则称k元素为Special Element，求这个数组有几个Special Elements
思路：滚动储存枚举即可，注意没有元素>n，所以枚举到>n可以直接跳出，这是个重要的剪枝条件
#include<cstdio>
#include<cstring>
using namespace std;
short a[8001];
bool vis[8001];
int main(void) {
int t;
scanf("%d", &t);
while (t--) {
memset(vis, 0, sizeof(vis));
int n;
scanf("%d", &n);
short sum = 0, te;
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
}
for (int i = 0; i < n; i++) {
sum = a[i];
for (int k = i + 1; k < n; k++) {
sum += a[k];
if (sum > n) {
break;
}
vis[sum] = 1;
}
}
short cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[a[i]]) {
cnt++;
}
}
printf("%d\n", cnt);
}
return 0;
}F-Binary String Reconstruction
题意：给定三个数字a,b,c,构建一个01字符串，其中包含a个00，b个01，c个11
思路：先存到字符串a个00，之后1，0交替构建01，然后构建11时注意，如果之前构建01时字符串末尾是0，则要把这个0删掉，在字符串前加个1，然后再构建11
代码：
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string s;
int main(void) {
int a, b, c;
int t;
scanf("%d", &t);
while (t--)
{
s.clear();
bool first = true;
scanf("%d%d%d", &a, &b, &c);
if (a--) {
s += "00";
first = false;
}
while (a > 0) {
a--;
s += "0";
}
int k = first;
while (b--) {
if (first) {
s += "01";
first = false;
continue;
}
first = false;
if (k & 1) {
s += "0";
k++;
}
else {
s += "1";
k++;
}
}
bool fi = false;
while (c--) {
if (first) {
s += "11";
first = false;
continue;
}
if (k % 2 == 0) {
//the end of string is 0
if (!fi) {
s.pop_back();
s = "1" + s;
fi = true;
}
s += "1";
}
else {
s += "1";
}
}
cout << s << endl;
}
return 0;
}G-Special Permutation
大水题构造。。。比赛时候还没看这个题。
题意：给定n，求在由1-n的构成的排列中，存不存在一种排列，使得每个相邻元素相差在[2,4]的区间内
思路：如果长度为1-3，显然不能满足条件。如果>3，我们构造前四个元素符合条件的排列，然后就轮流前后插就ok了。
代码：
#include<iostream>
#include<string>
using namespace std;
string s;
int main(void) {
int t;
cin >> t;
while (t--) {
s.clear();
int n;
cin >> n;
if (n < 4) {
cout << "-1" << endl;
continue;
}
s = "3 1 4 2 ";
for (int i = 5; i <= n; i++) {
if (i & 1) {
s += to_string(i) + " ";
}
else {
s =to_string(i) + " " + s;
}
}
s.pop_back();
cout << s << endl;
}
return 0;
}总结
题目难度整体简单，适合刚刚接触的选手和老年人找信心（显然我是后者：P
