【2019】 CSP - S 题解
T2
全集转后缀,后缀用递推可以求出,$f[ABC] = f[AB] + 1$,
解释一下,全集两点不固定,后缀固定一点,所以可以转化,
显然递推式是 $f[ABC] = f[AB] + 1$ 的关系,
最后做前缀和 $s[ABC] = s[AB] + f[ABC]$ 即可求出根节点到当前点的全集,这就是我们要的。
$STL$ 记得判空,有插入就要有弹出,有弹出就要有插入,
搜索过程中用数组存递推式和当前节点到根节点的全集。
最终答案按要求处理即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, ans;
char c[N];
int h[N], e[N], ne[N], fa[N], idx;
int cnt[N], sum[N];
stack<int> s;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
int tmp = 0;
if (c[u] == ')' && s.size())
{
int t = s.top();
s.pop();
cnt[u] = cnt[fa[t]] + 1;
tmp = t;
}
else if (c[u] == '(') s.push(u);
sum[u] = sum[fa[u]] + cnt[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
dfs(j);
}
if (tmp) s.push(tmp);
else if (s.size()) s.pop();
}
signed main()
{
memset(h, -1, sizeof h);
scanf("%lld%s", &n, c + 1);
for (int i = 1; i < n; i ++ )
{
int f;
scanf("%lld", &f);
add(f, i + 1);
fa[i + 1] = f;
}
dfs(1);
for (int i = 1; i <= n; i ++ )
{
ans ^= i * sum[i];
}
printf("%lld", ans);
}
T4
由于 $m$ 很大,不能像考虑乌龟棋那样具体记录每个主要食材选了多少,由于正难则反,
我们发现只要有一个主要食材在 $> 2/n下取整$ 的方案里被使用,就不合法,
因为一个主要食材比多个更好维护,所以我们转为求解不合法方案。
定义数组 f[i][j][k]:
用前i
种烹饪方式,j
个越界食材,k
个其它食材的方案数。
状态转移方程:
$f[i][j][k] += f[i-1][j][k]$
选第$c$种越界食材,$f[i][j][k] += f[i-1][j-1][k] * a_{i, c}$
选其它食材,$f[i][j][k] += f[i-1][j][k-1]*(s_i - a_{i, c})$
考虑优化,由于我们只关心 $j > k$ 的方案数,所以我们可以去维护 $j, k$ 的 差值,
这样就可以 不去管 $j, k$到底是几了,从而 优化一维时间和一维空间复杂度。
在乌龟棋中也用到了这类优化,不过哪里是优化了和,这里是优化了差,
这种优化在题目要求维护两个或多个状态的和或差满足XX条件时可以使用,
这叫作和差优化,其思想在于对选数类问题或者说背包类问题体积这一维度的运用,
将多维体积降维,或者说减少了它的独立参数,比如说一个是$i, j$,一个是$k (k = i - j)$
由背包子问题重叠的特点,进行求解,这个方法的局限在于不能维护 $i = XX$,$j = XX$ 的方案,
f[i][j]:
用前i
种烹饪方式,越界食材 $-$ 其它食材为j
的方案数。
状态转移方程:
$f[i][j] = f[i-1][j]$
选第$c$种越界食材,$f[i][j] += f[i-1][j-1] * a_{i, c}$
选其它食材,$f[i][j] += f[i-1][j+1] * (s_i - a_{i, c})$
总方案中,菜可以不做,所以有空集,要 $+ 1$。
本题要求菜至少有一道,答案减去空集,即 $- 1$。
#include <bits/stdc++.h>
#define int long long
#define mod(a) (a + 998244353) % 998244353
using namespace std;
const int N = 110, M = 2010;
int n, m;
int w[N][M];
int s[N], tos[M], f[N][2 * N];
int sum;
signed main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%lld", &w[i][j]);
sum = 1;
for (int i = 1; i <= n; i ++ )
{
int op = 0;
for (int j = 1; j <= m; j ++ )
op = mod(op + w[i][j]);
sum = mod(sum * (op + 1));
s[i] = op;
}
for (int t = 1; t <= m; t ++ )
{
memset(f, 0, sizeof f);
f[0][n + 1] = 1;
for (int i = 1; i <= n; i ++ )
for (int k = -n; k <= n; k ++ )
{
int j = k + n + 1;
f[i][j] = f[i - 1][j];
f[i][j] += mod(f[i - 1][j - 1] * w[i][t]);
f[i][j] += mod(f[i - 1][j + 1] * mod(s[i] - w[i][t]));
f[i][j] = mod(f[i][j]);
}
for (int i = 1; i <= n; i ++ )
tos[t] = mod(tos[t] + f[n][i + n + 1]);
sum = mod(sum - tos[t]);
}
printf("%lld", mod(sum - 1));
}
T5
36 pts
我们设计状态 $f[i][j]$ 为当前划分区间为i~j
的最小值。
for (int i = 1; i <= n; i ++ ) s[i] = s[i-1] + a[i];
for (int i = 1; i <= n; i ++ ) f[1][i] = s[i] * s[i];
for (int j = 1; j <= n; j ++ )
for (int i = 1; i <= j; i ++ )
{
for (int k = 1; k < i; k ++ )
{
if (s[j] - s[i-1] < s[i-1] - s[k-1]) continue;
f[i][j] = min(f[i][j], f[k][i-1] + (s[j]-s[i-1])*(s[j]-s[i-1]));
}
}
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
ans = min(ans, f[i][n]);
}
printf("%d", ans);
68 pts
发现贪心性质,在转移的所有划分中选 $j$ 最大的。
f[i]:
结尾为 i
的最小值。
f[i] = min(f[check(j)] + sum[i] - sum[j])
为了快速判断,我们还应该处理一个数组 $pre$ 维护以 $i$ 为结尾前的最大连续区间开头。
100 pts
有两个位置 $a, b$,若有 $a > b 且 f(a) < f(b)$,我们就排除 $b$。
可以确定$f$数组的数 一定是单调的,于是我们用一个单调队列维护所有可能的转移点。
由于我们要找的是符合 $sum[j] - sum[pre[j]] <= sum[i] - sum[j]$ 的最大值,
变式后等价于维护 $2*sum[j] - sum[pre[j]]$ 的最小值,
当队列内元素符合要求 $<= sum[i]$ 我们就不断弹出队列内元素,找最小值。
$O(1)$ 判断,$O(n)$ 复杂度。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e7 + 10, M = 1e5 + 10, mod = 1 << 30;
int n, m, type, x, y, z;
int a[N], b[N], p[M], l[M], r[M], q[N], pre[N];
long long sum[N];
inline long long d(int x){
return sum[x] - sum[pre[x]];
}
int main()
{
scanf("%d%d", &n, &type);
if (type) {
scanf("%d%d%d%d%d%d", &x, &y, &z, &b[1], &b[2], &m);
for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &p[i], &l[i], &r[i]);
for (int i = 3; i <= n; i ++ )
{
b[i] = (0ll + 1ll * b[i-1] * x + 1ll * b[i-2] * y + z) % mod;
}
for (int i = 1; i <= m; i ++ )
{
for (int j = p[i-1]+1; j <= p[i]; j ++ )
{
a[j] = b[j] % (r[i] - l[i] + 1) + l[i];
sum[j] = sum[j-1] + a[j];
}
}
}
else
{
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
}
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh < tt && d(q[hh+1]) + sum[q[hh+1]] <= sum[i]) hh ++;
pre[i] = q[hh];
while (hh < tt && d(q[tt]) + sum[q[tt]] >= d(i) + sum[i]) tt --;
q[ ++ tt] = i;
}
int now = n; __int128 ans = 0, tmp = 1;
while (now)
{
tmp = d(now);
tmp *= d(now); // 不能存到过程变量中
ans += tmp;
now = pre[now];
}
int st[50], tp = 0;
while (ans) // __int128 不能直接输出
{
st[ ++ tp] = ans % 10;
ans /= 10;
}
for (int i = tp; i >= 1; i -- ) printf("%d", st[i]);
}