CDZSC_2022寒假个人训练赛21级(2)

A

题解：输出n, 1, 2, 3, 4…即可。

#include<bits/stdc++.h>

using namespace std;

void solve() {
    
	int n;
	scanf("%d", &n);
	printf("%d", n);
	for (int i = 2; i <= n; i++)
		printf(" %d", i - 1);
	printf("\n");
}

signed main() {
    
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

B

题解：首先能想到符合条件的数很少，总共就81个；所以直接枚举这些数去判断是否小于等于n即可。

#include<bits/stdc++.h>

using namespace std;

void solve() {
    
	int n;
	scanf("%d", &n);
	int ans = 0;
	for (int i = 1; i <= 9; i++) {
    
		int x = 0;
		for (int j = 1; j <= 9; j++) {
    
			x = x * 10 + i;
			if (n >= x) ans++;
		}
	}
	printf("%d\n", ans);
}

signed main() {
    
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

C

题解：可以想象一下方块右移的过程，比如：
4 2 右移后–> 2 4
实际上就是两个数交换了位置，那么答案就是排序之后的数组。

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];

signed main() {
    
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
    
		if (i == 1) printf("%d", a[i]);
		else printf(" %d", a[i]);
	}
	printf("\n");
	return 0;
}

D

题解：逆向思维一下，我们可以从b往a去推，那么b的操作也是两种

1. b是偶数的前提下除2
2. b的最后一位是1的前提下去掉最后一位

这两种操作是互相独立的，所以b可以反复去做这两种操作直到没法操作或者b<=a为止，最后判断b是否等于a即可。

#include<bits/stdc++.h>

using namespace std;

signed main() {
    
	int a, b;
	scanf("%d%d", &a, &b);
	vector<int> ans;
	while (b > a) {
    
		if (b & 1) {
    
			if (b % 10 == 1) {
    
				b /= 10;
				ans.push_back(10);
			}
			else break;
		}
		else {
    
			b >>= 1;
			ans.push_back(2);
		}
	}
	reverse(ans.begin(), ans.end());
	if (a == b) {
    
		printf("YES\n");
		printf("%d\n", ans.size() + 1);
		printf("%d", a);
		for (auto x : ans) {
    
			if (x == 10) a = a * 10 + 1;
			else a <<= 1;
			printf(" %d", a);
		}
	}
	else {
    
		printf("NO\n");
	}
	return 0;
}

E

题解：可以先确定一个最小值，然后删掉比它小的数和与最小值差值大于d的数得到答案。以数组里每一个数都为最小值做一遍，答案取最小值即可。

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];

signed main() {
    
	int n, d;
	scanf("%d%d", &n, &d);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	int ans = n;
	for (int i = 1; i <= n; i++) {
    
		int cnt = n - 1;
		for (int j = i + 1; j <= n; j++)
			if (a[j] >= a[i] && a[j] - a[i] <= d) cnt--;
		ans = min(ans, cnt);
	}
	printf("%d\n", ans);
	return 0;
}

F

知识点：二进制的理解

题解：首先将n变成二进制形式，从高位往低位拆，看一下能不能拆到n的每一位之和等于k，比如题目第一个样例：
9 4

9 --> 1001
sum(所有位数之和) = 2

1001 --> 0201
sum = 3

0201 --> 0121
sum = 4

0121 = 0 * 2³ + 1 * 2² + 2 * 2¹ + 1 * 2⁰

#include<bits/stdc++.h>

using namespace std;
const int N = 100;
int a[N], tot;

signed main() {
    
	int n, k;
	scanf("%d%d", &n, &k);
	int sum = 0;
	while (n) {
    
		if (n & 1) sum++, a[++tot] = 1;
		else a[++tot] = 0;
		n >>= 1;
	}
	while (sum < k) {
    
		if (tot == 1) break;
		a[tot]--;
		a[tot - 1] += 2;
		sum++;
		if (a[tot] == 0) tot--;
	}
	if (sum != k) printf("NO\n");
	else {
    
		printf("YES\n");
		for (int i = 1; i <= tot; i++) {
    
			for (int j = 1; j <= a[i]; j++)
				printf("%d ", (1 << (i - 1)));
		}
		printf("\n");
	}
	return 0;
}

G

题解：首先我们按奇数和偶数把1~n分成两个数组，把奇数数组倒序输出，偶数数组的even[0]和even[1]换一下顺序然后输出即可。
例如：n = 11
odd : 1 3 5 7 9 11 —> 11 9 7 5 3 1
even : 2 4 6 8 —> 4 2 6 8
ans : 11 9 7 5 3 1 4 2 6 8
答案不唯一，网上还有很多构造方法，可自行查找

#include<bits/stdc++.h>

using namespace std;

void solve() {
    
	int n;
	scanf("%d", &n);
	if (n < 4) {
    
		printf("-1\n");
		return;
	}
	else {
    
		vector<int> odd, even;
		for (int i = 1; i <= n; i += 2)
			odd.push_back(i);
		for (int i = 2; i <= n; i += 2)
			even.push_back(i);
		reverse(odd.begin(), odd.end());
		for (int i = 0; i < odd.size(); i++)
			printf("%d ", odd[i]);
		printf("%d %d", even[1], even[0]);
		for (int i = 2; i < even.size(); i++)
			printf(" %d", even[i]);
		printf("\n");
	}
}

signed main() {
    
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}