活久见，Codeforces出了Div4，晚上睡早了后来虚拟参赛的。题目较为简单，构造，思维为主
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;
}