首页 > 其他分享 >咋提玄坛

咋提玄坛

时间:2023-03-02 11:13:13浏览次数:34  
标签:提玄坛 int long MAXN Np dp MOD

[ABC176F] Brave CHAIN

先转化一下问题为有\(2\)个数然后每一轮有固定三个数,每一轮在\(5\)个数中删去\(3\)个数

考虑朴素\(dp_{i,j,k}\)表示前\(i\)轮剩余\(j,k\)两个数的最大值,时间复杂度为\(O(10\times n^3)\)

考虑优化,设目前轮的固定的牌是\(A,B,C\),手里还有\(j,k\)

\(Case1:\)

如果\(j,k\)都被删去,则此时转移可以利用\(dp\)的最大值

假设留下\(A,B\),则先考虑\(j=k=C\)的情况要\(+1\),剩下的直接用最大值即可

\(Case2:\)

如果\(j,k\)被删去一个

假设固定\(j\),此时直接暴力\(O(n)\)转移

\(Case3:\)

如果\(j,k\)未被删去

此时\(dp\)的转移只与\(A,B,C\)是否相等有关,相当与直接打增量标记,注意前面的转移要剔除增量的影响

\(Tips:\)分析转移的形式可以优化掉许多无用转移

Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n;
int a[MAXN*3];
int dp[MAXN][MAXN]; 
int Mp[MAXN];
int fa[MAXN];
int fb[MAXN];
int fc[MAXN];
int main()
{
	memset(dp,-0x3f,sizeof(dp));
	memset(Mp,-0x3f,sizeof(Mp));
	scanf("%d",&n);
	for(int i=1;i<=3*n;i++)
	{
		scanf("%d",&a[i]);
	}
	dp[a[1]][a[2]]=0;
	dp[a[2]][a[1]]=0;
	Mp[a[1]]=0;
	Mp[a[2]]=0;
	int Add=0;
	int Maxi=0;
	for(int i=3;i<=3*n-2;i+=3)
	{
		int A=a[i];
		int B=a[i+1];
		int C=a[i+2];
		int Nod=((A==B)&&(B==C));
		Add+=Nod;
		for(int x=1;x<=n;x++)
		{
			fa[x]=dp[A][x];
			fb[x]=dp[B][x];
			fc[x]=dp[C][x];
		}
		dp[A][B]=max(dp[A][B],(fc[C]+1)-Nod);
		dp[A][B]=max(dp[A][B],Maxi-Nod);
		dp[B][A]=dp[A][B];
		dp[A][C]=max(dp[A][C],(fb[B]+1)-Nod);
		dp[A][C]=max(dp[A][C],Maxi-Nod);
		dp[C][A]=dp[A][C];
		dp[B][C]=max(dp[B][C],(fa[A]+1)-Nod);
		dp[B][C]=max(dp[B][C],Maxi-Nod);
		dp[C][B]=dp[B][C];
		for(int x=1;x<=n;x++)
		{
			if(B==C)
			{
				dp[A][x]=max(dp[A][x],fb[x]+1-Nod);
			}
			dp[A][x]=max(dp[A][x],Mp[x]-Nod);
			dp[x][A]=dp[A][x];
		}
		 for(int x=1;x<=n;x++)
		{
			if(A==C)
			{
				dp[B][x]=max(dp[B][x],fa[x]+1-Nod);
			}
			dp[B][x]=max(dp[B][x],Mp[x]-Nod);
			dp[x][B]=dp[B][x];
		}
		for(int x=1;x<=n;x++)
		{
			if(B==A)
			{
				dp[C][x]=max(dp[C][x],fb[x]+1-Nod);
			}
			dp[C][x]=max(dp[C][x],Mp[x]-Nod);
			dp[x][C]=dp[C][x];
		}
		Mp[A]=max(Mp[A],dp[A][B]);
		Mp[B]=max(Mp[B],dp[A][B]);
		Mp[A]=max(Mp[A],dp[A][C]);
		Mp[C]=max(Mp[C],dp[A][C]);
		Mp[C]=max(Mp[C],dp[C][B]);
		Mp[B]=max(Mp[B],dp[C][B]);
		for(int x=1;x<=n;x++)
		{
			Mp[A]=max(Mp[A],dp[A][x]);
			Mp[x]=max(Mp[x],dp[A][x]);
		}
		for(int x=1;x<=n;x++)
		{
			Mp[B]=max(Mp[B],dp[B][x]);
			Mp[x]=max(Mp[x],dp[B][x]);
		}
		for(int x=1;x<=n;x++)
		{
			Mp[C]=max(Mp[C],dp[C][x]);
			Mp[x]=max(Mp[x],dp[C][x]);
		}
		for(int x=1;x<=n;x++)
		{
			Maxi=max(Maxi,Mp[x]);
		}
	}
	int P=a[3*n];
	int Res=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			Res=max(Res,dp[i][j]+Add);
		}
	}
	Res=max(Res,dp[P][P]+Add+1);
	printf("%d\n",Res);
}

