Lvat_s Blog

水并查集

时光倒流就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
 
int f[400005],n,m,k,del[400005],cnt,star[400005],ans[400005];
vector<int> V[400005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){f[x]=y;}
 
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){int x,y;scanf("%d %d",&x,&y);x++;y++;V[x].push_back(y);V[y].push_back(x);}
scanf("%d",&k);
cnt=n-k;
for(int i=1;i<=k;i++){
    scanf("%d",&star[i]);
    del[++star[i]]=1;
}
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++){
    if(del[i])continue;
    for(int j=0;j<V[i].size();j++){
        if(!del[V[i][j]] && Find(i)!=Find(V[i][j])){cnt--;Union(Find(i),Find(V[i][j]));}
    }
}
ans[k+1]=cnt;
for(int i=k;i;i--){
    cnt++;del[star[i]]=0;
    for(int j=0;j<V[star[i]].size();j++){if(!del[V[star[i]][j]] && Find(V[star[i]][j])!=Find(star[i]))cnt--,Union(Find(star[i]),Find(V[star[i]][j]));}
    ans[i]=cnt;
}
for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);
return 0;
}

我做这题的经历告诉了我：不要乱取模

多取了一个mod 然后WA无数次

我这个方法并不是最优的

懒得写题解了

iwtwiioi大爷的题解

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

const long long Mod=20101009ll;
int mu[10000005],pri[10000005],cnt,tab[10000005];
long long n,m,ans,s[10000005],Mn;

long long Sum(long long x,long long y){return ((x*(x+1)/2)%Mod)*((y*(y+1)/2)%Mod)%Mod;}

void Prepare(){
mu[1]=1;
Mn=min(n,m);
for(long long i=2;i<=Mn;i++){
	if(!tab[i]){pri[++cnt]=i;mu[i]=-1;}
	for(long long j=1;j<=cnt && i*pri[j]<=Mn;j++){
		tab[i*pri[j]]=1;
		if(i%pri[j]){mu[i*pri[j]]=-mu[i];}
		else {mu[i*pri[j]]=0;break;}
	}
}
for(long long i=1;i<=Mn;i++)s[i]=(s[i-1]+(i*i*mu[i])%Mod)%Mod;
}

long long F(long long x,long long y){
long long j,ans=0,Mn2=min(x,y);
for(long long i=1;i<=Mn2;i=j+1){
	j=min(x/(x/i),y/(y/i));
	ans=(ans+(s[j]-s[i-1])*Sum(x/i,y/i)%Mod)%Mod;
}
return ans;
}

int main(){
freopen("2154.in","r",stdin);
freopen("2154.out","w",stdout);
scanf("%lld %lld",&n,&m);
Prepare();
long long j;
for(long long i=1;i<=Mn;i=j+1){
	j=min(n/(n/i),m/(m/i));
	ans=(ans+(j+i)*(j-i+1)/2%Mod*F(n/i,m/i)%Mod)%Mod;
}
printf("%lld\n",(ans+Mod)%Mod);
return 0;
}

这题是树形DP

暴力枚举三个点的中点

因为每个点的深度在以这个点为根的子树中的深度都一样

所以我们开三个数组维护就可以了

时间复杂度$O(n^2)$

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

int n,en,h[5005],tx1[5005],tx2[5005],dep[5005],mx_dep;
long long ans=0;

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

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

void Dfs(int u,int fa,int deep){
mx_dep=max(mx_dep,deep);
dep[deep]++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa)Dfs(v,u,deep+1);
}
}

int main(){
freopen("3522.in","r",stdin);
freopen("3522.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
	int x,y;
	scanf("%d %d",&x,&y);
    AddEdge(x,y);AddEdge(y,x);
}
for(int i=1;i<=n;i++){
	memset(tx1,0,sizeof(tx1));
	memset(tx2,0,sizeof(tx2));
	for(int j=h[i];j;j=e[j].next){
		memset(dep,0,sizeof(dep));
		int v=e[j].b;
		Dfs(v,i,1);
		for(int k=1;k<=mx_dep;k++){
			ans+=tx2[k]*dep[k];
			tx2[k]+=dep[k]*tx1[k];
			tx1[k]+=dep[k];
		}
	}
}
printf("%lld\n",ans);
return 0;
}

至于AH队的名单还是不发为好。。毕竟总成绩没有确定

Day 0

到了合肥

下午试机写了一个网络流

晚上隔膜

Day 1

早上考试

三个数据结构

直接滚粗

10+0+30

下午隔膜+KFC

晚上看模版

Day 2

早上考试

两个数据结构一个计算几何

直接弃疗

40+10+30

总分120

lyz进队了

slx day2全省rank4

wyx好像没进队。。默哀

AHOI2017,刷题一年,明年再战!

因为修改的次数比较少，所以每次暴力重构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;
}