Codeforces Round #698 (Div.1)

比赛链接 / 官方题解链接

A. Nezzar and Board

Solution

手玩一下可以发现，对于两个数 $x,y$，我们能生成所有形如 $(n+1)x-ny=n(x-y)+x$ 的数字，其中 $n\in \mathbb N_+$. 于是乎，取 $x=x_1$，遍历 $y\in\{x_2,\ldots,x_n\}$，我们就有了 $n-1$ 个包含 $x_1$ 的等差数列，它们能遍历到的数一定构成一个等差数列，且它的公差为各个等差数列公差的 $\gcd$.

Code

#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)

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

const int N = 200005;

LL n, k, x[N];

int main(){
	int T; for(read(T); T; T--){
		read(n, k);
		for(int i = 1; i <= n; i++)	read(x[i]);
		sort(x+1, x+n+1);
		LL g = x[2] - x[1];
		for(int i = 3; i <= n; i++)
			g = gcd(g, x[i] - x[1]);
		if(abs(k - x[1]) % g)	puts("NO");
		else	puts("YES");
	}
	return 0;
}

---

B. Nezzar and Binary String

Solution

从 $f$ 向 $s$ 反向思考，对于最后一步，在将串更改为 $f$ 之前，$[l[q],r[q]]$ 一定全为 $0$ 或全为 $1$，由于只能更改不超过一半的字符，所以如果 $f$ 中 $1$ 更多，那么之前一定全为 $1$，如果 $0$ 更多，之前一定全为 $0$；这样我们就唯一确定了最后一次操作前的字符串，以此往前推即可。

Code

#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 = 200005;

int n, q, T, l[N], r[N];
string s, f;

struct segTree{
	int l, r, cov, cnt;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
	tr[id].cnt = tr[lid].cnt + tr[rid].cnt;
}
inline void pushdown(int id){
	if(tr[id].l == tr[id].r)	return;
	if(tr[id].cov != -1){
		tr[lid].cov = tr[id].cov;
		tr[lid].cnt = len(lid) * tr[lid].cov;
		tr[rid].cov = tr[id].cov;
		tr[rid].cnt = len(rid) * tr[rid].cov;
		tr[id].cov = -1;
	}
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].cov = -1, tr[id].cnt = 0;
	if(tr[id].l == tr[id].r){
		tr[id].cnt = (f[tr[id].l-1] == '1');
		return;
	}
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void cover(int id, int l, int r, int val){
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r){
		tr[id].cov = val;
		tr[id].cnt = len(id) * val;
		return;
	}
	if(r <= mid)	cover(lid, l, r, val);
	else if(l > mid)	cover(rid, l, r, val);
	else	cover(lid, l, mid, val), cover(rid, mid+1, r, val);
	pushup(id);
}
int query(int id, int l, int r){
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r)	return tr[id].cnt;
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else	return query(lid, l, mid) + query(rid, mid+1, r);
}

string t;
void getStr(int id){
	pushdown(id);
	if(tr[id].l == tr[id].r){
		t += (tr[id].cnt == 1) + '0';
		return;
	}
	getStr(lid), getStr(rid);
}

int main(){
	for(read(T); T; T--){
		read(n, q);
		cin >> s >> f;
		build(1, 1, n);
		for(int i = 1; i <= q; i++)	read(l[i], r[i]);
		bool ok = true;
		for(int i = q; i >= 1; i--){
			int num = query(1, l[i], r[i]);
			if(num * 2 == r[i] - l[i] + 1){ ok = false; break; }
			cover(1, l[i], r[i], num * 2 > r[i] - l[i] + 1);
		}
		t.clear();
		getStr(1);
		ok &= (t == s);
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

---

C. Nezzar and Nice Beatmap

Solution

任取一个点作为起点，只需不断取距离当前点最远的还没取过的点即可。

证明可行性：假设当前点为 $b$，上一个点为 $a$，距离 $b$ 最远的还没取过的点是 $c$，倘若 $a\to b\to c$ 是直角或钝角，则 $a\to c$ 的距离比 $a\to b$ 更远，那么上一步就不应取 $b$. 证毕。

Code

#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 = 5005;

int n;
bool b[N];
struct Node{
	LL x, y;
}a[N];

LL dis(int i, int j){
	return (a[i].x - a[j].x) * (a[i].x - a[j].x)
	 + (a[i].y - a[j].y) * (a[i].y - a[j].y);
}

int main(){
	read(n);
	for(int i = 1; i <= n; i++)	read(a[i].x, a[i].y);
	printf("%d ", 1);
	b[1] = true;
	int p = 1;
	for(int i = 2; i <= n; i++){
		int k = -1; LL mxd = 0;
		for(int j = 1; j <= n; j++){
			if(b[j])	continue;
			if(mxd < dis(p, j)){
				mxd = dis(p, j);
				k = j;
			}
		}
		printf("%d ", k);
		b[k] = true, p = k;
	}
	return 0;
}