Lvat_s Blog

因为修改的次数比较少，所以每次暴力重构hash就可以了

LCP可以用二分来做

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const unsigned long long Mod1=131ll,Mod2=171ll;

int n,q;
string s;
char ch[1000005];
unsigned long long hash1[1000005],hash2[1000005],Pow1[1000005],Pow2[1000005];

void MakeHash(){
n=s.length();
hash1[n-1]=s[n-1];
hash2[n-1]=s[n-1];
for(int i=n-2;i>=0;i--){
    hash1[i]=hash1[i+1]*Mod1+s[i];
    hash2[i]=hash2[i+1]*Mod2+s[i];
}
}

void Prepare(){
Pow1[0]=1ll;
Pow2[0]=1ll;
for(int i=1;i<=1000000;i++){
    Pow1[i]=Pow1[i-1]*Mod1;
    Pow2[i]=Pow2[i-1]*Mod2;
}
}

pair<unsigned long long,unsigned long long> GetHash(int l,int len){
return make_pair(hash1[l]-hash1[l+len]*Pow1[len],hash2[l]-hash2[l+len]*Pow2[len]);
}

int LCP(int a,int b){
if(a>b)swap(a,b);
int l=0,r=n-b;
while(l<=r){
    int mid=l+r>>1;
    if(GetHash(a,mid)!=GetHash(b,mid))r=mid-1;
    else l=mid+1;
}
return r;
}

int main(){
freopen("2105.in","r",stdin);
freopen("2105.out","w",stdout);
scanf("%d %d",&n,&q);
scanf("%s",ch);s=ch;
Prepare();
MakeHash();
while(q--){
    char opt[10];
    scanf("%s",opt);
    if(opt[0]=='L'){
        int l,r;
        scanf("%d %d",&l,&r);
        l--;r--;
        printf("%d\n",LCP(l,r));
    }
    if(opt[0]=='A'){
        int x;
        scanf("%d %s",&x,ch);
        x--;
        s.insert(x,ch);
        MakeHash();
    }
    if(opt[0]=='C'){
        int x,y;
        scanf("%d %d %s",&x,&y,ch);
        x--;y--;
        for(int i=x;i<=y;i++)s[i]=ch[i-x];
        MakeHash();
    }
    if(opt[0]=='D'){
        int x,y;
        scanf("%d %d",&x,&y);
        x--;y--;
        s.erase(x,y-x+1);
        MakeHash();
    }
}
return 0;
}

这题如果没有环的话就是一个依赖背包问题，可以树形DP

有环就用tarjan缩点就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int en,en2,h[105],h2[105],w[505],v[105],d[105],low[105],dfn[105],n,m,scc,dp[105][505],cnt,Q[105],Qcnt,inQ[105],belong[105],sv[105],sw[105],in[105];

struct Edge{
int b,next;
}e[10005],e2[10005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void AddEdge2(int sa,int sb){
in[sb]=1;
e2[++en2].b=sb;
e2[en2].next=h2[sa];
h2[sa]=en2;
}

void Tarjan(int u){
dfn[u]=low[u]=++cnt;
Q[++Qcnt]=u;inQ[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}
    else if(inQ[v]){low[u]=min(low[u],dfn[v]);}
}
if(dfn[u]==low[u]){
	scc++;
	int nw=0;
	while(nw!=u){
		nw=Q[Qcnt--];inQ[nw]=0;
		belong[nw]=scc;
		sv[scc]+=v[nw];
		sw[scc]+=w[nw];
	}
}
}

void Rebuild(){
for(int i=1;i<=n;i++){
	for(int j=h[i];j;j=e[j].next){
		int v=e[j].b;
		if(belong[i]!=belong[v]){
			AddEdge2(belong[i],belong[v]);
		}
	}
}
for(int i=1;i<=scc;i++){if(!in[i])AddEdge2(scc+1,i);}
}

void DP(int u){
for(int i=h2[u];i;i=e2[i].next){
	int v=e2[i].b;DP(v);
	for(int j=m-sw[u];j>=0;j--){
		for(int k=0;k<=j;k++){
			dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
		}
	}
}
for(int j=m;j>=0;j--){
	if(j>=sw[u])dp[u][j]=dp[u][j-sw[u]]+sv[u];
	else dp[u][j]=0;
}
}

