noip模拟测试10

这道题在考场上想到了二维前缀和，就是自己算前缀和的方式有点麻烦，导致花的时间较长，但还是成功搞了出来。

因为暴力计算的话需要不停枚举左上角和右下角的 i ,j, 时间复杂度为 n^4 ,我当时就想一种能不能减少一层或者两层枚举内容，但是没什么思路。

考虑这样一个性质：在模k意义下相同的前缀和，任意两个相减可以被 k 整除

这道题正解为 n^3 ,的复杂度，我们考虑将每一列压缩，这样，我们只需要通过枚举每个矩形区域的上下边界，就可以求得答案

注意：当余数为0的时候要多算一次答案

代码：

#include<bits/stdc++.h>
#define re register int
#define int long long
#define ll long long
using namespace std;
const int N=410,M=1e6+10;
int n,m,k,ans;
int a[N][N],sum[N][N],s[N];
int vis[M];
ll read()
{
	ll x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}	
	return x;
}
#undef int
int main()
{
	#define int long long
	n=read();
	m=read();
	k=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			a[i][j]=read();
		}
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}	
	}
	for(re i=0;i<n;i++)
	{
		for(re j=i+1;j<=n;j++)
		{
			for(re p=1;p<=m;p++)
			{
				s[p]=(sum[j][p]-sum[i][p]+k)%k;
				ans+=vis[s[p]]++;
			}
			ans+=vis[0];
			for(re p=1;p<=m;p++)
				vis[s[p]]=0;
			vis[0]=0;
			
		}
	}
	printf("%lld\n",ans);
	return 0;
}

　这道题，是一道贪心题，但是我在考场上没看出来，当时之打了个dfs。

　其实不难看出，如果要修建小队，则在距离他的最远的祖先哪里最优

　所以我们可以按深度从大到小排序，从深度最大的儿子向上更新答案

　代码：

#include<bits/stdc++.h>
#define re register int
#define next neet
#define INF 9999999
using namespace std;
const int N=1e5+10;
int n,k,t,ans,tot;
int fa[N],deep[N],num[N],o[N];
int to[N<<1],next[N<<1],head[N<<1];
struct node
{
	int out,ff;
};
int my(int a,int b)
{
	return deep[a]>deep[b];
}
node gett(int v)
{
	node P;
	int u=v,out=INF,mf=v;
	for(re i=1;i<=k;i++)
	{
		u=fa[u];
		out=min(out,o[u]+i);
		mf=u;
		if(u==0)
			break;
		
	}
	P.out=out;
	P.ff=mf;
	return P;
}
void change(int x)
{
	int u=x;
	for(re i=1;i<=k;i++)
	{
		u=fa[u];
		o[u]=min(o[u],i);
		if(u==0)
			break;
	}
}
void add(int x,int y)
{
	to[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
void dfs(int st,int f)
{
	deep[st]=deep[f]+1;
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==f)
			continue;
		fa[p]=st;
		dfs(p,st);
	}
}
int main()
{
	scanf("%d%d%d",&n,&k,&t);
	int a,b,c,d;
	for(re i=2;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	deep[0]=-1;
	dfs(1,0);
	for(re i=1;i<=n;i++)
	{
		num[i]=i;
		o[i]=INF;
	}
	o[0]=INF;
	sort(num+1,num+n+1,my);
	for(re i=1;i<=n;i++)
	{
		int v=num[i];
		node X;
		X=gett(v);
		o[v]=min(o[v],X.out);
		if(o[v]>k)
		{
			++ans;
			o[X.ff]=0;
			change(X.ff);
		}
	}
	printf("%d\n",ans);
	return 0;
}

这道题，确实比较有难度

看到对于一个区间的操作，我当时想了线段树，书装数组，但是没什么思路。

正解是利用差分！！，这道题思路非常妙，考虑一个差分数组，那么考虑对原 $a[l]^=1,a[r+1]^=1,$

而我们的目的是将差分数组全部变为0，考虑转移时的情况：

1.两端都是 0，变为 1

2.两端都是1.变为 0

3.一个 1，一个 0；

可见，只有第二种情况对答案有贡献，所以我们之考虑第二种情况；

我们将每个 i与i+b[j] 连一条长度为1的边，那么将 [L,R] 的区间翻转的最小次数就是 L到 R 的最短路

我们将所有的 1 进行状态压缩，易得：

t=s^(1<<i-1)^(1<<j-1)

f[t]=min(f[t],f[s]+dis[i][j]);

最后输出答案 f[0]，即可

代码：

#include<bits/stdc++.h>
#define re register int
using namespace std;
const int N=4e4+10;
int n,k,m,sum;
int b[N],pos[N],dis[N],q[N];
int f[(1<<16)+5];
int d[N>>2][N>>2];
bool vis[N];
void bfs()
{
	int u,v,l,r;
	for(re i=1;i<=sum;i++)
	{
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		dis[pos[i]]=0;
		vis[pos[i]]=1;
		l=r=1;
		q[l]=pos[i];
		while(l<=r)
		{
			u=q[l];
			++l;
			for(re j=1;j<=m;j++)
			{
				v=u-b[j];
				if(v>=1&&(!vis[v]))
				{
					dis[v]=dis[u]+1;
					vis[v]=1;
					q[++r]=v;
				}
				v=u+b[j];
				if(v<=n+1&&(!vis[v]))
				{
					dis[v]=dis[u]+1;
					vis[v]=1;
					q[++r]=v;
				}
			}
		}
		for(re j=1;j<=sum;j++)
			d[i][j]=dis[pos[j]];
	}
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	int a;
	for(re i=1;i<=k;i++)
	{
		scanf("%d",&a);
		vis[a]^=1;
		vis[a+1]^=1;
	}
	for(re i=1;i<=m;i++)
		scanf("%d",&b[i]);
	for(re i=1;i<=n+1;i++)
		if(vis[i])
			pos[++sum]=i;
	bfs();
	memset(f,0x3f,sizeof(f));
	f[(1<<sum)-1]=0;
	for(re s=(1<<sum)-1;s;s--)
	{
		int p=1;
		int ss=s;
		while((ss&1)==0)
		{
			++p;
			ss>>=1;
		}
		for(re i=p+1;i<=sum;i++)
		{
			int t=s^(1<<(i-1))^(1<<(p-1));
			f[t]=min(f[t],f[s]+d[p][i]);
		}
	}
	printf("%d\n",f[0]);
	return 0;
}