首页 > 其他分享 >AtCoder Beginner Contest 308 题解

AtCoder Beginner Contest 308 题解

时间：2023-07-07 21:22:56浏览次数：52  
标签：308 __ AtCoder int 题解 ll gnu tree include

https://atcoder.jp/contests/abc308/tasks_print

A - New Scheme

过水已隐藏。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int s[10];
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	for (int i = 1;i <= 8; ++ i) read (s[i]);
	int ok = 1;
	for (int i = 1;i < 8; ++ i) ok &= (s[i] <= s[i + 1]);
	for (int i = 1;i <= 8; ++ i) ok &= (s[i] >= 100 && s[i] <= 675);
	for (int i = 1;i <= 8; ++ i) ok &= (s[i] % 25 == 0);
	if (ok) printf ("Yes\n");
	else printf ("No\n");
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

B - Default Price

很水：直接用 map 记一下即可。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int n, m;
char c[105][25], d[105][25];
int p[105];
map < string, int > mp;
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n), read (m);
	for (int i = 1;i <= n; ++ i) scanf ("%s", c[i] + 1);
	for (int j = 1;j <= m; ++ j) scanf ("%s", d[j] + 1);
	for (int i = 0;i <= m; ++ i) read (p[i]);
	mp.clear ();
	for (int i = 1;i <= m; ++ i) {
		int len = strlen (d[i] + 1);
		string str = "";
		for (int j = 1;j <= len; ++ j) {
			str += (char) (d[i][j]);
		}
		mp[str] = p[i];
	}
	int ans = 0;
	for (int i = 1;i <= n; ++ i) {
		int len = strlen (c[i] + 1);
		string str = "";
		for (int j = 1;j <= len; ++ j) {
			str += (char) (c[i][j]);
		}
		if (mp[str]) ans += mp[str];
		else ans += p[0];
	}
	printf ("%d\n", ans);
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

C - Standings

分数比较。然后排序。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
struct person {
	int id;
	ll suc, fai;
	inline bool operator < (person p1) {
		ll fir = suc * p1.fai, sec = p1.suc * fai;
		if (fir != sec) return fir > sec;
		else return id < p1.id;
	}
} p[200005];
int n;
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n);
	for (int i = 1;i <= n; ++ i) {
		read (p[i].suc), read (p[i].fai);
		p[i].fai += p[i].suc;
		p[i].id = i;
	}
	sort (p + 1, p + 1 + n);
	for (int i = 1;i <= n; ++ i) printf ("%d ", p[i].id);
	printf ("\n");
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

D - Snuke Maze

可以直接 BFS，记录一下当前的点 + 字符。

记得加一下记忆化。

我以前写的代码因没有考虑方向寄了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int n, m;
char s[505][505];
int vis[505][505];
queue < pair < int, int > > q;
int mp[170];
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n), read (m);
	for (int i = 1;i <= n; ++ i) scanf ("%s", s[i] + 1);
	memset (mp, 0, sizeof mp);
	mp['s'] = 1, mp['n'] = 2, mp['u'] = 3, mp['k'] = 4, mp['e'] = 5;
	if (s[1][1] == 's') q.push (make_pair (1, 1));
	while (!q.empty ()) {
		int u = q.front ().first, v = q.front ().second;
		q.pop ();
		if (vis[u][v]) continue;
		vis[u][v] = 1;
		if (u == n && v == m) break;
		for (int i = -1;i <= 1; ++ i) {
			for (int j = -1;j <= 1; ++ j) {
				if (abs (i) + abs (j) != 1) continue;
				if (u + i < 1 || u + i > n) continue;
				if (v + j < 1 || v + j > m) continue;
				int X = mp[s[u][v]], Y = mp[s[u + i][v + j]];
				if (!X || !Y) continue;
				if (X < 5 && X + 1 == Y) q.push (make_pair (u + i, v + j));
				if (X == 5 && Y == 1) q.push (make_pair (u + i, v + j));
			}
		}
	}
	if (vis[n][m]) printf ("Yes\n");
	else printf ("No\n");
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

E - MEX

考虑先计数 \((i, j)\) 满足 \(1 \leq i < j \leq n\) 并且 \(s_{i}\) 为 E，\(s_{j}\) 为 X（按 \((A_i, A_j)\) 分开计数）。