[ABC213G] Connectivity 2

很明显可以枚举一个\(S\),\(i\in S,k\in S\),然后计算\(S\)的联通子图个数\(\times\)补集随便连的方案

我们就设\(F_S\)为\(S\)的联通子图个数,\(G_S\)为补集随便连的方案

很明显\(G\)就是\(S\)中的边数\(2^{Cnt}\)

最开始我想\(F\)的转移是从\(S\)向外连一条边转移,但\(S\)内部的边不好算方案

这时我们考虑容斥,用总方案\(G_S-\)不合法的方案

考虑不合法的方案是由一个联通的\(sub\)与不联通的\(S \oplus {sub}\),注意我们要保证\(1\)是联通的

所以\(F_S=\sum\limits_{sub\subseteq S,1\in sub}F_{sub}\times G_{S-sub}\)

Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int Pow(int a,int b,int p)
{
	int res=1;
	int base=a;
	while(b)
	{
		if(b&1)
		{
			res=((long long)res*base)%p;
		}
		base=((long long)base*base)%p;
		b>>=1;
	}
	return res;
}
int n,m;
int a[25][25];
int G[(1<<17)+5];
int F[(1<<17)+5];
int Ans[25];
int x,y;
void Print(int S)
{
	vector<int>R;
	R.clear();
	while(S)
	{
		R.push_back(S&1);
		S>>=1;
	}
	reverse(R.begin(),R.end());
	for(int i=0;i<R.size();i++)
	{
		printf("%d",R[i]);
	}
	printf("\n");
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		a[x][y]=1;
	}
	for(int S=0;S<(1<<n);S++)
	{
		int Cnt=0; 
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if((S>>(i-1))&1)
				{
					if((S>>(j-1))&1)
					{
						Cnt+=a[i][j]; 
					}
				}
			}
		}
		G[S]=Pow(2,Cnt,MOD);
	}
	F[0]=1;
	for(int S=1;S<(1<<n);S++)
	{
		F[S]=G[S];
		for(int sub=(S&(S-1));sub;sub=(S&(sub-1)))
		{
			if(sub&1)
			{
			}
			else
			{
				continue;
			}
			F[S]=((long long)F[S]-((long long)F[sub]*G[S^sub])%MOD+MOD)%MOD; 
		}
	}
	int Sp=(1<<n)-1;
	for(int S=0;S<(1<<n);S++)
	{
		if(S&1)
		{
			for(int i=2;i<=n;i++)
			{
				if((S>>(i-1))&1)
				{
					Ans[i]=((long long)Ans[i]+((long long)F[S]*G[Sp^S])%MOD)%MOD;
				}
			 } 
		}
	}
	for(int i=2;i<=n;i++)
	{
		printf("%d\n",Ans[i]);
	}
}

[CF1749F]Distance to the Path

原问题的修改肯定不好直接修改,而询问是单点修改肯定是在询问上有不同

我最开始是在询问的点找符合条件的链,貌似可以用树剖维护但会算重

然后换个思路,我们维护\(f_{x,d}\)表示\(x\)点为根,距离刚好为\(d\)的增量