int main(){
freopen("2427.in","r",stdin);
freopen("2427.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++){
	scanf("%d",&d[i]);
	if(d[i])AddEdge(d[i],i);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
Rebuild();
DP(scc+1);
printf("%d\n",dp[scc+1][m]);
return 0;
}

Hash水题，枚举每一位然后hash搞一搞

听说自然溢出很快就试了一下

然后就WAWA不休

最后还是回归正常的办法：模大数字（为什么不是质数呢？因为我的两个数字是随便敲的）

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const long long Mod1=666666666666667ll,Mod2=233333333333333ll;

int n,len,x,ans=0;
long long Ha_F[30005][205],Ha_L[30005][205],tp[30005];
char s[30005][205];

void Get(int x){
for(int i=1;i<=len;i++)Ha_F[x][i]=(Ha_F[x][i-1]*233+s[x][i])%Mod1;
for(int i=len;i;i--)Ha_L[x][i]=(Ha_L[x][i+1]*137+s[x][i])%Mod2;
}

int main(){
freopen("3555.in","r",stdin);
freopen("3555.out","w",stdout);
scanf("%d %d %d",&n,&len,&x);
for(int i=1;i<=n;i++){
	scanf("%s",s[i]+1);
	Get(i);
}
for(int i=1;i<=len;i++){
	for(int j=1;j<=n;j++){
		tp[j]=(Ha_F[j][i-1]*Mod2+Ha_L[j][i+1]*Mod1)%(Mod2*Mod1);
	}
    sort(tp+1,tp+n+1);
    int cnt=1;
    for(int j=2;j<=n;j++){
		if(tp[j]==tp[j-1])ans+=cnt,cnt++;
		else cnt=1;
    }
}
printf("%d\n",ans);
return 0;
}

线段树大水题

#include<cstdio>
 
int n,m;
long long k[200005],b[200005];
const long long Mod=1000000007ll;
 
struct SegTree{
long long k,b;
int l,r;
}tree[1000005];
 
void Pushup(int rt){
tree[rt].k=tree[rt*2].k*tree[rt*2+1].k%Mod;
tree[rt].b=(tree[rt*2+1].b+tree[rt*2+1].k*tree[rt*2].b%Mod)%Mod;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].k=k[l]%Mod;tree[rt].b=b[l]%Mod;return;}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
Pushup(rt);
}
 
void Modify(int rt,int pos,long long k,long long b){
if(tree[rt].l==tree[rt].r){tree[rt].k=k%Mod;tree[rt].b=b%Mod;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Modify(rt*2,pos,k,b);
if(pos>mid)Modify(rt*2+1,pos,k,b);
Pushup(rt);
}
 
long long Query(int rt,int l,int r,long long x){
if(l<=tree[rt].l && tree[rt].r<=r){return (tree[rt].k*x%Mod+tree[rt].b)%Mod;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return Query(rt*2+1,l,r,x)%Mod;
else if(r<=mid)return Query(rt*2,l,r,x)%Mod;
return Query(rt*2+1,l,r,Query(rt*2,l,r,x)%Mod)%Mod;
}
 
int main(){
freopen("4499.in","r",stdin);
freopen("4499.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%lld %lld",&k[i],&b[i]);
}
Build(1,1,n);
for(int i=1;i<=m;i++){
    char s[5];
    long long l,r,v;
    scanf("%s %lld %lld %lld",s,&l,&r,&v);
    if(s[0]=='M')Modify(1,(int)l,r,v);
    else printf("%lld\n",Query(1,(int)l,(int)r,v));
}
return 0;
}

奇怪的二分+LCP

orz rky 考场上直接后缀平衡树秒掉

orz lyz 随手后缀数组秒掉

orz 两位2h AK SDOI2016 Day2的神犇

高二大爷们和wyx全AK了简直太可怕

因为我不敢写后缀数组（因为只写过2次），所以考场上GG咯

回来补一个二分LCP的做法

首先我们考虑两个后缀A,B对答案的贡献(已经按字典序排序)

贡献是$|A|+|B|-LCP(A,B)$

那么我们用一个set动态维护就可以了

每次插入一个字符一定会多一个后缀

然后我们在set里面找一找前驱后继算一下就好了

下面是rky的神·题解

-------------------------------------------------

-------------------------------------------------

orz 你萌都会后缀+平衡树。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;

typedef long long LL;

const int N=100005;
const LL P=1e9+7;

int n,a[N];
LL Pow[N],Hash[N],ans;

LL GetHash(int l,int r){return (Hash[l]-Hash[r+1])*Pow[n-l];}

int LCP(int a,int b){
if(a>b)a^=b^=a^=b;
int l=0,r=n-b+2,ans=0;
while(l+1<r){
	int mid=l+r>>1;
	if(GetHash(a,a+mid-1)!=GetHash(b,b+mid-1)){r=mid;}
	else {l=mid;ans=mid;}
}
return ans;
}

struct Cmp{
bool operator()(int A,int B){
int Lcp=LCP(A,B);
if(B+Lcp>n)return 0;
if(A+Lcp>n)return 1;
return a[A+Lcp]<a[B+Lcp];
}
};

set<int,Cmp> St;

void Solve(){
for(int i=n;i;i--){
	set<int,Cmp>::iterator It,Pre,Nxt;
	Hash[i]=Hash[i+1]+a[i]*Pow[i];
	It=St.insert(i).first;
	Pre=It;Pre--;Nxt=It;Nxt++;
	ans+=n-i+1;
	if(It!=St.begin())ans-=LCP(*Pre,*It);
	if(Nxt!=St.end())ans-=LCP(*It,*Nxt);
	if(It!=St.begin() && Nxt!=St.end())ans+=LCP(*Pre,*Nxt);
	printf("%lld\n",ans);
}
}

template<typename T> void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("4516.in","r",stdin);
freopen("4516.out","w",stdout);
Read(n);
for(int i=n;i;i--)Read(a[i]);
Pow[0]=1ll;
for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*P;
Solve();
return 0;
}

