wjyppm's Blog

T1 8 数码问题简化版，O(7!)O(7!)O(7!) 爆搜 BFS，没了。 T2 ∑i=0m+1(n+1i)=∑i=0m(ni)+(n−1i)\sum\limits_{i=0}^{m+1}\binom{n+1}{i}=\sum\limits_{i=0}^{m}\binom{n}{i}+\binom{n-1}{i} i=0∑m+1​(in+1​)=i=0∑m​(in​)+(in−1​) ∑i=0m+1(ni)=∑i=0m(ni)+(nm+1)\sum\limits_{i=0}^{m+1}\binom{n}{i}=\sum\limits_{i=0}^m \binom{n}{i}+\binom{n}{m+1} i=0∑m+1​(in​)=i=0∑m​(in​)+(m+1n​) 时间复杂度为 O(n)O(n)O(n)，瓶颈在预处理组合数。 T3 Subtask 1 暴力枚举排列，逆序对也可以暴力统计，时间复杂度 O(7!)O(7!)O(7!)。 Subtask 2 注意到暴力枚举排列不行，但是注意到这个只和排列奇偶性有关。本质上就是求行列式。具体的就是照题目的把矩阵 [...

前言 省流：300 分。 T1 考虑 DP，设 f(i,0/1/2)f(i,0/1/2)f(i,0/1/2) 表示处理到第 iii 个数，当前是往左，不动，往右，方案是否合法，转移如下： f[i][0]=f[i−1][0]⋅[xi−xi−1=1]+f[i−1][1]⋅[xi−(xi−1−1)=1]+f[i−1][2]⋅[xi−(xi−1+1)=1],f[i][1]=f[i−1][0]⋅[xi−1−xi−1=1]+f[i−1][1]⋅[xi−1−(xi−1−1)=1]+f[i−1][2]⋅[xi−1−(xi−1+1)=1],f[i][2]=f[i−1][0]⋅[xi+1−xi−1=1]+f[i−1][1]⋅[xi+1−(xi−1−1)=1]+f[i−1][2]⋅[xi+1−(xi−1+1)=1],\begin{aligned} f[i][0] &= f[i-1][0] \cdot [x_i - x_{i-1} = 1] + f[i-1][1] \cdot [x_i - (x_{i-1} - 1) = 1] + f[i-1][2] \c...

0. 前言 我们主要讨论的就是广义的圆方树。 1. 介绍 广义圆方树是刻画图上点连通性的工具，是 Tarjan 算法的一个强有力拓展。广义圆方树能够述原图任意两点之间的所有割点，即路径 u→vu\to vu→v 上所有必须经过的点。下面有一张图来举例： 图的问题我们不好处理，但是众所周知，树上问题是比普通的图论问题处理起来方便得多的。所以我们将图转化为圆方树的意义就是在于通过树上的算法简化问题。 广义圆方树中的节点分为两类：圆点和方点，在上图中所表示出来。圆点就是原本图上的点，而每个方点都代表了一个点双联通分量。将每个方点和所有在这个联通分量中的点连起来。 注意，只有原图联通的时候才能是一棵树，如果不连通的话那么会形成森林。 我们在求解点双的时候可以顺便建出圆方树，以下为代码，adjadjadj 为原图，GGG 为圆方树。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<bits/stdc++....

0. 前言 你需要知道： FFT 或 NTT。 CDQ 分治。 1. 介绍 分治 FFT，用于解决这一个问题： 给定长为 n−1n-1n−1 的序列 ggg，求长为 n−1n-1n−1 的序列 fff，满足： fi=∑j=1ifi−jgjf_i=\sum_{j=1}^i f_{i-j}g_jfi​=∑j=1i​fi−j​gj​，边界为 f0=1f_0=1f0​=1。 要求时间复杂度 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 你可能会说：“这不就是卷积吗，FFT秒了！”但是你发现这玩意不太对劲，因为你卷积默认你是知道 fff，现在问题在于你不知道 fff，要一个一个求。 我们解决这个问题可以利用 CDQ 分治的思想，具体的，设 solve(l,r) 表示计算 g[l,r]g[l,r]g[l,r] 内这一段子问题的函数，注意这里算的不是 fif_ifi​，而是这一段自己对自己的贡献。为了我们 FFT 的方便，一开始肯定是调用 solve(0,1<<k) 的形式。 让后就是分治的部分，首先 midmidmid 劈成 [l,mid],[mi...

0.前言与ntt 组合数学过于差得我，必须重修！ ntt板子？其中MOD，G,INVG需要自行定义 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657namespace Poly{ int rev[MN]; int ksm(int a,int b){ int ret=1; while(b){ if(b&1) ret=ret*a%MOD; a=a*a%MOD; b>>=1; } return ret; } void dorev(int f[],int len){ for(int i=0;i<len;i++){ rev[i]=rev[i>...

把未感染和感染抽象为 0/1，那么原问题可以转化为初始有一个全为 111 的序列，可以在特定时间进行一次区间覆盖操作（有代价），111 会向左右扩散，问能不能将整个序列全部覆盖为 0 且使得操作代价最小。 对于选择区间进行覆盖的问题，这一类经典问题有一种状态设计就是设 f(i)f(i)f(i) 表示将 [1,i][1,i][1,i] 这个前缀进行覆盖的最小代价。但是问题在于这样转移是 O(nm)O(nm)O(nm) 的不太好搞，考虑这个 mmm 的瓶颈就是在于我们需要知道每一个覆盖区间右端点在哪里。考虑切换一下 dp 状态，设 f(i)f(i)f(i) 表示将 [1,ri][1,r_i][1,ri​] 覆盖的最小代价，转移通过 ttt 的偏序关系进行转移： f(i)←f(j)+cirj−li+1≥∣ti−tj∣\begin{aligned}f(i) & \leftarrow f(j)+c_i & r_j -l_i+1 \ge |t_i -t_j| \end{aligned} f(i)​←f(j)+ci​​rj​−li​+1≥∣ti​−tj​∣​ 时间复杂度还是 O...

题面过于复杂，有一个显然的想法就是让导师们去找学生，设 f(i,j,k,p)f(i,j,k,p)f(i,j,k,p) 表示四个导师选的人数状态下的方案数，转移判断满不满足题目中所给的派系和阵营限制即可，时间复杂度 O(nm4)O(nm^4)O(nm4)，不难发现只需要确定三个即可，时间复杂度 O(nm3)O(nm^3)O(nm3)。然后就不会了。 观察这个 DP 及其难以优化，因为如果我们缺任何一个信息都无法描述完整的子问题，而且复杂度要求的可是 O(nm)O(nm)O(nm)，你只知道一个信息那么肯定啥也导出不了啊。我们考虑发掘几个性质： 确定一个派系和一个阵营可以唯一确定一位导师。 题目中 ban 导师的相当于不选钦定的派系和阵营。 上述性质启示我们让每一个学生去确定它们的派系和阵营，而不是导师去确定学生。但是还有我们的 “坏” 学生，不喜欢选的。我们先丢掉它们，先考虑 k=0k=0k=0 的部分分。 有一个显然的 DP 就是 f(i,j)f(i,j)f(i,j) 表示 iii 个蓝阵营的人，jjj 个鸭阵营的人的方案数，剩余两个可以由这两个状态唯一表示出来，时间复杂度 ...

有很大一部分来自于 zxy，课件等，一般都是很强的 Trick。 CF1476F 考虑 DP，设 f(i)f(i)f(i) 表示前 iii 个灯可以点亮的最长前缀，有转移： iii 朝右，若 f(i−1)≥if(i-1)\ge if(i−1)≥i，则 f(i)=max⁡(f(i−1),i+pi)f(i)=\max(f(i-1),i+p_i )f(i)=max(f(i−1),i+pi​)，若 f(i−1)<if(i-1)<if(i−1)<i，则 f(i)=f(i−1)f(i)=f(i-1)f(i)=f(i−1)。 iii 朝左：不难发现只要将前缀覆盖到 i−pii-p_ii−pi​ 即可就行，设 jjj 为第一个 f(j)≥i−pif(j)\ge i-p_if(j)≥i−pi​ 的位置，那么 [j+1,i−1][j+1,i-1][j+1,i−1] 的位置都可以朝右，那么 f(i)=max⁡k=j+1i−1k+pkf(i)=\max\limits_{k=j+1}^{i-1}k+p_kf(i)=k=j+1maxi−1​k+pk​，可以二分 jjj 加 ST 表查出...