lp3868 TJOI2009 猜数字

这是一道中国剩余定理(又名孙子定理、CRT)的模板题。
它最早来自于「孙子算经」,形式化的说,它是一种用于求解如下的线性同余方程组的解的算法。
$$ \left\{ \begin{matrix}x\equiv a_{1} \pmod{p_1} \\x\equiv a_{2}\pmod{p_2}\\\cdots\\x\equiv a_{n}\pmod{p_i}\end{matrix} \right.$$
我们令:
$$\begin{equation}\begin{split}P&=&\prod_{i=1}^{n}p_{i}\\t_{i},st: \frac{P}{p_{i}}t_{i}&\equiv &1\pmod{p_i}\\\exists x,st: x&\equiv &\sum_{i=1}^n \frac{P}{p_{i}}a_{i}t_{i}\\x&\in&\{x_0+kP,k\in Z\pmod{P}\}\end{split}\end{equation}$$
然而这是怎么证明的呢?我们有如下推导:
$$\begin{equation}\begin{split}\forall i,\forall j,st:i\neq j, a_{i}t_{i}\frac{P}{p_{i}}&\equiv&0&\pmod{p_i}\\a_{i}t_{i}\frac{P}{p_i}&\equiv&a_{i} &\pmod{p_i}\\\forall j,\sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\equiv&a_{j}t_{j}\frac{P}{p_{j}} \equiv a_{j}&\pmod{p_{j}}\\\exists x_0&\equiv& \sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\pmod{p_{j}}\\\end{split}\end{equation}$$
故而我们就可以求得上述方程的最小正整数解。
另外,看到这题的数据范围就可以猜到又是龟速乘登场的时刻了。
这一题还有个坑点就是读入的数可能是负数…

#include<iostream>
#include<cstdio>

long long MOD=1;


inline long long mlt(long long A,long long X){
	long long BS=A,RT=0;
	while(X){
		if(X&1){
			RT+=BS;
			RT%=MOD;
		}
		BS+=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}
inline long long exgcd(long long A,long long B,long long &X,long long &Y,long long D=0){
	return B?(D=exgcd(B,A%B,Y,X),Y-=A/B*X,D):(X=1,Y=0,A);
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=mlt(RT,BS)%MOD;
		}
		BS=mlt(BS,BS)%MOD;
		X>>=1;
	}
	return RT;
}
long long n,a[100005],b[100005];
void init(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&b[i]);
		a[i]=(a[i]%b[i]+b[i])%b[i];//注意负数!! 
		MOD*=b[i];
	}
	long long X,Y,T,ans=0;
	for(int i=1;i<=n;++i){
		T=MOD/b[i];
        exgcd(T,b[i],X,Y);
        X=(X%b[i]+b[i])%b[i];;
        ans=(ans+mlt(mlt(T,X),a[i]))%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
}

int main(){
	init();
	return 0;
}

lp2044 NOI2012 随机数生成器

我们不妨将原式递归展开,可以得到形如此的式子:
$$f_{n}=a^nf_{0}+\frac{(a^{n}-1)c}{a-1}$$
对于这个式子的值,我们看似可以上一个快速幂直接求得。
然而仔细观察上式的情况,发现如果出现了奇妙的模数时,\(a-1\)是不一定有逆元的!
这就很令人难受了。
我们找到原来的问题,我们不得不求下述式子的值:
$$f_{n}=a^nf_{0}+\sum_{i=0}^{n-1}a^ic=a^nf_{0}+(\sum_{i=0}^{n-1}a^i)c$$
求值的最大障碍是这个式子:
$$\sum_{i=0}^{n-1}a^i$$
将这个式子分奇偶讨论后递归求解。
我们令:
$$u_{x}=\sum_{i=0}^{x-1}a^i$$
若是偶数,则有:
$$u_x=\sum_{i=0}^{\frac{x-1}{2}}a^i+a^{\frac{x+1}{2}} (\sum_{i=0}^{\frac{x-1}{2}}a^i)$$
即,
$$u_x=(a^{\frac{x+1}{2}}+1)u_{\frac{x-1}{2}}$$
若是奇数,则只需将第一项单独计算。
这样就可以在对数复杂度内对式子求解了。
另外,考虑到模数的数据范围,我们需要使用一种被称为「龟速乘」,也就是「快速幂」在乘法意义上的等同的操作,使得不会出现乘法,也就不会爆范围。

#include<iostream>
#include<cstdio>

long long MOD,a,c,x0,n,g;
//必须注意,不能重载一个全部是标准型的运算符。 
inline long long mlt(long long A,long long X){
	long long BS=A,RT=0,CNT=X;
	while(CNT){
		if(CNT&1){
			RT+=BS;
			RT%=MOD;
		}
		CNT>>=1;
		BS+=BS;
		BS%=MOD;
	}
	return RT;
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1,CNT=X;
	while(CNT){
		if(CNT&1){
			RT=mlt(RT,BS)%MOD;
		}
		CNT>>=1;
		BS=mlt(BS,BS)%MOD;
	}
	return RT;
}
inline long long calc(long long X){
	if(X==2){
		return (a+1)%MOD;
	}
	if(X==1){
		return 1;
	}
	if(X&1){
		return (pw(a,X-1)+calc(X-1))%MOD;
	}
	return mlt((pw(a,(X+1)>>1)+1),calc(X>>1));
}
void init(){
	scanf("%lld%lld%lld%lld%lld%lld",&MOD,&a,&c,&x0,&n,&g);
	printf("%lld",((mlt(pw(a,n),x0)+mlt(calc(n),c))%MOD)%g);
}

int main(){
	init();
	return 0;
}

lp3803 【模板】多项式乘法(FFT)(NTT实现)

程序运行效率。(评测系统为duck.ac)

我们现在已经有一种快速完成多项式卷积的方案了。然而这种方案还存在两个缺陷。
首先,是浮点型运算带来的精度误差。这在多次乘积之后会不断扩大,最终到一个无法解决的地步。
第二,就是结构体运算带来的大常数。这也使得这道题的时间限制变得比较紧张。
于是,我们考虑另辟蹊径,使用某一种大模数来完成整数多项式卷积。
快速数论变换(Fast Number Transform)就是一种这样的算法。

