Hello 2020 题解 · 徐皓天

Hello 2020

New Year and Naming

模拟。

const int N = 23;
int n, m;
string s[N], t[N];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i];
	for (int i = 0; i < m; i++) cin >> t[i];
	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		--x;
		cout << s[x%n] << t[x%m] << endl;
	}
	return 0;
}

New Year and Ascent Sequence

组合计数，前缀和。

const int N = 1e5 + 7, M = 1e6 + 7;
int n, c[M], d[M], cnt;
vi e[N];
bool ok[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		int m;
		rd(m);
		while (m--) {
			int x;
			rd(x);
			e[i].pb(x);
		}
		for (ui j = 1; j < e[i].size(); j++)
			if (e[i][j-1] < e[i][j]) ok[i] = 1;
	}
	for (int i = 1; i <= n; i++)
		if (ok[i]) ++cnt;
		else {
			c[e[i][0]]++, d[e[i].back()]++;
		}
	for (int i = M - 2; ~i; i--) c[i] += c[i+1];
	ll ans = 1ll * n * n - 1ll * (n - cnt) * (n - cnt);
	for (int i = 0; i < M - 1; i++) {
		ans += 1ll * d[i] * c[i+1];
	}
	print(ans);
	return 0;
}

New Year and Permutation

组合计数。

const int N = 2.5e5 + 7;
int n;
modint p[N], ans;

int main() {
	rd(n), rd(P);
	p[0] = 1;
	for (int i = 1; i <= n; i++) p[i] = p[i-1] * i;
	for (int i = 1; i <= n; i++) ans += p[i] * p[n+1-i] * i;
	print(ans);
	return 0;
}

New Year and Conference

以某一维为时间轴，我们需要判定在这一维上有交的在另一维上是否有交。

那么扫过这一维的所有时间点，用 multiset 实时维护包含这个时间点的所有区间即可。

总时间复杂度 $\mathcal O(n \log n)$ 。

const int N = 1e5 + 7;
int n, m, sa[N], ea[N], sb[N], eb[N], a[N*4];
vi l[N*4], r[N*4];

inline bool solve() {
	for (int i = 1; i <= m; ++i) l[i].clear(), r[i].clear();
	for (int i = 1; i <= n; ++i) l[sa[i]].pb(i), r[ea[i]].pb(i);
	multiset <int, greater <int> > lmax;
	multiset <int> rmin;
	for (int i = 1; i <= m; ++i) {
		for (int id : l[i]) lmax.insert(sb[id]), rmin.insert(eb[id]);
		if (lmax.size() && *lmax.begin() > *rmin.begin()) return 1;
		for (int id : r[i]) lmax.erase(lmax.find(sb[id])), rmin.erase(rmin.find(eb[id]));
	}
	return 0;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(sa[i]), rd(ea[i]), rd(sb[i]), rd(eb[i]);
	copy(sa + 1, sa + n + 1, a + 1);
	copy(ea + 1, ea + n + 1, a + n + 1);
	copy(sb + 1, sb + n + 1, a + n * 2 + 1);
	copy(eb + 1, eb + n + 1, a + n * 3 + 1);
	sort(a + 1, a + n * 4 + 1);
	m = unique(a + 1, a + n * 4 + 1) - a - 1;
	for (int i = 1; i <= n; ++i)
		sa[i] = lower_bound(a + 1, a + m + 1, sa[i]) - a,
		ea[i] = lower_bound(a + 1, a + m + 1, ea[i]) - a,
		sb[i] = lower_bound(a + 1, a + m + 1, sb[i]) - a,
		eb[i] = lower_bound(a + 1, a + m + 1, eb[i]) - a;
	bool ans = solve();
	swap(sa, sb), swap(ea, eb);
	puts((ans | solve()) ? "NO" : "YES");
	return 0;
}

New Year and Castle Construction

以每个点为原点做一次 P2992 [USACO10OPEN]三角形计数Triangle Counting，最后将答案 $\times \frac {n - 4}2$ 即可。

const int N = 2.5e3 + 7;
int n;
P a[N];

inline int f(P o) {
	int x = o.x, y = o.y;
	if (x <= 0 && y < 0) return 0;
	if (x > 0 && y <= 0) return 1;
	if (x >= 0 && y > 0) return 2;
	return 3;
}

inline bool cmpa(P x, P y) { return f(x) == f(y) ? x % y > 0 : f(x) < f(y); }

inline ll solve(int o) {
	if (n <= 3) return 0;
	ll ans = 1ll * (n - 1) * (n - 2) * (n - 3) / 6;
	vector <P> p;
	for (int i = 1; i <= n; i++)
		if (i != o) p.pb(a[i] - a[o]);
	sort(p.begin(), p.end(), cmpa);
	int w = p.size();
	for (int i = 0; i < w; i++) p.pb(p[i]);
	for (int i = 0, j = 1; i < w; i++) {
		if (j == i) j = i + 1;
		while (j < 2 * w && j != i + w && p[i] % p[j] > 0) ++j;
		int w = j - i - 1;
		ans -= 1ll * w * (w - 1) / 2;
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lf %lf", &a[i].x, &a[i].y);
	ll ans = 0;
	for (int i = 1; i <= n; i++) ans += solve(i);
	print(ans * (n - 4) / 2);
	return 0;
}

New Year and Social Network

题目太神仙了，先咕咕咕着。

Seollal