当前位置:网站首页>CSP-S2019 Day2
CSP-S2019 Day2
2022-08-03 08:09:00 【lAWTYl】
Day 2
T1 Emiya 家今天的饭
题目大意
给定一个 n × m n \times m n×m 的矩阵,矩阵上坐标为 ( i , j ) (i, j) (i,j) 的位置有 $$a_{i, j} 个数,矩阵中每一行最多选 1 1 1 个数,每一列选的数不能超过总选取数 k k k 的一半,且在矩阵中至少选一个数,问选取的方案数。
分析
我们看看这三个约束条件,首先,至少选一个数和每行最多选一个的条件是很好满足的。难点就在于每列不能超过一半这个条件。
所以我们考虑简单容斥一下,我们求出全集再减去超过一半的数量,这样就得到了不超过一半的数量。
为什么要这样做呢,因为我们简单的分析一下就会发现,不超过一半这个条件是要求所有列都要满足的,但是超过一半只需要有且仅有一个列满足 非常显然不可能有两列都大于一半的。
于是我们考虑 d p dp dp,求出存在且只存在一列超过一半的方案数。我们枚举是第 c o l col col 列超过了一半,令 f i , j , k f_{i, j, k} fi,j,k 表示 d p dp dp 到第 i i i 行, c o l col col 列选了 j j j 个,除了 c o l col col 列意外的选了 k k k 个。转移方程就是:
f i , j , k = f i − 1 , j , k + f i − 1 , j − 1 , k × a i , c o l + f i − 1 , j , k − 1 × ∑ p ∈ [ 1 , m ] ∧ p ≠ c o l a i , p f_{i, j, k} = f_{i - 1, j, k} + f_{i - 1, j - 1, k} \times a_{i, col} + f_{i - 1, j, k - 1} \times \sum_{p \in [1, m]\land p \neq col}a_{i, p} fi,j,k=fi−1,j,k+fi−1,j−1,k×ai,col+fi−1,j,k−1×p∈[1,m]∧p=col∑ai,p
我们记 s i = ∑ p = 1 m a i , p s_i = \sum\limits_{p = 1}^m a_{i, p} si=p=1∑mai,p,也就是第 i i i 行的和,那么方程就能写成:
f i , j , k = f i − 1 , j , k + f i − 1 , j − 1 , k × a i , c o l + f i − 1 , j , k − 1 × ( s i − a i , c o l ) f_{i, j, k} = f_{i - 1, j, k} + f_{i - 1, j - 1, k} \times a_{i, col} + f_{i - 1, j, k - 1} \times (s_i - a_{i, col}) fi,j,k=fi−1,j,k+fi−1,j−1,k×ai,col+fi−1,j,k−1×(si−ai,col)
这个方程的意思就是首先加上 f i − 1 , j , k f_{i - 1, j, k} fi−1,j,k 就是从上一行过来,这一行啥也不选。然后 f i − 1 , j − 1 , k f_{i - 1, j - 1, k} fi−1,j−1,k 就是在 c o l col col 列选选了一个,有 a i , c o l a_{i, col} ai,col 种选法,所以是 f i − 1 , j − 1 , k × a i , c o l f_{i - 1, j - 1, k} \times a_{i, col} fi−1,j−1,k×ai,col。 f i − 1 , j , k − 1 f_{i - 1, j, k - 1} fi−1,j,k−1 就是在除了 c o l col col 之外的选了一个,有 s i − a i , c o l s_i - a_{i, col} si−ai,col 种选法。三个加起来就是这里的答案。
这样做的复杂度就是 O ( n 3 m ) O(n^3m) O(n3m) 的,所以我们考虑优化这个做法。但是再考虑优化之前,我们还要求出总的答案(没有每一列的限制的),所以我们设 g i , j g_{i, j} gi,j 表示到第 i i i 行,选了 j j j 个的方案数,那么就有:
g i , j = g i − 1 , j + s i × g i − 1 , j − 1 g_{i, j} = g_{i - 1, j} + s_i \times g_{i - 1, j - 1} gi,j=gi−1,j+si×gi−1,j−1
这个式子的含义和上面我们写的 f f f 的转移式基本相同,所以在这里不过多解释。这样算出总的的复杂度是 O ( n 2 ) O(n^2) O(n2) 的,还可以接受,所以我们只用考虑优化 f f f 的转移。
因为我们发现我们在统计答案的时候只需要找 j > k j > k j>k 的 f i , j , k f_{i, j, k} fi,j,k 来统计(因为 c o l col col 列的大于一半,换言之就是大于其他地方的总合),所以我们考虑直接省掉一个维度,记 f i , j f_{i, j} fi,j 表示第 i i i 行, c o l col col 的数量减去 c o l col col 以外的数量的差为 j j j 时的方案数,那么:
f i , j = f i − 1 , j + f i − 1 , j − 1 × a i , c o l + f i − 1 , j + 1 × ( s i − a i , c o l ) f_{i, j} = f_{i - 1, j} + f_{i -1, j - 1} \times a_{i, col} + f_{i - 1, j + 1} \times(s_i - a_{i, col}) fi,j=fi−1,j+fi−1,j−1×ai,col+fi−1,j+1×(si−ai,col)
这样一搞直接就变成 O ( n 2 m ) O(n^2m) O(n2m) 的了,瞬间就过掉了。
这里要注意一下, j j j 有可能是负数,所以我们考虑把 j j j 整体向右移 n n n,范围就是 0 ∼ 2 n 0 \sim 2n 0∼2n。
代码
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 101
#define MAXM 2020
#define MOD 998244353
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9'){
x = x * 10 + c - '0'; c = getchar();
}
return x;
}
int n = 0; int m = 0;
int a[MAXN][MAXM] = {
0 };
int f[MAXN][MAXN << 1] = {
0 };
int g[MAXN][MAXN] = {
0 };
int s[MAXN] = {
0 };
int main(){
n = in; m = in; int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = in, s[i] = (s[i] + a[i][j]) % MOD;
g[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= n; j++)
if(j > 0) g[i][j] = (g[i - 1][j] + (1ll * g[i - 1][j - 1] * s[i] % MOD) % MOD) % MOD;
else g[i][j] = g[i - 1][j] % MOD;
for(int col = 1; col <= m; col++){
memset(f, 0, sizeof f);
f[0][n] = 1;
for(int i = 1; i <= n; i++)
for(int j = n - i; j <= n + i; j++)
f[i][j] = (f[i - 1][j] + (1ll * f[i - 1][j - 1] * a[i][col] % MOD) % MOD + (1ll * f[i - 1][j + 1] * (s[i] - a[i][col]) % MOD) % MOD) % MOD;
for(int j = 1; j <= n; j++) ans = (ans + f[n][n + j]) % MOD;
}
for(int i = 1; i <= n; i++) ans = (ans - g[n][i] + MOD) % MOD;
cout << 1ll * ans * (MOD - 1) % MOD << '\n';
return 0;
}
T2 划分
题目大意
给定一个数列 { a n } \{ a_n \} { an},然后让你求出 p p p 个划分点 1 ≤ k 1 < k 2 < ⋯ < k p < n 1 \leq k_1 < k_2 < \cdots < k_p < n 1≤k1<k2<⋯<kp<n( p p p 可以为 0 0 0,此时 k 0 = 0 k_0 = 0 k0=0),并且要满足一个条件:
∑ i = 1 k 1 a i ≤ ∑ i = k 1 + 1 k 2 a i ≤ ⋯ ≤ ∑ i = k p + 1 n a i \sum_{i = 1}^{k_1} a_i \leq \sum_{i = k_1 + 1}^{k_2}a_i \leq \cdots \leq \sum_{i = k_p + 1}^n a_i i=1∑k1ai≤i=k1+1∑k2ai≤⋯≤i=kp+1∑nai
使得一个式子:
( ∑ i = 1 k 1 a i ) 2 + ( ∑ i = k 1 + 1 k 2 a i ) 2 + ⋯ + ( ∑ i = k p + 1 n a i ) 2 (\sum_{i = 1}^{k_1} a_i)^2 + (\sum_{i = k_1 + 1}^{k_2}a_i)^2 + \cdots + (\sum_{i = k_p + 1}^n a_i)^2 (i=1∑k1ai)2+(i=k1+1∑k2ai)2+⋯+(i=kp+1∑nai)2
的值最小。
分析
虽然但是,这似乎是一道结论题 痛苦.jpg 说实话,结论题的这些结论我是真的不知道怎么想出来。
结论是这样的:越靠后的越小越好。
也就是说我们在判断两个方案哪一个更好的时候,我们只用判断两个方案中的最后一段,更小的那个一定就更优。
证明就考虑用微扰法。现在有一个最优解,最后相邻两段的和的平方分别 a 2 a^2 a2 和 b 2 b^2 b2,我们给 b 2 b^2 b2 这一段加上 x x x, a 2 a^2 a2 这一段减去 x x x,那么产生的贡献就是:
( a − x ) 2 + ( b + x ) 2 − a 2 − b 2 = 2 x 2 + 2 b x − 2 a x = 2 x ( x + b − a ) \begin{aligned} & (a - x)^2 + (b + x)^2 - a^2 - b^2 \\ = & 2x^2 + 2bx - 2ax \\ = & 2x(x + b - a) \end{aligned} ==(a−x)2+(b+x)2−a2−b22x2+2bx−2ax2x(x+b−a)
因为 2 x > 0 2x > 0 2x>0 且 b − a + x > 0 b - a + x > 0 b−a+x>0,所以贡献就是大于零的,所以这样微扰之后的结果会变得更大,就说明最后一段最小的结果时最优的。
我们考虑一个 d p dp dp,令 f i , j f_{i, j} fi,j 表示前 i i i 个数最后一个端点是 j j j 时候的答案,于是就有:
f i , j = min k = 1 i { f j , k + ( ∑ p = j + 1 i a p ) 2 } f_{i, j} = \min_{k = 1}^i \{ f_{j, k} + (\sum_{p = j + 1}^i a_p)^2 \} fi,j=k=1mini{ fj,k+(p=j+1∑iap)2}
这里显然又有一个前缀和,所以我们令 s i = ∑ k = 1 n a k s_i = \sum\limits_{k = 1}^n a_k si=k=1∑nak,那么:
f i , j = min k = 1 i { f j , k + ( s i − s j ) 2 } f_{i, j} = \min_{k = 1}^i \{ f_{j, k} + (s_i - s_j)^2 \} fi,j=k=1mini{ fj,k+(si−sj)2}
这个做法显然就是 O ( n 3 ) O(n^3) O(n3) 的,所以我们要优化这个做法。
考虑怎样用上刚才说 d p dp dp 之前我们观察到的性质,我们发现其实如果我们保证了 f i , j f_{i, j} fi,j 现在是最小的话,同时就保证了 j j j 这个点就应该是最靠右的。所以我们是不是能考虑把 f i , j f_{i, j} fi,j 的后面这一维直接去掉呢?
令 f i f_i fi 表示前 i i i 个数的答案, l s t i lst_i lsti 表示前 i i i 个数最后划分出来的一段的大小,转移的话就是这样:
f i = min j = 1 i { f j + ( s i − s j ) 2 } 其中 l s t j ≤ s i − s j f_{i} = \min_{j = 1}^i \{ f_j + (s_i - s_j)^2 \} \quad 其中 lst_j \leq s_i - s_j fi=j=1mini{ fj+(si−sj)2}其中lstj≤si−sj
这样的复杂度就是 O ( n 2 ) O(n^2) O(n2) 的了,但是还是过不了,于是继续优化。
因为我们在上面说过,比较两个方案哪一种更有只需要比较最后一段的大小即可,所以我们考虑从位置入手。设 g i g_i gi 表示 i i i 的上一个端点的位置(也就是 l s t i lst_i lsti的一个变式)。那么:
g i = max j { j } 其中 j 满足 s i − s j ≥ s j − s g j g_i = \max_j \{ j \} \quad 其中 j 满足 s_i - s_j \geq s_j - s_{g_j} gi=jmax{ j}其中j满足si−sj≥sj−sgj
也就是选出一个最靠右的 j j j 满足题目的条件(段之间是单增的),我们这样还是看不出来怎样优化,那么我们化简一下式子:
s i ≥ 2 s j − s g j s_i \geq 2s_j - s_{g_j} si≥2sj−sgj
令 v a l j = 2 s j − s g j val_j = 2s_j - s_{g_j} valj=2sj−sgj,于是:
g i = max { j } 其中 v a l j ≤ s i g_{i} = \max \{ j \} 其中 val_j \leq s_i gi=max{ j}其中valj≤si
这个东西看起来像什么东西呢,没错,单调队列。每次加入取出队尾 j ′ j' j′,如果 j > j ′ j > j' j>j′ 且 v a l j ≤ v a l j ′ val_j \leq val_{j'} valj≤valj′ 就可以把队尾弹出去了,每次再取队首就好了。
最后我们就能 O ( n ) O(n) O(n) 求出 g g g,然后 O ( n ) O(n) O(n) 就能得到划分方案了。
代码
因为正解要写高精还要卡空间和卡时间,所以就不打算写了,就写一个复杂度是正确的前 22 22 22 个点吧。
// 88 pts
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 100100
#define val(x) (s[x] << 1) - s[g[x]]
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9'){
x = x * 10 + c - '0'; c = getchar();
}
return x;
}
int a[MAXN] = {
0 };
int n = 0; int opt = 0;
int s[MAXN] = {
0 };
int g[MAXN] = {
0 };
int head = 1, tail = 1;
int q[MAXN] = {
0 };
signed main(){
n = in; opt = in; int ans = 0;
for(int i = 1; i <= n; i++) a[i] = in, s[i] = s[i - 1] + a[i];
for(int i = 1; i <= n; i++){
while(head < tail and val(q[head + 1]) <= s[i]) head++;
g[i] = q[head];
while(head <= tail and val(q[tail]) >= val(i)) tail--;
q[++tail] = i;
}
// for(int i = 1; i <= n; i++) cout << g[i] << ' '; puts("");
int r = n, l = g[r];
while(!(l == 0 and r == 0)){
// printf("l = %d r = %d\n", l, r);
ans += (s[r] - s[l]) * (s[r] - s[l]);
r = l; l = g[r];
} cout << ans << '\n';
return 0;
}
T3 树的重心
题目大意
给出一颗大小为 n n n 的树 S = ( V , E ) S = (V, E) S=(V,E),树中节点从 1 ∼ n 1 \sim n 1∼n,求出 S S S 单独删去每条边后,分裂出的两个子树的重心编号的和,也就是:
a n s = ∑ ( u , v ) ∈ E ( ∑ x 是 S u ′ 的重心 x + ∑ y 是 S v ′ 的重心 y ) ans = \sum_{(u, v)\in E} \left( \sum_{x 是 S_u' 的重心}x + \sum_{y 是 S_v' 的重心} y \right) ans=(u,v)∈E∑⎝⎛x是Su′的重心∑x+y是Sv′的重心∑y⎠⎞
分析
这道题的关键就在于计数方式:以重心为根节点,对于每个点,统计让它成为重心的边数。
为什么是以重心为根节点?因为如果以重心为根,整棵树就有一个很好的性质:假设要让一个费根节点 x x x 成为删掉某一条边之后的重心,那我们一定不会删 x x x 的子树里面的边 这很显然吧qwq。
对于一个非根节点 x x x,我们考虑怎样统计答案,因为刚才提到的性质,所以我们也就是要在除去 x x x 的子树的剩余的树上找边,使得 x x x 的每棵子树的 s i z e size size 都小于等于一半,且删去边后形成的 x x x 的新子树的 s i z e size size 也要小于等于一半。
我们设 x x x 节点最大的子树的 s i z e size size 为 g x g_x gx,我们删去某条边后,不包含 x x x 的部分的大小为 S S S,那么就要满足这样一个表达式:
n − S ≥ 2 g x n - S \geq 2g_x n−S≥2gx
这也就是 x x x 的每棵子树的 s i z e size size 都小于等于一半的符号表达。
那么我们考虑另一个条件怎么表示。令 s x s_x sx 表示 x x x 的子树的大小,那么删去边之后 x x x 的新子树的大小就是 n − s x − S n - s_x - S n−sx−S,那么就有:
n − S ≥ 2 ( n − s x − S ) n - S \geq 2(n - s_x - S) n−S≥2(n−sx−S)
化简一下:
n − 2 s x ≤ S ≤ n − 2 g x n - 2s_x \leq S \leq n - 2g_x n−2sx≤S≤n−2gx
那么这个限制条件就之和 x x x 有关了。那么问题就转化成了如果以 x x x 为根节点,有多少颗子树中节点的子树满足它的 s i z e size size 在 [ n − 2 s x , n − 2 g x ] [n - 2s_x, n - 2g_x] [n−2sx,n−2gx] 里面。这个问题就很好解决,就弄个树状数组查询就好了。
但是这里有一个问题,我们这样统计就会多统计了以重心为根时 x x x 的子树的贡献。所以我们就容斥答案:令开一个树状数组,记录 x x x 子树内的信息,最后的答案就是两个相减就可以了。要统计子树的答案其实也很简单,维护一个 d f s dfs dfs 序, x x x 的子树就是 d f s dfs dfs 序中连续的一段,另开的树状数组就统计这一段连续区间的答案即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 300300
#define MAXM MAXN << 1
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9'){
x = x * 10 + c - '0'; c = getchar();
}
return x;
}
int T = 0;
int n = 0; int ans = 0;
int u = 0; int v = 0;
int tot = 0;
int first[MAXN] = {
0 };
int nxt[MAXM] = {
0 };
int to[MAXM] = {
0 };
inline void add(int x, int y){
nxt[++tot] = first[x];
first[x] = tot; to[tot] = y;
}
int root = 0;
int s[MAXN] = {
0 };
int g[MAXN] = {
0 };
void dfs1(int x, int fa){
s[x] = 1, g[x] = 0;
bool flag = 1;
for(int e = first[x]; e; e = nxt[e]){
int y = to[e];
if(y == fa) continue;
dfs1(y, x);
s[x] += s[y], g[x] = max(g[x], s[y]);
if(s[y] > (n >> 1)) flag = 0;
}
if(n - s[x] > (n >> 1)) flag = 0;
if(flag) root = x;
}
int c1[MAXN << 2] = {
0 };
int c2[MAXN << 2] = {
0 };
inline int lowbit(int x) {
return x & -x; }
void add(int *c, int x, int k){
x++;
for(; x <= n + 1; x += lowbit(x)) c[x] += k;
}
int query(int *c, int x){
int ans = 0; x++;
for(; x; x -= lowbit(x)) ans += c[x];
return ans;
}
int z[MAXN] = {
0 };
void dfs2(int x, int fa){
add(c1, s[fa], -1);
add(c1, n - s[x], 1);
if(x ^ root){
ans += x * query(c1, n - 2 * g[x]);
ans -= x * query(c1, n - 2 * s[x] - 1);
ans += x * query(c2, n - 2 * g[x]);
ans -= x * query(c2, n - 2 * s[x] - 1);
if(!z[x] and z[fa]) z[x] = 1;
ans += root * (s[x] <= n - 2 * s[z[x] ? v : u]);
}
add(c2, s[x], 1);
for(int e = first[x]; e; e = nxt[e]){
int y = to[e];
if(y == fa) continue;
dfs2(y, x);
}
add(c1, s[fa], 1);
add(c1, n - s[x], -1);
if(x ^ root){
ans -= x * query(c2, n - 2 * g[x]);
ans += x * query(c2, n - 2 * s[x] - 1);
}
}
void init(){
tot = 0, ans = 0, u = v = 0;
memset(s, 0, sizeof s); memset(g, 0, sizeof g);
memset(c1, 0, sizeof c1); memset(c2, 0, sizeof c2);
memset(to, 0, sizeof to); memset(nxt, 0, sizeof nxt);
memset(z, 0, sizeof z); memset(first, 0, sizeof first);
}
signed main(){
T = in;
while(T--){
n = in; init();
for(int i = 1; i < n; i++){
int x = in, y = in;
add(x, y), add(y, x);
} dfs1(1, 0); dfs1(root, 0);
for(int e = first[root]; e; e = nxt[e]){
int y = to[e];
if(s[y] > s[v]) v = y;
if(s[v] > s[u]) swap(u, v);
}
for(int i = 0; i <= n; i++) add(c1, s[i], 1), z[i] = 0;
z[u] = 1;
dfs2(root, 0);
cout << ans << '\n';
}
return 0;
}
边栏推荐
猜你喜欢
【愚公系列】2022年07月 Go教学课程 026-结构体
Fortify白盒神器20.1.1下载及安装(非百度网盘)
day12---接口和协议
sqlserver2019安装失败
并发之多把锁和活跃性
NFT到底有哪些实际用途?
sqlite date field plus one day
【Kaggle实战】泰坦尼克号生存人数预测(从零到提交到Kaggle再到模型的保存与恢复)
mysql5.7服务器The innodb_system data file 'ibdata1' must be writable导致无法启动服务器
"Swordsman Offer" brush questions print from 1 to the largest n digits
随机推荐
并发之固定运行和交替运行方案
frp: open source intranet penetration tool
thop 使用心得
Exch:重命名或删除默认邮箱数据库
《剑指Offer》刷题之打印从1到最大的n位数
netstat 及 ifconfig 是如何工作的。
BOM系列之localStorage
NFT到底有哪些实际用途?
Taro框架-微信小程序-内嵌h5页面
IDEA2021.2安装与配置(持续更新)
mysql备份时的快照原理
学习笔记:机器学习之逻辑回归
Evaluate: A detailed introduction to the introduction of huggingface evaluation indicator module
mysqlbinlog: unknown variable 'default-character-set=utf8'
【收获合辑】k-NN与检索任务的异同+jupyter转pdf
并发之ReentrantLock
001-进程与线程
Pyspark - an empty string is replaced by None
ceph简介
ArcEngine(六)用tool工具实现拉框放大缩小和平移