noip模拟赛#24

这套题我只会写第二题。。。我。。。

T1：给出一个含有向边和无向边的混合图，如何确定无向边的方向使得图中不存在环。保证有解。多解情况输出任意解。

=>我往最大流的残量网络的方向去想了。。。因为混合图求欧拉回路用的就是最大流。。。然而什么都想不出来。。。

正解：

原图是个有向无环图，也就是说是个拓扑图，如果加完边后依然是拓扑图，也就是依然无环。

对原图做拓扑排序，得到每个点的入队时间，加边的时候把边定向为从入队时间早的点到晚的点，原来的入队顺序就依然成立，就无环了。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define qwq(x) for(edge *o=head[x];o;o=o->next)

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=1e5+5;

const int inf=0x7f7f7f7f;

struct edge{

	int to;edge *next;

};edge es[nmax],*pt=es,*head[nmax];

void add(int u,int v){

	pt->to=v;pt->next=head[u];head[u]=pt++;

}

int q[nmax],in[nmax],qe[nmax];

int main(){

	freopen("dizzy.in","r",stdin);freopen("dizzy.out","w",stdout);

	int n=read(),m=read(),tm=read(),u,v;

	rep(i,1,m) u=read(),v=read(),add(u,v),in[v]++;

	int cur=0;

	rep(i,1,n) if(!in[i]) q[i]=++cur,qe[cur]=i;

	rep(i,1,cur) qwq(qe[i]) if(!--in[o->to]) q[o->to]=++cur,qe[cur]=o->to;

	//rep(i,1,n) printf("%d ",q[i]);printf("\n");

	rep(i,1,tm) {

		u=read(),v=read();

		if(q[u]>q[v]) swap(u,v);

		printf("%d %d\n",u,v);

	}

	fclose(stdin);fclose(stdout);

	return 0;

}

/*

4 5 3

1 2

1 3

2 3

2 4

3 4

*/

T2：给出一个500*500的矩阵。可横着切A刀，竖着切B刀。求最小块的最大值。

=>二分答案。。。发现尽量的弄到函数里面清晰好多啊T_T

//特别奇怪。输出ans的时候我写成了%lld就全WA。。。还以为没有什么关系的TAT

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define ll long long

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=505;

const int inf=0x7f7f7f7f;

int a[nmax][nmax],n,m,A,B;

bool pd(int r,int l,int x){

	int pre=0,ans=0,tp=0;

	rep(i,1,m) if((tp+=a[r][i]-a[l][i])>=x) pre=i,++ans,tp=0;

	return ans>=B;

}

bool check(int x){

	int pre=0,ans=0;

	rep(i,1,n) if(pd(i,pre,x)) pre=i,++ans;

	return ans>=A;

}

int main(){

	freopen("browine.in","r",stdin);freopen("browine.out","w",stdout);

	n=read(),m=read(),A=read(),B=read();int sm=0;

	rep(i,1,n) rep(j,1,m) a[i][j]=read(),sm+=a[i][j];

	rep(j,1,m) rep(i,1,n) a[i][j]+=a[i-1][j];

	int l=0,r=sm,ans=0,mid;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	printf("%d\n",ans);

	fclose(stdin);fclose(stdout);

	return 0;

}

/*

5 4 4 2

1 2 2 1

3 1 1 1

2 0 1 3

1 1 1 1

1 1 1 1

*/

T3：给出一个500*500的矩阵，要求在同一条直线上取n个点，点的间距>=d。求有多少中方案？

=>maya确定两个端点后这根本不能无法确定有多少种方案啊。。。

正解

枚举一个点（x,y)，先算出（0，0）——>(x,y)这条直线上放N个点,（0，0）处一定放第一个点，(x,y)处一定放最后一个点的方案数，把最后一个点平移（其他N-1个点跟着整体平移）到以(x,y)为左上角，(w+1,h+1)为右下角的矩形中的任何一个格点又是不重复的新的方案。

第一步的方案可以这样计算：

设g=gcd(x,y),则（0，0）——>(x,y)的线段上共有g+1个相邻的距离相同的格点，把这些点从1到g+1编号。设比i点编号大的点中离i最近且距离不小于d的点是i+k,我们要在这g-1个点（开头结尾已定）中取n-2个点，满足编号

X_i-X_i-1>=k。此问题等价于

1+k(n-1)<=X₂+k(n-2)<=……<=X_n-1+k<=g+1的解的方案数

上面这个问题又等价于

1+k(n-1)+1<=X₂+k(n-2)+1<X₃+k(n-3)+2<……

<X_n-1+k+(n-2)<=g+1+n-2 的解的方案数

这样方案数就显然了，首先开头结尾都定了，我们要在[1+k(n-1)+1,g+1+n-2]这g-(k-1)(n-1)-1个数中选出n-2个数，方案数就是原问题的方案数。

时间复杂度O（WH）

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cmath>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=505;

const int inf=0x7f7f7f7f;

const int mod=1e9;

int c[nmax][nmax],g[nmax][nmax];

void M(int &a){

	if(a>=mod) a-=mod;

}

int gcd(int a,int b){

	return b==0?a:gcd(b,a%b);

}

void init(){

	c[1][0]=1;c[1][1]=1;

	rep(i,0,500) c[i][0]=1;

	rep(i,2,500) rep(j,1,i) M(c[i][j]=c[i-1][j]+c[i-1][j-1]);

	rep(i,1,500) rep(j,1,500) g[i][j]=gcd(i,j);

	rep(i,1,500) g[i][0]=i,g[0][i]=i;g[0][0]=0;

}

int cal(int n,int m,int A,int D){

	if(A==1) return (n+1)*(m+1);

	int ans=0,k;

	rep(i,0,n) rep(j,0,m){

		k=(int)((double)D*(g[i][j])/sqrt((double)i*i+j*j)+0.999999);

		if(g[i][j]-1<A-2||g[i][j]-(k-1)*(A-1)-1<0) continue;

		M(ans+=1ll*(!i||!j?1:2)*c[g[i][j]-(k-1)*(A-1)-1][A-2]*(n-i+1)%mod*(m-j+1)%mod);

	}

	return ans;

}

int main(){

	freopen("backyard.in","r",stdin);freopen("backyard.out","w",stdout);

	int T=read();init();

	rep(_T,1,T){

		int A=read(),n=read(),m=read(),D=read();

		printf("%d\n",cal(n,m,A,D));

	}

	fclose(stdin);fclose(stdout);

	return 0;

}

/*

6

2 4 4 1

13 36 48 5

5 5 5 1

50 49 49 1

6 5 5 2

10 55 75 5

*/

巴特西

noip模拟赛#24

最新文章

热门文章