2019南京区域赛

2019年南京区域赛 .

以下题目按照个人认为的难度顺序排列.

题目连接

https://www.jisuanke.com/contest/5528/challenges

A. A Hard Problem

一般这种标题都是正话反说?

可能看到这个题之后,有灵感的人可以立马猜出结论.

我个人倾向于打表找规律,利用位运算枚举小数据的情况,得到一个大概结论的规律.

打表代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

bool ok(vector<int> chosen){
	for(int i=0;i<chosen.size();i++)
		for(int j=0;j<chosen.size();j++)
			if(i!=j){
				int a=chosen[i];
				int b=chosen[j];
				if(a>b) if(a%b==0) return true;
				else if(b%a==0) return true;
			}
	return false;
}

bool  solve(int n,int k){
	for(int i=1;i<=((1<<n)-1);i++){
		vector<int> vec;
		for(int j=0;j<n;j++) 
			if((1<<j)& i) vec.pb(j+1);
		if(vec.size()==k) 
			if(ok(vec)==0) return false;
	}
	return true;
}

int main(){
	/*
	int n,k;while(cin>>n>>k){
		cout<<solve(n,k)<<endl;
	}
	*/

	for(int n=2;n<=20;n++){

		int ans=n;
		for(int j=n;j>=1;j--){
			if(solve(n,j)==0) break;

			ans=j;
		}
		cout<<n<<" : "<<ans<<endl;
	}
	return 0;
}

通过代码

//ac
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

int main(){
	int T=read();while(T--){
		int n=read();
		cout<<(n+1)/2+1<<"\n";
	}
	return 0;

}

H Prince and Princess

这个题在现场赛的时候坑了不少队伍,感觉一方面是题意杀,另一方面是1 0 0 这个数据可能没想到.

在这个题目当中,随机的人和存心捣乱的人可以看成一类人,

输入为1 0 0 的时候其实一个人都不用问了,因为只有一个人肯定是公主.

这个题目可能可以吸取的教训是从比较小的数据开始推算一下结果,可能就会把一些特殊情况规避掉.

通过代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


int main(){
	int a,b,c;
	while(~scanf("%d%d%d",&a,&b,&c)){
		if(a==1&&b==0&&c==0) printf("YES\n0\n");
		else if(a>b+c) printf("YES\n%d\n",2*(b+c)+1);
		else printf("NO\n");
	}return 0;
}

K. Triangle

一个较为基础的计算几何题目,二分的思路也非常好想.

计算几何非常容易写出问题,因为涉及到很多double的运算,往往是非常危险的,而且比较难出样例进行测试.

是时候需要整理一下计算几何的模板了.

下面放几份我通过的代码,细节实现略有不同.

通过代码1

// first
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const double eps=1e-6;

struct point
{
    double x;  //x坐标
    double y;  //y坐标

}a,b,c,p;  //定义点



//判断点是否在线上,在返回1,不在返回0
int onSegement(point p1,point p2,point Q)
{
    double maxx,minx,maxy,miny;

    maxx = p1.x >p2.x ?p1.x :p2.x ;    //矩形的右边长
    minx = p1.x >p2.x ?p2.x :p1.x ;     //矩形的左边长
    maxy = p1.y >p2.y ?p1.y :p2.y ;    //矩形的上边长
    miny = p1.y >p2.y ?p2.y :p1.y ;     //矩形的下边长

    if( ((Q.x -p1.x )*(p2.y -p1.y) == (p2.x -p1.x) *(Q.y -p1.y)) && ( Q.x >= minx && Q.x <= maxx ) && ( Q.y >= miny && Q.y <= maxy))
        return 1;
    else
        return 0;
}



#define x1 x_1
#define y1 y_1
#define x2 x_2
#define y2 y_2
#define x3 x_3
#define y3 y_3


double cal(point a,point b,point c){
	double x_1=a.x;
	double y_1=a.y;
	double x_2=b.x;
	double y_2=b.y;
	double x_3=c.x;
	double y_3=c.y;
	double ans=fabs(0.5*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2));
	return ans;

 //  bug is here  我居然写了两次 - x_1*y_3   :|
 //  实际上第一份代码就是cal函数没写对,泪目 
	double res=fabs(0.5*(x_1*y_2+x_2*y_3+x_3*y_1-x_1*y_3-x_1*y_3-x_2*y_1-x_3*y_2));
	return res;
}

