Flandre Scarlet's Blog

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

恭喜前6名获奖，以及cyxhahaha成功AK！

题解：

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吧！