斜率优化DP，和玩具装箱很像。。。基本是裸的

注：那个Bf函数是暴力DP，可以参考一下和下面Upper函数(斜率优化DP)的共同点

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

int first,last,Que[30005];
long long n,m,f[3005][3005],a[3005];

void Bf(){
for(int i=1;i<=n;i++){
	f[i][1]=a[i]*a[i];
	for(int j=2;j<=m;j++){
		f[i][j]=f[i][j-1];
		for(int k=1;k<i;k++){
			f[i][j]=min(f[i][j],f[k][j-1]+(a[i]-a[k])*(a[i]-a[k]));
		}
	}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}

bool DelFirst(int q1,int q2,int i,int j){
return f[q1][j-1]+a[q1]*a[q1]-2ll*a[q1]*a[i]>f[q2][j-1]+a[q2]*a[q2]-2ll*a[q2]*a[i];
}

bool DelLast(int q1,int q2,int i,int j){
return (f[q1][j-1]+a[q1]*a[q1]-f[q2][j-1]-a[q2]*a[q2])*(a[i]-a[q2])<(f[q2][j-1]+a[q2]*a[q2]-f[i][j-1]-a[i]*a[i])*(a[q2]-a[q1]);
}

void Upper(){
for(int i=1;i<=n;i++)f[i][1]=a[i]*a[i];
for(int j=2;j<=m;j++){
	f[1][j]=a[1]*a[1];
	first=1;
	last=0;
	Que[++last]=1;
	for(int i=2;i<=n;i++){
		while(first<last && DelFirst(Que[first],Que[first+1],i,j))first++;
		f[i][j]=f[Que[first]][j-1]+(a[Que[first]]-a[i])*(a[Que[first]]-a[i]);
		while(first<last && DelLast(Que[last-1],Que[last],i,j))last--;
		Que[++last]=i;
	}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}

int main(){
freopen("4518.in","r",stdin);
freopen("4518.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
	long long x;
	scanf("%lld",&x);
	a[i]=a[i-1]+x;
}
Upper();
return 0;
}

首先我们知道答案是$C(n,m)*Perm(n-m)$

$Perm(x)$表示为$x$的错排方案数

($n$个数里面选$m$个数作为稳定点，其余点均不在自己的位置上)

错排公式:$Perm(x)=(x-1)Perm(x-1)Perm(x-2)$

考场上这个想了很久。。。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const int N=1000005;
const long long Mod=1e9+7;
const long double eps=1e-10;

int T;
long long Pv[N+1],Px[N+1],Cu[N+1],m,n;

long long Qpow(long long A,long long B){
long long base=A,ans=1;
while(B){
	if(B&1)ans=ans*base%Mod;
	base=base*base%Mod;
	B>>=1;
}
return ans;
}

void Prepare(){
long long s=1;
Px[0]=1;
Pv[0]=1;
for(int i=1;i<=N;i++){
	s=s*i%Mod;
	Pv[i]=s;
	Px[i]=Qpow(s,Mod-2);
}
Cu[0]=1;
Cu[1]=0;
Cu[2]=1;
for(long long i=3;i<=N;i++)Cu[i]=(Cu[i-1]+Cu[i-2])%Mod*(i-1)%Mod;
}

long long C(long long a,long long b){
return Pv[a]*Px[b]%Mod*Px[a-b]%Mod;
}

int main(){
freopen("4517.in","r",stdin);
freopen("4517.out","w",stdout);
scanf("%d",&T);
Prepare();
while(T--){
	scanf("%lld %lld",&n,&m);
	printf("%lld\n",C(n,m)*Cu[n-m]%Mod);
}
return 0;
}

神转化。。。

首先我们考虑因为每一次只会知道奇偶性，所以我们对于一个区间[l,r]是否有球至少保证要知道[l...r]全部的奇偶性才可以判定每个杯子下面是否有球。（意味着如果每个杯子抽象成点，那么这些点之间必须全部连通才会知道每个杯子下面是否有球）

因为要费用最少，所以我们每次选择费用最小且有用的边加上去

然后就变成了最小生成树了。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,h[2005],cnt,f[2005];
long long ans=0;

struct Edge{
int a,b,v;
friend bool operator<(Edge a,Edge b){return a.v<b.v;}
}e[4000005];

void AddEdge(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){f[sb]=sa;}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("3714.in","r",stdin);
freopen("3714.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	for(int j=i;j<=n;j++){
		int x;
		scanf("%d",&x);
		AddEdge(i,j+1,x);
	}
}
sort(e+1,e+en+1);
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=en && cnt<=n;i++){
	if(Find(e[i].a)!=Find(e[i].b)){Union(Find(e[i].a),Find(e[i].b));ans+=(long long)e[i].v;cnt++;}
}
printf("%lld\n",ans);
return 0;
}

