https://atcoder.jp/contests/abc285/tasks
h * w 的格子 要用 1x1 和1x2 填满
上面有写 1,2,? 三种
1需要1x1覆盖
2需要1x2 覆盖(可以旋转成2x1)
? 任意
问 是否有可行方案
h,w 300
3s
1024mb
1 不需要关心, 只用关心2, 以及辅助2的?
看起来可以奇偶分边, 来做 二分图最大匹配 O(300^4) 感觉过不了
而且还有问题, 这里并不是要最大匹配, 只是要无冲突和匹配完所有2
另一个想法类似的, 能不能网络流, 还是奇偶分左右点, ?与?不连边, 但是 依然不知道如何表示 优先选2, 难道要费用流? 2的费用更低? 但似乎也没有”保证”
https://codeforces.com/contest/1633
给n点,m边一个连通无向图
k个询问, 每次一个xi
你需要找一个生成树, 让 sum |wj-xi| 最小, wj为生成树的边的权重, 不需要输出具体方案
前 p个询问具体给出 xi
[p+1~k] 的询问 通过 q[j]=(q[j-1]a+b)%c 给出
输出所有询问的结果的xor
n 50
m 300
wi, xi [0,1e8]
p 1e5
k 1e7
c [1,1e8]
4s
256mb
对于一个具体的一个询问, 那么就是 经典的最小生成树算法, 让边权 = |wj-xi| 即可
但如果 把边排序了 并记录边的id
如果x变化, 但是排序后id顺序没有变, 那么最小生成树选择的边就不会边(虽然边权重变了)
那么排序后会有多少种情况呢, 感觉上 比 binom(50,25) 还多, 想x分割大于和小于的边,两个穿插
如果这个情况少, 那就变成 统计 情况内的边选择, 和对应>x小于x的个数与和来计算了
p 1e5 n 50 , m 300 是可以接受 暴力的
但是 k 1e7 一定要实现某种批量算法
https://codeforces.com/contest/1644
F(a数组,k数字) = 把a每个数组重复k次, 然后取 和a等长的前缀 [a_0_1,a_0_2...,a_0_k, a_1_1...a_1,k, a_2_1,...,a_2_k,...]
`x!=y, G(a数组,x数字,y数字) = 把a中所有x变成y, 所有y变成x
如果满足以下条件,则称a数组是b数组的父数组:
如果 有父数组链关系, 则称作祖先
问题, 给定n,k
构造系列 数组s={ s1,s2,..,sm}
每个si包含n个元素, si中的的值\in [1,k]
对于 任意的长n 值在 [1,k]的数组a, 至少在你给的s中存在一个si是a的祖先
问s的最小长度 mod 998244353
n,k 2e5
6s
512mb
si 通过 F,G的操作能变成任意数组
一个纯数字的数组, 那么通过F操作一定是自己的祖先,
两个不同的纯数字数组, 通过一次G操作 互为祖先
纯数字数组, 通过两次操作G一定是自己的祖先,
每个数组通过巨大k 操作, 都能变成纯数字数组
G的性质, 让数组的内容和具体值无关, 变成的一段一段的同样的值,(可以看成交换)
所以 比如 xxxyyyxxzz 是否能达到, 就是看 111221133 是否能达到
F的性质, 则是说不要考虑任何 x * w y * w z * w 的形状, 也就是能找到一个连续段的分割, 因为它总对应一个更小的
如果 k >= n, 那么就好了 [1,2,3,…,n], 啥都能变
–
考虑 k < n
两个没有 前缀 循环节的如何判断是否可以相互转化呢
1 | n=5,k=4 |
一个猜想, 没有用完k的一定可以由 用完k的转化来, 因为至少有同色的个数 >= 2, 而且它不能转化回去(所以它的父一旦能被表示它则一定被表示, 所以它自身不需要存在)
两个序列之间如果可以转化 则 一定没有F操作, 否则形状会变有周期的,
而两个序列如果之间有G操作, 则不满足 从小到达命名1,2,3,4 的性质
综上, 需要统计
长度n, 用完k个,没有循环段, 且满足顺序赋值的个数(每个位置的值 <= 之前用的最大值+1)
有循环段很好算,枚举循环长度就行, 所以就找出满足 顺序赋值 的个数 再来减法
f[i][t] = 前i个最大命名为t的方案数
f[i][t] = f[i-1][t] * t + f[i-1][t-1] * 1, 分别是用前面一样的和用更大的
那么ans = f[n][k] - 有循环段的
直接搞是 O(n^2)
看成生成方程
$f_i(x) = f_{i-1}’(x) x + x f_{i-1}(x)$
$f_i(x)e^x = x (f_{i-1}e^x)’$
$令a_i = f_i(x)e^x$
再看 系数 $a[i][t] = a[i-1][t] * t$
所以 $a[n][t] = a[0][t] * t^n$
然后乘上$f[n] = a[n] * e^{-x}$ 就能得到 f[n][k]完了?
$a[0] = f[0] * e^x$
似乎有点问题
https://codeforces.com/contest/1651
塔防游戏, i位置上 塔 能量上限c[i] 每秒充能r[i], 初始满能量
一关卡 生成 q 个怪, 第j个怪, 在point 1位置, tj时刻, 生成, 血量hj, 移动速度1格子/s
当怪经过 塔时, 塔对它 造成 min(怪血量,塔能量) 的伤害, 并且消耗同样多能量
但是还是会有的怪 活着经过所有塔
求 或者的怪的血量和
n 2e5
ci,ri [1,1e9]
q 2e5
tj [0,2e5] 保证严格单调递增
hj [1,1e12]
假设 每个怪都不死, 而且每个塔充能无上限
那么除了第一个怪, 第i个怪 受到的伤害 = (i与i-1的时间差) * (sum r)
但似乎没有什么帮助
再看 既然 伤害唯一来源是塔, 那么 伤害 + 剩余血量 = 总血量
如果能计算出塔实际造成的伤害, 那么 剩余血量也可以算出
第一个塔
min(c[1],h[1]): c[1] -> c[1] - min(c[1],h[1]) = p[1]
min(c[1],p[1]+r[1](t[2]-t[1]),h[2])
.. 感觉就是关联很紧, 如何消除这种 强关联
第一个 假设在 塔i倒下 或 塔j倒下, 有啥不同
i倒下, 说明i-1都是完全能量, j 倒下,说明j-1塔都是完全能量, min(i,j) -1 都是完全能量
所以看起来需要一个前缀能量和
而第二个 如果 在 p2 倒下, 第一个在p1 倒下
那么 如果哦 p2 < p1 对于 前 p2-1 对 第二个造成的伤害 就是 = sum min((t[2]-t[1])r[i],c[i])
一个与t,i 相关的 函数, 对于给定t, 随i严格单调递增, 但是问题是 难以?快速求点值, 不然可以二分
另一个问题, 如果 p2 > p1, 那么超出的部分还要和 更前面的相关
想拆一个单独x, 或者调整血量, 似乎都没啥能和原题方案一致的办法
感觉很卡在一个 无法快速计算一轮的结果
换个视角, 不按怪来看, 按塔来看
第一个塔接受的是 (t0,h0) (t1,h1) …
输出的内容被第塔接受, 而可以通过时间偏移让时间不变 (t0,h0_1) (t1,h1_1) (t2,h2_1)...
那么问题变成
有一堆点 (t0,h0) (t1, h1)
依次 n个操作 (ri,ci), 对每个点的高度进行修改, 问最后的高度和
看起来 每个h变化在允许小于0时, 下降要么是 ci, 要么是间隔 * ri ?
但实际上并不是, 可能是击倒了上一个 有残余
但是每个单位最多被击倒一次!
n次 残余情况, 剩下的都是 ci, 间隔 * ri
如果 h > ci 一定不被击倒, 如果 h < min(间隔 * ri, ci), 一定被击倒
还剩 间隔 * ri < h < ci 的情况
感觉上需要 实现一定的区间操作, 而且可能需要先排序什么的?
https://codeforces.com/contest/1701
如果 i < j < k 且 k-i <= d 则 称作美丽
初始没有点, q次操作, 每次操作3种可能
保证 集合中不会有相同点
每次操作后 计算 美丽的三元组个数
q 2e5
d 2e5
a[i] 点坐标 [1,2e5]
6.5 s
512 mb
简单讲, 就是 选两个距离小于d的点作为首尾, 然后问它们之间其它点的个数 作为贡献, 的贡献和
维护
其实增加一个点, 和删除一个点, 并不会影响其它点的组合,
影响的 三元组一定和操作的这个点有关
如果它是 最小的
= sum_{l=2~d} count(i,i+l) * c[l]
如果暴力算, 需要 O(d)
如果它在中间
= sum_{l=1~d-1} count(i,i-l) * c[i+d-l]
也是O(d)
感觉 似乎可能按照sqrt(max{a}) 分块
分块 对于不在中间的情况还好, 因为 相当于计算 (i,i+d] 之间 的不同值的点对个数, 在一个块里 预计算了, 在不同块里, 通过前缀和 可以算掉,
问题是 当加入的/删除的 为中间点时, 那么要找的就是 i < point < k, 且 k-i <= d
不知道有啥办法搞