5.19 省选模拟赛 T1 小B的棋盘双指针性质

LINK：小B的棋盘

考试的时候没有认真的思考导致没做出来.

容易发现当k>=n的时候存在无限解其余都存在有限解

对于30分容易想到暴力枚举对称中心然后 n^2判断.

对于前者容易发现对称中心为某个点或某两个点的中点对于后者可以发现排序过后双指针可以做。

双指针做的时候还是存在一些小细节的(爆零警告两种属性不可以随便判断就跳指针得根据自己排序的顺序来判断是否跳指针.

拿到30之后还是考虑对称中心的问题.

对于一些点对的中点或者一些点当对称中心显然是不合法的如以某个点为对称中心的时候的四个象限画出来然后很容易发现端倪。

且最后最多只有k个点可以不匹配且匹配的时候的点对也有相对顺序的关系.

如左下方的点一定是和右上方的点尽可能匹配的类似等等...

特殊的考虑最靠下且尽可能靠左的k+1个点一定和相对的最靠上且尽可能靠右的k+1个点之间存在匹配关系。

如果没有一对存在那么显然不存在合法解存在的话我们直接进行判定这样就把刚才n^2的点集变成了 k^2的点集。

带上双指针就是nk^2的了.

由此推测这道题的60分做法是希望我们写一个hash来判断重复而不是sort 这样做的话点集被缩小为k^2.

值得一提的是这样还是存在一个比较常见的check 虽然两点的中点坐标公式需要/2 但是可以都乘以2 来更好的避免小数误差.

const int MAXN=100010,G=3;

int n,k,cnt,ans;

struct wy{int x,y;}t[MAXN],w[MAXN];

inline int cmp(wy a,wy b){return a.y==b.y?a.x<b.x:a.y<b.y;}

inline int pd(wy a,wy b){return a.x==b.x&&a.y==b.y;}

inline int calc(int x,int y)

{

	int l=1,r=n,cnt=0;

	while(l<=r)

	{

		if(l==r)

		{

			if(t[l].x*2!=x||t[r].y*2!=y)++cnt;

			break;

		}

		if(t[l].x+t[r].x==x&&t[r].y+t[l].y==y)++l,--r;

		else

		{

			++cnt;

			if(t[r].y>y-t[l].y)--r;

			else

			{

				if(t[r].y==y-t[l].y)

				{

					if(t[r].x>x-t[l].x)--r;

					else ++l;

				}

				else ++l;

			}

		}

	}

	return cnt<=k;

}

int main()

{

	freopen("1.in","r",stdin);

	//freopen("a.out","w",stdout);

	get(n);get(k);

	if(k>=n){puts("-1");return 0;}

	rep(1,n,i)

	{

		int get(x),get(y);

		t[i]=(wy){x,y};

	}

	sort(t+1,t+1+n,cmp);

	rep(1,k+1,i)rep(n-k,n,j)w[++cnt]=(wy){t[i].x+t[j].x,t[i].y+t[j].y};

	sort(w+1,w+1+cnt,cmp);

	rep(1,cnt,i)

	{

		if(i!=1&&pd(w[i],w[i-1]))continue;

		ans+=calc(w[i].x,w[i].y);

	}

	put(ans);

	return 0;

}

巴特西

5.19 省选模拟赛 T1 小B的棋盘双指针性质

最新文章

热门文章

巴特西

5.19 省选模拟赛 T1 小B的棋盘 双指针 性质

最新文章

热门文章

5.19 省选模拟赛 T1 小B的棋盘双指针性质