B. MEXor Mixup
有一未知数组的mex值为a，异或值为b，求数组的最小长度。
由于mex值为a，因此至少需要 [0,a-1] 这a个元素。令前a个元素的异或值为x，
- 若x=b，则只需要前a个元素
- 若x!=b，显然存在一个数y满足x^y=b，但是需要判断y是否是a，即是否会破坏mex条件。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int pre[N];
void solve()
{
int a, b;
scanf("%d%d", &a, &b);
int res = 0;
res = pre[a - 1];
if (res == b)
printf("%d\n", a);
else if ((res ^ b) == a)
printf("%d\n", a + 2);
else
printf("%d\n", a + 1);
}
int main()
{
for (int i = 1; i < N; i++)
pre[i] = pre[i - 1] ^ i;
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}
C. Carrying Conundrum
赛时被C卡到自闭。
Solution I
奇数位进位到奇数位，偶数位进位到偶数位，因此可以将奇偶位分开来考虑，然后用乘法原理计算贡献。
设一个数为ABCDEF，拆成ACE和BDF两个数，单独考虑ACE，求a+b=ACE的方案数，显然方案数为ACE+1。同理 BDF的方案数为BDF+1，答案就是 ( A C E + 1 ) × ( B D F + 1 ) (ACE+1)\times (BDF+1) (ACE+1)×(BDF+1)再减去a为0，b为0 两种情况
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
void solve()
{
string a;
cin >> a;
int s[2], p = 0;
s[0] = s[1] = 0;
for (auto it : a)
{
s[p] = s[p] * 10 + it - '0';
p ^= 1;
}
cout << (s[0] + 1) * (s[1] + 1) - 2 << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Solution II
可以考虑枚举进位的情况。
代码
#include <bits/stdc++.h>
using namespace std;
int num[22];
void solve()
{
string n;
cin >> n;
vector<int> vec(12);
int len = n.size();
for (int i = 0; i < len; i++)
vec[10 - (len - i - 1)] = n[i] - '0';
int ans = 0;
for (int i = 0; i < (1 << 10); i++)
{
if (i % 4)
continue;
vector<int> temp = vec;
bool flag = 1;
int res = 1;
for (int j = 0; j < 10; j++)
{
int p = 10 - j;
if ((1 << j) & i)
temp[p]--;
if ((1 << (j + 2)) & i)
temp[p] += 10;
res *= num[temp[p]];
}
if (flag)
ans += res;
}
printf("%d\n", ans - 2);
}
int main()
{
for (int a = 0; a <= 9; a++)
for (int b = 0; b <= 9; b++)
for (int c = 0; c <= 18; c++)
if (a + b == c)
num[c]++;
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}
D. Carrying Conundrum
对比一下十进制和十一进制
100 10 1
121 11 1
结论：将数放在尽可能的高位上是最优的。
但是又要满足所有数都不为0，因此贪心的将低位的数进行拆分，这样损失的贡献最少。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
int a[N];
int p10[N];
void solve()
{
int s, n;
scanf("%d %d", &s, &n);
for (int i = 1; i <= n; i++)
a[i] = 0;
int num[100];
int p = 0;
while (s)
{
num[++p] = s % 10;
s /= 10;
}
while (1)
{
int sum = 0;
for (int i = 1; i <= p; i++)
sum += num[i];
if (sum < n)
{
for (int i = 2; i <= p; i++)
{
if (num[i])
{
num[i]--;
num[i - 1] += 10;
break;
}
}
}
else
break;
}
int pos = 1;
for (int j = 1; j <= p; j++)
{
while (num[j]--)
{
a[pos++] += p10[j];
if (pos > n)
pos = 1;
}
}
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
printf("\n");
}
void init()
{
p10[1] = 1;
for (int i = 2; i <= 10; i++)
p10[i] = p10[i - 1] * 10;
}
int main()
{
init();
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}
E. Carrying Conundrum
比较显然的线段树维护。
考虑合并两个区间时，怎么维护询问要求的 区间的贡献。
对于最底层、长度为1的区间（单个元素），显然贡献是1，合并两个长度为1的区间，贡献即是两个子区间的贡献和，再加上区间合并带来的新增贡献。只需维护好新增的贡献即可。
考虑维护新增贡献。
假设左区间为1 2 3 1 2 3 。右区间为4 5 1 2。
记左区间的最长的以右端点结束的不下降区间长度为
M
X
R
MX_R
MXR
记右区间的最长的以左端点开始的不下降区间长度为
M
X
L
MX_L
MXL
当左区间的右端点值小于右区间的左端点值时，显然新增贡献为
M
X
R
×
M
X
L
MX_R\times MX_L
MXR×MXL。
那么对于每个区间，还需要维护好MX_L、MX_R。
考虑维护MX_L。（MX_R同理）
还是以上面两个区间为例，现有：
LSON.MX_L=3
LSON.MX_R=3
RSON.MX_R=2
RSON.MX_R=2
要求
FATHER.MX_L
FATHER.MX_R
这个条件总是成立：
FATHER.MX_L=LSON.MX_L
FATHER.MX_R=RSON.MX_R
那么FATHER.MX_L (/FATHER.MX_R)能否进行拓展呢？
当左区间的右端点值小于右区间的左端点值、且LSON.MX_L为LSON的整个区间长度时，才可以进行拓展。R同理。
另外，询问时需要注意的问题：假设询问区间为[5,6]，可能在线段树上询问的是LSON[1,5]，RSON[6,10]，这时候LSON.MX_R和RSON.MX_L就需要和询问区间取一个min
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
struct node
{
int k, l, r, mx_L, mx_R;
long long sum;
//mx_L 从左端点开始 最长的不下降子区间长度
//mx_R 以右端点结束 最长的不下降子区间长度
} tr[N << 2];
void push_up(int k)
{
long long res = 0;
tr[k].mx_L = tr[k << 1].mx_L;
tr[k].mx_R = tr[k << 1 | 1].mx_R;
if (a[tr[k << 1].r] <= a[tr[k << 1 | 1].l]) //考虑连接两个区间
{
res = 1ll * (tr[k << 1].mx_R) * (tr[k << 1 | 1].mx_L);
if (tr[k << 1].mx_L == tr[k << 1].r - tr[k << 1].l + 1) //如果整个左儿子区间都是不下降的，那么可以合并
tr[k].mx_L = tr[k << 1 | 1].mx_L + (tr[k << 1].r - tr[k << 1].l + 1);
if (tr[k << 1 | 1].mx_R == tr[k << 1 | 1].r - tr[k << 1 | 1].l + 1) //如果整个右儿子区间都是不下降的，那么可以合并
tr[k].mx_R = tr[k << 1].mx_R + (tr[k << 1 | 1].r - tr[k << 1 | 1].l + 1);
}
tr[k].sum = tr[k << 1 | 1].sum + tr[k << 1].sum + res;
}
void build(int k, int l, int r)
{
tr[k].l = l, tr[k].r = r;
if (l == r)
{
tr[k].sum = tr[k].mx_L = tr[k].mx_R = 1;
return;
}
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
push_up(k);
}
void change(int k, int pos, int val)
{
if (tr[k].l == tr[k].r)
{
tr[k].sum = tr[k].mx_L = tr[k].mx_R = 1;
return;
}
int mid = tr[k].l + tr[k].r >> 1;
if (pos <= mid)
change(k << 1, pos, val);
else
change(k << 1 | 1, pos, val);
push_up(k);
}
long long query(int k, int l, int r)
{
if (tr[k].l == l && tr[k].r == r)
return tr[k].sum;
int mid = tr[k].l + tr[k].r >> 1;
long long ans = 0;
if (r <= mid)
ans += query(k << 1, l, r);
else if (l > mid)
ans += query(k << 1 | 1, l, r);
else
{
ans += query(k << 1, l, mid);
ans += query(k << 1 | 1, mid + 1, r);
if (a[tr[k << 1].r] <= a[tr[k << 1 | 1].l]) //中间的贡献，注意要和区间大小取min。
ans += 1ll * min(mid - l + 1, tr[k << 1].mx_R) *
min(r - (mid + 1) + 1, tr[k << 1 | 1].mx_L);
}
return ans;
}
void solve()
{
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
while (q--)
{
int opt, l, r;
scanf("%d %d %d", &opt, &l, &r);
if (opt == 1)
{
a[l] = r;
change(1, l, r);
}
else
printf("%lld\n", query(1, l, r));
}
}
int main()
{
solve();
return 0;
}