致歉
对不起,我不应该在全题解的编写上咕咕咕两个月,导致流量大量流失。
我知错了,下次还犯。
AB
无
C
考虑一个箱子里的所有球,我们需要把这些球放进互不相同的一些箱子里。然而我们可以留一个球在箱子里,显然留重量最大的最好,所以答案就是 $ \sum_{i=1}^{N} W_i $ 减去每个箱子里的最重的球的重量(没球的为 0)。
// Problem: C - Move It
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
int a[100005], w[100005];
int sum[100005], mx[100005];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
a[i]--;
}
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
sum[a[i]] += w[i];
mx[a[i]] = max(mx[a[i]], w[i]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += sum[i] - mx[i];
}
printf("%d", ans);
}
D
显然只有相对的两只蚂蚁可能相遇,所以我们可以先记录向右的蚂蚁坐标,然后对向左的蚂蚁使用二分。
假如两只蚂蚁各走了 $ K $ 个单位的长度,我们可以相对运动(bushi,把一只蚂蚁固定住,这时候另一只蚂蚁为了追上摆烂的蚂蚁(),就会以两倍的速度怒气冲冲的赶过去()()()
所以对于一只位于 $ X $ 的,向左的蚂蚁,她(?)能遇到的向右的蚂蚁坐标就处在 $ X - 2T \sim X $ 中,然后就可以愉快的使用二分了。
// Problem: D - Ghost Ants
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[200005], b[200005];
int main() {
int n;
ll t;
cin >> n >> t;
string s;
cin >> s;
int p = 0, q = 0;
for (int i = 0; i < n; i++) {
ll x;
scanf("%lld", &x);
if (s[i] == '1') {
a[p++] = x;
} else {
b[q++] = x;
}
}
sort(a, a + p);
ll ans = 0;
for (int i = 0; i < q; i++) {
ans += upper_bound(a, a + p, b[i]) - lower_bound(a, a + p, b[i] - t - t);
// upper_bound(a, a + p, b[i]) 查询第一个 > b[i] 的,即太右的蚂蚁
// lower_bound(a, a + p, b[i] - t - t) 查询第一个 >= b[i] - 2t 的,即可以在 t 时间内遇到的蚂蚁
}
printf("%lld", ans);
}
E
神仙期望。
期望是这样的,出题人只需要写标程得到一个半 rng 不 rand 的东西就可以了,而我们写各种程序凑到 $ \frac{1}{998244353} $ 的概率可就难了。
首先 1 和其它位置肯定要分开考虑,毕竟要是运气那么不好,一直没有交换,那么黑球就一直留在 1 上了。
考虑(某种意义上的)DP,设 $ f $ 和 $ g $ 为黑球在 1 上的概率和黑球不在 1 上的概率。
转移的概率:
-
$ f \to g : \cfrac{2}{N} - \cfrac{2}{N^2} $
-
$ g \to f : \cfrac{2}{N^2} $
-
$ f \to f : 1 - \cfrac{2}{N} + \cfrac{2}{N^2} $
-
$ g \to g : 1 - \cfrac{2}{N^2} $
然后进行转移。
易证如果不是 1 那么概率均等,所以最后的答案就是 $ f + (\cfrac{N}{2} + 1)g $。
// Problem: E - Random Swaps of Balls
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
ll qpow(ll a, ll x, ll m) {
ll ans = 1;
while (x) {
if (x & 1) {
ans = ans * a % m;
}
x >>= 1;
a = a * a % m;
}
return ans;
}
int main() {
ll n, m;
scanf("%lld %lld", &n, &m);
ll on1 = 1, other = 0;
ll other_1 = 2 * qpow(n, 2 * mod - 4, mod) % mod; // f -> g
ll swapp = (2 * qpow(n, mod - 2, mod) % mod + 2 * (mod - qpow(n, 2 * mod - 4, mod)) % mod) % mod; // g -> f
// 注 mod - x 在模 mod 意义下就相当于 -x
for (int i = 0; i < m; i++) {
ll n1 = 0, no = 0;
// other + (1 other / other 1)
n1 += other * other_1 % mod;
// 1 + no swap
n1 += on1 * (mod + 1 - swapp) % mod;
// other + (bushi 1
no += other * (mod + 1 - other_1) % mod;
// 1 + swap
no += on1 * swapp % mod;
on1 = n1 % mod;
other = no % mod;
}
printf("%lld", (on1 + (n * 499122177 + 1) % mod * other % mod) % mod); // 499122177 * 2 = 998244354
}
F
扫描线。
考虑将 $ (l, r) $ 表示成一个点。
那么,跟 $ (l, r) $ 相交的区间就会是两个长方形:$ 0 \le x \le l - 1, l + 1 \le y \le f - 1 $ 和 $ l + 1 \le x \le r - 1, r + 1 \le y \le 1e9 $,而我们要做的就是找到被长方形覆盖次数最多的一个点。
这个问题可以用扫描线解决,但是这里的线段树就简单很多了:区间修改,区间查询最大值,以及最大值中最前面的下标。
注意需要特判一下答案为 $ (0, 1) $ 的情况。
// Problem: F - InterSections
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
// bool _st;
struct line { // 扫描“线”,使用一种差分
int y, l, r, d;
line(int _y = -1, int _l = -1, int _r = -1, int _d = 0) {
y = _y, l = _l, r = _r, d = _d;
}
} a[400005];
bool cmp(line a, line b) {
// 优先比坐标,同坐标先加后减(因为我的代码是这么写的)
if (a.y != b.y) {
return a.y < b.y;
} else {
return a.d > b.d;
}
}
namespace seg { // 线段树部分
// 我选择动态开点
int tot = 1, rt = 1;
struct node {
int idx, mx, l, r, tag;
node() {
idx = mx = l = r = tag = 0;
}
} tree[400005 << 5];
void pushdown(int L, int R, int p) {
int mid = (L + R) / 2;
if (!tree[p].l) {
tree[p].l = ++tot;
tree[tree[p].l].idx = L;
}
tree[tree[p].l].mx += tree[p].tag;
tree[tree[p].l].tag += tree[p].tag;
if (!tree[p].r) {
tree[p].r = ++tot;
tree[tree[p].r].idx = mid + 1;
}
tree[tree[p].r].mx += tree[p].tag;
tree[tree[p].r].tag += tree[p].tag;
tree[p].tag = 0;
}
void update(int l, int r, int x, int L = 0, int R = 1e9, int &p = rt) {
if (!p) {
p = ++tot;
tree[p].idx = L;
}
if (l <= L && R <= r) {
tree[p].mx += x;
tree[p].tag += x;
return;
}
pushdown(L, R, p);
int mid = (L + R) / 2;
if (mid >= l) {
update(l, r, x, L, mid, tree[p].l);
}
if (mid < r) {
update(l, r, x, mid + 1, R, tree[p].r);
}
if (tree[tree[p].l].mx >= tree[tree[p].r].mx) {
tree[p].idx = tree[tree[p].l].idx;
} else {
tree[p].idx = tree[tree[p].r].idx;
}
tree[p].mx = max(tree[tree[p].l].mx, tree[tree[p].r].mx);
}
}
// bool _ed;
int main() {
// cerr << (&_ed - &_st) / 1024.0 / 1024.0 << endl;
int n;
scanf("%d", &n);
int cnt = 0;
for (int i = 0; i < n; i++) {
int l, r;
scanf("%d %d", &l, &r);
// 将四条线按照差分的方式(我写的左闭右闭所以更新先加后减)
a[cnt++] = line(0, l + 1, r - 1, 1);
a[cnt++] = line(l - 1, l + 1, r - 1, -1);
a[cnt++] = line(l + 1, r + 1, 1e9, 1);
a[cnt++] = line(r - 1, r + 1, 1e9, -1);
}
sort(a, a + cnt, cmp);
int l = 0, r = 1, mx = 0;
for (int i = 0; i < cnt; i++) {
seg::update(a[i].l, a[i].r, a[i].d);
if (a[i].y >= 0 && seg::tree[1].mx > mx) { // a[i].y >= 0 就是所谓的特判
mx = seg::tree[1].mx;
l = a[i].y, r = seg::tree[1].idx;
}
}
printf("%d %d", l, r);
}
G
震惊!某博主竟然自己 hack 了自己的 AC 做法!这究竟是 Atcoder 的不重视,还是博主的自虐?()()()()()()
先讲一下被我 hack 的做法。
(此处省略 ? 字)
那么正解是什么呢,其实正解是一个类 LIS 的 DP:
设 $ f_{i, j, 0/1} $ 为前 $ i $ 个,当前 LIS 的最后一个为 $ j $,现在用过/没用过超能力()能得到的最大 LIS 是多长。
有两种转移方式:
-
$ 0 \to 0 $ ,$ 1 \to 1 $,正常转移即可。
-
$ 0 \to 1 $。
在 $ 0 \to 1 $ 的时候,必然是设成当前最大的 + 1 最好,不好也有个地方好()
注:这题在离散化(我的做法)时有个小坑,由于这里 LIS 是要严格递增的,所以要把每个数和这个数 +1 都放进去再离散化。
// Problem: G - Suitable Edit for LIS
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
int a[200005], b[400005];
int c0[400005], c1[400005];
// c0 是 f[][][0] 的树状数组,c1 是 f[][][1] 的
void update(int *c, int u, int x) {
while (u < 400003) {
c[u] = max(c[u], x);
u += (u & -u);
}
}
int query(int *c, int u) {
int ans = 0;
while (u) {
ans = max(ans, c[u]);
u -= (u & -u);
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
int cnt = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[++cnt] = a[i];
b[++cnt] = a[i] + 1;
}
sort(b + 1, b + 1 + cnt);
cnt = unique(b + 1, b + 1 + cnt) - b;
for (int i = 1; i <= n; i++) { // 离散化
a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b + 1;
}
int mx0 = 0;
for (int i = 1; i <= n; i++) {
update(c0, a[i], query(c0, a[i] - 1) + 1);
update(c1, a[i], query(c1, a[i] - 1) + 1);
update(c1, mx0 + 1, query(c0, mx0) + 1);
// 第三句务必写在最后!(不然会出现一个阶段多次转移)
mx0 = max(mx0, a[i]);
}
printf("%d", max(query(c0, 400003), query(c1, 400003)));
}
标签:Atcoder,ABC,int,题解,ll,tree,ans,mx,mod
From: https://www.cnblogs.com/AProblemSolver/p/18278832