回到FFT的本质,FFT是一种精确选取取值以后代值优化系数表达和点值表达相互转化的方案。我们尝试在模意义下找到一些满足与单位复根性质类似的数。
一种在数论上被称为原根的数可以满足这一族性质。
首先我们有原根的定义。
形式化的说,若\(g\)模\(p\)的阶等于\(\phi(p)\),则称\(g\)为\(p\)的一个原根。
具体来说,我们认为,若\(g^x \equiv 1\ (mod\ p) \)总是有解,那么我们称\(g\)是质数\(p\)的一个原根。
对于\(\forall g\in Z,p\in P\),总是有\(g^{p-1}\equiv 1\ (mod\ p) \)
那么,对于一个\(p=t2^{k}+1\)我们有,\(g^{\frac{p-1}{2^i}}\ (0\le i\le k)\)在模$latexp$意义下始终有正整数解。这一点和单位复根类似。
通过选取满足上述条件的质数,即\(p=t2^{k}+1\),我们还有这样的性质:
消去引理:
$$g^{\frac{dk(p-1)}{dn}}\equiv g^{\frac{k(p-1)}{n}}$$
折半引理:
$$(g^{\frac{(k+\frac{n}{2})(p-1)}{n}})^2\equiv (g^{\frac{k(p-1)}{n}}g^{\frac{p-1}{2}})^2\equiv (g^{\frac{k(p-1)}{n}}(p-1))^2\equiv (g^{\frac{k(p-1)}{n}})^2$$
求和引理:
$$\sum_{j=0}^{n-1}(g^{\frac{k(p-1)}{n}})^j\equiv \frac{(g^{\frac{k(p-1)}{n}})^n-1}{g^{\frac{k(p-1)}{n}}-1}\equiv \frac{g^{k(p-1)}-1}{g^{\frac{k(p-1)}{n}}-1}\equiv \frac{1^k-1}{g^{\frac{k(p-1)}{n}}}\equiv 0$$
折半引理的一个推论:
$$\sum_{i=0}^{n-1}g^{\frac{i(p-1)}{n}}\equiv 0$$
我们惊讶地发现原根具有单位复根具有的三个定理和一个推论。这说明,我们可以将快速傅里叶变换的操作以原根的形式拓展到模意义下。
我们令:
$$\omega_{n}^{k}=g^{\frac{k(p-1)}{n}}$$
那么我们就可以简单地将快速傅里叶变换中的单位复根全部替换为原根,这样就实现了快速数论变换。
对于这里的模数\(p\),我们可以选取998244353,它是\(2^{23}*119+1\)。

#include<iostream>
#include<cstdio>
#define Swap(A,B) (A^=B^=A^=B)
const long long P=998244353;
const long long g0=3,gi=332748118;
//*****非常重要:gi是332748118!!!!!!! 
int L=1,R[1<<21|1];
long long invL;
inline int pw(int A,int X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=RT*BS%P;
		}
		BS=BS*BS%P;
		X>>=1;
	}
	return RT;
}
inline void prpr(int LEN){
	int B=0;
	while(L<=LEN){
		L<<=1;
		++B;
	}
	invL=P-(P-1)/L;
	for(int i=0;i<L;++i){
		R[i]=R[i>>1]>>1|(i&1)<<(B-1);
	}
}
inline void FNTT(int *A,int typ){
	for(int i=0;i<L;++i){
		if(R[i]<i){
			Swap(A[R[i]],A[i]);
		}
	}
	int gn,g,X,Y,M;
	for(int i=2;i<=L;i<<=1){
		M=i>>1;
		gn=pw(~typ?g0:gi,(P-1)/i);
		for(int j=0;j<L;j+=i){
			g=1;
			for(int k=0;k<M;++k,g=1ll*g*gn%P){
				X=A[j+k],Y=1ll*g*A[M+j+k]%P;
				A[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;
			}
		}
	}
}
int n,m,a[1<<21|1],b[1<<21|1];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=0;i<=m;++i){
		scanf("%d",b+i);
	}
	prpr(n+m);
	FNTT(a,1);
	FNTT(b,1);
	for(int i=0;i<L;++i){
		a[i]=1ll*a[i]*b[i]%P;
	}
	FNTT(a,-1);
	for(int i=0;i<=n+m;++i){
		printf("%d ",1ll*(a[i]+P)*invL%P);
	}
}

int main(){
	init();
	return 0;
}

lp3812 【模板】线性基

线性基这个名字似乎是来自于它的数学意义。它的用途一般是在集合异或的题目中简化复杂度。
对于关于一个数集的线性基,它是一个集合。这个集合包含的数大概是数集中的数取对2取对数个。
它满足以下性质:它们中的每个数异或在一起可以得到原数集中任何数的异或和。
它是一个尽可能小的集合。
它是「数集中线性无关的最大子集」。(这一定义会在之后的深入学习中概括)
它的每个数的二进制最高位互不相同。

构造一个线性基可以用贪心的构造法。
对于一个即将插入线性基中的数\(x\),我们必须尽量让它能够以某一种方式被线性基中已有的数构造出来。
我们不妨令线性基中第\(i\)个数表示的是最高位为第\(i\)位的数。
如果线性基中能够构造出这个数,那么显然,从高到低枚举每一个数,每一次都将它异或去最高位的线性基所代表的数,那么最终一定会有两种情况之一:
一:这个数存在,则这个数按照上述方法异或后最终肯定会变成0。
二:这个数不存在,则这个数按照上述方法异或后最终肯定会遇到某一位线性基,使得这个线性基并不存在。那么这个数就可以放到给定线性基上。
上述两个情况是很显然的,因为根本不存在上述两种情况之外的情况。对于任意一种情况它的较高位一定可以被异或掉,而随之诞生的较低位也可以依次按需异或掉。

为什么这样构造出来的东西一定是满足性质一的呢?如果原数集中任意一个数都可以通过线性基里的某些数异或得到,那么任意一些数的异或和也一定可以通过这些数在线性基里的表示法的异或和得到。

回到这一题。这些数中的最大异或和一定是线性基中的最大异或和。
根据最大异或和的贪心构造法(即从高到低尝试异或每一项,如果能变得更大就异或),这样得到的结果必然是一个原数集能够构造出的数。这是有线性基的插入方式决定的。
按照上述的插入方式,一个新的数\(x\)只会在它的某一位作为最高位在线性基中不存在的时候连同它剩余的位被插入。故而任何一个较后面的位的修改都一定是在原数集中可以构造出来的修改。
所以这一题可以用线性基解决。