这样可以直接前缀和做。

然后枚举一下 \(s_k\) 为 M 的 \(i\)，再枚举一下 \(A_i, A_j, A_k\)，带权计一下数即可。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
const int N = 2e5 + 5;
ll f[N][3][3];
int n, a[N];
ll sum[N][3][3];
char s[N];
inline int mex (int i, int j, int k) {
	if (i != 0 && j != 0 && k != 0) return 0;
	if (i != 1 && j != 1 && k != 1) return 1;
	if (i != 2 && j != 2 && k != 2) return 2;
	return 3;
}
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n);
	for (int i = 1;i <= n; ++ i) read (a[i]);
	scanf ("%s", s + 1);
	for (int i = 1;i <= n; ++ i) {
		for (int j = 0;j < 3; ++ j) {
			for (int k = 0;k < 3; ++ k) {
				f[i][j][k] = f[i - 1][j][k];
			}
		}
		if (s[i] == 'M') f[i][a[i]][0] ++;
		if (s[i] == 'E') f[i][a[i]][1] ++;
		if (s[i] == 'X') f[i][a[i]][2] ++;
	}
	for (int i = n - 1;i >= 1; -- i) {
		for (int j = 0;j < 3; ++ j) {
			for (int k = 0;k < 3; ++ k) {
				sum[i][j][k] = sum[i + 1][j][k];
			}
		}
		if (s[i] == 'E') {
			sum[i][a[i]][0] += f[n][0][2] - f[i][0][2];
			sum[i][a[i]][1] += f[n][1][2] - f[i][1][2];
			sum[i][a[i]][2] += f[n][2][2] - f[i][2][2];
		}
	}
	ll ans = 0;
	for (int i = 0;i < 3; ++ i) {
		for (int j = 0;j < 3; ++ j) {
			for (int k = 0;k < 3; ++ k) {
				for (int _ = 1;_ <= n; ++ _) {
					if (s[_] == 'M' && a[_] == i) ans += mex (i, j, k) * sum[_ + 1][j][k];
				}
			}
		}
	}
	printf ("%lld\n", ans);
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

F - Vouchers

考虑贪心，因为要求的是总和，所以先将优惠按 \(D\) 从大到小排序。

取最小的 \(\geq L\) 的即可，这样可以为后面准备。

具体实现可以用平衡树 / set / ...。

记得开 long long。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int n, m;
const int N = 2e5 + 5, V = 1e7 + 10;
struct fhq_treap {
	int root, tot;
	struct node {int ls, rs, val, pri, siz;} tr[N];
	inline void update (int u) {tr[u].siz = tr[tr[u].ls].siz + tr[tr[u].rs].siz + 1;}
	inline void split (int u, int v, int &x, int &y) {
		if (!u) {x = y = 0; return ;}
		if (tr[u].val <= v) split (tr[u].rs, v, tr[x = u].rs, y);
		else split (tr[u].ls, v, x, tr[y = u].ls);
		update (u);
	}
	inline int merge (int x, int y) {
		if (!x || !y) return x | y;
		if (tr[x].pri < tr[y].pri) return tr[y].ls = merge (x, tr[y].ls), update (y), y;
		return tr[x].rs = merge (tr[x].rs, y), update (x), x;
	}
	inline int create (int w) {int x = ++ tot; tr[x].val = w, tr[x].pri = randomly (1, V), tr[x].siz = 1; return x;}
	inline void ins (int w) {
		int x, y; x = y = 0;
		split (root, w - 1, x, y);
		root = merge (merge (x, create (w)), y);
	}
	inline void del (int w) {
		int x, y, z; x = y = z = 0;
		split (root, w, x, z), split (x, w - 1, x, y);
		root = merge (merge (x, y = merge (tr[y].ls, tr[y].rs)), z);
	}
	inline int kth (int k) {
		int u = root;
		while (true) {
			if (k <= tr[tr[u].ls].siz) u = tr[u].ls;
			else if (k == tr[tr[u].ls].siz + 1) return tr[u].val;
			else k -= tr[tr[u].ls].siz + 1, u = tr[u].rs;
		}
	}
	inline int pre (int w) {
		int u = root, ans = 0;
		while (true) {
			if (!u) return ans;
			else if (w <= tr[u].val) u = tr[u].ls;
			else ans = tr[u].val, u = tr[u].rs;
		}
	}
	inline int nxt (int w) {
		int u = root, ans = 0;
		while (true) {
			if (!u) return ans;
			else if (w >= tr[u].val) u = tr[u].rs;
			else ans = tr[u].val, u = tr[u].ls;
		}
	}
	inline int rank (int w) {
		int x, y, ans; x = y = ans = 0;
		split (root, w - 1, x, y), ans = tr[x].siz + 1;
		return root = merge (x, y), ans;
	}
} fhq;
struct down {
	int L, D;
	inline bool operator < (down p1) {
		if (D != p1.D) return D > p1.D;
		else return L > p1.L;
	}
} ok[N]; 
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n), read (m);
	fhq.ins (-2e9), fhq.ins (2e9);
	ll ans = 0; 
	for (int i = 1;i <= n; ++ i) {
		int w;
		read (w);
		fhq.ins (w);
		ans += 1ll * w;
	} 
	for (int i = 1;i <= m; ++ i) {
		read (ok[i].L);
	}
	for (int i = 1;i <= m; ++ i) {
		read (ok[i].D);
	}
	sort (ok + 1, ok + 1 + m);
	for (int i = 1;i <= m; ++ i) {
		if (fhq.nxt (ok[i].L - 1) != 2e9) {
			int w = fhq.nxt (ok[i].L - 1);
			fhq.del (w);
			ans -= 1ll * ok[i].D; 
		}
	}
	printf ("%lld\n", ans);
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