很明显\(x\)的权值为\(\sum\limits_{v是x的祖先}f_{v,dist(v,x)}\)

现在考虑维护\(f\),对于\(x\rightarrow y\),对于其中的\(u\),如果直接给距离\(\le d\)节点\(+k\)

那对于\(fa_u\),给距离\(\le d\)节点\(+k\),对于与\(u\)距离\(<d\)的节点会算重

而\(u\)和\(fa_u\)唯一有用的贡献只有距离刚好为\(d\)的

所以如果我们直接对\(u\in x\rightarrow y\),\(f_{u,d}+=k\)

对于距离\(lca\ge d\)的点应该是不会算重的,但对于\(<d\)的以及\(lca\)外的点是无法加到的

考虑\(lca\)的父亲\(fa\),距离它\(\le d-1\)的点能加上,在\(lca\)子树内距离\(d-2\)

再考虑\(fa\)的父亲\(ffa\),距离它\(\le d-2\)的点能加上,在\(lca\)子树内距离\(d-4\)

由此启发我们让\(fa\)管理\(d-2\)和\(d-3\),而\(ffa\)管理\(d-4,d-5\)(祖先一次管两层)

可以手玩一下,发现是不会算重的

最后树剖维护一下就好了

Show Code
#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int MAXN=3e5+5;
int n;
int q,d;
int x,y;
int op,k;
vector<int>g[MAXN];
int dfn[MAXN];
int cnt_dfn;
int Wson[MAXN];
int Siz[MAXN];
int Fa[MAXN];
int dep[MAXN];
int top[MAXN];
void dfs1(int x,int f)
{
	Siz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i];
		if(v==f)
		{
			continue;
		}
		dep[v]=dep[x]+1;
		Fa[v]=x;
		dfs1(v,x);
		Siz[x]+=Siz[v];
		if(Siz[v]>Siz[Wson[x]])
		{
			Wson[x]=v;
		}
	}
}
void dfs2(int x,int Top)
{
	top[x]=Top;
	dfn[x]=++cnt_dfn;
	if(Wson[x])
	{
		dfs2(Wson[x],Top);
	}
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i];
		if(v==Fa[x])
		{
			continue;
		}
		if(v==Wson[x])
		{
			continue;
		}
		dfs2(v,v);
	}
}
struct Seg_node{
	int l,r;
	int lazy;
};
struct Seg{
	Seg_node Tree[MAXN*4];
	void push_down(int p)
	{
		if(Tree[p].lazy)
		{
			Tree[ls].lazy+=Tree[p].lazy;
			Tree[rs].lazy+=Tree[p].lazy;
			Tree[p].lazy=0; 
		}
	} 
	void Build(int p,int l,int r)
	{
		Tree[p].l=l;
		Tree[p].r=r;
		if(l==r)
		{
			Tree[p].lazy=0;
			return;
		}
		int mid=(l+r)>>1;
		Build(ls,l,mid);
		Build(rs,mid+1,r);
	}
	void Update(int p,int l,int r,int k)
	{
		if(Tree[p].l>=l&&Tree[p].r<=r)
		{
			Tree[p].lazy+=k;
			return;
		}
		push_down(p);
		int mid=(Tree[p].l+Tree[p].r)>>1;
		if(l<=mid)
		{
			Update(ls,l,r,k);
		}
		if(r>mid)
		{
			Update(rs,l,r,k); 
		}
	}
	int Query(int p,int x)
	{
		if(Tree[p].l==Tree[p].r)
		{
			return Tree[p].lazy;
		}
		push_down(p);
		int mid=(Tree[p].l+Tree[p].r)>>1;
		if(x<=mid)
		{
			return Query(ls,x);
		}
		else
		{
			return Query(rs,x);
		}
	}
}tree[21];
int Query_lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
		{
			swap(x,y);
		}
		x=Fa[top[x]];
	}
	if(dep[x]<dep[y])
	{
		swap(x,y);
	}
	return y;
}
void Update_chain(int x,int y,int k,int d)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
		{
			swap(x,y);
		} 
		tree[d].Update(1,dfn[top[x]],dfn[x],k);
		x=Fa[top[x]];
	}
	if(dep[x]<dep[y])
	{
		swap(x,y);
	}
	tree[d].Update(1,dfn[y],dfn[x],k);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int cnt_node=n;
	int last=1;
	for(int i=0;i<=20;i++)
	{
		++cnt_node;
		g[last].push_back(cnt_node);
		g[cnt_node].push_back(last);
		last=cnt_node; 
	}
	scanf("%d",&q);
	for(int i=0;i<=20;i++)
	{
		tree[i].Build(1,1,cnt_node);
	}
	dfs1(cnt_node,0);
	dfs2(cnt_node,cnt_node);
	while(q--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d",&x);
			int Res=0;
			int Now=0;
			while(Now<=20)
			{
				Res+=tree[Now].Query(1,dfn[x]);
		//		printf("%d %d ?\n",x,tree[Now].Query(1,dfn[x]));
				Now++;
				x=Fa[x];
			}
			printf("%d\n",Res);
		}
		else
		{
			scanf("%d %d %d %d",&x,&y,&k,&d);
			Update_chain(x,y,k,d);
			int lca=Query_lca(x,y);
			if(d)
			{
				tree[d-1].Update(1,dfn[lca],dfn[lca],k);
			}
			lca=Fa[lca];
			while(d)
			{
		//		printf("%d?\n",Now);
				d--;
				tree[d].Update(1,dfn[lca],dfn[lca],k);		
				if(d)
				{
					tree[d-1].Update(1,dfn[lca],dfn[lca],k);
				}
				lca=Fa[lca];
			}
		}
	}
}

