5
7
2016
0

【洛谷5月月赛】题解

省选滚粗来出一套题冷静一下233333

恭喜前6名获奖,以及cyxhahaha成功AK!

400 (9433ms)100
100
100
100
380 (7429ms)
100
100
80
100
344 (1968ms)
100
100
80
64
328 (5625ms)
100
100
80
48
304 (5607ms)
100
100
80
24
#6
Riolu
292 (1552ms)
100
100
80
12

 

 

 

题解

T1:

枚举好题。

枚举A、B:30分。

枚举A、B的和G,判断神犇编号对G取模后的最大值以及蒟蒻编号对G取模后的最小值,判断有没有相交即可。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 1001
#define INF 2000000000
using namespace std;
int n,m,a[maxn],b[maxn],maxl,aa,ab;
int main()
{
	while(scanf("%d%d",&n,&m)==2)
	{
		maxl=0,aa=INF,ab=INF;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxl=max(--a[i],maxl);
		for(int i=1;i<=m;i++)scanf("%d",&b[i]),maxl=max(--b[i],maxl);
		for(int G=2;G<=maxl;G++)
		{
			int ma=0,mb=INF;
			for(int i=1;i<=n;i++)ma=max(ma,a[i]%G);
			for(int i=1;i<=m;i++){mb=min(mb,b[i]%G);if(mb<=ma)break;}
			if(mb<=ma)continue;ma++,mb=G-ma;
			if(aa>ma||(aa==ma&&ab>mb))aa=ma,ab=mb;
		}
		if(aa==INF&&ab==INF)puts("NO");
		else printf("%d %d\n",aa,ab);
	}
}

T2:

数学好题

前30分:对于1-m中的每个数以枚举给定质数集判断能否整除。

接下去20分:小学奥数

满分:容斥原理(还是小学奥数)容斥原理详见百度百科。用搜索(状压)实现。

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxn 20
using namespace std;
typedef long long LL;
int n;LL m,a[21],M=376544743;
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	if(n*m<=10000000)
	{
		LL ans=0;
		for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(i%a[j]==0){ans+=(LL)i;break;}
		printf("%lld",ans%M);
		return 0;
	}
	int S=1<<n;LL ans=0;
	for(int i=0;i<S;i++)
	{
		int s=0;LL x=1;for(int j=1,w=i;w;j++,w>>=1)if(w&1)s++,x*=a[j];
		LL N=m/x;
		if(s)if(s&1)ans=(ans+x*(N+1)%M*N%M*((M+1)/2)%M)%M;
		else ans=(ans-x*(N+1)%M*N%M*((M+1)/2)%M)%M;
	}
	printf("%lld",ans);
} 

T3:

DP好题。

10分:puts("0");/writeln('0');

20分:k=2的时候两种颜色间隔,判断奇偶

80分:状压DP,m位k进制状压表示每行状态,处理相邻两行能否转移。复杂度n*k^(2m)

100分:(伪)轮廓线DP,f[n][m][S]表示(n,m)以及前m位的状态(■处)为S(如下图),在★处转移,要和上面的和左边的格子不同。

□□■■■■

■■★□□□

注意上面这个和下面这个情况不一样特殊处理(转移时只要注意和上面一格不同)

■■■■■■

★□□□□□

(□■不代表颜色,代表状压时的状态)

Code:(写得丑,瞎凑活着看)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxm 8
#define maxk 4
#define M 376544743
#define maxn 100
using namespace std;
int dp[2][65536],tmp[maxm+1],s[maxm+1],t[maxm+1];
int n,m,k,Ss,St,x,c1,c2,S=1;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)scanf("%d",&x),s[i]=x,Ss=Ss*k+x;
	for(int i=1;i<=m;i++)scanf("%d",&x),t[i]=x,St=St*k+x;
	for(int i=1;i<m;i++)if(s[i]==s[i+1]||t[i]==t[i+1]){printf("0");return 0;}
	if(k==2){if((s[1]==t[1])^(n&1))printf("0");else printf("1");return 0;}
	for(int i=1;i<=m;i++)S*=k;
	c1=0,c2=1;dp[c1][Ss]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=m;j++,c1^=1,c2^=1)
		{
			memset(dp[c2],0,sizeof(dp[c2]));
			for(int l=0;l<S;l++)
				if(dp[c1][l])
				{
					int K=l;
					for(int t=0;t<m;t++)tmp[t]=K%k,K/=k;
					for(int t=0;t<k;t++)
					{
						int w=0;
						if((j!=1&&t!=tmp[m-1]&&t!=tmp[0])||(j==1&&t!=tmp[0]))
						{
							tmp[m]=t;
							for(int s=m;s>=1;s--)w=w*k+tmp[s];
							dp[c2][w]=(dp[c2][w]+dp[c1][l])%M;
						}
					}		
				}
		}
	printf("%d",dp[c1][St]);	
} 