/*
double cal(point a,point b,point c){
	double x_1=a.x;
	double y_1=a.y;
	double x_2=b.x;
	double y_2=b.y;
	double x_3=c.x;
	double y_3=c.y;

	double res=fabs(0.5*(x_1*y_2+x_2*y_3+x_3*y_1-x_1*y_3-x_1*y_3-x_2*y_1-x_3*y_2));
	return res;
}
*/


int main(){
	int T=read();while(T--){
		scanf("%lf%lf",&a.x,&a.y);
		scanf("%lf%lf",&b.x,&b.y);
		scanf("%lf%lf",&c.x,&c.y);
		scanf("%lf%lf",&p.x,&p.y);

		if(fabs(p.x*2-a.x-b.x)<eps && fabs(p.y*2-a.y-b.y) <eps) {
			printf("%.12f %.12f\n",c.x,c.y);
			continue;
		}
		else if(fabs(p.x*2-a.x-c.x)<eps && fabs(p.y*2-a.y-c.y)<eps) {
			printf("%.12f %.12f\n",b.x,b.y);
			continue;
		}else if(fabs(p.x*2-b.x-c.x)<eps && fabs(p.y*2-b.y-c.y)<eps){
			printf("%.12f %.12f\n",a.x,b.y);
			continue;
		}



		if(onSegement(a,b,p)) ;
		else if(onSegement(b,c,p)) swap(a,c);
		else if(onSegement(a,c,p)) swap(b,c);
		else {
			printf("-1\n");
			continue;
		}

		double area1=cal(a,p,c);
		double area2=cal(b,p,c);
		if(area1>=area2) ;
		else swap(a,b);


		double area=cal(a,b,c)*0.5;

		double l=0,r=1;
		int cnt=1000;
		point ans;

		while(cnt--){
			double m=(l+r)*0.5;
			point pos;
			pos.x=a.x+(c.x-a.x)*m;
			pos.y=a.y+(c.y-a.y)*m;

			double tmp=cal(pos,a,p);
			ans.x=pos.x;
			ans.y=pos.y;

			if(tmp<area) l=m;
			else r=m;
		}

		printf("%.15f %.15f\n",ans.x,ans.y);

	}

	return 0;
}

通过代码2

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long #define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

#define db double


const db eps=1e-9;


class point{
 	public:
	double x;
	double y;
	point(double x_=0,double y_=0):x(x_),y(y_){} 
	friend const point operator+(const point& p1,const point& p2){
		return point(p1.x+p2.x,p1.y+p2.y);
	};
	friend const point operator-(const point& p1,const point& p2){
		return point(p1.x-p2.x,p1.y-p2.y);
	};
	friend const point operator*(const point& p,const double& m){
		return point(p.x*m,p.y*m);
	};
	friend const point operator*(const double& m,const point& p){
		return point(p.x*m,p.y*m);
	};
	friend const point operator/(const point& p,const double& m){
		return point(p.x/m,p.y/m);
	};
	friend ostream& operator <<(ostream& out,point& a){
		printf("(%lf,%lf)",a.x,a.y);
		return out;
	};
}a,b,c,p;

typedef point vect2;//重命名,向量也是用坐标表示 
 
class line{
	public:
	point start;
	point end; 
	line(point s=point(0,0),point e=point(0,0)):start(s),end(e){}
};
 
double cross(point O,point A,point B){//叉乘 
	double oa_x=A.x-O.x;
	double oa_y=A.y-O.y;
	double ob_x=B.x-O.x;
	double ob_y=B.y-O.y;
	return oa_x*ob_y-oa_y*ob_x;
}
bool pointIsOnLine(point O,line L){
	point S=L.start;
	point E=L.end;
	if(cross(O,S,E)==0//在直线L上 
	and min(S.x,E.x)<=O.x&&O.x<=max(S.x,E.x)
	and min(S.y,E.y)<=O.y&&O.y<=max(S.y,E.y))
		return true;
	else return false; 
} 

