首页 > 其他分享 >AtCoder Beginner Contest 252 Ex K-th beautiful Necklace

AtCoder Beginner Contest 252 Ex K-th beautiful Necklace

时间:2023-06-25 22:12:08浏览次数:50  
标签:beautiful AtCoder typedef ch Beginner int ll long

洛谷传送门

AtCoder 传送门

不知道为什么可以想到设 \(n_c\) 为颜色 \(c\) 的出现次数,那么 \(\prod n_c\) 也即选的方案数 \(\approx 1.25 \times 10^{11}\)。

发现 \(B = \sqrt{\prod n_c}\) 不大,考虑 meet-in-the-middle,把所有颜色分成两部分,每一部分的 \(\prod n_c\) 都接近 \(B\)。先搜出每一部分的所有可能的异或和,问题转化为,给定两个数组 \(a_{1 \sim n}\) 和 \(b_{1 \sim m}\),求 \(a_i \oplus b_j\) 的第 \(k\) 大。

朴素想法是二分,二分后即求 \(a_i \oplus b_j \ge x\) 的对数。对 \(a\) 建 01Trie,对于每个 \(b_j\) 钦定到哪一位之前全部相等,在这一位异或起来 \(> x\),在 Trie 上走一遍即可求得。但是时间复杂度是 \(O(B \log^2 V)\) 的,比较难通过。

必须得降一个 \(\log\)。考虑直接逐位确定答案,所有 \(b_i\) 同时在 Trie 树上走,对于每个 \(b_i\) 都维护一个 \(p_i\) 表示它当前的位置。那如果我们要判断当前位是否为 \(1\),就把所有 \(p_i\) 往异于 \(b_i\) 当前位的方向走,累加子树大小,就是当前位为 \(1\) 的对数。时间复杂度降为 \(O(B \log V)\),可以通过。

感觉技巧性挺强的。

code
// Problem: Ex - K-th beautiful Necklace
// Contest: AtCoder - AtCoder Beginner Contest 252
// URL: https://atcoder.jp/contests/abc252/tasks/abc252_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 75;

ll n, m, K, a[maxn], b[maxn];
int ch[40000000][2], ntot, sz[40000000], p[40000000];
vector<ll> vc[maxn], va, vb;

void dfs(int d, ll s, vector<ll> &v) {
	if (d > m) {
		v.pb(s);
		return;
	}
	for (ll x : vc[d]) {
		dfs(d + 2, s ^ x, v);
	}
}

inline void insert(ll x) {
	int p = 0;
	for (int i = 59; ~i; --i) {
		int t = ((x >> i) & 1);
		if (!ch[p][t]) {
			ch[p][t] = ++ntot;
		}
		p = ch[p][t];
		++sz[p];
	}
}