CF1770E Koxia and Tree加强版

只说大体思路

肯定是考虑每条边的贡献

首先转换\(k\)个点选\(m\)个点

选定其中一个连通块的中标记点大小\(S\),统计不合法的情况即可计算每条边经过的次数

然后解决每个点子树标记点大小为\(S\)的概率

注意到大小只会有\(1\)的变动,然后\(f_{x,t}\)为\(x\)点在\(t\)时有标记的概率,转移很简单

Show Code
#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	x=0;
	int f=1;
	char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-')
		{
			f*=-1;
		}
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=(x*10+(s-'0'));
		s=getchar();
	}
	x*=f;
	return;
}
const int MAXN=5e5+5;
const int MOD=998244353;
int fac[MAXN];
int inv_fac[MAXN];
int Pow(int a,int b,int p)
{
	int res=1;
	int base=a;
	while(b)
	{
		if(b&1)
		{
			res=((long long)res*base)%p; 
		}
		base=((long long)base*base)%p;
		b>>=1;
	}
	return res;
}
int inv(int a,int p)
{
	return Pow(a,p-2,p);
}
int C(int n,int m)
{
	if(n<m||m<0)
	{
		return 0;
	}
	if(n==m||m==0)
	{
		return 1;
	}
	return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD; 
}
int n,k,m;
int x,y;
pair<int,int>edge[MAXN];
int a[MAXN];
int f[MAXN];
int dep[MAXN];
vector<int>g[MAXN];
int Siz[MAXN];
int dp1[MAXN];
int dp2[MAXN];
int dp3[MAXN];
int P;
void dfs(int x,int f)
{
	Siz[x]=a[x];
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i];
		if(v==f)
		{
			continue;
		 } 
		 dep[v]=dep[x]+1;
		 dfs(v,x);
		 Siz[x]+=Siz[v];
	}
}
int main()
{
	fac[0]=1;
	for(int i=1;i<=MAXN-5;i++)
	{
		fac[i]=((long long)fac[i-1]*i)%MOD;
	}
	inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
	for(int i=MAXN-5-1;i>=0;i--)
	{
		inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
	}
	scanf("%d %d",&n,&k);
	m=2;
	for(int i=1;i<=k;i++)
	{
		read(x);
		f[x]=1;
		a[x]=1; 
	}
	for(int i=1;i<n;i++){
		read(x);
		read(y);
		edge[i].first=x;
		edge[i].second=y;
		g[x].push_back(y);
		g[y].push_back(x); 
	}
	int inv2=(MOD-MOD/2);
	dfs(1,0);
	for(int i=1;i<n;i++)
	{
		P=i;
		int u=edge[P].first;
		int v=edge[P].second;
		if(dep[u]<dep[v])
		{
			swap(u,v);
		}
		int Lu=f[u];
		int Lv=f[v];
		f[u]=(((long long)Lu+Lv)*inv2)%MOD;
		f[v]=(((long long)Lu+Lv)*inv2)%MOD;
		dp1[u]=((long long)Lu*((long long)(1-Lv+MOD)%MOD))%MOD;
		dp1[u]=((long long)dp1[u]*inv2)%MOD;
		dp2[u]=((long long)Lv*((long long)(1-Lu+MOD)%MOD))%MOD;
		dp2[u]=((long long)dp2[u]*inv2)%MOD;
		dp3[u]=((long long)1-dp1[u]-dp2[u]+MOD)%MOD;
	}
	int Res=0;
	for(int i=1;i<n;i++)
	{
		int u=edge[i].first;
		int v=edge[i].second;
		if(dep[u]<dep[v])
		{
			swap(u,v);
		}
		if(Siz[u]>=1)
		{
			int S=Siz[u]-1;
			int Np=((long long)C(S,m)+C(k-S,m))%MOD;
			Np=((long long)Np*inv(C(k,m),MOD))%MOD;
			Np=((long long)1-Np+MOD)%MOD;
			Np=((long long)Np*dp1[u])%MOD;
			Res=((long long)Res+Np)%MOD;
		}
		if(1)
		{
			int S=Siz[u]+1;
			int Np=((long long)C(S,m)+C(k-S,m))%MOD;
			Np=((long long)Np*inv(C(k,m),MOD))%MOD;
			Np=((long long)1-Np+MOD)%MOD;
			Np=((long long)Np*dp2[u])%MOD;
			Res=((long long)Res+Np)%MOD;
		}
		if(1)
		{
			int S=Siz[u];
			int Np=((long long)C(S,m)+C(k-S,m))%MOD;
			Np=((long long)Np*inv(C(k,m),MOD))%MOD;
			Np=((long long)1-Np+MOD)%MOD;
			Np=((long long)Np*dp3[u])%MOD;
			Res=((long long)Res+Np)%MOD;
		}
	}
//	Res=((long long)Res*2)%MOD;
	printf("%d\n",Res);
}

