JZTXT

1851 Round 888 (Div. 3)

发布时间 2023-08-02 09:39:16作者: 浣辰

Escalator Conversations

判断两人台阶是否为 \(k\) 的倍数且在 \((0, m)\) 内即可

#include <bits/stdc++.h>
using namespace std;
signed main() {
	int T;
	scanf("%d", &T);
	
	for (int n, m, k, H; T; --T) {
		scanf("%d%d%d%d", &n, &m, &k, &H);
		int ans = 0;
		
		for (int i = 1, x; i <= n; ++i) {
			scanf("%d", &x);
			int delta = abs(x - H);
			ans += delta && !(delta % k) && (delta / k < m);
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Parity Sort

判断排序后相同下标数字与原理奇偶性是否相同即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

int a[N], b[N];

int T, n;

inline bool check() {
	for (int i = 1; i <= n; ++i)
		if ((a[i] & 1) != (b[i] & 1))
			return false;
	
	return true;
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d", &n);
		
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
			b[i] = a[i];
		}
		
		sort(b + 1, b + 1 + n);
		puts(check() ? "YES" : "NO");
	}
	
	return 0;
}

Tiles Comeback

直接从 \(1\) 跳到 \(n\) ，判断是否满足条件即可，注意特判 \(1, n\) 颜色相同的情况

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

vector<int> pos1, posn;

int a[N];

int T, n, K;

inline bool solve() {
	if (a[1] == a[n])
		return pos1.size() >= K;
	else
		return pos1.size() >= K && posn.size() >= K && pos1[K - 1] < posn[posn.size() - K];
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		pos1.clear(), posn.clear();
		scanf("%d%d", &n, &K);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", a + i);
		
		for (int i = 1; i <= n; ++i) {
			if (a[i] == a[1])
				pos1.push_back(i);
			
			if (a[i] == a[n])
				posn.push_back(i);
		}
		
		puts(solve() ? "YES" : "NO");
	}
	
	return 0;
}

Prefix Permutation Sums

分类讨论空缺位置即可

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;

ll a[N];
int vis[N];

int T, n;

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		memset(vis, 0, sizeof(vis));
		scanf("%d", &n);
		bool flag = false;
		int pos = -1;
		
		for(int i = 1; i < n; ++i) {
			scanf("%lld", a + i);
			
			if(a[i] - a[i - 1] > n)
				flag |= ~pos, pos = i;
			else
				++vis[a[i] - a[i - 1]];
		}
		
		int sum = 0, num = 0;
		
		for(int i = 1; i <= n; ++i)
			if(!vis[i]) 
				sum += i, ++num;
			
		if(flag) 
			puts("NO");
		else if(num == 1) 
			puts("YES");
		else if(num > 2) 
			puts("NO");
		else if(~pos) 
			puts(a[pos] - a[pos - 1] == sum ? "YES" : "NO");
		else {
			for(int i = 1; i <= n; ++i)
				if(vis[i] > 1) {
					pos = i;
					break;
				}
			
			puts(pos == sum ? "YES" : "NO");
		}
	}
	
	return 0;
}

Nastya and Potions

对于第 \(i\) 类药剂，将其原材料向其连边

无法自己合成自己的条件实际上保证了这个图无环

拓扑排序即可

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;

vector<int> e[N];

ll c[N], ans[N];
int indeg[N];

int T, n, K;

inline void clear() {
	for (int i = 1; i <= n; ++i)
		e[i].clear(), ans[i] = indeg[i] = 0;
}

inline void AddEdge(int u, int v) {
	e[u].push_back(v);
}

inline void TopoSort() {
	queue<int> q;
	
	for (int i = 1; i <= n; ++i)
		if (!indeg[i])
			q.push(i);
	
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		ans[u] = min(ans[u], c[u]);
		
		for (int v : e[u]) {
			ans[v] += ans[u], --indeg[v];
			
			if (!indeg[v])
				q.push(v);
		}
	}
}

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &K);
		clear();
		
		for (int i = 1; i <= n; ++i)
			scanf("%lld", c + i);
		
		for (int i = 1, x; i <= K; ++i) {
			scanf("%d", &x);
			c[x] = 0;
		}
		
		for (int i = 1; i <= n; ++i) {
			scanf("%d", indeg + i);
			
			if (!indeg[i]) {
				ans[i] = c[i];
				continue;
			}
			
			for (int j = 1, u; j <= indeg[i]; ++j) {
				scanf("%d", &u);
				AddEdge(u, i);
			}
		}
	
		TopoSort();
		
		for (int i = 1; i <= n; ++i)
			printf("%lld ", ans[i]);
		
		puts("");
	}
	
	return 0;
}

Lisa and the Martians

假设已经有 \(u = a_i, v = a_j\) ，考虑计算最大的 \(x\) ，对于第 \(i\) 位当且仅当 \(u, v\) 这一位相同时，\(x\) 可以使得答案为 \(1\) ，否则必为 \(0\) 。那么答案即为 \((2^k - u) \oplus v - 1\) ，最大化这个值，即找到 \(\min a_i \oplus a_j\)

结论：将 \(a\) 排序后，对于 \(a_i\) ，当 \(j = i + 1\) 时，\(a_i \oplus a_j\) 取得最小值

