AtCoder Beginner Contest 366
title: AtCoder Beginner Contest 366
categories:
- ICPC
tags:
- null
abbrlink: e46359dc
date: 2023-05-09 00:00:00
AtCoder Beginner Contest 366
D.三维前缀和板子,预处理可以选择不容斥查询的时候只能容斥
int a[N][N][N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
cin >> a[i][j][k];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
a[i][j][k] += a[i][j][k - 1];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
a[i][j][k] += a[i][j - 1][k];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
a[i][j][k] += a[i - 1][j][k];
}
}
}
cin >> m;
for (int i = 1; i <= m; i++) {
int x1, x2, y1, y2, z1, z2;
cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
int res = a[x2][y2][z2] - a[x1 - 1][y2][z2] - a[x2][y1 - 1][z2] -
a[x2][y2][z1 - 1] + a[x1 - 1][y1 - 1][z2] +
a[x1 - 1][y2][z1 - 1] + a[x2][y1 - 1][z1 - 1] - a[x1 - 1][y1 - 1][z1 - 1];
cout<<res<<endl;
}
}
E.给你一个二维平面上的 $N$ 点 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ 和一个非负整数 $D$ 。求 $(x, y)$ 使得 $\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D$ 的整数对的个数。
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq D \leq 10^6$
- $-10^6 \leq x_i, y_i \leq 10^6$
- $(x_i, y_i) \neq (x_j, y_j)$ for $i \neq j$.
- All input values are integers.
Sol:考虑横纵坐标显然独立,根据数据范围我们可以枚举一维,快速查询另一维。我们需要快速得到的是一个一维的点到n个点的绝对值距离之和,这在曼哈顿距离专题是很典的东西,我们只需要提前计算前缀和,查询的时候二分即可。此时我们还需要处理另一维,同样也可以继续二分,显然绝对值求和这个式子关于y是凹函数,但这样需要讨论并且左右两次二分比较麻烦。
- 对于求<=val的值的个数,如果val不大,我们可以先求等于val的数量,然后求一遍前缀和就可以了
左右两次二分的代码:
void solve() {
cin >> n >> m;
vector<int> vx(n + 1), vy(n + 1);
for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];
// deb(vx);
// deb(vy);
sort(alls(vx));
sort(alls(vy));
vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
for (int i = 1; i <= n; i++) {
prex[i] += vx[i] + prex[i - 1];
prey[i] += vy[i] + prey[i - 1];
}
for (int i = n; i >= 1; i--) {
sufx[i] += vx[i] + sufx[i + 1];
sufy[i] += vy[i] + sufy[i + 1];
}
deb(vx);
deb(prex);
deb(sufx);
deb(vy);
deb(prey);
deb(sufy);
int ans = 0;
for (int x = -2e6; x <= 2e6; x++) {
auto it = lower_bound(alls(vx), x);
int tmp = 0;
if (it == vx.end()) {
tmp = n * x - prex[n];
} else {
int cnt = it - vx.begin() - 1;
tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
}
int you = m - tmp;
if (you < 0)
continue;
deb(x, tmp, you);
auto check = [&](int y) {
auto it = lower_bound(alls(vy), y);
int val = 0;
if (it == vy.end()) {
val = n * y - prey[n];
} else {
int cnt = it - vy.begin() - 1;
val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
}
return val <= you;
};
int st = vy[(n + 1) / 2];
if (check(st) == 0)
continue;
int l = st, r = 2e6;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
deb(st, r);
ans += r - st + 1;
// int ql = l;
l = -2e6, r = st;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
deb(l, st);
ans += st - l + 1;
// int qr = r;
ans -= 1;
// auto cal=[&](int cx,int cy){
// int res=0;
// for(int i=1;i<=n;i++){
// res+=abs(vx[i]-cx)+abs(vy[i]-cy);
// }
// return res;
// };
// for(int i=ql;i<=qr;i++){
// //cerr<<"**************************"<<endl;
// int res=cal(x,i);
// if(res>m){ cerr<<"**************************"<<endl;deb("acm!!!",x,i,res);}
// }
}
cout << ans << endl;
}
利用trick的代码:
void solve() {
cin >> n >> m;
vector<int> vx(n + 1), vy(n + 1);
for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];
sort(alls(vx));
sort(alls(vy));
vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
for (int i = 1; i <= n; i++) {
prex[i] += vx[i] + prex[i - 1];
prey[i] += vy[i] + prey[i - 1];
}
for (int i = n; i >= 1; i--) {
sufx[i] += vx[i] + sufx[i + 1];
sufy[i] += vy[i] + sufy[i + 1];
}
int ans = 0;
auto check = [&](int y) {
auto it = lower_bound(alls(vy), y);
int val = 0;
if (it == vy.end()) {
val = n * y - prey[n];
} else {
int cnt = it - vy.begin() - 1;
val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
}
return val;
};
vector<int> cnt(1e6 + 5);
for (int i = -2e6; i <= 2e6; i++) {
int res = check(i);
if (res <= 1e6)
cnt[res]++;
}
for (int i = 1; i <= 1e6; i++) cnt[i] += cnt[i - 1];
for (int x = -2e6; x <= 2e6; x++) {
auto it = lower_bound(alls(vx), x);
int tmp = 0;
if (it == vx.end()) {
tmp = n * x - prex[n];
} else {
int cnt = it - vx.begin() - 1;
tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
}
int you = m - tmp;
if (you < 0)
continue;
ans += cnt[you];
}
cout << ans << endl;
}
F.给你 $N$ 个线性函数 $f_1, f_2, \ldots, f_N$ ,其中 $f_i(x) = A_i x + B_i$ .从N个中选k个函数并进行复合,求由 $K$ 组成的序列 $p = (p_1, p_2, \ldots, p_K)$ 中 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ 的最大可能值。
Constraints
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq K \leq \text{min}(N,10)$
- $1 \leq A_i, B_i \leq 50$ $(1 \leq i \leq N)$
- All input values are integers.
Sol:不难想到一个可能是一个$O(nk)$的dp,先贪心考虑这个问题怎么最优,发现可以用交换法推公式,然后按某种标准排序,也就是内层嵌套的顺序是存在调整优化空间的。我们认为按照这个标准排序后,$f_{j}(f_{i}(suf))<f_{i}(f_{j}(suf))(i<j)$。所以我们只有先确定内层的情况,才能求出外层,所以需要倒着dp。$dp[i][j]$表示当前考虑i-n这些位置选了j个函数,转移考虑选与不选即可。
bool cmp(pii c, pii d) {
return c.sec * (1 - d.fs) > d.sec * (1 - c.fs);
}
void solve() {
cin >> n >> m;
vector<pii> v(n + 1);
for (int i = 1; i <= n; i++) cin >> v[i].fs >> v[i].sec;
sort(v.begin() + 1, v.end(), cmp);
int k = min(10LL, m);
vector<vector<int>> dp(n + 2, vector<int>(k + 1, 0));
dp[n+1][0]=1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= k; j++) {
dp[i][j] = dp[i + 1][j];
if(j)dp[i][j] = max(dp[i][j], v[i].fs * dp[i + 1][j - 1] + v[i].sec);
}
}
cout<<dp[1][k]<<endl;
}
G.给你一个简单的无向图,图中有 $N$ 个顶点和 $M$ 条边。 $i$ -th 边双向连接顶点 $u_i$ 和 $v_i$ 。给出构造:每个点赋值点权,要求满足:
- 对于出度至少为 $1$ 的每个顶点 $v$ ,写在其相邻顶点上的数字(不包括 $v$ 本身)的总 XOR 为 $0$ 。
Constraints
- $1 \leq N \leq 60$
- $0 \leq M \leq N(N-1)/2$
- $1 \leq u_i < v_i \leq N$
- $(u_i, v_i) \neq (u_j, v_j)$ for $i \neq j$.
- All input values are integers.
Sol:考虑高斯消元解异或方程组,本题特殊之处在于:对于无穷多解的情况需要输出构造一种非零解(这里特指每个变量都不为0).考虑为自由变量赋正整数值,且尽可能异或不为0.
int gauss(vector<vector<int>>& a, int n, vector<int>& solution) {
vector<int> freevar; // 记录自由变量对应的列
vector<int> pivot(n + 1, -1); // 记录每一行的主元所在的列
solution.assign(n + 1, 0);
int r = 1;
for (int c = 1; c <= n; c++) {
int t = r;
// 找到当前列中的主元
for (int i = r; i <= n; i++) {
if (a[i][c]) {
t = i;
break;
}
}
if (!a[t][c]) {
freevar.push_back(c);
continue; // 当前列没有主元,继续到下一列
}
pivot[r] = c; // 第 r 行的主元在 c 列
if (t != r) { // 交换行,将主元行放在第 r 行
for (int i = c; i <= n + 1; i++)
swap(a[r][i], a[t][i]);
}
// 消去主元下方的所有行
for (int i = r + 1; i <= n; i++) {
if (a[i][c])
for (int j = n + 1; j >= c; j--) a[i][j] ^= a[r][j];
}
r++;
}
// 检查是否有解
for (int i = r; i <= n; i++) {
if (a[i][n + 1])
return 0; // 无解
}
int tot = 0;
int rksz = r - 1; // 这是系数矩阵的秩
// 自由变量根据题目要求情况去赋值
for (auto i : freevar) solution[i] = 1LL << tot, tot++;
//------------------------------
for (int i = rksz; i >= 1; i--) {
int sum = a[i][n + 1];
for (int j = 1; j <= n; j++) {
if (j == pivot[i]) {
continue;
} // 如果不是主元所在的列
sum ^= (a[i][j] * solution[j]); // 右边已经求出来的,左边自由变量遗留
}
solution[pivot[i]] = sum; // 求解对应的主元变量
}
assert(rksz <= n);
if (rksz < n)
return 2; // 无穷多解
return 1; // 唯一解
}
void solve() {
int n, m;
cin >> n >> m;
vector b(n + 1, vector<int>(n + 2));
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
b[u][v] = b[v][u] = 1;
}
vector<int> sol(n + 1);
int t = gauss(b, n, sol);
if (t == 0)
cout << "No" << endl;
else {
for (int i = 1; i <= n; i++)
if (sol[i] < 1) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
for (int i = 1; i <= n; i++) cout << sol[i] << " ";
}
}