CSAcademy Round #35 Counting Quests

好像第一步转化就不会/kk,原问题等价于设\(S_i\)为覆盖到\(i\)的区间集合,\(S_i\)互不相同

具体证明好像不会/kk,手玩一下挺对的

然后有个性质若\(S_a=S_b,a<b,\)则不会存在选定的区间相交且不包含/包含于\([a,b]\)

证明考虑假设存在选定的区间\(p\)相交且不包含/包含于\([a,b]\),假设\(a\)不被\(p\)覆盖则\(S_a\)不存在\(p\)而\(S_b\)中存在\(p\),所以与\(S_a=S_b\)矛盾

这其实我们可以将最大的\([a,b]\)使得\(S_a=S_b\)划分为\(1\)段具体来说我们可以以\(i=1\)为起点找最后一个\(S_1=S_j\)的位置,将\([1,j]\)划分为一段,并以\(i=j+1\)为新的起点

假设当前的序列划分为若干段,其中一段区间\([a,b]\)满足\(S_a=S_b\),则\([a,b]\)内部连边并不会使得划分的段有变化

考虑\(S_a=S_b\),说明一定存在一个选定区间横跨\([a,b]\),而对于\(i\in(a,b)\),\(S_a \subseteq S_i\),这就保证了按上述方式划分,内部任意连边不会产生影响

这样做有什么意义呢?考虑合法方案其实就是段数为\(n\)的方案,而这样分段好转移

设\(dp_i\)为长度为\(i\)时的合法方案数,考虑用总方案减去不合法的方案

