2020杭电多校（第七场）

比赛链接

收获

• 互质的数对分布的很稠密
• 递归思想可以用在构造题中

---

1007 Game

我们倒着考虑，先手要赢，最长的那条边必须由先手走（或者走不到），于是乎次长的边必须由先手走（或者走不到），于是乎第三长的边……因此，如果第 $1$ 个点和其他某个点进行了匹配，则先手胜；否则先手负。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 2005;

int T, n, sid;
LL x[N], y[N];
struct Segment{
	LL x, y, dis;
	bool operator < (const Segment &A) const{
		return dis > A.dis;
	}
}s[N*N];

inline LL dis2(int a, int b){
	return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(x[i], y[i]);
		sid = 0;
		vector<int> vis(n+5, 0);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j < i; j++)
				s[++sid] = (Segment){j, i, dis2(i, j)};
		sort(s+1, s+sid+1);
		for(int i = 1, bl = 1, sum = 0; sum <= n - 2; i++, bl++){
			while(i <= sid && (vis[s[i].x] || vis[s[i].y]))	i++;
			if(i == sid + 1)	break;
			for(int k = i; k <= sid; k++){
				if(s[k].dis != s[i].dis){ i = k; break; }
				if (vis[s[k].x] == 0 && vis[s[k].y] == 0)
					vis[s[k].x] = bl, vis[s[k].y] = bl, sum += 2;
				else if (vis[s[k].x] == 0 && vis[s[k].y] == bl)
					vis[s[k].y] = bl, ++sum;
				else if(vis[s[k].y] == 0 && vis[s[k].x] == bl)
					vis[s[k].y] = bl, ++sum;
			}
		}
		bool ok = false;
		for(int i = 2; i <= n; i++){
			if(vis[i] == vis[1]){
				ok = true;
				break;
			}
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

---

1009 Increasing and Decreasing

对于 $\{1,2,\cdots,n\}$，要得到长度为 $y$ 的最长下降子序列，将后 $y$ 个数翻转；现在要得到长度为 $x$ 的最长上升子序列，只需要把前 $n-y$ 个数分割成 $x-1$ 段，每一段长度 $\leqslant y$，每一段分别翻转。为了保证字典序最小，尽可能使靠前的段长度小。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n, x, y, ans[N];

bool solve(int pos, int k){
	if(pos < k)	return false;
	if(pos > 1ll * k * y)	return false;
	if(pos == k)	return true;
	if(k == 1){
		reverse(ans + 1, ans + pos + 1);
		return true;
	}
	int len = min(y, pos - k + 1);
	reverse(ans + pos - len + 1, ans + pos + 1);
	return solve(pos - len, k - 1);
}

int main(){
	for(read(T); T; T--){
		read(n, x, y);
		for(int i = 1; i <= n; i++)	ans[i] = i;
		reverse(ans + n - y + 1, ans + n + 1);
		int now = n-y;
		if(solve(now, x - 1)){
			puts("YES");
			for(int i = 1; i <= n; i++)	printf("%d%c", ans[i], " \n"[i==n]);
		}
		else	puts("NO");
	}
	return 0;
}

---

1010 Jogging

打个表可以发现，互质的数对分布的很稠密，只要从 $(x,y)$ 出发不走到对角线 $(i,i)$，走到的点就是有穷且较少的。

答案就是起点的度数除以能走到的点的度数和（这里说的“度数”指的是能到达的点的数量，包括自己）

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 998244353;
const int N = 105;

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

inline int z(LL x, LL y){
	int res = 0;
	for(int i = -1; i <= 1; i++)
		for(int j = -1; j <= 1; j++)
			if(!(i == 0 && j == 0))
				res += (gcd(x+i, y+j) > 1);
	return res;
}

bool inf;
int sum = 0;
map<pair<LL, LL>, bool> vis;
void dfs(LL x, LL y){
	if(inf)	return;
	if(x == y){ inf = true; return; }
	vis[mp(x,y)] = true;
	sum += 1 + z(x,y);
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
			if(i == 0 && j == 0)	continue;
			if(gcd(x+i,y+j) <= 1)	continue;
			if(!vis[mp(x+i,y+j)])	dfs(x+i,y+j);
		}
	}
}

int main(){
	int T; for(read(T); T; T--){
		LL x, y; read(x, y);
		inf = false;
		sum = 0;
		vis.clear();
		dfs(x, y);
		if(inf)	puts("0/1");
		else{
			int up = 1 + z(x,y);
			int g = gcd(up, sum);
			sum /= g; up /= g;
			printf("%d/%d\n", up, sum);
		}
	}
	return 0;
}