double getArea(point a,point b,point c){
	return fabs(0.5*cross(a,b,c));
}

/*
double cal(point a,point b,point c){
	db dis1=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
	db dis2=sqrt((a.x-c.x)*(a.x-c.x)+(a.y-c.y)*(a.y-c.y));
	db dis3=sqrt((b.x-c.x)*(b.x-c.x)+(b.y-c.y)*(b.y-c.y));

	double aa=dis1;
	double bb=dis2;
	double cc=dis3;
	double p=0.5*(aa+bb+cc);
	return sqrt(p*(p-aa)*(p-bb)*(p-cc));
}
*/

point getMid(point a,point b){
	return point(0.5*(a.x+b.x),0.5*(a.y+b.y));
}


int main(){
	int T=read();while(T--){
		scanf("%lf%lf",&a.x,&a.y);
		scanf("%lf%lf",&b.x,&b.y);
		scanf("%lf%lf",&c.x,&c.y);
		scanf("%lf%lf",&p.x,&p.y);
		line ab=line(a,b);
		line bc=line(b,c);
		line ac=line(a,c);

		if(pointIsOnLine(p,ab)) ;
		else if(pointIsOnLine(p,bc)) swap(a,c);
		else if(pointIsOnLine(p,ac)) swap(b,c);

		else {
			printf("-1\n");
			continue;
		}
		





//--------------------------------------------------------------
		if(fabs(p.x-a.x)<eps && fabs(p.y-a.y)<eps) {
			point o=getMid(b,c);
			printf("%.15f %.15f\n",o.x,o.y);
			continue;
		}else if(fabs(p.x-b.x)<eps && fabs(p.y-b.y) < eps){
			point o=getMid(a,c);
			printf("%.15f %.15f\n",o.x,o.y);
			continue;
		}
		else if(fabs(p.x-c.x)<eps && fabs(p.y-c.y) <eps) {
			point o=getMid(a,b);
			printf("%.15f %.15f\n",o.x,o.y);
			continue;
		}


		point o=getMid(b,c);
		if(fabs(o.x-p.x)<eps && fabs(o.y-p.y)<eps) {
			printf("%.15f %.15f\n",a.x,a.y);
			continue;
		}

		o=getMid(a,b);

		if(fabs(o.x-p.x)<eps && fabs(o.y-p.y) < eps){
			printf("%.15f %.15f\n",c.x,c.y);
			continue;
		}

		o=getMid(a,c);
		if(fabs(o.x-p.x)<eps && fabs(o.y-p.y) <eps){
			printf("%.15f %.15f\n",b.x,b.y);
			continue;
		}


//--------------------------------------------------------------


		double area1=getArea(a,p,c);
		double area2=getArea(b,p,c);

		if(fabs(area1-area2)<eps) {
			printf("%.15f %.15f\n",c);
		}else if(area1<area2)  swap(a,b);

		double l=0,r=1;
		double area=getArea(a,b,c)*0.5;

		int cnt=1000;

		while(cnt--){
			double m=(l+r)*0.5;
			point pos;
			pos.x=a.x+(c.x-a.x)*m;
			pos.y=a.y+(c.y-a.y)*m;
			double tmp=getArea(pos,a,p);
			
			if(tmp<area) l=m;
			else r=m;
		}

		double delta=l;

		point ans;
		ans.x=a.x+(c.x-a.x)*delta;
		ans.y=a.y+(c.y-a.y)*delta;
		printf("%.15f %.15f\n",ans.x,ans.y);
	}
	return 0;

}

D. Digital Path

记忆化搜索,本质上是一个有向无环图,这就很适合使用dp来解决这个问题.

一个可能的坑点是 -2 -1 0 1 2 这种链也是符合条件的.

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int maxv=1e3+10;
int a[maxv][maxv];
ll dp[maxv][maxv][6];
bool vis[maxv][maxv];
int n,m;

bool in(int x,int y){
	if(x>=1&&x<=n&&y>=1&&y<=m) return true;
	return false;
}

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
const ll mod=1e9+7;

