一句话题解系列(二):NEERC 2017

一句话解答 NEERC 2017 比赛的所有问题

参考资料

NEERC 是北欧的 ACM 区域赛决赛。由于俄罗斯的存在,这个赛区的题目往往质量和难度都很高。

比赛相关资料的下载地址:http://neerc.ifmo.ru/archive/2017.html

A. Archery Tournament

平面圆覆盖+单点查询。首先可以用矩形覆盖来代替圆覆盖,虽然这样会导致一些地方被重复覆盖,但显然重复覆盖的次数是 以内的。又因为所有圆都在水平面上,又可以进一步用线段覆盖来代替矩形覆盖,转化为线段树区间更新、单点查询的问题,其中线段树的节点是 set。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
const int maxn = 1<<19;
struct st{
	set<int> s[maxn<<1];
	void update(const int l, const int r, const int val, int L=1, int R=maxn, int x=1){
		if(l>=L && r<=R){
			s[x].insert(val);
			return;
		}
		int mid = L+R>>1;
		if(mid >= l){
			update(l, r, val, L, mid, x<<1); 
		}
		if(mid < r){
			update(l, r, val, mid+1, R, x<<1|1);
		}
	}
	void update2(const int l, const int r, const int val, int L=1, int R=maxn, int x=1){
		if(l<=L && r>=R){
			s[x].erase(val);
			return;
		}
		int mid = L+R>>1;
		if(mid >= l){
			update2(l, r, val, L, mid, x<<1);
		}
		if(mid < r){
			update2(l, r, val, mid+1, R, x<<1|1);
		}
	}
	int query(int x, function<bool(int)> test){
		int ans = -1;
		x+=maxn;
		for(int i=20; i>=0; i--){
			int now = x>>i; 
			if(!now)continue;
			for(auto j:s[now]){
				if((!~ans || ans>j) && test(j)){
					ans=j;
				}
			}
		}
		return ans;
	}
} s;
int main(int argc, char* argv[]){
	int N=read();
	vector<int> t(N+1), x(N+1), y(N+1), dx(N+1), ex(N+1);
	vector<int> Xs;
	for(int i=1; i<=N; i++){
		t[i]=read(), x[i]=read(), y[i]=read();
		if(t[i]==1){
			Xs.push_back(x[i]-y[i]), Xs.push_back(x[i]+y[i]);
		}
		else{
			Xs.push_back(x[i]);
		}
	}
	sort(Xs.begin(), Xs.end());
	for(int i=1; i<=N; i++){
		if(t[i]==1){
			dx[i]=lower_bound(Xs.begin(), Xs.end(), x[i]-y[i])-Xs.begin();
			ex[i]=lower_bound(Xs.begin(), Xs.end(), x[i]+y[i])-Xs.begin();
		}
		else{
			dx[i]=lower_bound(Xs.begin(), Xs.end(), x[i])-Xs.begin();
		}
	}
	for(int i=1; i<=N; i++){
		if(t[i]==1){
			if(dx[i]+1<ex[i]){
				s.update(dx[i]+2, ex[i], i);
			}
		}
		else{
			int res = s.query(dx[i], [&](int j){
				return 1.0*(x[j]-x[i])*(x[j]-x[i]) + 1.0*(y[j]-y[i])*(y[j]-y[i]) < 1.0*y[j]*y[j] - 1e-6;
			});
			printf("%d\n", res);
			if(res > 0){
				s.update2(dx[res]+2, ex[res], res);
			}
		}
	}
	return 0;
}

B. Box

签到题。正方体的展开图有 11 种,出题人很好心地帮你画在 Statement 里了,枚举 (a, b, c, w, h) 的所有组合,判断一下即可。

代码略。

 

C. Connections

题目中 2*n 条边的限制略有迷惑性。有向图 n 个点强联通至少需要 n 条边,至多需要 2*(n-1) 条边,方法是任选一点求出生成树 (n-1 条边) 和反向图的生成树 (n-1 条边) 即可。这里用到一个结论:反向图的强连通分量一定与原图相同。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	int T=read();
	while(T--){
		int N=read(), M=read();
		vector<vector<int>> edge(N), edge2(N);
		map<pii, int> Mp;
		for(int i=0; i<M; i++){
			int a=read()-1, b=read()-1;
			Mp[make_pair(a, b)]=i;
			edge[a].push_back(b);
			edge2[b].push_back(a);
		}
		queue<int> Q;
		vector<bool> vis(N, 0);
		vis[0]=1;
		Q.push(0);
		while(!Q.empty()){
			int t = Q.front();
			Q.pop();
			for(int u:edge[t])if(!vis[u]){
				Q.push(u);
				vis[u]=1;
				Mp.erase({t, u});
			}
		}
		vis.swap(*new vector<bool>(N, 0));
		vis[0]=1;
		Q.push(0);
		while(!Q.empty()){
			int t = Q.front();
			Q.pop();
			for(int u:edge2[t])if(!vis[u]){
				Q.push(u);
				vis[u]=1;
				Mp.erase({u, t});
			}
		}
		auto it=Mp.begin();
		for(int i=0; i<M-2*N; i++, it++){
			printf("%d %d\n", it->first.first + 1, 1 + it->first.second);
		}
	}
	return 0;
}

 

