C. Hello 2019 (cf-705e)

题意

输入一个字符串，区间询问 $[s_l,s_r]$ 中，删去最少的字符，使得出现子序列 $”2019”$ ，而不出现 $”2018”$

H. NAND

题意

给一个真值表，问最少使用多少个二输入与非门能够实现这个真值表的功能。

D. Fish eating fruit

题意

将树上任意两点之间的距离按取模 $3$ 分类，分别求出三种情况的路径和

题解

• 解法1:

  $dp1[u][j]$ 表示以 $u$ 为根节点的树，树上任意两点之间的距离取模 $3$ 为 $j$ 的路径和

  $dp2[u][j]$ 表示以 $u$ 为根节点的树，树上的点到 $u$ 的距离取模 $3$ 为 $j$ 的路径和

  $dp3[u][j]$ 表示以 $u$ 为根节点的树，树上的点到 $u$ 的距离取模 $3$ 为 $j$ 的节点数

• 解法2:

  根据模 3 的余数设计 dp 方程

  $dp[i][k]$ 统计距 i 模 3 为 k 的子节点的数目

  $fp[i][k]$ 统计距 i 模 3 为 k 的非子节点的数目（父节点，兄弟节点，兄弟节点 的子节点）

  $ans[i][k]$ 统计距 i 模 3 为 k 的子节点到 i 的距离和

  $fans[i][k]$ 统计距 i 模 3 为 k 的非子节点距离和

代码

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

ll dp1[N][3],dp2[N][3],dp3[N][3];
vector<pii> node[N];
int n;
void dfs(int u,int fa){
    dp3[u][0]=1;
    for(auto i:node[u]){
        int v=i.fi,w=i.se;
        if(v==fa)continue;
        dfs(v,u);
        for0(i,3)dp1[u][i]=(dp1[u][i]+dp1[v][i])%mod;
        for0(i,3)
        for0(j,3){
            int tm=(i+j+w)%3;
            dp1[u][tm]=(dp1[u][tm]+dp2[u][i]*dp3[v][j]%mod+dp2[v][j]*dp3[u][i]%mod+dp3[v][j]*dp3[u][i]%mod*w%mod)%mod;
        }
        for0(i,3)dp2[u][(w+i)%3]=(dp2[u][(w+i)%3]+dp2[v][i]+w*dp3[v][i])%mod;
        for0(i,3)dp3[u][(w+i)%3]=(dp3[u][(w+i)%3]+dp3[v][i])%mod;
    }
    return ;
}
int main() {
    int u,v,w;
    while(~in(n)){
        for0(i,n){
            node[i].clear();
            mem0(dp1[i]);mem0(dp2[i]);mem0(dp3[i]);
        }
        for0(i,n-1){
            in(u,v,w);
            node[u].push_back(pii(v,w));
            node[v].push_back(pii(u,w));
        }
        dfs(0,-1);
        for0(i,3)dp1[0][i]=dp1[0][i]*2%mod;
        out0(dp1[0],3);
    }
    return 0;
}

题意

题意

$n(2\le n\le 4e5)$ 个物品，每个的颜色为 $a_i(1\le a_i\le 20)$ ，仅允许将相邻的物品两两交换，问使得相同颜色的物品聚集到一起的最小花费

C. Triple

题意

给三个序列，分别从中选取一个数，输出能够构成一个三角形（线段也算）的方案数。

E. 2-3-4 Tree

题意

裸的 $B+$ 树

题意

求圆心轨迹的总长度。

题意

集合 $S\subseteq \{x|x\in[0,m-1]\}$ ，由这些数组成一个长度为 $N$ 的数列，给定整数 $r(r\in[0,m-1])$，求满足数列中所有数的乘积 $\mod m$ 的值等于 $r$ 的不同的数列的有多少个。

G. Indie Album

题意

有 $n$ 个字符串,对于第 $i$ 个字符串通过以下两种方式中的一个给出。

1. $1 c$，该字符串只含一个字符 $c$ 。
2. $2 x c$ ,该字符串为第 $x(1\le x<i)$ 个字符串末尾添加一个字符 $c$ 得到。

有 $m$ 次询问，每次询问给出一个字符串 $s$ 和位置编号 $x$,问在上述第 $x$ 个字符串中，字符串 $s$ 出现了几次。

D. Neko and Aki’s Prank

题意

将长度为 $2n$ 的所有合法括号匹配放入字典树中，求这棵树的最大的边集，边集里的边两两不相连