void foo(int x,int y){
	if(vis[x][y]) return;
	//cout<<x<<" "<<y<<endl;
	bool flag=0;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		/*
		   cout<<"tx "<<tx<<" ty "<<ty<<endl;
		   cout<<in(tx,ty)<<endl;
		   */
		if(in(tx,ty)){
			if(a[x][y]==a[tx][ty]+1) {
				foo(tx,ty);
				for(int i=1;i<=3;i++){
					dp[x][y][i+1]+=dp[tx][ty][i];
					dp[x][y][i+1]%=mod;
				}
				dp[x][y][4]+=dp[tx][ty][4];
				dp[x][y][4]%=mod;
			}
		}
	}
	vis[x][y]=true;
	return ;
}

int main(){
	while(~scanf("%d%d",&n,&m)){
		inc(i,1,n) inc(j,1,m) {
			scanf("%d",&a[i][j]);
			dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=dp[i][j][3]=dp[i][j][4]=0;
			vis[i][j]=0;
		}
		inc(i,1,n) inc(j,1,m) {
			int o=0;
			inc(k,0,3){
				int x=i,y=j,tx=dx[k]+i,ty=dy[k]+j;
				if(in(tx,ty)){
					if(a[tx][ty]+1==a[x][y]) o++;
				}
			}
			if(o==0) dp[i][j][1]=1,vis[i][j]=1;
		}
		inc(i,1,n) inc(j,1,m) foo(i,j);
		/*
		inc(i,1,n){
			inc(j,1,m) printf("%4d",dp[i][j][3]);
			putchar('\n');
		}
		inc(i,1,n) {
			inc(j,1,m) printf("%4d",dp[i][j][4]);
			putchar('\n');
		}
		*/

		ll res=0;

		inc(i,1,n) {
			inc(j,1,m){
				int chu=0;
				int x=i,y=j;

				for(int k=0;k<=3;k++){
					int tx=x+dx[k];
					int ty=y+dy[k];
					if(a[tx][ty]==a[x][y]+1) chu++;
				}
				if(chu==0) res=(res+dp[x][y][4])%mod;
			}
		}
		printf("%lld\n",res);
	}return 0;

}

J. Spy

感觉是很巧妙的,略微有点题意杀.

利用了二分图最大权匹配的模型,KM算法各种资料上都是 $n^4$的,或者有的模板号称是$n^3$,但是其实很慢.

如果现场赛没有合适的模板就会gg,还是平时注重积累吧.

https://blog.csdn.net/qq_43497140/article/details/103337606

这个代码的 KM算法部分 是网上找的,有时间自己研究一下KM算法具体的原理,暂时把这个代码加入模板吧.

通过代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=400+10;
ll a[maxv],p[maxv],b[maxv],c[maxv];

const int N=maxv;

int n;
int nx,ny;

#define g w

int g[N][N];
int linker[N];
ll lx[N],ly[N];
ll slack[N];
bool visx[N],visy[N];

ll pre[N];




void bfs( ll k ){
    ll x , y = 0 , yy = 0 , delta;
    memset( pre , 0 , sizeof(pre) );
    for( ll i = 1 ; i <= n ; i++ ) slack[i] = LONG_MAX;
    linker[y] = k;
    while(1){
        x = linker[y]; delta = LONG_MAX; visy[y] = true;
        for( ll i = 1 ; i <= n ;i++ ){
            if( !visy[i] ){
                if( slack[i] > lx[x] + ly[i] - w[x][i] ){
                    slack[i] = lx[x] + ly[i] - w[x][i];
                    pre[i] = y;
                }
                if( slack[i] < delta ) delta = slack[i] , yy = i ;
            }
        }
        for( ll i = 0 ; i <= n ; i++ ){
            if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
            else slack[i] -= delta;
        }
        y = yy ;
        if( linker[y] == -1 ) break;
    }
    while( y ) linker[y] = linker[pre[y]] , y = pre[y];
}

 
ll KM(){
    memset( lx , 0 ,sizeof(lx) );
    memset( ly , 0 ,sizeof(ly) );
    memset( linker , -1, sizeof(linker) );
    for( ll i = 1 ; i <= n ; i++ ){
        memset( visy , false , sizeof(visy) );
        bfs(i);
    }
    ll res = 0 ;
        for( ll i = 1 ; i <= n ; i++ ){
            if( linker[i] != -1 ){
                res += w[linker[i]][i] ;
            }
        }
        return res;
}
 