D. Designing the Toy

需要一点空间想象力。不妨设 a<b<c ,那么把所有块都尽量放在 a, b 的那个平面,这样能让 c 放的最多,极限是 。从这个角度出发构造一下结果即可。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	int a=read(), b=read(), c=read();
	bool s1=0, s2=0, s3=0;
	if(a>b)swap(a, b), s1=true;
	if(b>c)swap(b, c), s2=true;
	if(a>b)swap(a, b), s3=true;
	if(c>a*b)return puts("-1"), 0;
	vector<tii> ans;
	for(int i=0; i<a; i++){
		ans.emplace_back(0, i, i);
	}
	for(int i=a; i<b; i++){
		ans.emplace_back(0, a-1, i);
	}
	int cnt = b;
	for(int i=0; i<a; i++){
		for(int j=0; j<b; j++){
			if(i!=j && !(i==a-1 && j>=a)){
				if(++cnt > c)goto out;
				ans.emplace_back(0, i, j);
			}
		}
	}
out:;
	printf("%d\n", ans.size());
	for(auto i:ans){
		int a, b, c;
		tie(a, b, c) = i;
		if(s3)swap(c, b);
		if(s2)swap(a, b);
		if(s1)swap(c, b);
		printf("%d %d %d\n", a, b, c);
	}
	return 0;
}

E. Easy Quest

开 map 记录一下所有遇到的 positive,以及有多少个 unicorn 可以分配;每遇到一个 negative 优先分配 positive ,不行就分配 unicorn,最后未分配的 unicorn 随意赋值即可。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	int N=read(), cnt=0;
	map<int, int> M;
	vector<int> ans;
	for(int i=1; i<=N; i++){
		int a=read();
		if(!a)cnt++;
		else if(a>0){
			M[a]++;
		}
		else if(a<0){
			a=-a;
			if(M[a])M[a]--;
			else if(cnt){
				ans.push_back(a);
				cnt--;
			}
			else return puts("No"), 0;
		}
	}
	puts("Yes");
	for(auto i:ans)printf("%d ", i);
	for(int i=1; i<=cnt; i++)printf("%d ", 1);
	return 0;
}

 

F. The Final Level

贪心,尽量直线距离接近 (a, b) 点,对最后一步做特判即可。题目如果改成不输出方案(见代码中 solve() 函数)可能更加优雅一些,输出方案则变成了纯 Casework,意义不大。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	auto solve = [&](int x, int y, int N){
		if(x<0)x=-x;
		if(y<0)y=-y;
		if(x>y)swap(x, y);
		if(1ll*(x+1)*N <= 1ll*(y+1)*(N-1)){
			return y/N+1;
		}
		return (x+y)/(2*N-1)+1;
	};
	auto solve2 = [&](int a, int b, int n){
		int ans1 = solve(a, b, n);
		bool s1 = 0, s2 = 0, s3 = 0;
		int sa = 0, sb = 0;
		vector<tuple<int, int, int, int>> ans;
		auto add = [&](int x1, int y1, int x2, int y2) {
			x1+=sa, x2+=sa, y1+=sb, y2+=sb;
			if(s1){
				x1=-x1;
				x2=-x2;
			}
			if(s2){
				y1=-y1;
				y2=-y2;
			}
			if(s3){
				swap(x1, y2);
				swap(x2, y1);
			}
			ans.push_back({x1, y1, x2, y2});
		};
		if(a<0) s1=true, a=-a;
		if(b<0) s2=true, b=-b;
		while(a > 0 || b > 0){
			if(a > b && a > n-1){
				s3=!s3;
				swap(a, b);
				swap(sa, sb);
			}
			if(a > n-1){
				add(n-1, n-1, 0, 0);
				b -= n, sb += n;
				a -= n-1, sa += n-1;
			}
			else{
				add(a, n-1, a-n+1, 0);
				b -= n, sb += n;
				sa += a;
				a = 0;
			}
		}
		if(!a && !b){
			add(n-1, n-1, 0, 0);
		}
		printf("%d\n", ans1);
		for(auto x:ans){
			int a, b, c, d;
			tie(a, b, c, d) = x;
			printf("%d %d %d %d\n", a, b, c, d);
		}
	};
	int T=read();
	while(T--){
		int x=read(), y=read(), N=read();
		solve2(x, y, N);
	}
	return 0;
}

 

G. The Great Wall

二分答案,转化为求答案为 mid 以下的方案数。方案数利用前缀和暴力计数(分别枚举 x 和 y 区间的位置)是 的,考虑维护 y 区间移动时 x 区间的取值范围,可能要用到线段树/平衡树?,最终复杂度

思路比较容易,代码感觉很麻烦,运气不好可能要调一下午。等实习回来如果有兴趣再写。