标签：题目 sum solution 大意 binom 杂题考虑

杂题乱刷

杂题乱刷

P7231 COCI2015-2016#3] DOMINO

有个$n^2(n\le2e3)$大小的矩阵，每个点有个权值，有$k(k\le8)$个$1\times2$的多米诺骨牌，要求骨牌间不能重叠，求骨牌覆盖的权值和最大值

考虑朴素网络流，黑白染色二分图，再加一条限制总流量为k，跑费用流，可以考虑优化

我们发现k很小，考虑优化建图，手模发现，放置一个骨牌最多影响8个骨牌放置的位置（包括本身），所以根据求最大权值和，可以只找到前7k大的边建图，即可通过

CF888G Xor-MST

给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$，求MST

考虑Kruskal的流程，优先边权小的，没相连的点的连接起来，然后就考虑用a来建trie，然后考虑肯定是先选下面的点合并，然后就遍历一遍trie，然后考虑向上合并，两堆点找最小的一条边，然后合并再一起

然后发现可以启发式合并，然后暴力处理即可

有几个小tips：

把a排序后，trie子树对应的是连续区间，可以简化合并过程
trie数上恰有(n-1)个点有两个儿子，其他都是一个儿子，所以刚好是就是这种情况才连边

CF1886E

题目大意

每个人有能力值$a_i$，每个怪有个生命值$b_i$，给每个怪分配若干个人（不能为0，但可以有人不打怪）

若有k个人打怪i，那么要求每个人的能力值大于等于$\frac{b_i}k$

若合法，求方案

solution

考虑简单贪心，把a值排序，每个怪对应的人一定连续

然后可以处理出$dis_{i,j}$，表示以i为开头打怪j，要$i\sim dis_{i,j}$的人一起

然后考虑求一下后缀最小值，$dis_{i,j}$表示用i之后的人打怪，最少用到$dis_{i,j}$号人，然后再顺便处理出$st_{i,j}$表示这种情况用的人是$st_{i,j}\sim dis_{i,j}$

然后就可以愉快状压了，设$f_s$表示刷怪情况为s最后的人最前为多少

然后找一个怪打，然后转移，记录前驱即可

CF1209G2 Into Blocks (hard version)

题目大意

给定一个序列，定义一次操作(x,y)表示把所有元素x改为y，代价为元素x的数量

问把序列变成同一元素必须连续一段的最小操作代价和

每次修改一个元素的值，并询问

solution

不考虑修改，我们考虑如何做

我们找到每个元素对应的最前和最后的位置，组成一个区间，可以发现相交的区间最后一定会变成相同元素，所以把区间取并，然后每个区间内的代价就是长度-众数元素的数量

然后考虑带修，我们先用值域个set维护所有元素的区间，考虑一个经典的维护区间并的做法：

把区间$[l,r]$变成$[l,r)$的区间加1，那么我们发现区间并的断点就是值为零的地方

然后考虑维护众数，可以把数量挂在区间的左端点，然后查最值

最后就是考虑如何结合起来，先考虑已经处理好一个区间，最左断点左边的最值mxl，中间若干段的最值和ans，最右断点右边的最值mxl，全局最值mx，然后答案就是n-根节点的mxl,ans,mxl

有什么问题呢？

我们想直接让0为断点，发现如果区间的值变为零后，我们必须递归下去处理，时间复杂度会错

所以就有个小妙招，让区间最小值为断点，可以很简单的处理上面的问题，并且n这个位置的值一定是0，所以答案还是正确的

CSP-S2019Emiya 家今天的饭

题目大意

有一个n*m的网格图($n\le100,m\le2000$)，每个点有个权值，不能不选，每行最多能选一个，不能出现有某一列选的超过一共选的一半，每种方案的代价是权值的积，问所有合法方案的代价和

preface

三个限制：

不能不选
每行最多能选一个
不能出现有某一列选的超过一共选的一半

我们发现最后一个比较难搞，然后我就想先枚举一共选的个数，然后每列选择的个数就确定了，然后按列DP

结果发现不好打，因为每行的只能选1个，只有记录前面的状态才能转移，所以只能按行DP

正解

发现只能按行DP，那应该怎么办呢？

首先对于条件3，容斥一下，发现最多只有一列会不合法，所以方案数=总数-$\sum$有一列不合法

然后枚举那一列，按行DP，设$f_{i,j,k}$表示第i行，特殊列选了j个，其他列选了k个的方案数