#include<iostream>
#include<cstdio>

long long bs[105];
int n;
void init(){
	scanf("%d",&n);
	long long x;
	for(int i=1;i<=n;++i){
		scanf("%lld",&x);
		for(int j=50;j>=0;--j){
			if(x&(1ll<<j)){
				if(!bs[j]){
					bs[j]=x;
				}
				x^=bs[j];
			}
		}
	}
	x=0;
	for(int i=50;i>=0;--i){
		if(x<(x^bs[i])){
			x^=bs[i];
		}
	}
	printf("%lld\n",x);
}

int main(){
	init();
	return 0;
}

lp3648 APIO2014 序列分割

首先证明序列分割的次序和最后的答案毫无关系。
这可以用乘法的基本性质证明。例如分成三段,我们有:
$$a(b+c)+bc=b(a+c)+ac$$

我们可以进行DP。
我们记\(f_{i,k}\)表示当前访问到第\(i\)个点,使用了\(k\)次切割的答案。
那么根据题目中贡献的定义,我们有:
$$f_{i,k}=max_{j=k}^{i-1}{f_{j,k-1}+sm_{j}(sm_{i}-sm_{j})}$$ 令\(k\le j_1(sm_i-sm_{j_1})\le f_{j_2,k-1}+sm_{j_2}(sm_i-sm_{j_2})\)$ 展开,移项,合并。 $$f_{j_1,k-1}+sm_{j_1}sm_i-sm_{j_1}^2\le f_{j_2,k-1}+sm_{j_2}sm_i-sm_{j_2}^2$$ $$f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2\le sm_{j_2}sm_i-sm_{j_1}*sm_i$$
$$\frac{f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2}{sm_{j_2}-sm_{j_1}}\le sm_i$$
这个式子显然是可以斜率优化的。
这样做的时空复杂度是\(O(nk)\)的。
考虑到这一题的空间限制比较紧张,我们可以用滚动数组把\(k\)这一维压掉。

#include<iostream>
#include<cstdio>

int q[100005];
long long f[100005][2],sm[100005];
int ans[100005][205],n,K;
inline double slope(int j1,int j2,int k){
	return (sm[j1]^sm[j2])?(double)(f[j1][(k&1)^1]-f[j2][(k&1)^1]+sm[j2]*sm[j2]-sm[j1]*sm[j1])/(double)(sm[j2]-sm[j1]):-1E18;
} 
void init(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i){
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	for(int i=1;i<=K;++i){
		int l,r;
		l=r=1;
		for(int j=1;j<=n;++j){
			while(l<r&&slope(q[l],q[l+1],i)<=sm[j]){
				++l;
			}
			f[j][i&1]=f[q[l]][(i&1)^1]+sm[q[l]]*(sm[j]-sm[q[l]]);
			ans[j][i]=q[l];
			while(l<r&&slope(q[r-1],q[r],i)>slope(q[r],j,i)){
				--r;
			}
			q[++r]=j;
		}
	}
	int nw=n;
	printf("%lld\n",f[n][K&1]);
	for(int i=K;i>=1;--i){
		nw=ans[nw][i];
		printf("%d ",nw);
	}
}

int main(){
	init();
	return 0;
}

lp3803 【模板】多项式乘法(FFT)(非递归版本)

快速傅里叶变换(FFT)的一种较高效的实现

*由于快速傅里叶变换(FFT)常常被用在通信领域,故而FFT的实现效率成为了一个需要被考察的对象。

事实上,观察FFT的实现过程,我们发现它没有非递归不可的理由。

具体来说,我们发现,如果我们想要把FFT改造为递推模式,最大的障碍就是每一次合并操作。
在快速离散傅里叶变换中,每一次合并操作都会导致两个距离为\(\frac{n}{2}\)的点的值合并在一起。因此,如果将原序列传入,那么得到的就是一个乱序的队列。
我们考虑将序列以什么顺序传入。
我们发现,每一次这样的合并操作本质上都是将两个部分「翻转」了。
以0~7为例:
0 1 2 3 4 5 6 7
0 4 2 6 1 5 3 7
将它们写成二进制:
000 001 010 011 100 101 110 111
000 100 010 110 001 101 011 111
发现变换之后每个数的二进制位都倒转了。
故而我们可以通过倒转二进制位的方式来预处理原序列,使得FFT之后的序列顺序是正常的。
但是不知道是什么原因,这个代码跑出来的速度竟然也是4500ms…这就很让人挠头了。
于是向PinkRabbit巨神请教了几个经验:
1.不用中间数组,直接在原数组上操作。
2.调整赋值操作,使得修改尽量少。
3.将蝴蝶变换预处理为一个数组。
综合几点,就成功地卡到了2500ms
当然还是有待卡常,毕竟这还是一个比较危险的时间。

#include<iostream>
#include<cstdio>
#include<cmath>
#define PI 3.141592653589793238462

struct Complex{
	double r;
	double i;
	Complex(double ri=0.0,double ii=0.0):r(ri),i(ii){}
	inline Complex operator+(const Complex &B)const{
		return (Complex){r+B.r,i+B.i}; 
	}
	inline Complex operator-(const Complex &B)const{
		return (Complex){r-B.r,i-B.i};
	}
	inline Complex operator*(const Complex &B)const{
		return (Complex){r*B.r-i*B.i,r*B.i+i*B.r};
	}
}a[1<<21|1],b[1<<21|1],s[1<<21|1];
int r[1<<21|1];
inline void FFT(Complex *A,int N,int typ){
	//ButterflyTransform
	for(int i=0;i<N;++i){
		(r[i]>i)?std::swap(A[i],A[r[i]]),0:0;
	}
	Complex bs,nw,x,y;
	for(int i=2,mid;i<=N;i<<=1){
		bs=Complex(cos(2.0*PI/i),typ*sin(2.0*PI/i));
		mid=i>>1;
		for(int j=0;j<N;j+=i){
			nw=Complex(1.0,0.0);
			for(int k=0;k<mid;++k,nw=nw*bs){
				x=A[j+k],y=(A[mid+j+k]*nw);
				A[j+k]=x+y;
				A[mid+j+k]=x-y;
			}
		}
	}
}
int n,m,cnt=1,byt=0;;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i){
		scanf("%lf",&a[i].r);
	}
	for(int i=0;i<=m;++i){
		scanf("%lf",&b[i].r);
	}
	while(cnt<=n+m){
		cnt<<=1;
		++byt;
	}
	for(int i=0;i<cnt;++i){
		r[i]=(r[i>>1]>>1)|((i&1)<<(byt-1));
	}
	FFT(a,cnt,1);
	FFT(b,cnt,1);
	for(int i=0;i<cnt;++i){
		a[i]=a[i]*b[i];
	}
	FFT(a,cnt,-1);
	//注意这里typ应该是-1 
	for(int i=0;i<=n+m;++i){
		printf("%d ",(int)(a[i].r/cnt+0.5));
		//注意输出应该强转格式。 
	}
	puts("");
}

