#3211. 「CSP-S 2019」Emiya 家今天的饭

Summarize

在 $n\times m$ 的矩阵中选 $k$ 个元素，要求 $k\ge 1$，每行最多选 $1$ 个元素，每列元素个数不超过 $\lfloor \frac{k}{2}\rfloor$ 的方案数。

$n\le 100,m\le 2000$

#3108. 「TJOI2019」甲苯先生和大中锋的字符串

Summarize

给定字符串 $s$，求出 $s$ 恰好出现 $k$ 次的子串中长度中出现次数最多的长度数。

$|s|\le 100000$

刚刚学习了后缀自动机，当然要写一篇算法学习啦。

占坑，先咕。

Summarize

给定 $n$ 种原材料，每种材料有一个特征值 $a_i$ 和强度 $b_i$。有 $q$ 次查询或修改，询问是给出一段区间 $[l,r]$，要求在 $l,l+1..r-1,r$ 的原材料中选出一个特征值线性无关的子集，是强度值之和最大；修改是修改某种原材料的特征值和强度。

$n\le 100000,q\le 10000,1\le a_i,b_i\le 1000000000$

#43463. 「计蒜客 2020.2 提高组」保卫水库

Summarize

给定有 $n$ 个节点和 $m$ 条边的有向无环图。每个节点有一定的水量，每个结点的水在水库被破坏后会均等地沿着出边流向其他节点。给出 $k$ 个操作，要求查询某个节点流入的水量，以及修改某个节点的初始水量。

$n\le 5000,m\le 10000,k\le 500000$

测试点的查询和修改次数比例接近 $1:1$

#43462. 「计蒜客 2020.2 提高组」受力平衡

Summarize

题目概括咕咕中~