考虑不合法的就是段数小于\(i\)的方案,考虑枚举\(j<i\)

考虑将\(i\)个数划分为\(j\)段(不考虑段与段之间的连边)为\(f_{i,j}\),这个是可以直接求的

在考虑横贯段的连边,为了保持\(j\)个段,也就是说我们可以把每一段看成一个点连边使得\(S\)各不相同,这部分就是\(dp_j\)

Show Code
#include<bits/stdc++.h>
using namespace std;
int MOD;
int n;
int f[305][305];
int dp[305];
int Pow[100005];
int main()
{
	scanf("%d %d",&n,&MOD);
	Pow[0]=1;
	for(int i=1;i<=100000;i++)
	{
		Pow[i]=((long long)Pow[i-1]*2)%MOD;
	}
	f[0][0]=1;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(!f[i][j])
			{
				continue;
			}
			for(int k=1;k<=n;k++)
			{
				if(i+k>n)
				{
					continue;
				}
				f[i+k][j+1]=((long long)f[i+k][j+1]+((long long)Pow[(k-1)*(k-2)/2]*f[i][j])%MOD)%MOD;
			}
		}
	}
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i]=Pow[(i*(i+1))/2];
		//printf("%d %d?\n",i,dp[i]);
		for(int j=1;j<i;j++)
		{
			dp[i]=((long long)dp[i]-((long long)dp[j]*f[i][j])%MOD+MOD)%MOD;
		}
	}
	printf("%d\n",dp[n]);
}

[ARC126E] Infinite Operations

首先我们肯定可以确定的是操作后序列全相同是贡献最大

然后因为和不变所以平均数作为最后的数,然后贡献就是原数减平均数?

这好像没有考虑操作的过程中额外产生的贡献,至少没法构造一种这样的解

然后我们考虑构造一个\(F(x)=\sum\limits_{i<j}|a_i-a_j|\)

我们考虑一次价值为\(x\)的操作对\(F(x)\)的影响,对于操作的\(i,j\)至少会减少\(2x\)

而如果不存在\(a_i<a_k<a_j\),则一定只会减少\(2x\)

而终止条件为\(F(x)=0\),如果我们要价值最大一定是每次都选择上面的\(i,j\)