/*
bool DFS(int x){
	visx[x] = true;
	for(int y = 0; y < ny; y++){
		if(visy[y])continue;
		ll tmp = lx[x] + ly[y]-g[x][y];
		if(tmp == 0){
			visy[y] = true;
			if(linker[y] == -1 || DFS(linker[y])){
				linker[y] = x;
				return true;
			}
		}
		else if(slack[y] > tmp)
			slack[y] = tmp;
	}
	return false;
}

ll  KM(){
	memset(linker,-1,sizeof(linker));
	memset(ly,0,sizeof(ly));
	for(int i = 0;i < nx;i++){
		lx[i] = LONG_MIN;
		for(int j = 0;j < ny;j++)
			if(g[i][j] > lx[i])
				lx[i] = g[i][j];
	}
	for(int x = 0;x < nx;x++){
		for(int i = 0;i < ny;i++)
			slack[i] = LONG_MAX;
		while(true){
			memset(visx,false,sizeof(visx));
			memset(visy,false,sizeof(visy));
			if(DFS(x))break;
			ll  d = LONG_MAX;
			for(int i = 0;i < ny;i++)
				if(!visy[i] && d > slack[i])
					d = slack[i];
			for(int i = 0;i < nx;i++)
				if(visx[i])
					lx[i]-= d;
			for(int i = 0;i < ny;i++){
				if(visy[i])ly[i] += d;
				else slack[i]-= d;
			}
		}
	}
	ll res = 0;
	for(int i = 0;i < ny;i++)
		if(linker[i] != -1)
			res += g[linker[i]][i];
	return res;
}

*/
void getw(){
	inc(i,1,n) scanf("%lld",a+i);
	inc(i,1,n) scanf("%lld",p+i);
	inc(i,1,n) scanf("%lld",b+i);
	inc(i,1,n) scanf("%lld",c+i);

	inc(i,1,n) inc(j,1,n) {
		w[i][j]=0;
		ll v=b[i]+c[j];
		inc(k,1,n) if(v>a[k]) w[i][j]+=p[k];
	}
}

bool show=false;

int main(){


	while(~scanf("%d",&n)){
		getw();
		nx=ny=n;
		if(show)
			inc(i,1,n) {
				inc(j,1,n) printf("%4lld",w[i][j]);
				putchar('\n');
			}

		printf("%lld\n",KM());

	}return 0;
}

B. chessboard

lucas定理在这个题目中作为了STL一样的工具性存在.

这个题目真的是太太太太难读了!!!

我说一个我认为是正确的理解: 要保证在涂格子的任何时刻,已经涂的格子中任何两个在已涂格子上的距离等于曼哈顿距离.

另外一个困难就是要得到得到最后结果的公式,感觉挺需要数学直觉的.

可能需要场上自己想一些小样例之后大力猜结论.

通过代码

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int N=2e6+10;
const ll mod=1e9+7;

ll a[N];

void init(){ a[0]=1; inc(i,1,2000000) a[i]=a[i-1]*i%mod; }
ll ksm(ll a,ll n,ll p){
	ll res=1;
	while(n){
		if(n&1) res=res*a%p;
		a=a*a%p;
		n>>=1;
	}return res;
}

ll c(ll n,ll m,ll p){
	if(n<m) return 0;
	return a[n]*ksm(a[m],p-2,p)%p*ksm(a[n-m],p-2,p)%p;
}
int main(){
	init();int T=read();while(T--){
		ll n,m;scanf("%lld%lld",&n,&m);
		if(n==1&&m==1) printf("1\n");
		else if(n==1 || 1==m) printf("2\n");
		else printf("%lld\n",4LL*c(n+m-2,n-1,mod)%mod);
	}return 0;
}

and More

https://www.cnblogs.com/bringlu/p/12285181.html

https://blog.csdn.net/qq_18125607/article/details/103351401