AtCoder Beginner Contest 314
A - 3.14
嗯,你可以用string 存小数点后的...
B - Roulette
对于每一个金额,用个vector存 pair <>存一个人赌了多少,以及是哪一个人 。
C - Rotate Colored Subsequence
每种数用个双向链表记下来。
D - LOWER
我们观察到,对于2,3操作,只有最后一次有用,且具有全局性操作。
对于1操作,我们模拟,并看最后是否被覆盖就行了。
E - Roulettes
好一个题面
像一个背包,要平衡代价与收益,且是有依赖的背包,必须把小的更新完才能更新大的。
我们记\(f_i\)表示从\(i\)转移到\(m\)的期望次数。
\(f_i \leftarrow \min\{\frac{\sum_j f_{i - s_{j,k}}}{p_j}+c_j\}\)
F - A Certain Game
我们可以每次建立一个新点来存下每次合并后的team。
用并查集存下维护每个人的所属队伍。
最后一次dfs更新答案。
\(O(\alpha n)\)
G - Amulets
显然能打败的monster随我们所拥有的护身符数量单调不严格递增。
我们考虑双指针,然后我们所选护身符肯定是当前的前\(k\)大。
这个可以用平衡树权值线段树做,每次动态开点,线段树上二分即可。
#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define per_(i,a,b) for (int i = (a); i >= (b); i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define endl '\n'
#define int ll
using namespace std;
const int maxn = 3e5 + 10, mod = 998244353;// mod = 1949777;
int n, m, h;
int a[maxn], b[maxn];
int inf = 1e15;
const int N = 1.5e7;
struct node{
int ls, rs, lv, rv, cnt, val;
}t[N];
int c[maxn];
int cnt = 1;
void upd(int p, int lv, int rv, int x, int y) {
if (lv == rv) {
t[p].cnt += y;
t[p].val += lv * y;
return;
}
int mid = (lv + rv) / 2;
if (x <= mid) {
if (!t[p].ls) t[p].ls = ++cnt, t[cnt].lv = lv, t[cnt].rv = mid;
upd(t[p].ls, lv, mid, x, y);
} else {
if (!t[p].rs) t[p].rs = ++cnt, t[cnt].lv = mid + 1, t[cnt].rv = rv;
upd(t[p].rs, mid + 1, rv, x, y);
}
t[p].cnt = ((t[p].ls ? t[t[p].ls].cnt : 0) + (t[p].rs ? t[t[p].rs].cnt : 0));
t[p].val = ((t[p].ls ? t[t[p].ls].val : 0) + (t[p].rs ? t[t[p].rs].val : 0));
}
int fuct(int x) {
int p = 1;
if (t[p].cnt <= x) return t[p].val;
int sum = 0;
while(x) {
if (t[t[p].rs].cnt <= x) {
x -= t[t[p].rs].cnt;
sum += t[t[p].rs].val;
p = t[p].ls;
} else {
p = t[p].rs;
}
if (t[p].lv == t[p].rv) {
sum += t[p].lv * x;
break;
}
}
return sum;
}
int ans[maxn];
signed main() {
#ifdef LOCAL
freopen("w.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> h;
rep_(i, 1, n){
cin >> a[i] >> b[i];
}
t[1].lv = 1, t[1].rv = inf;
int j = 0, tot = 0;
rep_(i, 0, m) {
while(j <= n && tot - fuct(i) < h) {
j++;
tot += a[j];
if (c[b[j]]) upd(1, 1, inf, c[b[j]], -1);
c[b[j]] += a[j];
if (c[b[j]]) upd(1, 1, inf, c[b[j]], 1);
}
ans[i] = j - 1;
}
rep_(i, 0, m) {
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}
//by whc
Ex - Disk and Segments
如果设\(f(x,y)\)表示在\((x, y)\)这个点对的答案值的话。
固定\(x\),考察\(y\) ,显然是一个单峰函数。
扩展到二维,\(x\)应该也是个单峰函数,(但是本蒟蒻不会证)。
然后我们对两个维度分别三分逼近值。
对于一个点到线段的距离,可以叉积出面积然后除以底边长(orz wls)。
- 题解 Beginner AtCoder Contest 314beginner atcoder contest 314 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 334