最大价值为\(\dfrac{F(x)}{2}\),线段树维护一下即可

Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=3e6+5;
const int MOD=998244353;
int cnt_node;
struct Seg{
	int date;
	int lc,rc;
	int num;
}Tree[MAXN*4];
int rt;
void Update(int &p,int l,int r,int x,int op)
{
	 if(!p)
	 {
	 	p=++cnt_node;
	 }
	 Tree[p].date=((long long)Tree[p].date+op*x+MOD)%MOD;
	 Tree[p].num+=op;
	 if(l==r)
	 {
	 	return;
	 }
	 int mid=(l+r)>>1;
	if(x<=mid)
	{
	 	Update(ls,l,mid,x,op);
	}
	else
	{
		Update(rs,mid+1,r,x,op);
	 } 
}
int Query(int p,int l,int r,int ql,int qr)
{
	if(ql>qr)
	{
		return 0;
	}
	if(!p)
	{
		return 0;
	}
	if(l>=ql&&r<=qr)
	{
		return Tree[p].date;
	}
	int Res=0;
	int mid=(l+r)>>1;
	if(ql<=mid)
	{
		Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
	}
	if(qr>mid)
	{
		Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
	}
	return Res;
}
int query(int p,int l,int r,int ql,int qr)
{
	if(ql>qr)
	{
		return 0;
	}
	if(!p)
	{
		return 0;
	}
	if(l>=ql&&r<=qr)
	{
		return Tree[p].num;
	}
	int Res=0;
	int mid=(l+r)>>1;
	if(ql<=mid)
	{
		Res=((long long)Res+query(ls,l,mid,ql,qr))%MOD;
	}
	if(qr>mid)
	{
		Res=((long long)Res+query(rs,mid+1,r,ql,qr))%MOD;
	}
	return Res;
}
int n,q;
int a[MAXN];
int x,y;
int inv2;
int main()
{
	inv2=MOD-MOD/2;
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		Update(rt,1,1e9,a[i],1);
	}
	int F=0;
	for(int i=1;i<=n;i++)
	{
		F=((long long)F+((long long)query(rt,1,1e9,1,a[i]-1)*a[i])%MOD)%MOD;
		F=((long long)F-Query(rt,1,1e9,1,a[i]-1)+MOD)%MOD;
		F=((long long)F-((long long)query(rt,1,1e9,a[i]+1,1e9)*a[i])%MOD+MOD)%MOD;
		F=((long long)F+Query(rt,1,1e9,a[i]+1,1e9))%MOD;
	}
	F=((long long)F*inv2)%MOD;
	while(q--)
	{
		scanf("%d %d",&x,&y);
		F=((long long)F-((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD+MOD)%MOD;
		F=((long long)F+Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
		F=((long long)F+((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD)%MOD;
		F=((long long)F-Query(rt,1,1e9,a[x]+1,1e9)+MOD)%MOD;
		Update(rt,1,1e9,a[x],-1);
		a[x]=y;
		Update(rt,1,1e9,a[x],1);
		F=((long long)F+((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD)%MOD;
		F=((long long)F-Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
		F=((long long)F-((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD+MOD)%MOD;
		F=((long long)F+Query(rt,1,1e9,a[x]+1,1e9))%MOD;
		printf("%d\n",(((long long)F*inv2)%MOD));
	}
}

[ARC101F] Robots and Exits

又一次觉得自己是智障

很明显的转化,可以计算每个点左右走最近的出口,设距离为\(L_i,R_i\)

注意如果左或右没有出口直接忽略(可以直接确定是从哪个出口出去的)我就是因为这个被卡了

我最开始想的是给\(L_i\)排序,然后设\(dp_i\)为前\(i\)个数的方案

然后枚举一个\(j,R_j<R_i\)然后我们就假设\((i,j)\)从\(L\)走的,即\(dp_i=dp_j+1\)

不过很明显不对,没有考虑\(L\)的顺序,好像吧

然后换个思路我们考虑答案序列的构造

对于\(L_i\le L_j,R_i\ge R_j\),若\(i\)是从\(R\)走的,那\(j\)一定也是从\(R\)走

因此我们同样可以对\(L_i\)排序,考虑\(i\)如果选择,将会同样选择后面\(<R_i\)的\(j\)

这启示我们可以对第一次的选择\(Dp\)

设\(dp_i\)为前\(i\)个且第一次选择\(i\)的方案,这里要求选的\(i\)是单调递增的,即\(dp_i=\sum dp_j+1,R_j<R_I\)

这个式子和我错误的想法是一样的,大概能过?(/yiw)(反转了,好像举不出反例)

好像可以解释,我最开始想的反例是可能是不对的

Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
#define INF 2e9
using namespace std;
const int MAXN=2e5+5;
const int MOD=1e9+7;
int n,m;
int X[MAXN];
int Y[MAXN];
struct node{
	int up,down;
	bool operator<(const node x)const{
		if(down==x.down)
		{
			return up>x.up;
		}
		return down<x.down;
	}	 
}a[MAXN]; 
int dp[MAXN];
struct Seg{
	int date;
	int lc,rc;
}Tree[MAXN*20];
int rt;
int cnt_node;
void Update(int &p,int l,int r,int x,int k)
{
	if(!p)
	{
		p=++cnt_node;
	}
	Tree[p].date=((long long)Tree[p].date+k)%MOD;
	if(l==r)
	{
		return;	
	} 
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		Update(ls,l,mid,x,k);
	}
	else
	{
		Update(rs,mid+1,r,x,k);	
	} 
}
int Query(int p,int l,int r,int ql,int qr)
{
	if(ql>qr)
	{
		return 0;
	}
	if(!p)
	{
		return 0;
	}
	if(l>=ql&&r<=qr)
	{
		return Tree[p].date;
	}
	int Res=0;
	int mid=(l+r)>>1;
	if(ql<=mid)
	{
		Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
	}
	if(qr>mid)
	{
		Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
	}
	return Res;
}
int main()
{
	scanf("%d %d",&n,&m);
	printf("%d %d?\n",n,m); 
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&X[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&Y[i]);
	}
	sort(X+1,X+1+n);
	sort(Y+1,Y+1+m);
	int Cnt=0;
	for(int i=1;i<=n;i++)
	{
		int R=lower_bound(Y+1,Y+1+m,X[i])-Y;
		int L=R-1;
		if(R==m+1)
		{
			continue;
		}
		if(L==0)
		{
			continue;
		}
		a[++Cnt].up=Y[R]-X[i];
		a[Cnt].down=X[i]-Y[L];
	}
	sort(a+1,a+1+Cnt);
	dp[0]=1;
	for(int i=1;i<=Cnt;i++)
	{
		if(a[i].up==a[i-1].up&&a[i].down==a[i-1].down)
		{
			continue;
		}
	//	printf("%d?\n",i);
		dp[i]=((long long)Query(rt,1,1e9,1,a[i].up-1)+1)%MOD;
		Update(rt,1,1e9,a[i].up,dp[i]);
	}
	int Res=0;
//	printf("%d??\n",Cnt);
	for(int i=0;i<=Cnt;i++)
	{
		Res=((long long)Res+dp[i])%MOD;
	}
	printf("%d\n",Res);
}

[AGC049D] Convex Sequence

首先很明显转化成差分的形式后是下凸函数的形式(然后就不会了/kk)

然后肯定有个底,最下面是平台,我们考虑设平台最左端的点为\(i\)

考虑满足题意最小总和的序列,一定是平台为\(0\),左边依次加\(1\),右边全部为\(0\)

考虑在此基础上经过一些操作使得总和为\(m\)且依旧是个凸函数

回想之前一个很经典的题,构造一个总和为\(m\)的递增序列,具体做法就是用在末尾加\(1\)和整体加\(1\)构造

同样,在这道题中,我们可以设计三个操作

首先可以给序列整体加\(1\)

然后可以给\(i\)左边整体加一个等差数列\((k,k-1,k-2...1)\)

和给右边整体加一个等差数列\((1,2,....k)\)

可以证明这样的操作是可以覆盖所有满足条件的序列且合法的

然后注意到一次操作的贡献是\(n\)或\(\dfrac{k(k+1)}{2}\),说明\(k\)的取值只有\(\sqrt{m}\)个

对于固定的\(i\),做有\(\sqrt m\)个物品的完全背包即可

考虑从\((i-1)\rightarrow i\),不难想到左边的物品多了一个,右边少了一个,做一次完全背包删加物品即可

Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int n,m;
int dp[MAXN];
int a[MAXN];
int f[MAXN];
int main()
{
	scanf("%d %d",&n,&m);
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]+i;
		if(a[i]>m)
		{
			a[i]=m+1;
		 } 
	}
	dp[0]=1;
	for(int i=1;i<n;i++)
	{
		for(int j=a[i];j<=m;j++)
		{
			dp[j]=((long long)dp[j]+dp[j-a[i]])%MOD;
		}
	}
	for(int i=n;i<=m;i++)
	{
		dp[i]=((long long)dp[i]+dp[i-n])%MOD;
	}
	int Res=dp[m];
	int Rs=m;
	for(int i=2;i<=n;i++)
	{
		Rs-=(i-1);
		if(Rs<0)
		{
			break;
		}
		int Del=a[n-i+1];
		for(int j=m;j>=Del;j--)
		{
			dp[j]=((long long)dp[j]-dp[j-Del]+MOD)%MOD; 
		}
		int Add=a[i-1];
		for(int j=Add;j<=m;j++)
		{
			dp[j]=((long long)dp[j]+dp[j-Add])%MOD;
		}
		Res=((long long)Res+dp[Rs])%MOD;
	}
	printf("%d\n",Res);
}

标签:提玄坛,int,long,MAXN,Np,dp,MOD
From: https://www.cnblogs.com/kid-magic/p/17162204.html

相关文章