证明：

考察 \(u \leq v \leq w\) ，只需证明 \(\min(u \oplus v, v \oplus w) \leq u \oplus w\) 即可

假设从高到低在 \(i\) 位开始不同，由于 \(u \leq v \leq w\) ，故第 \(i\) 位 \(u\) 为 \(0\) ，\(w\) 为 \(1\) ，从而

\[\begin{cases} u \oplus v < u \oplus w & v = 0 \\ v \oplus w < u \oplus w \end{cases} \]

构造即可

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;

pair<int, int> a[N];

int T, n, K;

signed main() {
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &K);
		
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i].first);
			a[i].second = i;
		}
		
		sort(a + 1, a + 1 + n);
		int pos = 1;
		
		for (int i = 2; i < n; ++i)
			if ((a[i].first ^ a[i + 1].first) < (a[pos].first ^ a[pos + 1].first))
				pos = i;
		
		int ans = 0;
		
		for (int i = 0; i < K; ++i)
			if (!((a[pos].first >> i) & 1) && !((a[pos + 1].first >> i) & 1))
				ans += 1 << i;
		
		printf("%d %d %d\n", a[pos].second, a[pos + 1].second, ans);
	}
	
	return 0;
}

Vlad and the Mountains

注意到无论中间过程如何， \(i \to j\) 所需能量必为 \(h_j - h_i\) ，因此路径能量最低点去在路径中 \(h\) 的最大点，从而按照 \(max(h_u, h_v)\) 的顺序加入边 \(u, v\) ，建立 Kruskal 重构树即可

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7, LOGN = 23;

vector<int> e[N];
pair<int, int> h[N];

int id[N], LOG[N];

int T, n, m, q;

namespace DSU {
	int fa[N];
	
	inline void clear(int n) {
	    for (int i = 1; i <= n; ++i)
	        fa[i] = i;
	}
	
	inline int find(int x) {
	    while (x != fa[x])
	        fa[x] = fa[fa[x]], x = fa[x];
	
	    return x;
	}
	
	inline void merge(int x, int y) {
	    fa[find(y)] = find(x);
	}
} // namespace DSU

inline void AddEdge(int u, int v) {
	e[u].push_back(v);
}

namespace Ktree {
	vector<int> e[N];
	
	int fa[N][LOGN];
	int dep[N];
	
	inline void AddEdge(int u, int v) {
		e[u].push_back(v);
	}
	
	void dfs(int u, int f) {
		fa[u][0] = f, dep[u] = dep[f] + 1;
		
		for (int i = 1; i < LOGN; ++i)
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		
		for (int v : e[u])
			dfs(v, u);
	}
	
	inline int LCA(int x, int y) {
	    if (dep[x] < dep[y])
	    	swap(x, y);
	        
	    for (int i = 0, h = dep[x] - dep[y]; h; ++i, h >>= 1)
	    	if (h & 1)
	    		x = fa[x][i];
	
	    if (x == y)
	        return x;
	
	    for (int i = LOG[dep[x]]; ~i; --i)
	        if (fa[x][i] != fa[y][i])
	            x = fa[x][i], y = fa[y][i];
	
	    return fa[x][0];
	}
}

inline void Kruskal() {
	DSU::clear(n << 1);
	int cnt = n;
	
	for (int x = 1; x <= n; ++x)
		for (int y : e[x]) {
			int fx = DSU::find(x), fy = DSU::find(y);
			
			if (fx == fy)
				continue;
			
			++cnt;
			Ktree::AddEdge(cnt, fx);
			Ktree::AddEdge(cnt, fy);
			DSU::fa[fx] = DSU::fa[fy] = cnt;
			id[cnt] = id[x], h[cnt] = h[x];
		}
}

inline void init() {
	LOG[0] = -1;
	
	for (int i = 1; i < N; ++i)
		LOG[i] = LOG[i >> 1] + 1;
}

inline void clear(int n) {
	for (int i = 1; i <= n; ++i)
		e[i].clear(), Ktree::e[i].clear();
}

signed main() {
	init();
	scanf("%d", &T);
	
	for (; T; --T) {
		scanf("%d%d", &n, &m);
		clear(n << 1);
		
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &h[i].first);
			h[i].second = i;
		}
		
		sort(h + 1, h + 1 + n);
		
		for (int i = 1; i <= n; ++i)
			id[h[i].second] = i;
		
		for (int i = 1, u, v; i <= m; ++i) {
			scanf("%d%d", &u, &v);
			AddEdge(max(id[u], id[v]), min(id[u], id[v]));
		}
		
		Kruskal();
		
		for (int i = 1; i <= (n << 1); ++i)
			if (DSU::find(i) == i)
				Ktree::dfs(i, 0);
		
		scanf("%d", &q);
		
		for (int u, v, E; q; --q) {
			scanf("%d%d%d", &u, &v, &E);
			u = id[u], v = id[v];
			
			if (DSU::find(u) != DSU::find(v))
				puts("NO");
			else {
				int lca = Ktree::LCA(u, v);
				puts((E >= h[lca].first - h[u].first) ? "YES" : "NO");
			}
		}
		
		puts("");
	}
	
	return 0;
}