Codeforces Round #742 (Div. 2)
B. MEXor Mixup
题目描述：
输入a和b，让你造一个数组，使得这个数组内所有数异或和为b，且这个数组中未出现的最小的非负数是a
思路：
因为最小非负数是a，也就是说最少要用a-1个数，且a是不可用的
我们可以维护一个前缀异或和为tr[i]，表示从0异或到i的值
- 如果tr[a – 1] = b，就说明用0到a-1就可以了，输出a即可
- 如果tr[a – 1] ^b = a，就说明要将tr[a – 1]异或上a才能变成b，但是由于a不可选，所以需要用两个数才能异或成功，也就是a+2
- 如果tr[a – 1] ^ b != a，就说明只需要一个数就可以异或上tr[a – 1]就可以造出b，也就是输出a+1即可
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 400000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int t, n;
int a, b;
int tr[MAX];
void work(){
sdd(a, b);
if((tr[a - 1] ^ b) == a)cout<<a + 2<<endl;
else if(tr[a - 1] == b)cout<<a<<endl;
else cout<<a + 1<<endl;
}
void init(){
for(int i = 1; i < MAX; ++i){
tr[i] = tr[i - 1] ^ i;
}
}
int main(){
sd(t);
init();
while (t--) {
work();
}
return 0;
}
C. Carrying Conundrum
题目描述：
正常的十进制加法进位是向上一位进1，但是现在改为向上上位进1，例如1 + 9 = 100，现在给你一个n，问你有多少对(a, b)在刚刚的条件下使得a+b = n，（1，9）与（9，1）算两种情况，a和b不能为0
思路：
这个题很妙，真是妙妙屋里，妙蛙种子吃了妙脆角，妙到家了
因为是向上上位进1，也就是说奇数进到奇数，偶数进到偶数，那就将奇偶分开，比如2021，拆成01与22，也就是1与22，考虑凑1有两种方法，1与0，0与1，凑22就有23种方法，也就是说凑m，有m+1种方法。
你可能会怀疑，不是说不能用0么，对，不过这个分奇偶构造出来的数只有两种情况为0，也就是n与0，0与n，其他情况都是在数里面的，不是单独的0，是可以造的，比如：1012，拆成11，02，11可以用11 与 00来造，假设2用01与01来造，那就是1011与0001等，虽然里面选了0，但是却不影响，如果有影响，那只影响上面说的那两种极端情况，只需要-2就行
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 10000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int t, n;
void work(){
sd(n);
vector<int>v;
while (n) {
v.push_back(n % 10);
n /= 10;
}
reverse(v.begin(), v.end());
int a, b;
a = b = 0;
for(int i = 0; i < v.size(); i += 2){
a = a * 10 + v[i];
}
for(int j = 1; j < v.size(); j += 2){
b = b * 10 + v[j];
}
cout<<(a + 1) * (b + 1) - 2<<endl;
}
int main(){
sd(t);
while (t--) {
work();
}
return 0;
}
D. Expression Evaluation Error
题目描述：
一个十进制数n，拆成m个十进制数，问怎么拆能使得这m个数在11进制下的和最大
思路：
对于任意一个进制的数来说，肯定是越高位数量越多值越大，那这个也一样，假设这个n的所有位的和是num，如果m<=num，就说明可以直接按十位十位来拆就行，比如n=97，m=10，那我们就可以拆成9个10和1个7，或者7个1，2个10，1个70都可以，反正是按将每一位都拆成十的次幂，然后随便找出m-1个输出，剩下的就全加起来输出即可。如果m>num，就说明肯定会有亏损，不能达到上面那种最最优的结果，也就是需要拆位来凑，因为高位的值大，低位的值小，所以肯定得拆值小的，也就是从倒数第二位，也就是十位开始拆，每次拆的时候就给这位减1，给这位后面一位+10，然后判断此时num于m的关系，如果还是m>num，那就继续从低位拆，直到m<=num，那就和上面一样了，按上面的方法输出即可
思想还是挺好想的，起码比c好多了，不过写起来不是特别舒服，有点无从下手的感觉
我用的是优先队列(小根堆)来解决输出的问题，拆成十的次幂来存，输出前m-1个，再将队列里面所有的加起来输出
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 400000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))
typedef long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int t, n, m, cnt;
vector<int>v;
int getnum(){
int num = 0;
for(int i = 0; i < v.size(); ++i)num += v[i];
return num;
}
void pp(){
priority_queue<int, vector<int>, greater<int> >q;
int p = 1;
for(int i = (int)v.size() - 1; i >= 0; --i){
int x = v[i];
while (x--) {
q.push(p);
}
p *= 10;
}
--m;
while (m--) {
cout<<q.top()<<' ';
q.pop();
}
int sum = 0;
while (!q.empty()) {
sum += q.top();
q.pop();
}
cout<<sum<<endl;
}
void work(){
v.clear();
sdd(n, m);
while (n) {
v.push_back(n % 10);
n /= 10;
}
reverse(v.begin(), v.end());
while (getnum() < m) {
for(int i = (int)v.size() - 2; i >= 0; --i){
if(v[i]){
v[i + 1] += 10;
--v[i];
break;
}
}
}
pp();
}
int main(){
sd(t);
while (t--) {
work();
}
return 0;
}
