专栏文章

AtCoder Beginner Contest 431

TT0mle
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbc2vw
此快照首次捕获于
2025/12/01 23:37
3 个月前
此快照最后确认于
2025/12/01 23:37
3 个月前
查看原文
顺序：GABCDEF。

G

将 f(l,r)f(l,r) 分成三部分：字典序小于原来，等于原来，大于原来。
小于的大于是逆序对和正序对，fenwick 数数。
将询问离线下来排序。
对于 xx 不大于逆序对个数的询问，字典序小于原来。
这部分 f(l,r)f(l,r) 的顺序是：ll 最小的前提下，ara_r 最小，然后 rr 最大。
线段树随便算一算。但是我的代码要求集合第 kk 大，set advance 假了，并且不会用平板电视，只能再写个动态开点线段树了。
其余两部分同理。
5.2k，fwk+2smt。
40min
代码过长放在这里吧CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005;
// const int V = ;
// const int mod = ;
typedef unsigned us;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vl;
template <class T> using pq = priority_queue <T>;
template <class T> using pqg = priority_queue <T, vector <T>, greater <T> >;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repr(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define perr(i, a, b) for (int i = (a); i > (b); --i)

#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back

template <class T1, class T2> inline void ckmn(T1 &a, T2 b) { (a > b) && (a = b, 0); }
template <class T1, class T2> inline void ckmx(T1 &a, T2 b) { (a < b) && (a = b, 0); }

namespace IO {
	// char buf[1 << 23], *p1 = buf, *p2 = buf;
	// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
	template <class T> void rd(T &a, unsigned c = 0) {
		while (c = getchar(), c < 48 || c > 57);
		for (a = 0; c >= 48 && c <= 57; c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
	}
	template <class T> void wrt(T x) { if (x > 9) wrt(x / 10); putchar(x % 10 ^ 48); }
} using IO::rd; using IO::wrt;

int n, q, a[N];
pii ans[N];
struct Ques { int x, id; } qu[N];
map <int, int> mp;

struct shit {
	int ls, rs, ct;
	#define ll(p) Tr[p].ls
	#define rr(p) Tr[p].rs
	#define cct(p) Tr[p].ct
} Tr[N * 200];
#define MM (L + R >> 1)
int tot;
void pushpu(int p) { cct(p) = cct(ll(p)) + cct(rr(p)); }
inline void sb(int p, int x, int k, int L, int R) {
	if (L == R) { cct(p) += k; return; }
	if (x <= MM) {
		if (!ll(p)) ll(p) = ++tot;
		sb(ll(p), x, k, L, MM);
	} else {
		if (!rr(p)) rr(p) = ++tot;
		sb(rr(p), x, k, MM + 1, R);
	}
	pushpu(p);
}
int shabi1(int p, int x, int L, int R) {
	if (L == R) return L;
	if (cct(ll(p)) >= x) return shabi1(ll(p), x, L, MM);
	return shabi1(rr(p), x - cct(ll(p)), MM + 1, R);
}

struct Seg {
	int l, r, ct;
	int rt;
	#define l(p) tr[p].l
	#define r(p) tr[p].r
	#define ct(p) tr[p].ct
	#define rt(p) tr[p].rt
} tr[N << 2];
#define M (l(p) + r(p) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)

inline void pushup(int p) {
	ct(p) = ct(ls) + ct(rs);
}
void build(int p, int l, int r) {
	l(p) = l, r(p) = r;
	if (l == r) { rt(p) = ++tot, ct(p) = 0; return; }
	build(ls, l, M), build(rs, M + 1, r);
	pushup(p);
}
void mod1(int p, int x, int k) {
	if (l(p) == r(p)) {
		sb(rt(p), k, 1, 1, n);
		ct(p) = cct(rt(p));
		return;
	}
	mod1(x <= M ? ls : rs, x, k), pushup(p);
}
void mod2(int p, int x, int k) {
	if (l(p) == r(p)) {
		sb(rt(p), k, -1, 1, n);
		ct(p) = cct(rt(p));
		return;
	}
	mod2(x <= M ? ls : rs, x, k), pushup(p);
}
int qrk(int p, int x) {
	if (l(p) == r(p)) {
		return shabi1(rt(p), ct(p) - x + 1, 1, n);
	}
	if (ct(ls) >= x) return qrk(ls, x);
	return qrk(rs, x - ct(ls));
}
int qry(int p, int l, int r) {
	if (l > r || l > r(p) || r < l(p)) return 0;
	if (l <= l(p) && r >= r(p)) return ct(p);
	if (r <= M) return qry(ls, l, r);
	if (l > M)  return qry(rs, l, r);
	return qry(ls, l, r) + qry(rs, l, r);
}
int qrk2(int p, int x, int l, int r) {
	if (l(p) == r(p)) {
		return shabi1(rt(p), x, 1, n);
	}
	int c = qry(ls, l, r);
	// cout << l(p) << "  " << r(p) << "  " << c << endl;
	if (c >= x) return qrk2(ls, x, l, r);
	return qrk2(rs, x - c, l, r);
}

struct BIT {
	int a[N];
	#define LB(k) ((k) & -(k))
	void clr() { memset(a, 0, sizeof(a)); }
	void add(int x, int k) { for (; x < N; x += LB(x)) a[x] += k; }
	int qry(int x) { int R = 0; for (; x; x -= LB(x)) R += a[x]; return R; }
} fwk;

bool cmp(Ques a, Ques b) { return a.x < b.x; }
int ivct() {
	int R = 0;
	per(i, n, 1) {
		R += fwk.qry(a[i] - 1);
		fwk.add(a[i], 1);
	}
	return R;
}
int nivct() {
	fwk.clr();
	int R = 0;
	rep(i, 1, n) {
		R += fwk.qry(a[i] - 1);
		fwk.add(a[i], 1);
	}
	return R;
}
void solve() {
	rd(n), rd(q);
	rep(i, 1, n) rd(a[i]);
	rep(i, 1, q) rd(qu[i].x), qu[i].id = i;
	sort(qu + 1, qu + q + 1, cmp);
	int A = ivct(), C = nivct();
	int B = n * (n - 1) / 2 - A - C;
	int now = 0;
	build(1, 1, n);
	rep(i, 1, n) mod1(1, a[i], i);
	int j = 1;
	rep(i, 1, n) {
		mod2(1, a[i], i);
		int cc = qry(1, 1, a[i] - 1);
		while (j <= q && now + cc >= qu[j].x) {
			ans[qu[j].id] = {i, qrk(1, qu[j].x - now)};
			j++;
		}
		now += cc;
	}
	pii sm;
	rep(i, 1, n) {
		if (mp[a[i]]) sm = {mp[a[i]], i};
		mp[a[i]] = i;
	}
	while (j <= q && A + B >= qu[j].x) {
		ans[qu[j].id] = sm;
		j++;
	}
	now = A + B;
	build(1, 1, n);
	per(i, n, 1) {
		int cc = qry(1, a[i] + 1, n);
		while (j <= q && now + cc >= qu[j].x) {
			ans[qu[j].id] = {i, qrk2(1, qu[j].x - now, a[i] + 1, n)};
			j++;
		}
		now += cc;
		mod1(1, a[i], i);
	}
	rep(i, 1, q) wrt(ans[i].fi), putchar(32), wrt(ans[i].se), putchar(10);
}
signed main() {
	int T = 1;
	if (0) rd(T);
	while (T--) solve();
}

A

max⁡(0,H−B)\max(0,H-B)。

B

随便搞。

C

简单贪贪贪。

D

简单背包。
先假定所有部件都在身体，然后背包调整。

E

有点史。
我们发现一个镜子如果被改只会经过一次。
然后诡异建图，拆 88 个点，前四个点是进入格子时的方向，后四个是出去时的方向。
然后可以 01bfs 的，省事写的 dij。
脑子不太清楚，写了 30min。
写完 80min。
CPP
void solve() {
	rd(n), rd(m);
	rep(i, 1, n * m * 8) H[i] = 0, dis[i] = 1e9, vis[i] = 0;
	et = 0;
	rep(i, 1, n) {
		rep(j, 1, m) {
			int c = 0; while (isspace(c = getchar()));
			if (c == 'A') {
				rep(k, 1, 4) {
					add(id(i, j, k), id(i, j, k + 4), 0);
					add(id(i, j, k), id(i, j, k % 4 + 5), 1);
					add(id(i, j, k), id(i, j, (k + 2) % 4 + 5), 1);
				}
			} else if (c == 'B') {
				rep(k, 1, 4) {
					add(id(i, j, k), id(i, j, k + 4), 1);
					add(id(i, j, k), id(i, j, k % 4 + 5), k == 2 || k == 4);
					add(id(i, j, k), id(i, j, (k + 2) % 4 + 5), k == 1 || k == 3);
				}
			} else if (c == 'C') {
				rep(k, 1, 4) {
					add(id(i, j, k), id(i, j, k + 4), 1);
					add(id(i, j, k), id(i, j, k % 4 + 5), k == 1 || k == 3);
					add(id(i, j, k), id(i, j, (k + 2) % 4 + 5), k == 2 || k == 4);
				}
			}
		}
	}
	rep(i, 1, n) {
		rep(j, 1, m) {
			if (j != m) add(id(i, j, 5), id(i, j + 1, 1), 0);
			if (i != n) add(id(i, j, 6), id(i + 1, j, 2), 0);
			if (j != 1) add(id(i, j, 7), id(i, j - 1, 3), 0);
			if (i != 1) add(id(i, j, 8), id(i - 1, j, 4), 0);
		}
	}
	dij();
	cout << dis[id(n, m, 5)] << endl;
}

F

排序，对于一种出现 lenlen 次的数 xx，有 cntcnt 个在 [x−d,x−1][x-d,x-1] 的数，可以把 lenlen 个 xx 放进 cnt+1cnt+1 个地方，组合数简单算。
90:59，AK。
CPP
void solve() {
	rep(i, fac[0] = 1, 4e5) fac[i] = 1ll * fac[i - 1] * i % mod;
	fiv[400000] = qpw(fac[400000], mod - 2);
	per(i, 399999, 0) fiv[i] = fiv[i + 1] * (i + 1ll) % mod;
	cin >> n >> d;
	rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + n + 1);
	int ans = 1;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = l; while (r < n && a[r + 1] == a[l]) r++;
		int ct = l - (lower_bound(a + 1, a + n + 1, a[l] - d) - a) + 1;
		int len = r - l + 1;
		ans = 1ll * ans * C(len + ct - 1, ct - 1) % mod;
	}
	cout << ans;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...