今天考试考了一个斜率优化DP，一大群人A了。。

这让从没写过斜率优化的我情何以堪

所以我就把这题写了。。

感觉还是很好理解的：维护最优决策，再维护决策单调性

顺便Orz lyz rky今天AK了省选模拟

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
 
int n,first,last;
long long L,s[50005],dp[50005],q[500005],C;
 
bool DelFirst(int a,int b,int c){
return dp[a]+(s[c]-s[a]-C)*(s[c]-s[a]-C)>dp[b]+(s[c]-s[b]-C)*(s[c]-s[b]-C);
}
 
bool DelLast(int a,int b,int c){
return (dp[a]-dp[b]+s[a]*s[a]-s[b]*s[b])*(s[c]-s[b])<(dp[b]-dp[c]+s[b]*s[b]-s[c]*s[c])*(s[b]-s[a]);
}
 
int main(){
freopen("1010.in","r",stdin);
freopen("1010.out","w",stdout);
scanf("%d %d",&n,&L);
C=L+1;
for(int i=1;i<=n;i++){
    long long x;
    scanf("%lld",&x);
    s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)s[i]+=i;
first=1;
last=0;
q[++last]=0;
for(int i=1;i<=n;i++){
    while(first<last && DelFirst(q[first],q[first+1],i))first++;
    dp[i]=dp[q[first]]+(s[i]-s[q[first]]-C)*(s[i]-s[q[first]]-C);
    while(first<last && DelLast(q[last-1],q[last],i))last--;
    q[++last]=i;
}
printf("%lld\n",dp[n]);
return 0;
}

首先，如果一个串可以被分割成两个串且这两个串均满足条件，那么这个串一定满足条件。

证明:$a=0(mod$ $m)$,$b=0(mod$ $m)$则$a*x+b*y=0(mod$ $m)$（显然）

那么我们只要统计有多少种满足情况的子串就可以了，设数目为$k$，然后方案数就是$2^k$

注意如果最后原串不满足条件就要输出0（显然原串不满足那么拆成的子串中至少有一个不满足该性质）

说了这么多，其实特别好写。。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,ans=0,len;
const int Mod=1e9+7;

int main(){
freopen("4421.in","r",stdin);
freopen("4421.out","w",stdout);
scanf("%d %d",&n,&m);
char ch;
while((ch=getchar())<'0' || ch>'9');
if((ch-'0')%m==0)ans=1;
len=ch-'0';
while((ch=getchar())>='0' && ch<='9'){
	len=(len*10+ch-'0')%m;
	if(len==0){
		if(ans==0)ans=1;
		else ans=ans*2%Mod;
	}
}
printf("%d\n",len==0?ans:0);
return 0;
}