G - Minimum Xor Pair Query

难题来了。diff = *2008，做不出来。

Hint：最小的异或和 \(x\) 一定是由从小到大排序后两个相邻的数 XOR 之后得到的，因为异或和最小是要差尽可能的小，所以要相邻。

有了这个 Hint，我们就可以用 std :: multiset 维护每个数和相邻两数的异或和，动态维护一下即可，还有几个 multiset 的用法：

  • *st.begin ()：求最小值。

  • if (st.find (x) != st.end ()) st.erase (st.find (x))：删除 \(x\)。

  • multiset < ll > :: iterator it：迭代器。

  • it --;：it 的前驱。

  • it ++;：it 的后继。

  • *it：it 的具体值。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
multiset < ll > st, xsm;
int n;
inline ll F (ll x) {
	return x > 0 ? x : -x;
}
bool Memory_Ends;
signed main () {
	fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
	read (n);
	st.insert (-2147483647);
	st.insert (2147483647);
	while (n --) {
		int op;
		read (op);
		if (op == 1) {
			ll x;
			read (x);
			st.insert (x);
			multiset < ll > :: iterator it = st.find (x);
			multiset < ll > :: iterator l = it, r = it;
			l --, r ++;
			ll L = *l, R = *r;
			if (F (L) != 2147483647 && F (R) != 2147483647) {
				if (xsm.find (L ^ R) != xsm.end ()) xsm.erase (xsm.find (L ^ R));
			}
			if (F (L) != 2147483647) xsm.insert (L ^ x);
			if (F (R) != 2147483647) xsm.insert (R ^ x);
		} 
		else if (op == 2) {
			ll x; read (x);
			multiset < ll > :: iterator it = st.find (x);
			multiset < ll > :: iterator l = it, r = it;
			l --, r ++;
			ll L = *l, R = *r;
			if (F (L) != 2147483647 && F (R) != 2147483647) xsm.insert (L ^ R);
			if (F (L) != 2147483647) {
				if (xsm.find (L ^ x) != xsm.end ()) xsm.erase (xsm.find (L ^ x));
			}
			if (F (R) != 2147483647) {
				if (xsm.find (R ^ x) != xsm.end ()) xsm.erase (xsm.find (R ^ x));
			}
			st.erase (x);
		}
		else {
			printf ("%lld\n", *xsm.begin ());
		}
	}
	fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
	return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/

标签：308,__,AtCoder,int,题解,ll,gnu,tree,include
From： https://www.cnblogs.com/RB16B/p/17536091.html

相关文章

  • [HNOI2008] 玩具装箱 题解
    很难得遇到细节题打码5分钟调试两小时感谢游老师送出的1.5h调试，感激(争取每天用我的代码训练老师的该题能力）细节/思路见注释#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;/*本题细节很多！！！1.注意要把‘0’放进去，否则'1'一直弹不出去，导致答案偏大2......
  • 题解 P8648【[蓝桥杯 2017 省 A] 油漆面积】
    怎么题解区全是扫描线，还有个\(O(n^3)\)暴力老哥。为防止误导新人，给个理论上稳过的\(O(n^2)\)解法。二维前缀和可以处理若干次单点加，最后若干次矩形查的问题。将其差分，即可处理若干次矩形加，最后若干次单点查的问题。于是我们使用差分将所有矩形加上，然后做一遍二维前缀和，即......
  • 「NOIP 模拟赛 20230707」T2 - 涂照片 题解
    题目大意原题有一个\(n+1\timesm+1\)的网格。对于每一行\(i\)，都要将左侧的一些格子\((i,1),(i,2),\ldots,(i,x)\)涂黑，其中\(x=k\)的概率为\(a_{i,k}\)。同理对于每一列\(j\)，都要将上方的一些格子\((1,j),(2,j),\ldots,(x,j)\)涂黑，其中\(x=k\)的概率为\(b_{k,......
  • AtCoder Beginner Contest 264 ABCDE
    AtCoderBeginnerContest264A-"atcoder".substr()ProblemStatement题意：截取字符串atcoder的[L,R]一段并输出。Solution题解：用string.substr直接写#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings="?atcoder"; intl,r; cin&......
  • P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解
    P7561[JOISC2021Day2]道路の建設案(RoadConstruction)题解题目描述JOI国是一个\(x\timesy\)的二维平面，王国里有\(n\)个城镇，分别编号为\(1,2,\cdots,n\in[1,2.5\times10^5]\)，其中第\(i\)个城镇的坐标为\((x_i,y_i)\)。在JOI国，正计划修建连接两座城......
  • AT_bcu30_2019_qual_a 题解
    思路纯模拟题，给定N和P后，定义一个计数器sum，重复N次输入，每输入一次就判断P也就是子弹的能量是否≥每面墙的厚度x，如果是，就用P减去x，sum增加1，表示穿过了一面墙，否则跳出循环，输出sum。代码#include<iostream>usingnamespacestd;intmain(){intn,p,sum=0,......
  • AT_nikkei2019ex_h 题解
    思路这是一道博弈题，最优策略是高桥的k一直是1，青木的k一直是0，可以保证拿走的硬币不超过剩下的硬币，这样每次两人都取完后拿走硬币的数量是8^1+8^0，结果是9，那么就用Nmod9，得出的结果就是剩下的硬币。如果结果是0，那么最后拿的就是青木，输出Lose。如果结果是2、4、6，都......
  • 【HarmonyOS】【FAQ】HarmonyOS应用开发相关问题解答（三）
    ​贴接上回。。。 【往期FAQ参考】【HarmonyOS】【FAQ】HarmonyOS应用开发相关问题解答（一）【HarmonyOS】【FAQ】HarmonyOS应用开发相关问题解答（二） 【本期FAQ】1、第一次调用geolocation.getCurrentLocation()接口，弹出权限弹框后并未返回结果，再次调用接口才会成功返回？（API8......
  • AT_nikkei2019ex_e 题解
    思路进题扫一眼题目描述，可以写成这样：是不是很眼熟？这不就是角谷猜想嘛，但它不是让我们求步数果，而是求结果。它给了步数，求结果那就要倒推，第二个样例给了P最大时，也就是1000输出的结果1789997546303，我们就用这个结果往前推，带入角谷猜想的运算过程，就可以了。记得开longlong。......
  • AT_pakencamp_2020_day1_c 题解
    思路看到题目的第一句话我就知道要用map了。一道map的入门题，定义一个map来输入和统计参加次数后，定义一个计数器sum用来统计人数。代码#include<iostream>#include<string>#include<map>usingnamespacestd;map<string,int>personnel;intmain(){intn,sum......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99