T4:

边双连通缩点+LCA好题。@_xiaoxuan 发现puts("YES");/Writeln('YES');有一半分数23333

1-2:本来是条链,但是洛谷栈空间开不大不想写手写栈就删掉了数据

3-4:dfs存答案。

5-8:直接倍增LCA树剖更快

9-10:搜索。

100分:考虑影响某两个点能否往返的因素——桥(割边),于是将所有边双连通分量缩起来,原图变成一棵树。只需要询问树上两个点之间路径是否大于1,注意这里有边权和点权同时处理。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define AE(u,v,w) E[Si]=(Ed){u,v,w};nxt[Si]=idx[u];idx[u]=Si++
#define maxn 1000005
#define maxm 1000010
using namespace std;
struct Ed{int u,v,w;}E[maxm];
int idx[maxn],Si,nxt[maxm];
int n,m,q,dfn[maxn],low[maxn],cnt,St[maxn],is[maxn],belong[maxn],N,st,A[maxn],x,y,z;
int F[maxn][22],dis[maxn],dep[maxn],f[maxn],fl=0,mm=0;
void tarjan(int u,int fa)
{
	is[u]=1;St[++st]=u;
	dfn[u]=low[u]=++cnt;
	for (int i=idx[u];i+1;i=nxt[i])
		if(E[i].v!=fa)
		{			
			if(!dfn[E[i].v])tarjan(E[i].v,u),low[u]=min(low[u],low[E[i].v]);
			else if(dfn[E[i].v]<dfn[u])low[u]=min(low[u],dfn[E[i].v]);
		}
	if (dfn[u]==low[u])
	{
		int v=St[st--];is[v]=0;belong[v]=++N;
		for (;st&&v!=u;v=St[st--],is[v]=0,belong[v]=N);
	}
}
void dfs(int u,int fa)
{
	int i;for(i=1,F[u][0]=fa;i<22;i++)F[u][i]=F[F[u][i-1]][i-1];
	for(i=idx[u];i+1;i=nxt[i])if(E[i].v!=fa)dep[E[i].v]=dep[u]+1,dis[E[i].v]=dis[u]+A[E[i].v]+E[i].w,dfs(E[i].v,u);
}
int lca(int x,int y)
{
	if(dep[y]>dep[x])swap(x,y);for(int t=dep[x]-dep[y],i=0;t;t>>=1,i++)if(t&1)x=F[x][i];
	if(x==y)return x;for(int i=21;i>=0;i--)if(F[x][i]-F[y][i])x=F[x][i],y=F[y][i];
	return F[x][0];
}
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
int main()
{
	memset(idx,-1,sizeof(idx)); 
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		AE(x,y,z),AE(y,x,z);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);
	memset(idx,-1,sizeof(idx));Si=0;
	for(int i=1;i<=N;i++)f[i]=i;
	for(int i=0;i<2*m;i+=2)
	{
		int u=belong[E[i].u],v=belong[E[i].v];
		if(u==v)A[u]+=E[i].w;
		else
		{
			int a=gf(u),b=gf(v);
			if(a!=b)AE(u,v,E[i].w),AE(v,u,E[i].w),f[a]=b;
		}
	}
	dfs(1,0);
	scanf("%d",&q);
	for(;q--;)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		int w=lca(belong[s],belong[t]);
		if (dis[belong[s]]+dis[belong[t]]-2*dis[w]+A[w])puts("YES");
		else puts("NO");
	}
	return 0;
}

友情XJB推广时间:水题无法AK?反手无力,正手不精,脚步松散,反应迟钝,没一个代码像样的?快加入SOL的完美信息教室523697161,两个月AKNOI吧!

Category: HDU | Tags: | Read Count: 716

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com