https://codeforces.com/contest/1844
n个点 有边权(wi > 0权重未知)的树
给所有 i到i+1简单路径的长度di
求任意一个合法的边权方案,或者无方案
n 1e5
di [1,1e12]
5s
256mb
根不影响点间距离和边长,因此直接把1选做根
首先 可以 n log n 算所有 i与i+1的 lca
$u_i = lca(i,i+1)$
$path(i,i+1) = path(i,u_i)+path(i+1,u_i) = dep_i + dep_{i+1} - 2 dep_{u_i}$
所以可以得到一个 $(n-1)$行$(n+1)$列(其中一列是增广列) 矩阵
尝试求正解即可
它是一个 系数矩阵非零项 不多于 $4(n-1)$
然而 并不会解稀疏矩阵, 还要把距离弄正
跟我想的一样 也是 先去掉树变成单纯的线性代数问题
然后神奇的来了,
https://atcoder.jp/contests/arc058/tasks
有多少个 长度n,值域 [1,10]整数的数组a 满足 子区间
sum a[x..y) = X
sum a[y..z) = Y
sum a[z..w) = Z
答案mod 1e9+7
n [1,40]
x [1,5]
y [1,7]
z [1,5]
4s
512mb
范围这么小,可以打表!
想的还是 容斥暴力
总状态 =[5的实际状态][7的实际状态][5的实际状态]
考虑首个匹配在哪个位置,
sum (a[i…] 满足, a[<i…] 不满足)
问题是转移的话,似乎并不好转移
似乎测试数据太弱了
题意 给定a[1..10] <= 1e11, h <= 1e12
对于任意b, 求min(max(sum b[i] * i), h), b[i] \in [0,a[i]] b[i]是整数
2s
512mb
似乎没官方题解
我最开始想的用bitmask, 去做 dp, 按照不同顺序，有贪心最多
但是实际上 h=10, a[2] = 3, a[3] = 3时
选2个2和2个3刚好拼成10, 而贪心 会是 3 * 2 + 1 * 3 或者 0 * 2 + 3 * 3 都无法达到最大
然后测试数据弱就过了，根据讨论区 说，只要所有加起来都能过测试，这是什么坑爹的出题人和数据，
https://atcoder.jp/contests/abc309/tasks
N行 M列 grid
长K整数数组A
长L整数数组B
$f(i,j) =$从$(1,A_i)$移动到$(N,B_j)$恰好$(N-1)$次的路径方案数
其中每次移动$(+1,-1),(+1,+0),(+1,+1)$
求$\displaystyle \sum_{i\in[1,K]}\sum_{j\in[1,L]} f(i,j) \pmod{998244353}$
$1\le N\le 10^9$
$1 \le M,K,L,\le 10^5$
$1\le A_i,B_j\le M$
10 s
1024 MB
这个 坐标的x始终+1,看起来没什么用啊
所以$f(i,j)$等价于 $A_i$变为$B_j$,且每次$+1/+0/-1$,过程中不超过$[1,M]$范围的恰好$N-1$次的方案数
如果 没有范围限制, 对于合法$X+Y*0-Z = B_j-A_i, X+Y+Z=N-1$的方案数有$\binom{N-1}{X,Z}$
$\displaystyle \sum_{Z=1}^{N-1} \frac{(N-1)!}{Z!(B_j-A_i+Z)!((N-1)-Z-(B_j-A_i+Z))!}$
其中令$\frac{1}{(<0)!} = 0$
这种情况 只和 $B_j-A_i$的值有关,可以预处理(所有差在$[-(M-1),+(M-1)]$内 )+统计(??????????????????)就可以
似乎连统计两个数组的所有差都不会??
好像 $f_A(x) = \sum count(A[i]=v)x^{-v}$
$f_B(x) = \sum count(B[i]=v)x^{v}$
$f_A(x)f_B(x)$ 应该就能统计
然后为了不要处理负, $f’_A(x) = x^{\max{v}} f_A(x)$即可
其实这里还有个问题是 N很大的话 暴力计算阶乘够吗?
那么回到题目, 当有范围限制要如何做呢?
似乎没有办法
但这里既然想到生成函数
$[x^j] f_i(x)$ 表示移动$i$次后路径值变为$j$的方案数
$f_0(x) = x^{A_i}$
$g(x) =$转移方程
$f_i(x) = g(f_{i-1}(x))$
求 $[x^{B_j}]f_{n-1}(x)$
好像 为了$[1,M]$的范围 还是要处理 两端..
一个想法是, 去计算 2的幂次的转移变化, 这样的话 对于N就是log级别了
但似乎 这会变成 $M * M$的矩阵,而不是一个简单的乘上一个函数
https://atcoder.jp/contests/abc308/tasks
简单无向图, N点,M边, 初始边白色, 如果要把边染色成黑色代价Ci
也就是 要 给一个环上色，且延伸一个 环内点-环外点的边，也就是视觉意义上的Q
问 画出Q的最小代价
n300
ci 1e5
4s
1024mb
这个n300 不知道怎么用，看起来像是n^3 一类的玩意
如果给定了圆，那么延伸边，可以直接暴力枚举O(n^2)？
一个思路是最小生成树，而和最小生成树不同的是，当有同并查集的时候 直接触发 找环
问题是，每边尽量短并不意味环更短，10个1 > 3个2
钦定 环上延伸边的点
环上延伸边的点是u, 然后找环，再定延伸边
for u (O(n)): 找环?, 延伸边:O(n)
如果先定延伸边，那么就是 求不含延伸点，含固定点的最小环
似乎并不会找 含 固定点的最小环
另外，如果再处理一下， 先找含固定点的最小环，那么未包含的点就可以作为延伸点，包含的点再考虑
1 | 1-(1)-2-(1)-3 |