C – Sasha and a Bit of Relax
其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\)，然而这个运算可以直接移项：因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数，我们只需要在 Trie 树末端维护奇偶计数即可。
其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\)，然而这个运算可以直接移项：因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数，我们只需要在 Trie 树末端维护奇偶计数即可。
很简单，扫描的时候如果所在数位为偶数位，向答案添加当前数位即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
int ans = 0, len;
scanf("%d", &len), scanf("%s", str + 1);
for (int i = 1; i <= len; i++)
if (((str[i] - '0') & 1) == 0)
ans += i;
printf("%d", ans);
return 0;
}
我这个傻逼还搞个多重集容斥恶心自己。
首先分析题意，不难想出转移方程：
\[ dp[i][j] = dp[i-1][j]+\sum_{k = limit[i]}^{j} dp[i-1][k] \]
然后考虑用\(O(n)\)的时间先预处理出前缀和\(dp[i-1][k-1]\)，然后大的减小的\(O(1)\)查询即可。
// M.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110, MAX_K = 1e5 + 200, MOD = 1e9 + 7;
ll n, limit[MAX_N], dp[MAX_N][MAX_K], k, mxk, prefix[MAX_K];
int main()
{
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld", &limit[i]), dp[i][0] = 1;
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
prefix[i] = 0;
for (int j = 1; j <= k + 1; j++)
prefix[j] = prefix[j - 1] + dp[i - 1][j - 1];
for (int j = 1; j <= k; j++)
{
dp[i][j] = dp[i - 1][j] + prefix[j] - prefix[max(0LL, j - limit[i])];
dp[i][j] %= MOD;
}
}
printf("%d", dp[n][k]);
return 0;
}
非常有趣的一道数学题，我们来分析一下。原讲稿：https://comfortablecom.wordpress.com/2017/10/06/jzoj-b%E7%BB%84-10-6-%E6%80%BB%E7%BB%93/
我们先设一种情况的答案为\(S_x\)，显然，可以写成：
\[ S_x = |a_{x_1}-0|+|a_{x_2}-a_{x_1}|+|a_{x_3}-a_{x_2}|+|a_{x_4}-a_{x_3}|+\dots +|a_{x_n}-a_{x_{n-1}}| \]
这一长串的答案其实就是被减数与减数的组合。我们会发现，几乎每一个数都在这个式子中扮演了被减数与减数的角色，除了最后一个元素，即\(a_{x_n}\)。这个元素只充当了一次被减数，仅此而已。
我们考虑\(i\)对答案的贡献。首先，\(i\)作为被减数一共有\(n!\)中可能，其中减数缺了一部分的可能，这一缺失的部分就是\(i\)作为\(a_{x_n}\)的可能数，也就是\((n-1)!\)。之后，考虑在一种序列中\(i\)的贡献。当\(j<i\)时，包括\(0\)，一共有\(i\)个数使\(i\)可以在不变号的情况下减去减数；而，当\(i<j\)时，情况就不同了，一共有\(n-i\)种数是的\(i\)在变号的情况下进行对答案的贡献。部分分析结束，总结为一个式子：
\[ a_i(n-1)!i+(-a_i)(n-1)!(n-i) \]
结合上面我所分析的可能方案数和不同情况下的讨论，请读者用心领悟。
而作为减数其实就是换汤不换药了。只要把正负的两种关系变化一下即可，计算式为：
\[ (-a_i)(n-1)!(n-i)+a_i(n-1)!(i-1) \]
注意，此式中最后一项中的\(i-1\)是因为\(0\)无法作为其被减数而造成的。有那么一点点不对称吧。
// A.cpp
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MAX_N = 100200;
int n, arr[MAX_N];
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
sort(arr + 1, arr + 1 + n);
ll x = 0;
for (int i = 1; i <= n; i++)
x = x + 1LL * arr[i] * (1LL * 4 * i - 1LL * 2 * n - 1);
ll d = gcd(x, n);
printf("%lld %lld", x / d, n / d);
return 0;
}
这道题其实在考场上连斜率式子都推完了，但是因为太懒而且不知道怎么隔着\(k\)进行转移所以弃疗，最后边界忘记检查 50 分傻*暴力都没拿到。
这道题的 DP 方程式可通过一眼法得出，其中需要先进行排序：
\[ dp[i] = min\{ f[j-1]+C+(f[i]-f[j])^2 \}, j-1 \in [0,i-k] \]
之后我们来思考如何进行斜率优化。斜率优化是一个非常常用的 DP 优化手段，建议深入了解。我们设\(k\)为我们想要的最优解，那它一定满足：
\[ f[k-1]+C+(f[i]-f[k])^2 < f[j-1]+C+(f[i]-f[j]))^2, j \in [1, i-k+1], j \neq k \\ (f[k-1]-f[j-1])+(f[k]^2-f[j]^2) < 2f[i](f[k]-f[j]) \]
判断时，注意正负号对不等式的影响。
// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 2e6 + 20000;
const ll INF = (0x3f3f3f3f3f3f3f3f);
ll f[MAX_N], arr[MAX_N], n, k, c, q[MAX_N << 2];
int head = 1, tail = 0;
ll pow(ll num) { return num * num; }
double check(ll a, ll b)
{
return ((f[b - 1] + pow(arr[b])) - (f[a - 1] + pow(arr[a]))) / (2.0 * (arr[b] - arr[a]));
}
void insert(int x)
{
while (head <= tail && arr[q[tail]] == arr[x])
if (f[x - 1] < f[q[tail] - 1])
tail--;
else
return;
while (head < tail && check(q[tail - 1], q[tail]) > check(q[tail], x))
tail--;
q[++tail] = x;
}
int main()
{
freopen("work1.in", "r", stdin);
scanf("%lld%lld%lld", &n, &k, &c);
for (int i = 1; i <= n; i++)
scanf("%lld", &arr[i]);
f[0] = 0;
sort(arr + 1, arr + 1 + n);
for (int i = 1; i < k; i++)
f[i] = INF;
for (int i = k; i <= n; i++)
{
int x = i - k + 1;
insert(x);
while (head < tail && check(q[head], q[head + 1]) < arr[i])
head++;
f[i] = f[q[head] - 1] + c + pow(arr[q[head]] - arr[i]);
}
printf("%lld", f[n]);
return 0;
}
一道线段树的题目（我改题的时候差点下定决心整晚写个 Treap 的版本来搞，最后发现线段树绰绰有余）。我们维护左边极点、右边极点、最长空位长度和最佳停车点。线段树更新的时候选择左区间、合并区间和右区间进行比较即可。
// C.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 200200, INF = 0x3f3f3f3f;
int n, m, tree_l[MAX_N << 2], tree_r[MAX_N << 2], tree_len[MAX_N << 2], tree_pt[MAX_N << 2], park[(int)1e6 + 2000];
int getFirst(int a, int b, int c, int d)
{
if (a > 0)
return a;
if (b > 0)
return b;
if (c > 0)
return c;
if (d > 0)
return d;
return d;
}
void update(int qx, int l, int r, int p)
{
if (l == r && l == qx)
{
tree_l[p] = l, tree_r[p] = r, tree_len[p] = 0, tree_pt[p] = 0;
return;
}
if (qx <= mid)
update(qx, l, mid, lson);
else
update(qx, mid + 1, r, rson);
tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
// check three intervals;
// first;
tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
if (tree_len[rson] > tree_len[p])
tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
void remove(int qx, int l, int r, int p)
{
if (l == r && l == qx)
{
tree_l[p] = tree_r[p] = tree_len[p] = tree_pt[p] = 0;
return;
}
if (qx <= mid)
remove(qx, l, mid, lson);
else
remove(qx, mid + 1, r, rson);
tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
// check three intervals;
// first;
tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
if (tree_len[rson] > tree_len[p])
tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
int main()
{
scanf("%d%d", &n, &m);
while (m--)
{
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1)
{
if (tree_l[1] > 0)
{
int tmp = tree_len[1], key = tree_pt[1];
if (tree_l[1] - 1 >= tmp)
key = 1, tmp = tree_l[1] - 1;
if (n - tree_r[1] > tmp)
key = n, tmp = n - tree_r[1];
park[x] = key;
}
else
park[x] = 1;
printf("%d\n", park[x]), update(park[x], 1, n, 1);
}
else
remove(park[x], 1, n, 1);
}
return 0;
}
众所周知，XG_Zepto 是一位来自 FZOI 的神仙。他觉得眼下的比赛太简单了，就用扫雷的时间出了一道数学题给 kal0rona。kal0rona 太菜了，看不懂题也不会写，之后求救于你了。
很好的一道计数 DP，出自神仙组长 XG_Zepto 之手。首先，设\(f[i][j]\)为长度为\(i\)，换弹次数为\(j\)时满足条件的排列数量。之后，考虑枚举第\(i\)个数字出现的位置\(k\)，对于位置\(k\)后面的数字是不会有特殊贡献的（贡献为\((i-k)!\)），而对于前面的数，可以进行枚举前一段进行转移，一共有\({k-1}\choose{i-1}\)种选数字的方案和\(f[i-1][j-1\)种排列，乘起来即可，也就是：
\[ F[i][j] = \sum_{k = 1}^{i}f[k-1][j-1]* {{k-1} \choose {i-1}} *(i-1)! \]
可以化简，并用前缀和优化：
\[ F[i][j] = (i-1)!\sum_{k=1}^{i}\frac{f[k-1][j-1]}{(k-1)!} \]
// U63113.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5050, mod = 998244353;
ll f[MAX_N], prefix[MAX_N], level[MAX_N], inv[MAX_N], n, m;
ll quick_pow(ll bas, ll tim)
{
ll ans = 1;
while (tim)
{
if (tim & 1)
ans = ans * bas % mod;
bas = bas * bas % mod;
tim >>= 1;
}
return ans;
}
int main()
{
scanf("%lld%lld", &n, &m);
level[0] = 1, inv[0] = 1;
for (int i = 1; i <= n; i++)
level[i] = level[i - 1] * i % mod;
inv[n] = quick_pow(level[n], mod - 2);
for (int i = n; i >= 1; i--)
inv[i - 1] = inv[i] * i % mod;
for (int i = 0; i <= n; i++)
prefix[i] = 1;
for (int j = 1; j <= m; j++)
{
for (int i = j; i <= n; i++)
f[i] = prefix[i - 1] * level[i - 1] % mod;
for (int i = j; i <= n; i++)
prefix[i] = f[i] * inv[i] % mod;
for (int i = j + 1; i <= n; i++)
prefix[i] = (prefix[i] + prefix[i - 1]) % mod;
}
printf("%lld", f[n]);
return 0;
}
这道题是计数类 DP 中一道非常好的题。
我先来简述一下“试填法”。很多做过数位 DP 的神仙们都可能比较熟悉这样的技巧，一次次相减尝试并统计答案。这就是试填法，特别是在一些递推形式的数位 DP 中会经常简单这样的方法。
那我们开始来分析一下这道题吧。首先，设\(F[i][j][0/1]\)为木板数为\(i\)时，最后放置的木板排名为\(j\)且处于低位（0）或高位（1）。可以写出递推式：
\[ F[i][j][0] = \sum_{h=j}^{i-1} F[i-1][h][1] \\ F[i][j][1] = \sum_{h = 1}^{j-1} F[i-1][h][0] \]
之后，我们可以试图找出第一块木板的排名，设\(last\)为上一块木板的排名，\(k\)为上一块木板是否为高位（0/1）。通过枚举高度并试填：
对于之后的\([2,n]\)块木板，道理是一样的。需要注意的是，我们的枚举顺序从\(n\)到\(1\)，保证完整性。
// POJ1037.cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll n, m, T, f[25][25][2];
bool vis[25];
void initialize()
{
f[1][1][0] = f[1][1][1] = 1;
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= i; j++)
{
for (int k = j; k <= i - 1; k++)
f[i][j][0] += f[i - 1][k][1];
for (int k = 1; k <= j - 1; k++)
f[i][j][1] += f[i - 1][k][0];
}
}
int main()
{
scanf("%d", &T);
initialize();
while (T--)
{
memset(vis, 0, sizeof(vis));
scanf("%lld%lld", &n, &m);
// to determine the first condition;
ll last, k;
for (int j = 1; j <= n; j++)
{
if (f[n][j][1] >= m)
{
last = j, k = 1;
break;
}
else
m -= f[n][j][1];
if (f[n][j][0] >= m)
{
last = j, k = 0;
break;
}
else
m -= f[n][j][0];
}
vis[last] = true;
printf("%lld", last);
for (int i = 2; i <= n; i++)
{
k ^= 1;
int j = 0;
for (int len = 1; len <= n; len++)
{
if (vis[len])
continue;
j++;
if ((k == 1 && len > last) || (k == 0 && len < last))
if (f[n - i + 1][j][k] >= m)
{
last = len;
break;
}
else
m -= f[n - i + 1][j][k];
}
printf(" %lld", last);
vis[last] = true;
}
puts("");
}
return 0;
}