首页 > 其他分享 >1851 Round 888 (Div. 3)

1851 Round 888 (Div. 3)

时间：2023-08-02 09:46:59浏览次数：37  
标签：int 1851 scanf 888 namespace pos fa Div oplus

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;
}

标签：int,1851,scanf,888,namespace,pos,fa,Div,oplus
From： https://www.cnblogs.com/hcawa/p/17599726.html

相关文章

  • 1848 Round 885 (Div. 2)
    VikaandHerFriends给定一张网格图，Vika在\((x,y)\)处，她的\(k\)个朋友分别在\((x_{1\simk},y_{1\simk})\)处，每次所有人都必须移动到相邻各格子，询问Vika能否永远逃离她烦人的朋友考虑对格子进行黑白染色，每次移动一定会变换格子颜色，那么只有相同颜色的人才会碰......
  • 1855 Round 889 (Div. 2)
    DaltontheTeacher给定序列\(a_{1\simn}\)，定义一次操作为交换序列中的某两个数，求使得\(\foralli,a_i\not=i\)的最少操作次数对于所有数据，\(n\leq10^5\)计算出\(a_i=i\)的位置数量\(sum\)，若\(sum\)为偶数，则让其两两配对交换即可；否则会剩下一个数，在其他......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    Preface经典秒完SB题然后开始坐牢1h，写了个E的假算法T在24个点就不管了打lol去了妈的怎么稍微难点的题就是想不到呢A.MorningSandwich签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>......
  • Codeforces Round 889 (Div. 2)
    CodeforcesRound889(Div.2)T1​ 思路：我们将\(i\nep_i\)的数量记下来，再判断这个数的奇偶性，如果为偶，那么答案就为这个数/2，如果为奇，那么就是这个数/2+1。T2​ 思路：我们枚举\(1\simn\)，我们记录连续是\(n\)的因数的个数，如果不连续了就\(break\)，答案就是个数......
  • Codeforces Round 885 (Div. 2)
    CodeforcesRound885(Div.2)A.VikaandHerFriends题目大意太长了click思路可以手动模拟一下，可以发现当两个人的\(x+y\)值就行相同的就能抓到了#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){......
  • Codeforces Round 887 (Div. 2)
    CodeforcesRound887(Div.2)A.Desorting题目大意给出一个长度为\(n\)的数组\(a\),可以执行这个操作任意次。选择一下标\(i\),使得\(a_{1...i}\)加上\(1\)，\(a_{i+1...n}\)减少\(1\)。问最少几次操作使得数组\(a\)无序。思路首先如果\(a\)原本就无序的......
  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现，Vika以及她的朋友都不能走对角线，在这种情况下Vika和朋友的距离为偶数，且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心，枚举颜色，找到相邻距离最大的两块木板，记该距离为\(......
  • Codeforces Round 887 (Div. 2) 题解
    A.Desorting题目的核心操作就是选定一个位置\(i\)，使得：对于所有\(j\lei\)，\(a_j\leftarrowa_j+1\)对于所有\(j>i\)，\(a_j\leftarrowa_j-1\)这样一来，操作后\(a_{i+1}-a_i\)的值就会\(-2\)因为\(a_{i+1}-a_i<0\)时，也意味着\(a_i>a_{i+1}\)，所以就达到了要求那么题......
  • Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting
    初始所有点都是蓝色的，给定一个数组，每个元素为0，1，2等值，两种操作，选定一个点花1元变红，或者选定一个为1或者2的红色点，减去一个价值，让周围的点变红，最后所有点都要变红思路：贪心，对于一个数组来说我们找寻连续的不等于0的一段，判断每一段最多所能变红的存在两种情况010，这种情况花1可以最......
  • Educational Codeforces Round 152 (Rated for Div. 2) C. Binary String Copying
    题目大意为给定一个01字符串，给定m个区间，对于每个区间进行一次局部排序，求能得到的字符串种类数解法：因为字符串只包含0，1两个字符，我们观察可以得到，对于不同的区间来说如果排序后一样则说明肯定是某些位置在排序过程中无贡献，因此我们只需找出有贡献的位置即可对于一个区间[l,r],来说......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99