统计答案就是$i=n,j>k$的和

根据计算答案的方法，可以发现 j，k是什么并不重要，只要知道它们的大小关系即可

考虑重新设计状态$f_{i,j}$表示第i行，特殊列选的数个-其他列选的个数=j的方案

然后就是$O(mn^2)$的复杂度

What I have got

大胆考虑容斥，特殊条件可能会减少时间复杂度

对于行列条件不同时，都考虑DP顺序

P4151 [WC2011] 最大XOR和路径

求1到n的最大XOR路径

我们考虑把路径拆成若干环和链，假如我们先选择了一个1到n的链，我们可以找一个环拓展，具体来说，就是通过一条链到环，再遍历一遍环，再从链回来，于是发现链走了两次，就等价于只走了一个环

所以就是找到全部环（其实就是返祖边对应的环），放进线性基里，然后随便找个1到n的链询问

什么是对的？

随便的链如果不优，一定会被某个环更新

返祖边对应的环，通过一些重集可以搞出全部的环

[CF510D]Fox And Jumping

题目大意

给出 $n(n\le300)$ 张卡片，分别有 $l_i$ 和 $c_i$。在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 $-1$。

solution

第一次系统学裴蜀定理

定义：设$a,b$为非0整数，则一定存在$x,y$，满足$ax+by=\gcd(a,b)$

有逆定理，可以拓展到多元

对于本题，跳到全部位置相当于找到若干l，满足存在$k_1...$使$\sum k_il_i=1$，根据裴蜀定理的逆定理，就是$\gcd(l_1,l_2...)=1$

所以可以类似背包转移，然后用map处理一下，感受一下不会很多状态

ABC332G

题目大意

给定n种球，每种分别有$a_i$个，有m个盒子，每个盒子可以放$b_i$个球。特殊的，第i种球放在第$j$个箱子的最大数量为$i\times j$，问最后可以放最多可以放几个球($n\le500,m\le5e5$)

solution

首先可以非常简单的建出网络流，二分图，原点向第i个点连$a_i$的边，第j个点向汇点连$b_i$的边，$(i,j)$连$i\times j$的边，最大流是答案。然后就最大流转最小割，求$\sum_{i\in A}a_i+\sum_{j\in B}b_i+\sum_{i\in\complement A}\sum_{j\in\complement B}j$

一开始想了一个$(n+m)n^2m^2$的dp，表示$f_{i,j}$表示A集合中下标和为i，B集合中下标和为j的最小值，背包转移

然后考虑优化一下，观察一下，n比较小，设$f_i$表示A集合中下标和为i，$a_i$的最小和，然后对于每个j，贡献是$min(i\times j,b_j)$，最后按$b_j/j$排序，那么贡献就被分成两部分，用双指针+前缀和维护即可

P3354[IOI2005] Riv 河流

题目大意

给定一棵树，有边权$dis$，点权$w$，可以在树上染k个黑点（根节点本来就是黑点），那么每个点的贡献就是点权$\times$离它最近的被染色祖先的距离，问总贡献的最小值

solution

首先想一个很简单的暴力，设$f_{i,j,k}$表示到节点i，剩下有权值和为j的往上，已经染了k个点，然后发现第二维非常没用...权值和太难搞了，还要背包转移，于是考虑点权一定会到一个祖先被计算

设$f_{i,j,k}$表示到节点i，离i最近的被染色祖先深度为j，已经染了k个点，子树中的贡献+没计算的直接移动到祖先的贡献

然后就只有第三维要背包转移，根据以前的证明，时间复杂度大致是$O(n^2k)$

