T1

问题

给定一个n * m的矩阵,要求在每一个格子填入0或1,使得没有相邻的1,问方案数有多少

解法

用f[i][j][s]代表现在在(i,j),状态为s的方案数.状态S为一个数,将它转化成二进制后,每一位的0或1代表目前最晚填完的m个格子的方案数,也就是从[i-1][j]到[i-1][m];从[i][1]到[i][j-1]的这m个.这样就可以一直更新了.

T2

问题

给定n个字符串,构造一个串S使得S包含这些所有串,且长度最小.

解法

[数据删除]

T3

问题

现在有n个点,对于第i个点和第j个点,你可以选择不连接,也可以在c[i,j]条颜色不一样的边中选一条连接他们.要求最终将这些点连成一个连通图,而且没有自环,问方案数 mod 1e9+7.

n <= 15

解法

[数据删除]

T4

问题

给出一行N个点,在(u,v)之间连边的条件是|u-v|<=k,即下标相差不超过k.问连出一张欧拉图的方案数.

k <= 5,n <= 1e5

解法

斯坦纳树

T5

问题

给出一颗n个节点的树,树边边权给出.计算出树上每个节点的最远点到他的距离.

n<=1e5

解法

[数据删除]

T6

问题

给定一棵n个点的树,走L步使得经过的点权和最大

n <= 5000

解法

[数据删除]

T7

问题

给定A,B,求出[A,B]中各位数字之和能整除原数的数的个数.

A,B<=10^18

解法

T8

问题

定义不含前导0且相邻两个数之差至少为2的数为windy数,问A和B之间,包括A和B,共有多少个windy数?

解法

[数据删除]

T9

问题

给定一棵树,从中找出k个点,使得Σdis(a[i],a[i+1])最小

解法

先考虑k==n的时候,你会发现,除了起点和终点之间的那一条链以外,所有的边都经过了两次,即一次进入点一次出点.因此k==n时题目等价于寻找最长链.

考虑更一般化的情况,问题变成寻找一个大小为k的子集来处理.在这里,这个点集显然是一个连通的子树,所以就要用树上背包,斯坦纳树等我不会也听不懂的奇怪知识点来[数据删除].

——Gensokyo