目录
A. Sum of Round Numbers
将某个整数，分解为最少个数的形如x000的数之和(1 <= x <= 9,x右侧0的个数 >= 0).
- 直接从个位开始拆，当某位上数字非0时记录。
cin >> t;
while(t--){
idx = 0,a = 1;
cin >> n;
while(n){
if(n % 10) book[idx++] = (n % 10) * a;
a *= 10;
n /= 10;
}
cout << idx << endl;
for(int i = 0; i < idx; i++){
cout << book[i] << ' ';
}
if(t) cout << endl;
}
B. Same Parity Summands
给你一个整数n，要求拆成k个奇数或者k个偶数的和
- n为奇数，只有奇数才可以凑出来
- 判断k的奇偶性，k 是否大于n，前k - 1个奇数使用1，计算最后一个奇数的值
- n为偶数
- 偶数个奇数 - k是否大于n,前k - 1个奇数使用1，计算最后一个奇数的值
- 偶数 -- 判断2 * k是否大于n，前k - 1个偶数使用2，计算最后一个偶数
cin >> t;
while(t--){
cin >> n >> k;
if(n & 1){//奇数 奇数
if(k & 1 && k <= n){
cout << "YES" << endl;
for(int i = 0; i < k - 1; i ++) cout << "1 ";
cout << n - k + 1 << endl;
}else cout << "NO" << endl;
}else{
if(2 * k <= n){//偶数 奇数个 只能用偶数 偶数个 均可
cout << "YES" << endl;
for(int i = 0; i < k - 1; i++) cout << "2 ";
cout << n - (k - 1) * 2 << endl;
}else if(!(k & 1) && k <= n){
cout << "YES" << endl;
for(int i = 0; i < k - 1; i++) cout << "1 ";
cout << n - k + 1 << endl;
}else cout << "NO" << endl;
}
}
C.K-th Not Divisible by n
输入n,寻找第k个不能被n整除的数
- 从1开始，每n个数一组，每组中均有n - 1个数不可以被n整除
- 当k可以整除n - 1，第k个为 n * k - 1
- 第k个为k + i (i = k / (n - 1)): i * n + k - i * (n - 1) = k + i
cin >> t;
while(t--){
cin >> n >> k;
i = k / (n - 1);//每n个数you n-1个
if(i * (n - 1) == k) cout << n * i - 1 << endl;
else cout << k + i << endl;
}
D. Alice, Bob and Candies
模拟，a and b每次吃的糖果总大小要最大且吃的糖果个数尽可能少。
cin >> t;
while(t--){
cin >> n;
vector<int> ar(n);
for(int i = 0;i < n; i++) cin >> ar[i];
i = st = 0;//st 吃糖果次数 i j :a b的索引
j = n - 1;
s_a = s_b = mx = 0;//s_a,s_b:a,b吃的所有糖果的总大小
while(i <= j){
a = 0;//a这一次吃的糖果总大小
++st;
for(; i <= j && a <= mx; i++) a += ar[i];
s_a += a;
if(a > mx) mx = a;
if(i > j) break;
b = 0;//b
++st;
for(; j >= i && b <= mx; j--) b += ar[j];
s_b += b;
if(b > mx) mx = b;
if(i > j) break;
}
cout << st << ' ' << s_a << ' ' << s_b << endl;
}
E.Special Elements
一个数组中，存在一些特殊元素：数组中存在一些区间和 == a[i];求出数组中特殊元素个数。
- 1 <= n <= 8000,1 <= a[i] <= n
- n最大直到8000，所以O(n^2)以内的算法均可。
- 使用前缀和，直接计算所有的区间和，同时判断是否 <= n，若是，则记录下来(记录数组范围 <= n)
- 遍历数组，计算数组中有多少个元素被记录
int ans,t,v,n,a[8010],s[8010],book[8010];//需要处理的最大范围：[1,8000]
//数据量很小，暴力+前缀和 记录所有的长度大于2的子序列和 找符合条件的
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
ans = s[0] = 0;
memset(book,0,sizeof(book));
cin >> n;
for(int i = 1; i <= n; i++){//索引从1开始，避免处理边界问题
cin >> a[i];
if(i > 1){
s[i] = s[i - 1] + a[i];
for(int j = 0; j < i - 1; j++){//r - l >= 2
v = s[i] - s[j];
if(v <= n && !book[v]) book[v] = 1;
}
}else s[i] = a[i];
}
for(int i = 1; i <= n; i++) if(book[a[i]]) ++ans;
cout << ans << endl;
}
return 0;
}
F. Binary String Reconstruction
输入n0,n1,n2分别代表"00","01","11"串的个数。构造含有这些子串的01串。
-
首先，如果n1 == 0。结果只会是00.. or 11.. 串（n0 +1 or n2 + 1个）
-
n1不为0时，先生成00串(n0 + 1个 0),再加上01串(n0为0,先添加一个0；交替添加n1个 1 or 0)
-
最后，添加11串。在之前生成的字符串中找到最后一个1所在位置，插入n2个1。(插入到其它1所在的位置也可以)
string s;
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
cin >> n0 >> n1 >> n2;
if(!n1){//不存在01则n0 or n1有一个也为0
if(!n0) cout << string(n2 + 1,'1');//n2 + 1
else cout << string(n0 + 1,'0');//n0 + 1
cout << endl;
continue;
}
s = "";
if(n0) s = string(n0 + 1,'0');
//01010... n1奇偶性不同最终结尾数字不同 -- 把11串插到1相邻位置中间
if(!n0) s += '0';//n0为0,补一个0
for(int i = 0; i < n1; i++){
if(i & 1) s += '0';
else s += '1';
}
if(n2){
string a = string(n2,'1');
//11串有n2对 n2 + 1个
//for(int i = 0; i < n2; i++) a += '1';
if(s[s.length() - 1] == '1') s += a;
else s.insert(s.length() - 2,a);
}
cout << s << endl;
}
return 0;
}
G. Special Permutation
长为n的数组中，1~n每个数字只出现一次，在这个数组中，相邻元素差的绝对值的范围[2,4]。
- 贪心：
- n < 4，无解
- 从大到小输出小于等于n的所有奇数。
- 输出“4 2”
- 输出所有小于等于n的偶数
- method2：:先输出偶数，但是n == 4的时候需要特判，之后输出"5,1,3",其它奇数升序
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
cin >> n;
if(n < 4) cout << "-1";
else{
s = n;
if(!(s & 1)) --s;//先奇数
while(s > 0){
cout << s << ' ';
s -= 2;
}
cout << "4 2";
s = 6;
while(s <= n){
cout << ' ' << s;
s += 2;
}
}
cout << endl;
}
return 0;
}