A. Domino Disaster
2分钟签到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
string s;
cin >> s;
for(auto x : s){
if(x == 'U') cout << 'D';
else if(x == 'D') cout << 'U';
else cout << x;
}
cout << endl;
}
return 0;
}
|
B. MEXor Mixup
题意
现在有一个未定数组，它的$Mex$是$a$, 它所有元素的异或和是$b$，问这个数组最少有几个元素。$(0<a\leq 3e5,0\leq b\leq 5e4)$.
分析
由于$Mex=a$，故$[0,a-1]$必定出现。
讨论特殊情况：当$a=1,b=0$，这个数组是$\{0\}$，共一个元素。
其余的情况，首先我们对$[0,a-1 ]$做异或和，得出来一个数$x$。此时我们可以再取一个数$y$，使得$x\bigoplus y = b$. 但是要注意，这个$y$可能就是$a$. 根据异或的性质——$x\bigoplus y = z \Harr x \bigoplus z = y$.
故我们可以求出$y=x\bigoplus b$. 如果求出来的 $y$ 和 $a$ 不相等，那么我们的数组就是$[0,a-1]$加上 $y$，共 $a + 1$ 个元素；如果$y==a$，那么我们不可以直接给数组加上$a$，但一定可以通过另外两个不等于$a$的数作异或得到$a$，故数组共$a+2$个元素。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 3e5 + 10;
int pre[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
pre[0] = 0;
fors(i, 1, maxn - 1) pre[i] = (pre[i - 1] ^ i);
while(t--)
{
int a, b;
cin >> a >> b;
if(a == 1 && b == 0){
cout << 1 << endl;
}
else{
int sum = pre[a - 1];
if(sum == b) cout << a << endl;
else if((sum ^ a) == b) cout << a + 2 << endl;
else cout << a + 1 << endl;
}
}
return 0;
}
|
C. Carring Condrum
题意
作有着错误进位方式的竖式运算，每次遇到进位都会进两位而不是进一位。例如$1+9$，进位得到的1会放在百位而不是十位。
现在给出一个数$n$，问有多少对有序数对$(a,b)$，$0<a,b<n$，在经过这种错误运算方式之后会得到$n$.
分析
因为每次都进两位，故奇数位和偶数位之间互相不影响，可以把它们分开来看。
例如，2021这个数，我们可以拆成22和1.
其中，加和得到22的有序数对共23对（$a$从$0$到$22$），加和得到1的有序数对共2对。把这奇偶的方法合并，那么总共有$23×2=46$个数对。
但是，由于2021这个数不能拆成$(0,2021)$和$(2021,0)$，所以要减去2个，最终答案是44.
所以，若拆分后奇数位数字是$x$,偶数位的是$y$，答案显然是$(x+1)(y+1)-2$.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 3e5 + 10;
int pre[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
int a = 0, b = 0;
for(int i = 0; i < s.size(); ++i){
if(i & 1) a = a * 10 + s[i] - '0';
else b = b * 10 + s[i] - '0';
}
a++, b++;
cout << a * b - 2 << endl;
}
return 0;
}
|