void solve() {
	scanf("%lld%lld%lld", &n, &m, &K);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &a[i], &b[i]);
		vc[a[i]].pb(b[i]);
	}
	if (m == 1) {
		sort(b + 1, b + n + 1, greater<ll>());
		printf("%lld\n", b[K]);
		return;
	}
	sort(vc + 1, vc + m + 1, [&](auto a, auto b) {
		return a.size() > b.size();
	});
	dfs(1, 0, va);
	dfs(2, 0, vb);
	for (ll x : vb) {
		insert(x);
	}
	int t = (int)va.size();
	ll ans = 0;
	for (int d = 59; ~d; --d) {
		ll s = 0;
		for (int i = 0; i < t; ++i) {
			if (p[i] == -1) {
				continue;
			}
			s += sz[ch[p[i]][((va[i] >> d) & 1) ^ 1]];
		}
		bool fl = 0;
		if (s < K) {
			K -= s;
		} else {
			fl = 1;
			ans |= (1LL << d);
		}
		for (int i = 0; i < t; ++i) {
			if (p[i] == -1) {
				continue;
			}
			p[i] = ch[p[i]][((va[i] >> d) & 1) ^ fl];
			if (!p[i]) {
				p[i] = -1;
			}
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:beautiful,AtCoder,typedef,ch,Beginner,int,ll,long
From: https://www.cnblogs.com/zltzlt-blog/p/17504117.html

相关文章

  • AtCoder Beginner Contest 212(E,F)
    AtCoderBeginnerContest212(E,F)E(dp)E题目大意为有\(n\)个点,我们需要找到\(k+1\)个点,用数组\(A\)表示,其中,\(A_i\)和\(A_{i+1}\)也不能一模一样,而且,规定\(A_0\)是\(1\),并且\(A_k\)也是\(1\),而且,还要满足下面的\(m\)种条边是不可以代表为\(A_i\)和\(A_{i+1}\),问我们可以......
  • AtCoder Beginner Contest(abc) 299
    A-TreasureChest题目大意给定一个由'|''*'和'.'组成的字符串,并且保证一定有1个'*'和2个'|',检查'*'是否在两个'|'之间;解题思路签到题不多嗦了;但是这里可以注意一下string的find函数;find(charc,intpos)意为从第pos个字符开始找字符c,返回值......
  • AtCoder Regular Contest 154 C Roller
    洛谷传送门AtCoder传送门被这题干爆了考虑把环压缩成块。这样一次操作就是,选择两个相邻的块,把左边块长度减\(1\),右边块长度加\(1\)。特判\(a,b\)所有块长都是\(1\)的情况,这种情况不能操作。排除掉上面的情况,我们断言:有解的充要条件是,存在某一种\(a\)的顺序,使得\(b......
  • 【题解】AtCoder-ABC306G Return to 1
    这也太强了!容易想到的是用若干环拼出这个\(10^{10^{100}}\),也就是这些环的\(\gcd\mid10\)。之后就不会了。先正图反图两次DFS,只留下\(1\)所在强连通分量里的边,对正图跑DFS生成树,定义其深度从\(0\)开始,然后有一个结论是:对于任何正整数\(a\),图中存在一个包含\(1\)......
  • AtCoder Beginner Contest 229(F,G)
    AtCoderBeginnerContest229(F,G)F(二部图,dp)F这个题大致是给你\(n+1\)个点,为\(0\)到\(n\),然后\(n\)条边是点\(0\)到\(1...n\)这些点的\(n\)条边,后面还有\(n\)条边,连接点\(i\)和\(i+1\)(其中\(i\)为\(1\)到\(n\),其中\(n\)是和\(1\)连接的)前\(n\)条边的价值是\(a_i\),后......
  • AtCoder Beginner Contest(abc) 306
    A-Echo题目大意把一个字符串的每个字符输出两遍解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedefpair<int,int>PII;constintN=1e6+10;intn,m;signedmain(){cin>>n;string......
  • AtCoder Regular Contest 162 F Montage
    洛谷传送门AtCoder传送门题目限制可以被改写成,如果\(A_{a,b}=A_{c,d}=1\),那么\(A_{a,d}=A_{c,b}=1\)。考虑删去空白的行和列,那么对于每个\(A_{a,b}=A_{c,d}=1\),矩形\((a,b),(c,d)\)中一定都是\(1\)。发现每一行只可能存在一个极长\(1\)区间。并......
  • AtCoder Regular Contest 162 E Strange Constraints
    洛谷传送门AtCoder传送门完全没有思路。但是其实不难的。设\(d_i\)为\(i\)在\(B\)中的出现次数,题目要求:\(\foralli\in[1,n],d_i\leA_i\);对于位置\(i\),\(d_j\leA_i\)的数\(j\)可以被放到\(B_i\)。考虑按照\(d_i\)从大到小dp。设\(f_{i,j,k}\)......
  • AtCoder Beginner Contest(abc) 304
    A-FirstPlayer题目大意顺时针给定一个序列,序列的元素由一个字符串和一个数字组成;我们需要从有最小数字的元素开始,顺时针遍历整个序列,并输出字符串;解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;ty......
  • AtCoder Beginner Contest(abc) 300
    A-N-choicequestion题目大意从n个数里面找出a+b的结果解题思路签到题不多嗦了神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedefpair<int,int>PII;constintN=310;intn;signedmain(){inta,b;cin>>n......