int main(){
	init();
	return 0; 
}

lp3195 HNOI2008 玩具装箱TOY

一道斜率优化的经典例题。
对于这道题,DP式是容易得到的:
$$f_i=min\{f_j+(\sum_{j+1}^ia_{i}+i-j-1-L)^2\}$$
前缀和优化:
$$f_i=min\{f_j+(sm_i-sm_j+i-j-1-L)^2\}$$
考虑到这是一个与取值平方相关的式子,尝试用斜率优化来化简。
令:
$$u_i=sm_i+i$$
$$f_i=min{f_j+(u_i-u_j-1-L)^2}$$
对于右式,我们假定\(1\le j<k<i\)且从\(k\)转移较优。
那么我们有:
$$f_{k}+(u_{i}-u_{k}-1-L)^2\le f_{j}+(u_{i}-u_{j}-1-L)^2$$
展开并移项化简:
$$2u_{i}(u_{j}-u_{k})\le f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2$$
令:
$$g_{i}=(u_{i}+1+L)^2$$
并不妨假定:
$$u_{j}!=u_{k}$$
可得:
$$2u_{i}\le\frac{f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2}{(u_{j}-u_{k})}$$
故而,若要使得答案更大,则上式必然成立。
考虑到这个式子符合单调队列的性质,我们可以上一个类似单调队列的数据结构来维护右侧的式子,也就是俗称的“斜率”。
这就完成了斜率优化。

#include<iostream>
#include<cstdio>
#include<queue>


int n,L;
double sm[50005],f[50005];
int q[50005],l,r;
inline double u(int X){
	return sm[X]+X;
}
inline double g(int X){
	return u(X)+L+1;
}
inline double x(int X){
	return g(X);
}
inline double y(int X){
	return f[X]+g(X)*g(X);
}
inline double k(int A,int B){
	return (y(A)-y(B))/(x(A)-x(B));
}

void init(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;++i){
		scanf("%lf",&sm[i]);
		sm[i]+=sm[i-1];
	}
	l=r=1;
	for(int i=1;i<=n;++i){
		while(l<r&&k(q[l],q[l+1])<2*u(i)){
			++l; 
		} 
		f[i]=f[q[l]]+(u(i)-g(q[l]))*((u(i)-g(q[l])));
		while(l<r&&k(i,q[r-1])<k(q[r-1],q[r])){
			--r;
		}
		q[++r]=i;
	}
	printf("%lld\n",(long long)f[n]);
}

int main(){
	init();
	return 0;
}

CF1098B Nice table

话说考场上这题距离正解只差一步了,可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说,可以考虑,要么是行上两种字符交替出现而列上随意,要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息,然后检验一下即可。
顺便提一句,这一题的数据范围真的是恶意满满。考场上是瞎jb哈希,但是现在个人觉得还是string比较科学。

#include<iostream>
#include<cstdio>
#include<cstring>

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

int main(){
	init();
	return 0;
}

lp2597 ZJOI2012 灾难

这一题的思路还是比较清晰的。虽然可以当作支配树模板,但是事实上可以上一个LCA来代替支配树。
具体来说,就是把有多个食物的消费者连到它所有食物的LCA。然后计算一遍子树大小就好了。
注意连点之前要先拓扑排序。

#include<iostream>
#include<cstdio>
#include<queue>

#define Swap(A,B) (A^=B^=A^=B)

struct ee{
	int v;
	int nxt;
}e[2500005];
//h,树上的节点。g,拓扑排序的节点。to,每个节点的所有父亲。 
int h[70000],g[70000],et=0,dep[70000],fa[70000][18],in[70000],to[70000],sz[70000],loc[70000];
int n,tp=0;
inline void add(int *H,int U,int V){
	if(U==V){
		return;
	}
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void srt(){
	std::queue<int> q;
	for(int i=1;i<=n;++i){
		if(!in[i]){
			q.push(i);
		}
	}
	int p=0;
	while(!q.empty()){
		p=q.front();
		q.pop();
		loc[++tp]=p;
		for(int i=g[p];i;i=e[i].nxt){
			--in[e[i].v];
			if(!in[e[i].v]){
				q.push(e[i].v);
			}
		}
	}
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		Swap(X,Y);
	}
	for(int i=17;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i]; 
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=17;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
inline void prpr(){
	int nw=0;
	for(int i=1,j;i<=n;++i){
		j=loc[i];
		nw=e[to[j]].v;
		for(int k=to[j];k;k=e[k].nxt){
			nw=lca(nw,e[k].v);
		}
//		请注意这里的nw可能不存在任何父亲节点。 
		add(h,nw,j);
		fa[j][0]=nw;
		dep[j]=dep[nw]+1;
		for(int k=1;k<=17;++k){
			fa[j][k]=fa[fa[j][k-1]][k-1];
		}
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		sz[X]+=sz[e[i].v];
	}
	++sz[X];
}
void init(){
	scanf("%d",&n);
	int x; 
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		while(x){
			++in[i];
			add(g,x,i);
			add(to,i,x);
			scanf("%d",&x);
		}
	}
	srt();
	prpr();
	dfs(0);
	for(int i=1;i<=n;++i){
		printf("%d\n",sz[i]-1);
	}
}

int main(){
	init();
	return 0;
}

lp3615 如厕计划

观察题面我们可以发现,如果男性比女性多的话,显然是无法符合要求的;否则,女性使用男女通用单间的个数不应该超过男女性的人数差。
我们不妨把部分的男女性人数差个女性视为男性——这是一种贪心的做法。于是就把女性多于男性的情况归约成了男性和女性相同的情况。
在这种情况下,任何时候都不应该有女性进入男女通用单间。这也就意味着,如果令男性为1,女性为-1,那么在任何时候,数列的前缀和都应该保证为大于等于-1。
然而,要保证一个前缀和始终大于某个数是很难维护的——这是因为位于后面的信息我们无法得到。我们考虑维护后缀和,这样就可以预先得到位于后面的信息了。
于是,我们考虑对每一段计算它的贡献。

