涵盖知识点：思维、构造（div.4，i了i了）
比赛链接：传送门
A - Sum of Round Numbers
题意： 把一个数拆成若干个除首位都是(0)的数字的和
题解： (●'◡'●)
Accept Code：
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
vector<int> v;
v.clear();
int n,base=1;
cin>>n;
while(n){
if(n%10){
v.push_back(n%10*base);
}
n/=10;
base*=10;
}
cout<<v.size()<<"
";
for(auto i:v){
cout<<i<<" ";
}
cout<<"
";
}
return 0;
}
B - Same Parity Summands
题意： 构造(k)长序列要求满足所有元素奇偶性相同且和为(n)。
题解： 仅(n)为偶数且(nge2k)或(n,k)奇偶性相同且(nge k)时可以满足。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int n,k;
cin>>n>>k;
if(!(n&1)&&(n>=(k<<1))){
puts("YES");
for(int i=1;i<k;i++)cout<<2<<" ";
cout<<n-2*(k-1)<<"
";
continue;
}
if(!((n-k)&1)&&(n>=k)){
puts("YES");
for(int i=1;i<k;i++)cout<<1<<" ";
cout<<n-k+1<<"
";
continue;
}
puts("NO");
}
return 0;
}
C - K-th Not Divisible by n
题意： 无限长序列元素为从小到大排列的不能被(n)整除的数。求第(k)个数。
题解： 每个区间内为(n-1)个数。除一下算出来是第几个区间的第几个数乘上原长度即可。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
int main(){
int t;cin>>t;
while(t--){
int n,k;
cin>>n>>k;
ll a=k/(n-1),b=k%(n-1);
ll ans;
if(b==0)ans=a*n-1;
else ans=a*n+b;
cout<<ans<<"
";
}
return 0;
}
D - Alice, Bob and Candies
题意： A从左边取物，B从右边取物。要求当前人取物总和尽可能小，但要求至少大于另一个人上一次取物总和。最后不够时取完游戏结束。求取物次数以及A,B的取物总和。
题解： 暴力 前缀 双指针O(∩_∩)O
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn=1010;
int a[maxn];
int main(){
int t;cin>>t;
while(t--){
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,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;
}
cout<<cnt<<" "<<suml<<" "<<sumr<<"
";
}
return 0;
}
E - Special Elements
题意： 如果数组里的某个数等于该数组某一个区间内的所有数字之和，那么该数字即为特殊点。求整个数组的特殊点数量。
题解： 暴力 前缀 check (￣▽￣)"
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn=8010;
int a[maxn],pre[maxn];
bool check[maxn];
int main(){
int t;cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>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++;
cout<<ans<<"
";
}
return 0;
}
F - Binary String Reconstruction
题意： 要求构造一个二进制串的，使得所有长度为(2)的子序列满足：(1)的数量分别为(0,1,2)的个数为(n_0,n_1,n_2).
题解： 先(00)后(11)最后(01)。注意(00,11,01)交界处会多出两个(n_1)序列。以及特判(n_1)为(0)的情况（WA惨），由于题目保证一定有解，所以不用担心(n_1=0)时(n_0,n_2)同时不为(0)的情况。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn=8010;
int a[maxn],pre[maxn];
bool check[maxn];
int main(){
int t;cin>>t;
while(t--){
int a,b,c;
cin>>a>>b>>c;
if(b==0){
if(a)for(int i=0;i<a+1;i++)cout<<0;
if(c)for(int i=0;i<c+1;i++)cout<<1;
cout<<"
";
continue;
}
for(int i=0;i<a+1;i++)cout<<0;
for(int i=0;i<c+1;i++)cout<<1;
for(int i=0;i<b-1;i++)cout<<i%2;
cout<<"
";
}
return 0;
}
G - Special Permutation
题意： 构造序列满足任意相邻数字之差的绝对值在区间([2,4])中。
题解： (2n+1,2n-1,ldots ,5,3,1,4,2,6,8,ldots2n-2,2n).注意(1,2,3)无解。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn=8010;
int a[maxn],pre[maxn];
bool check[maxn];
int main(){
int t;cin>>t;
while(t--){
int n;
cin>>n;
if(n<4)puts("-1");
else{
for(int i=n;i>=1;i--)if(i&1)cout<<i<<" ";
cout<<"4 2 ";
for(int i=6;i<=n;i+=2)cout<<i<<" ";
cout<<"
";
}
}
return 0;
}