[P3565[POI2014] HOT-Hotels](https://www.luogu.com.cn/problem/P3565)

给定一棵树，在树上选 3 个点，要求两两距离相等，求方案数。

solution

可以发现选3个点，两两距离相等，一定存在一个中心点，满足到三个点的距离相等，于是考虑统计中心点

我们设$f_{i,j}$表示i的子树内到i距离为j的点数，设$g_{i,j}$表示i的子树内，$l=lca(x,y),dis(l,x)=dis(l,y)=dis(i,l)+j$的$(x,y)$的数量

首先考虑暴力转移，f的转移很显然是$o(n^2)$的，g先从从儿子更新，然后再利用f更新

然后想想如何优化，发现第二维和深度有关，于是考虑长链剖分（见长链剖分&DP）

[CF521D Shop](Shop - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目大意

有 $k$ 个正整数 $a_{1\dots k}$。

有 $n$ 个操作，每个操作给定正整数 $t, i, b$，有三种可能：

如果 $t = 1$，这个操作是将 $a_i$ 赋值为 $b$；
如果 $t = 2$，这个操作是将 $a_i$ 加上 $b$；
如果 $t = 3$，这个操作是将 $a_i$ 乘以 $b$。

你可以从 $n$ 个操作中选择最多 $m$ 个操作，并按照一定顺序执行。

你的目标是最大化 $\prod_{i=1}^k a_i$ 的值。

$k,n \le 10^5$。

solution

可以想到贪心

首先，操作一定是先赋值，再加，最后乘

其次，赋值操作只会取最大的，然后减去初始值，变成加操作

最后，加操作一定是从大到小选，那么把它变成乘操作

于是就只剩下乘操作，它问的是 $\prod$ ，所以是等价的，排序即可

[[ARC160D] Mahjong]([ARC160D] Mahjong - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目大意

找到可以通过以下两种操作，使得长度为 $N$、元素之和为 $M$ 的数列 $A$ 全为 $0$ 的 $A$ 的个数，再取模 $998244353$。

在 $A$ 中选一个元素，将其减去 $K$。
在 $A$ 中选取长度为 $K$ 的子串，子串中每个元素减去 $1$。

$1\le K\le N\le2000,1\le M\le10^{18}$

solution

我们发现，在一个区间做k次操作2，就会算重

于是问题转化成，有 $2n-k+1$ 个元素，和为 $\frac mk$ ，要求前 $n-k+1$ 个元素的值都小于k，求方案数

我们考虑容斥，有i个元素不满足小于k，其他位置随便的方案，然后用插板法即可

\[ans=\sum_{i=0}^{n-k+1} (-1)^i\binom{n-k+1}{i}\binom{\frac mk-ik+2n-k}{2n-k} \]

[ARC167C] MST on Line++

题目大意

给定正整数 $n,K$ 和一个长度为 $n$ 的序列 $A$。对于一个 $1\sim n$ 的排列 $P$，我们定义 $f(P)$ 为以下问题的答案：

给一个 $n$ 个点的无向带权图，对于两点 $i<j$，当且仅当 $j-i\le K$ 时，它们之间有边，边权为 $\max(A_{P_i},A_{P_j})$。
求这个图的最小生成树边权和。

对于所有可能的排列 $P$，求出它们的 $f(P)$ 之和，答案对 $998\,244\,353$ 取模。

$1\le K< N\le 5000$，$1\le A_i \le 10^9$。

solution

考虑分别考虑对于每个 $A_i$ 算答案，考虑定义 $f_i$ 为下面问题的答案：

对于所有排列 $P$ ，有一个边权限制i，考虑 $|x-y|\le k \&\&\max(P_x,P_y)\le i$ 的边。要求边之间不形成环， $f_i$ 为最多能选的边数的和

根据Kruskal的流程，可以发现 $f_i-f_{i-1}$ 就是大小为 $i$ 的边算的次数，于是：

\[ans=\sum_{i=2}^N A_i(f_i-f_{i-1}) \]

那么我们应该如何计算 $f_i$ 呢？

我们对于一个排列 $P$ 分开考虑，把 $P_j\le i$ 的元素下标 $j$ 提出来，组成集合 $Q$ ，那么其答案为 $\sum_{j=2}^i[Q_j-Q_{j-1}\le K]$

对于每个 $j$ 分别计算全部集合$Q$中，满足 $Q_j-Q_{j-1}\le K$ 的个数。首先 $Q_j-Q_{j-1}= K$ 的方案数是$\binom{n-k}{i-1}$，那么枚举j和k就得到 $(i-1)\sum_{j=1}^K\binom{n-j}{i-1}$

然后，一种集合 $Q$ 对了 $i!(n-i)!$ 种排列 $P$ ，可以计算：

\[f_i=i!(n-i)!(i-1)\sum_{j=1}^K\binom{n-j}{i-1} \]

CF1753C Wish I Knew How to Sort

题目大意

给定一个长度为 $n$ 的 01 序列 $a$ 和一种操作，你需要用这种操作将序列从小到大排序。

操作如下：

等概率随机选取两个位置 $i,j\ (i<j)$，若 $a_i>a_j$，则交换 $a_i,a_j$。

请你求出操作被执行的 期望次数。 .

solution

设区间有 $x$ 个 $0$ ，令 $k$ 为前 $x$ 位 $1$ 的个数，$sum=\dfrac{n(n-1)}2$

那么第一次有效操作的期望次数就是 $\dfrac{sum}k$

于是答案就是 $\sum_{k=1}^x \dfrac{sum}k$

[ARC148D] mod M Game

题目大意

场上 $2N$ 个整数， Alice，Bob轮流取数，Alice 先手，如果最终 Alice 取出的数字的和，与 Bob 取出来数的和，模 $M$ 后的结果相等，那么 Bob 获胜，否则 Alice 获胜。

solution

可以想到，若存在 $x \equiv y \pmod M$ ，那么一定是先手取一个，后手去另一个，余数不变

若是有 $x \equiv y+\frac M2 \pmod M,u \equiv v+\frac M2 \pmod M$ ，那么无论先手怎么取，后手都能保证余数不变

那么我们成对删除上面两种情况，若还有剩余，则先手必胜

Majority

题目大意

定义一个$01$串$s$是好的，当且仅当$s$可以通过以下操作变成全是$1$的串，可以操作无数次

选择$i,j$满足$i<j,s_i=s_j=1,2\sum_{k=i}^js_k\ge j-i+1$，然后将$k\in[i,j]$的$s_k$全部改为$1$

给定$n$和$m$，求有多少个长度为$n$的$01$串是好的，对$m$取模

solution

正难则反，我们考虑计算补集

一个串不是好的要求满足

任意一段连续的 $0$ 的数量要大于等于左右都做完的连续的 $1$ 的个数

于是设 $f_{i,j}$ 表示前 $i$ 位置，左右都是 $1$ ，经过操作，最后有 $j$ 个 $1$

\[f_{i,i}=2^{i-2}-\sum_{j=1}^{\lfloor\frac {i-1}2\rfloor}f_{i,j}\\ f_{i,j}=f_{j,j}\sum_{j+2}^{i-j-1}\sum_{l=1}^{k-j-1}f_{i-j-k,l} \]

发现转移是个倒三角，于是可以斜着维护前缀和

[ARC151E] Keep Being Substring

题目大意

有一个序列 $A$。$X,Y$ 是给定的 $A$ 的两个子串，每次可以在 $X$ 的开头或末尾增添或删除一个数字，且需满足任意时刻 $X$ 非空且为 $A$ 的子串，求把 $X$ 变成 $Y$ 的最少次数。

solution

若 $X$ 和 $Y$ 有公共子串，那么答案就是 $|X|+|Y|-2|lcp|$ ，用SAM计算即可

否则就是把 $X$ 删成一个，再把它加成 $Y$ 的一个数字，再加成 $Y$

建图，$a_i$ 向 $a_{i+1}$ 连边，以 $X$ 中的数字位起点，跑最短路，再 $Y$ 中找最近的dis，答案就是 $|X|+|Y|+dis-2$

Yet Another Partiton Problem

题目大意

给定数组 $a_1,a_2\cdots a_n$，你需要将它划分成 $k$ 段（每个元素在且仅在一段中），某段 $a_l,a_{l+1}\cdots a_r$ 的权值为 $(r-l+1)\times \max_{l\leq i\leq r}\{a_i\}$，整个划分的权值是每段权值之和。求最小划分权值。

$n \leq 2 \times 10^4$，$k \leq 100$。

solution

可以想到 $O(n^2k)$ 的DP

\[f_{i,j}=\min_{k=1}^j\{f_{i-1,k}+(i-j)\max_{l=k+1}^ja_i\} \]

发现贡献不满足四边形不等式，没有决策单调性，考虑 $O(nk\log n)$ 的做法，对每层转移优化

方法一：

我们考虑一个后缀的单调栈，那么在一个区间的最大值是固定的，那么再一个最大值区间中的转移可以斜率优化，维护一个凸包，然后对于每个区间的最值，我们可以发现它是凸的

可以用两个李超树，或者把其中一个改成启发式合并凸包解决

方法二：

分治处理，考虑 $[l,mid]$ 对 $[mid+1,r]$ 的贡献

令 $\begin{equation} mx_i=\left\{ \begin{aligned} \max_{j=i+1}^{mid}a_j(i\le mid) \\ \max_{j=mid}^{i}a_j(i> mid) \\ \end{aligned} \right. \end{equation}$

那么转移就是

\[f_{i,j}=\min_{k=1}^j\{f_{i-1,k}+(i-j)\max(mx_i,mx_j)\} \]

若$mx_i> mx_j$，转移为 $g_j-j\times mx_i+i\times mx_i$，从小到大枚举 $i$ ，加入斜线 $y=jx+g_j$ ，斜率递减，查询横坐标变大，可以用单调栈维护
否则 $mx_i\le mx_j$，同理，维护直线，查询横坐标

斜率优化可以根据题目，分成两种：

维护点，查询斜率（单调队列）
维护直线，查询横坐标（单调栈）

当然要满足两个单调性才能做到线性，否则要用分治，二分等处理

[ARC061F] 3人でカードゲーム

题目大意

三人$a$, $b$, $c$面前分别有 $N$ ,$ M$ , $K$ 张牌，每张牌上写了$a$,$b$,$c$中的一个, 规则如下：

第一回合是$a$的回合,若轮到某个玩家行动时他面前没牌了，该玩家获胜，否则拿出牌堆中的一张牌，丢掉它，并进入该牌上写着的玩家的回合

游戏开始前牌的所有情况共 $3^{n+m+k}$ 种

求 $a$ 获胜的情况数，对 $1e9+7$ 取模

solution

轮到某个玩家行动时他面前没牌了，该玩家获胜

我们考虑一个合法状态的映射关系，假设游戏结束了，出的牌形成的序列，一定满足下列规律：恰好 $N$ 个 $a$ ， $b$ 的个数小于等于 $M$ ， $c$ 的个数小于等于 $K$ ，最后一个一定是 $a$ 。那么剩下的就可以乱选

于是考虑钦定 $b,c$ 的个数 $t$ ，那么方案数为：

\[\sum_{t=0}^{m+k}\binom{n+t-1}{t}3^{m+k-t}\sum_{i=t-k}^m\binom ti \]

后面一部分是一行组合数的区间和，但比较特殊：

\[S(t)=\sum_{i=t-k}^m\binom ti \\=\sum_{i=t-k}^m\binom {t-1}{i-1}+\sum_{i=t-k}^m\binom {t-1}{i} \\= \sum_{i=t-k-1}^{m-1}\binom {t-1}{i}+\sum_{i=t-k}^m\binom {t-1}{i} \\=2\sum_{i=t-k-1}^m\binom{t-1}i-\binom{t-1}m-\binom{t-1}{t-k-1} \\=2S(t-1)-\binom{t-1}m-\binom{t-1}{t-k-1} \]

于是可以递推

P3349 [ZJOI2016] 小星星

题目大意

给定一个图和一棵树，点数相同，问有多少种对应关系满足树上的边在图上都存在。（ $n\le17$）

solution

考虑往树上填排列，排列这个要求不好做，考虑容斥掉。一个经典的想法是，枚举一个点集 $S$ ，表示只能填 $S$ 中的元素，计算方案数，那么答案就是：

\[(|S|=n的方案数)-(|S|=n-1的方案数)+(|S|=n-2的方案数)... \]

于是就没有排列的限制，然后再设 $f_{i,j}$ 表示以 $i$ 为根的子树，填了 $j$ 的方案数， $O(n^3)$ 计算即可

总复杂度： $O(2^n n^3)$

标签：题目,sum,solution,大意,binom,杂题,考虑
From： https://www.cnblogs.com/zhy114514/p/18258947

杂题乱刷1

杂题乱刷

P7231 COCI2015-2016#3] DOMINO

题目大意

solution

题目大意

solution

题目大意

preface

正解

What I have got

题目大意

solution

题目大意

solution

题目大意

solution

[P3565[POI2014] HOT-Hotels](https://www.luogu.com.cn/problem/P3565)

solution

[CF521D Shop](Shop - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目大意

solution

[[ARC160D] Mahjong]([ARC160D] Mahjong - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目大意

solution

[ARC167C] MST on Line++

题目大意

solution

CF1753C Wish I Knew How to Sort

题目大意

solution

[ARC148D] mod M Game

题目大意

solution

Majority

题目大意

solution

[ARC151E] Keep Being Substring

题目大意

solution

Yet Another Partiton Problem

题目大意

solution

[ARC061F] 3人でカードゲーム

题目大意

solution

P3349 [ZJOI2016] 小星星

题目大意

solution

相关文章

赞助商

阅读排行