#include<iostream>
#include<cstdio>
#include<cstring>

inline long long Max(long long A,long long B){
	return A>B?A:B;
}
inline long long Min(long long A,long long B){
	return A<B?A:B;
}

long long n,m;
int len;
char ch[200005];
long long dlt=0,a[200005],mx[200005],l[200005];
void init(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		len=strlen(ch+1);
		scanf("%lld",&l[i]);
		for(int j=len;j>=1;--j){
			a[i]+=(ch[j]=='M'?1:-1); 
			mx[i]=Max(mx[i],a[i]);
		}
		dlt+=a[i]*l[i];
	}
	if(dlt>0){
		puts("-1");
		return ;
	}
	long long nw=0,ans=1;
	for(int i=m;i>=1;--i){
		if(a[i]>0){
			ans=Max(ans,(l[i]-1)*a[i]+nw+mx[i]);
		}else{
			ans=Max(ans,nw+mx[i]);
		}
		nw+=l[i]*a[i];
	}
	printf("%lld",ans-1);
}

int main(){
	freopen("queue.in","r",stdin);
	freopen("queue.out","w",stdout);
	init();
	return 0;
}

lp3809 【模板】后缀排序

我们考虑一下前缀排序。
很显然可以上一个后缀自动机。按顺序深度搜索输出即可。
那么对于后缀排序,只需要倒着插入然后输出parent树即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 2000005

inline int hsh(char C){
	return 'a'<=C&&C<='z'?C-'a'+36:('A'<=C&&C<='Z'?C-'A'+10:C-'0');
}

int l[MAXN],r[MAXN],nxt[MAXN][62],fa[MAXN],fst[MAXN],bckt[MAXN],a[MAXN];
int loc[MAXN];
char ch[1000005];
int cnt,nw;
int n;

int v[MAXN],to[MAXN],h[MAXN],et=0;
inline void add(int U,int V){
	++et,v[et]=V,to[et]=h[U],h[U]=et;
}

inline void prpr(){
	fa[0]=-1,cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int C,int I){
	np=++cnt;r[np]=l[np]=l[nw]+1;p=nw;nw=np;loc[np]=I;
	while(p>=0&&!nxt[p][C]){
		nxt[p][C]=np;
		p=fa[p];
	}
	if(p==-1){
		fa[np]=0;
		return;
	}
	q=nxt[p][C];
	if(l[p]+1==l[q]){
		fa[np]=q;
		return;
	}
	nq=++cnt;
	l[nq]=l[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq,r[nq]=r[q];
	for(int i=0;i<62;++i){
		nxt[nq][i]=nxt[q][i];
	}
	while(p>=0&&nxt[p][C]==q){
		nxt[p][C]=nq;
		p=fa[p];
	}
}
inline void srt(){
	for(int i=1;i<=cnt;++i){fst[i]=hsh(ch[n-r[i]+1+l[fa[i]]]),++bckt[fst[i]];}
	for(int i=0;i<62;++i){bckt[i]+=bckt[i-1];}
	for(int i=1;i<=cnt;++i){a[bckt[fst[i]]--]=i;}
	for(int i=cnt;i;--i){add(fa[a[i]],a[i]);}
}
int tp=0;
inline void dfs(int X){
	if(loc[X]){
		printf("%d ",loc[X]); 
	}
	for(int i=h[X];i;i=to[i]){
		dfs(v[i]);
	}
}
void init(){
	std::cin>>ch+1;
	n=strlen(ch+1);
	for(int i=n;i;--i){
		psh(hsh(ch[i]),i);
	}
	srt();dfs(0);
	puts("");
	
}

int main(){
	prpr(); 
	init();
	return 0;
}

lp3804 【模板】后缀自动机

如题所示,这是一道模板题。
事实上,尽管后缀自动机有着较为强大和完整的功能,但它的实现却是比较简单的。
概括地说,后缀自动机是一种用线性的时间复杂度和字符数与字符集的乘积的空间复杂度来储存一个字符串里每一个前缀的所有后缀,并且相同的字符串只会被表达一次的一类自动机。
下面我们考虑如何构造这个自动机。
构造后缀自动机使用的是一种被称为「增量算法」的构造方法。这种构造方法将所有的节点依次加入自动机。
后缀自动机由以下四个部分组成:
根节点,前缀节点,父亲边和字符边。
根节点一开始就存在,它象征着空串。而每一次加入的是一个前缀节点。
前缀节点表示的是原串中的某一个前缀。
每个前缀节点都有一条父亲边连向另一个节点。
每个前缀节点都有数条字符边连向另一些节点。
对于每个前缀节点,它储存的都是一些字符串。
具体而言,是这个点表示的最长串的所有长度严格大于它的父亲的最长串的长度的后缀。考虑到这个性质,每个点事实上不必记录整个字符串集合,而只需记录字符串的最长长度即可。
从这个节点沿着父亲边走到根的路径上的所有点表示的字符串集合构成的新集合,不重复不遗漏地表示了当前点的所有后缀。

我们记录一个节点nw,表示的是当前插入最长的一个前缀所在的点。
当我们加入了一个新的字符c,我们进行如下判断和操作。
新建一个点np,然后沿着nw到根的路径向上搜索,对路径上的每个点进行判断,如果这个点没有拉出过字符为c的边,就将它连一条字符为c的边连向新点。否则进行如下特殊处理。
如果沿着nw到根的每一个点都连向了新点,则表示新节点表示的每一个非空后缀都无法在已有的自动机内找到,那么它的后缀序列需要且仅需要两个点来表达:它本身,以及象征空字符串的根节点。
否则,我们考虑这个已经有字符为c的边的点,我们令它为p,它通过c连向的点为q。很明显这意味着,np代表的后缀集合与q代表的后缀集合有交集。
仍然是分类讨论。如果q表示的字符串数量是1的话,那么它代表的后缀集合显然一定是np代表的后缀集合的一个真子集。并且这个集合关于np代表的后缀集合的补集正好是np代表的字符串集合。
那么我们就可以把np的父亲边连向q。
如果q表示的字符串数量大于1,这就意味着两者的后缀集合含有交际并且互不包含。
于是我们需要把q节点拆成q和nq两个节点,其中nq表示被np包含的字符串集合,而q表示不被np包含的字符串集合。
显然需要修改字符边c的点只有p到根的路径上的所有点。因为只有这些点才能够拉出被np包含的字符串集合。
当然,这些需要修改c的点也一定是一段连续的区间。这由每个点包含的后缀集合不重复不遗漏可以得到。
而q与np的父亲都应该修改到点nq,这也很显然,因为拆点后q表示的后缀集合包含nq表示的后缀集合。
同时,原来的q点的字符出边也都应该复制到nq上。这是因为一个字符出边表示的是目的点包含了所有出发点所包含的每一个字符串末尾添上字符边代表的字符所构成的集合。
故而拆点前的q点给其他的点贡献的一部分字符串的字符出边的出发点在拆点后变成了nq。

这就完成了后缀自动机的构建。

对于这一题,我们考虑一个显而易见的性质:
一个子串在原串中出现的次数,等价于以它作为后缀的前缀个数。
因此,只要计算父亲边构成的树上的子树大小乘以节点最长字符串长度的最值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
 
inline long long Max(long long A,long long B){
	return A>B?A:B;
}
int n;
int l[2000005],fa[2000005],nxt[2000005][26],sz[2000005];
int h[2000005],v[2000005],to[2000005];
char ch[2000005];
int cnt,nw,et;
inline void add(int U,int V){
	++et,v[et]=V,to[et]=h[U],h[U]=et;
}
inline void prpr(){
	l[0]=0,fa[0]=-1,sz[0]=0;
	cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int c){
	np=++cnt,p=nw,l[np]=l[nw]+1,sz[np]=1,nw=np;
	while(p>=0&&!nxt[p][c]){
		nxt[p][c]=np;
		p=fa[p];
	}
	if(p==-1){
		fa[np]=0;
		return;
	}
	q=nxt[p][c];
	if(l[p]+1==l[q]){
		fa[np]=q;
		return;
	}
	nq=++cnt;
	for(int i=0;i<26;++i){
		nxt[nq][i]=nxt[q][i];
	}
	fa[nq]=fa[q],fa[q]=fa[np]=nq,l[nq]=l[p]+1;
	while(p>=0&&nxt[p][c]==q){
		nxt[p][c]=nq;
		p=fa[p];
	}
}
long long ans=0;
inline void dfs(int X){
	for(int i=h[X];i;i=to[i]){
		dfs(v[i]);
		sz[X]+=sz[v[i]];
	}
	if(sz[X]>1){
		ans=Max(ans,1ll*sz[X]*l[X]);
	}
}
void init(){
	std::cin>>ch+1;
	n=strlen(ch+1);
	for(int i=1;i<=n;++i){
		psh(ch[i]-'a');
	}
	for(int i=1;i<=cnt;++i){
		add(fa[i],i);
	}
	dfs(0);
	printf("%lld",ans);
}

int main(){
	prpr();
	init();
	return 0;
}

lp3980 NOI2008 志愿者招募

一开始YY了一种连边方式,就是源点向第一个点连边,第一个点向最后一个点连边,每个边的流量是1,希望能通过一些奇奇怪怪的约束条件来保证能从1跑到n。
但是很快这个想法就被枪毙了——每一天需要消耗的人力是不同的。
怎么办呢?
我们可以考虑一种(我瞎取名叫)替换法的建模方法。
具体来说就是,先确定一个最大流,然后将其中的一些流量替换为必须要通过实际需要的路径才能跑过,这样就保证了答案的合法性。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[400005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

long long ans=0,ans2=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		ans2+=val[t];
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
int a[20005],tot=0;
//tot不能想当然地取最大值,而应该取和。
//这是因为,过程中可能存在一些情况,使得先雇佣某个志愿者会更优。 
void init(){
	scanf("%d%d",&n,&m);
	s=n+2,t=n+3;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	++tot;
	add(s,1,tot,0),add(n+1,t,tot,0);
	for(int i=1;i<=n;++i){
		add(i,i+1,tot-a[i],0);
	}
	int l,r,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&l,&r,&c);
		add(l,r+1,tot,c);
	}
	EK();
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

lp2050 NOI2012 美食节

这一题是SCOI2007修车的威力加强版。
用常规的写法显然是无法通过的。
我们考虑动态加边。
这样就可以最小化每一次松弛带来的影响,于是复杂度就变成了O(能过)
(才怪呢。我卡常卡了半天结果还是开了O2才过。)
(赶紧学zkw费用流)

#include<iostream>
#include<cstdio>
#include<queue>
#define calc(I,J) ((J-1)*sm+I)
#define calc2(I) (I+sm*m)

namespace IO{
	const int S = 1E6;
	char buf[S];
	int len=0,pos=0;
	inline char frc(){
		if(len==pos){pos=0,len=fread(buf,1,S,stdin);}
		if(len==pos){exit(0);}else{putchar(buf[pos]);return buf[pos++];};
	}
	inline int fri(){
		int fr=1,ch=frc(),x=0;
		while(ch<=32)ch=frc();
		if(ch=='-')fr=-1,ch=frc();
		while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=frc();
		putchar(ch);
		return x*fr;
	}
}

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[6600005];
int h[90005],et=-1;

inline void add(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
	e[++et]=(ee){U,0,-C,h[V]};
	h[V]=et;
}
//mp[i][j]表示第i种菜由第j名厨师做需要消耗的时间。 
int n,m,s,t,sm,vis[90005],dis[90005],val[90005],fa[90005],nw[90005],po[45],mp[45][105];
int q[90005];
int l,r;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	l=1,r=0;
	q[++r]=s;
	register int p;
	while(l<=r){
		p=q[l++];
		vis[p]=0;
		for(register int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q[++r]=e[i].v;
				}
			}
		}
	}
	return fa[t]!=-1;
}
//倒数第I个,厨师J 
int ans;
inline void EK(){
	register int p,cnt,ck;
	while(SPFA()){
		cnt=fa[t]%sm,ck=fa[t]/sm+1;
		++cnt;
		//注意这里的逆hash 
		for(int i=1;i<=n;++i){
			add(calc2(i),calc(cnt,ck),1,cnt*mp[i][ck]);
		}
		p=t;
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
void init(){
	puts("2333");
	n=IO::fri(),m=IO::fri();
	for(int i=1;i<=n;++i){
		po[i]=IO::fri();
		sm+=po[i];
	}
	s=sm*m+n+1,t=sm*m+n+2;
	for(register int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			mp[i][j]=IO::fri();
			add(calc2(i),calc(1,j),1,mp[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		add(s,calc2(i),po[i],0);
	}
	for(register int i=1;i<=sm*m;++i){
		add(i,t,1,0);
	}
	EK();
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

CF1107

丢人场。
C题想了一个单调队列优化DP,然后瞎jb写,最后还是别人提醒了才发现自己傻了。


CF1107A
显然分成两段:第一个数和剩下全部的数是最容易想到的,也一定是合法的。
对于只有两个字符的要特殊处理。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char ch[305];
 
void init(){
	memset(ch,0,sizeof(ch));
	scanf("%d",&n);
	cin>>ch+1;
	if(n==2&&ch[1]>=ch[2]){
		puts("NO");
		return;
	}
	puts("YES");puts("2");
	printf("%c ",ch[1]);
	for(int i=2;i<=n;++i){
		putchar(ch[i]);
	}
	puts("");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}



CF1107B
找规律题。没什么好说的。当然要证明也是可以的,感觉用归纳法是可以,时间不够就没有证明了。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
long long k,x,ans;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%I64d%I64d",&k,&x);
		ans=(k-1)*9+x;
		printf("%I64d\n",ans);
	}
}
int main(){
	init();
	return 0;
}


CF1107C
傻逼贪心,我不知道我怎么想成单调队列优化DP的。
具体来说就是用pq尽可能删小的。正确性(可能一点都不)显然。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

priority_queue<int,vector<int>,greater<int> > q;
char ch[200005];
int a[200005];
void init(){
	int n,K;
	scanf("%d%d",&n,&K);
	long long ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ans+=a[i]; 
	}
	cin>>ch+1;
	int tot=1;
	for(int i=1;i<=n;++i){
		if(ch[i]==ch[i-1]){
			q.push(a[i]);
			++tot;
			while(tot>K&&!q.empty()){
				ans-=q.top();
				q.pop();
				--tot;
			}
		}else{
			tot=1;
			while(!q.empty()){
				q.pop();
			}
			q.push(a[i]);
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

CF1111

我一直以为这一天是除夕来着,不过也不算错就是了。
一场超级变态的比赛。具体来说就是:

We are sincerely apologize for the weak pretest of problem B.

——出题人

实际造成的效果就很感人了_(:з」∠)_,三分之一的选手被Hack,结束之后剩下的三分之二中的三分之二又FST了。

祝大家红红火火。

总之,我在只有两题的情况下涨分了…


CF1111A
热身题,暴力上个比较就行了。
(其实我没看数据范围,但复杂度大概是对的。)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const char yuan[]={'a','e','i','o','u'};
bool bo1[200005],bo2[200005];
char ch1[200005],ch2[200005];
int n1,n2;
void init(){
	std::cin>>ch1+1;
	std::cin>>ch2+1;
	n1=strlen(ch1+1),n2=strlen(ch2+1);
	if(n1!=n2){
		puts("No");
		return;
	}
	for(int i=1;i<=n1;++i){
		for(int j=0;j<5;++j){
			if(ch1[i]==yuan[j]){
				bo1[i]=1;
			}
			if(ch2[i]==yuan[j]){
				bo2[i]=1;
			}
		}
	}
	for(int i=1;i<=n1;++i){
		if(bo1[i]!=bo2[i]){
			puts("No");
			return;
		}
	}
	puts("Yes");
	return;
}
int main(){
	init();
	return 0;
}


CF1111C
发现两个结论:
如果一个要塞下面有英雄,除非英雄全部聚集在某半边,否则一定是剖开来处理更优。
如果一个要塞下面是空的,一定是不剖开处理更优。
这两个结论都可以有用题目给出的式子来轻易地证明。
所以我们现在要考虑的就是如果一个要塞下面有英雄并且英雄全部聚集在某半边的情况。
考虑分治。
但是最后有一个问题:如何快速地统计一个区间之内的英雄数量?
虽然数据范围很大,但是排个序然后大力二分统计即可。
善用upperbound。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
/*

*/ 
long long n,k,A,B;
long long ans=0;
long long a[100005];
//所有[L,R]之间的英雄个数。
//显然upperbound(L-1)并且upperbound(R),相减即可。 
inline long long calc(int L,int R){
	return (std::upper_bound(a+1,a+1+k,R)-std::upper_bound(a+1,a+1+k,L-1)); 
}
inline long long dfs(int L,int R){
	if(L==R){
		int X=calc(L,R);
		return X?B*X:A;
	}
	if(!calc(L,R)){
		return A;
	}
	int MID=(L+R)>>1;
	if(!calc(L,MID)||!calc(MID+1,R)){
		return std::min(B*(R-L+1)*calc(L,R),dfs(L,MID)+dfs(MID+1,R));
	}else{
		return dfs(L,MID)+dfs(MID+1,R);
	}
}
void init(){
	scanf("%I64d%I64d%I64d%I64d",&n,&k,&A,&B);
	for(int i=1;i<=k;++i){
		scanf("%I64d",a+i);
	}
	std::sort(a+1,a+1+k);
	printf("%I64d",dfs(1,1<<n));
}
int main(){
	init();
	return 0;
}

lp2604 ZJOI2010 网络扩容

第一问没什么好说的。直接看第二问。
一个很直接的想法就是,在每条边上都加上一条容量为\(k\),费用为\(c_{e}\)的边。
但是仔细一想会发现一个问题:如果s到t有多条路径的话,上述的方法就会使得流量总额过大。
有什么好方法呢?
第一个直接的想法是发现源汇之间如果有多条路径的话,那么必然是将所有的流量k全都贪心地放在花费最小的那条路径上是最优的。
但是这显然是不可能的,考虑一个残余网络非空的情况。
故而我们换一种思路:在原来所有边上额外连流量为k的边的同时,再从n向一个虚拟汇点t连一条边。这样既可完成。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[20005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,K,dis[20005],nw[20005],val[20005],fa[20005],vis[20005];
int u[20005],v[20005],w[20005],c[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		dis[i]=INF;
		val[i]=INF;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0,vis[s]=1,fa[t]=-1;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].c&&e[i].w>0){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;;
}

int answ=0,ansc=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	} 
}


void init(){
	scanf("%d%d%d",&n,&m,&K);
	s=1,t=n;
	for(int i=1;i<=n+1;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",u+i,v+i,w+i,c+i);
		add(u[i],v[i],w[i],0);
	}
	EK();
	printf("%d ",answ);
	for(int i=1;i<=m;++i){
		add(u[i],v[i],INF,c[i]);
	}
	add(t,t+1,K,0);
	++t;
	EK();
	printf("%d\n",ansc);
}

int main(){
	init();
	return 0;
}

lp3159 CQOI2012 交换棋子

首先是一个常见套路:将棋子的交换等价为棋子的移动——这很重要。我们不妨把交换看做黑子的移动。
那么我们考虑这个问题的弱化版:假设每个格子的移动次数没有限制,该怎么做。
很显然将每个格子拆成两个点,然后每个右点向相邻的左点连边,跑最大流即可。
对于一个黑子的移动,我们发现,如果一个格子是这个黑子中途经过的点,那么这个格子必然会消耗两次交换次数。
故而,我们给从左点到右点的边设置一个容量上限,其值为交换次数上限的一半。
但是这么做的话我们发现了一个问题:倘若一个点起始状态和结束状态不一样,这个模型是无法有效描述结果的。
这是因为,如果一个点的起始状态和结束状态不一样,那么它通过的次数必然是奇数。
我们考虑这样拆点:将每个点拆成左,中,右三个点。然后,将每个点的右点向它的所有相邻点的左点连边,流量1,费用0。表示某个棋子走向了它的另一个相邻的棋子。
从中点向右点连一条边,表示这个点移出去的次数。显然,如果最终情况是白的而初始情况是黑的,这个点应该会多移出去一次。
从左点向中点连一条边,表示这个点移进来的次数。显然,如果最终情况是黑的而初始情况是白的,这个点应该会多移进来一次。
我们考虑这个「多移进来」和「多移出去」对这个点可以参与的交换次数的影响。
假若限定次数是偶数,那么多出来的这一次移动将使得这个点能参与的交换次数少一次;倘若限定次数是奇数,那么多出来的这一次移动将不影响这个点能参与的交换次数。
所以,我们可以用形如\(\lfloor \frac{limit+[end>begin]}{2} \rfloor \)和\(\lfloor \frac{limit+[begin>end]}{2} \rfloor \)的式子来描述这两条边的流量。
然后,对于题目要求的最小交换次数,我们考虑将原来就存在的连边加上费用。这样就满足了题目的要求。

#include<iostream>
#include<cstdio>
#include<queue>

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[200005];
int h[1205],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,vis[1205],dis[1205],val[1205],fa[1205],nw[1205];

std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
int answ=0,ansc=0;
inline void zkw(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}

char begin[25][25],end[25][25],limit[25][25];
inline int calc(int X,int Y,int T){
	return T*n*m+(X-1)*m+Y;
}

void init(){
	scanf("%d%d",&n,&m);
	s=3*n*m+1,t=3*n*m+2;
	int cnt=0;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>begin[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>end[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>limit[i]+1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(begin[i][j]=='1'){
				++cnt;
				add(s,calc(i,j,1),1,0);
			}
			add(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);
			if(end[i][j]=='1'){
				add(calc(i,j,1),t,1,0);
			}
			add(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);
			for(int k=0;k<8;++k){
				int x=i+dx[k],y=j+dy[k];
				if(x>=1&&x<=n&&y>=1&&y<=m){
					//n,m!!!
					add(calc(i,j,2),calc(x,y,0),INF,0);
				}
			}
		}
	}
	zkw();
	printf("%d\n",(answ==cnt?ansc:-1)>>1);
}

int main(){
	init();
	return 0;
}

lp2153 SDOI2009 晨跑

题意简述:求一张图上不共点两点间最大路径数。
首先考虑不共边最大路径数,很容易可以想到大力上一个最大流,边流量为一。
然后考虑不共点最大路径数。我们发现,可以通过拆点来构成约束条件。具体来说就是将每个点拆成入点和出点,然后跑一个网络流。
现在还要求一个最短总路径长度,很容易可以想到费用流。具体来说,就将每一条边的费用设置为它的长度。然后跑一遍即可。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[405],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,dis[405],val[405],fa[405],nw[405];
bool vis[405];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

void init(){
	scanf("%d%d",&n,&m);
	s=1,t=2*n;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		add(n+u,v,1,c);
	}
	for(int i=2;i<n;++i){
		add(i,n+i,1,0);
	}
	add(1,n+1,1926,0);
	add(n,2*n,1926,0);
	int ansW=0,ansC=0,p;
	while(spfa()){
		p=t;
		ansW+=val[t];
		ansC+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
	printf("%d %d\n",ansW,ansC);
}

int main(){
	init();
	return 0;
}

lp2805 NOI2009 植物大战僵尸

仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭它。
故而,它就变成了一个这样的问题:存在一些植物,其中的一些要消灭了另外一些之后才能消灭,问收益最大化的方法。
如果我们对每一棵植物建点,然后从一棵植物向它的约束植物连边,那么问题就转化为:一张有向图,每个点都有点权,请选中其中的某些点,使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是,从源点向正权点连权值为点权的边;从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么,答案就是总权值减去最小割。


下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点,连向汇点的边被割掉表示选中这个点。
那么,最终的结果必然是一个闭合子图。
这是因为,对于这张图的最小割,当你选中一个节点之后,这个点的所有后继负权节点都一定被割掉/选中了(根据割的性质显然);
这个点的所有后继正权节点都一定不被割/选中了(根据最小割的性质,割掉这些边没有意义)。
并且,任何一个闭合子图的选法都至少可以对应一个割法。
这是因为,对于原图中的某一种连接方法,都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时,根据我们此前的定义,最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而,答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的,故而最小割可以得到最优答案。


PS:
这一题应当考虑死锁情况,想象一个无限攻击力和攻速的豌豆射手。(不考虑连样例都过不了)(但是尽管这样还是能够拿到80分)
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记,然后令这些点在网络流中不存在。
然而,如果我们直接写一个拓扑排序的话,还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想,因为这张图上每一条有向边的终点一旦被删去,那么它的所有前驱也都是不能存在的。
故而,对反图进行拓扑排序找环并删去才能符合题目的要求。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}