ABC366(A-G)
A - Election 2¶
题目大意
有 \(N\) 张选票(\(N\) 是奇数),有两个候选人,第一位候选人已经收到了 \(T\) 张选票,第二位候选人已经收到了 \(A\) 张选票,投票结束后选票多的人获胜。问:现在是否已经分出了选举的胜负?
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, a, b;
cin >> n >> a >> b;
n -= a + b;
if(a > b + n || b > a + n)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
B - Vertical Writing¶
题目大意
给你 \(N\) 行水平书写的字符串,将他们转换成垂直书写。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
size_t m = 0;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++)
{
cin >> s[i];
m = max(m, s[i].size());
}
for (size_t j = 0; j < m; j++)
{
int k = 0;
while (j >= s[k].size())
k++;
for (int i = n - 1; i >= k; i--)
cout << (j < s[i].size() ? s[i][j] : '*');
cout << '\n';
}
return 0;
}
C - Balls and Bag Query¶
题目大意
你需要维护一个数字集合,按顺序处理 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个操作,有三种不同类型的操作:
1 x
,在集合中加入一个数字 \(x\),相同的数字在集合中可以存在多个。2 x
,在集合中删除一个数字 \(x\),这个操作保证集合中至少有一个数字 \(x\)。3
查询集合中有多少个不同的数字。
解题思路
用一个 map
维护数字出现的次数即可。
参考代码
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
int n, op, x;
cin >> n;
unordered_map<int, int> cnt;
while(n--)
{
cin >> op;
if(op == 1)
{
cin >> x;
cnt[x]++;
}
else if(op == 2)
{
cin >> x;
auto it = cnt.find(x);
if(it->second == 1)
cnt.erase(it);
else
it->second--;
}
else
cout << cnt.size() << endl;
}
return 0;
}
D - Cuboid Sum Query¶
题目大意
给你一个 \(N \times N \times N (1 \le N \le 100)\) 的立方体,每个位置都写有一个数字。给你 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个询问,每个询问是一个六元组,表示一个子立方体的左下角坐标和右上角坐标,回答出这个子立方体的数字之和。
解题思路
三维前缀和模板题,不用记公式,容斥即可。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<vector<int>>> s(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
{
cin >> s[i][j][k];
s[i][j][k] += s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1] - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] + s[i - 1][j - 1][k - 1];
}
int q;
cin >> q;
while (q--)
{
int x1, x2, y1, y2, z1, z2;
cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
x1--, y1--, z1--;
cout << s[x2][y2][z2] - s[x1][y2][z2] - s[x2][y1][z2] - s[x2][y2][z1] + s[x2][y1][z1] + s[x1][y2][z1] + s[x1][y1][z2] - s[x1][y1][z1] << endl;
}
return 0;
}
E - Manhattan Multifocal Ellipse¶
题目大意
在二维平面上给你 \(N(2 \le N \le 10 ^5)\) 个点的坐标 \((x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\),其中 \(-10^6 \le x_i, y_i \le 10^6\),同时给你一个整数 \(D(0 \le D \le 10^6)\),求出平面上有多少个点满足 \(\sum\limits_{i = 1} ^ N(|x - x_i| + |y - y_i|) \le D\)
解题思路
设 \(s(x) = \sum\limits_{i = 1} ^ N|x - x_i|\),\(s(y) = \sum\limits_{i = 1} ^ N|y - y_i|\)
由于 \(0 \le D \le 10^6\) 且 \(-10^6 \le x_i, y_i \le 10^6\),因此符合条件的 \((x, y)\) 取值范围是 \(-2 \times10^6 \le x, y \le 2 \times 10^6\),我们可以先枚举 \(x\)。这样,我们还需要解决以下两个问题:
- 对于一个 \(x\),如何求出 \(s(x)\),需要用 \(O(1)\) 的时间求出 \(s(x)\)?
- 对于一个 \(x\),如何求出有多少个 \(y\) 满足 \(s(x) + s(y) \le D\) ?
先解决第一个问题。我们可以对所有的 \(x_i\)排序,然后枚举 \(x \in [-2 \times10^6, 2 \times10^6]\),逐步求出每一个 \(s(x)\) 的值,设有 \(L(x)\) 个 \(x_i\) 坐标小于等于 \(x\),则有:
所以只需要在遍历的时候维护好 \(L(x)\) 的值即可。这样我们可以预处理出 \(x \in [-2 \times10^6, 2 \times10^6]\) 所有的 \(s(x)\) 的值。
下面解决第二个问题:同样的,我们预处理出 \(y \in [-2 \times10^6, 2 \times10^6]\) 所有的 \(s(y)\) 值,然后对这个数组进行排序,然后每枚举到一个 \(x\) 的时候,直接二分有多少个 \(s(y)\) 值满足 \(s(x) + s(y) \le D\),不过更好的办法是直接双指针。
参考代码
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using LL = long long;
const int MAXC = 2E6;
const int LEN = MAXC * 2 + 1;
int main()
{
int n, d;
cin >> n >> d;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
x[i] += MAXC;
y[i] += MAXC;
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
auto cal_sum = [n](const vector<int> &x) -> vector<LL>
{
vector<LL> sum(LEN);
sum[0] = accumulate(x.begin(), x.end(), 0ll);
for (int i = 1, j = 0; i < LEN; i++)
{
sum[i] = sum[i - 1] + j - (n - j);
while (j < n && x[j] == i)
j++;
}
return sum;
};
vector<LL> xs = cal_sum(x);
vector<LL> ys = cal_sum(y);
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
LL ans = 0;
for(int i = LEN - 1, j = 0; i >= 0; i--)
{
while(j < LEN && xs[i] + ys[j] <= d)
j++;
ans += j;
}
cout << ans << endl;
return 0;
}
F - Maximum Composition¶
题目大意
有 \(N(2 \le N \le 2 \times 10 ^5)\) 个一次函数,第 \(i\) 个函数是 \(f_i(x) = A_ix + B_i\), 其中 \(1 \le A_i, B_i \le 50\)。你需要从中选择出 \(K(1 \le K \le \min(N, 10))\) 个不同的函数,假设选择的函数是 \(f_{p1}, f_{p2}, \cdots, f_{pK}\),你需要最大化 \(f_{p1}(f_{p2}(...f_{pK}(1)...))\) 的值。
解题思路
假设 \(K\) 个函数已经选好,考虑如何排列顺序。设有两个函数 \(f_i(x)\) 和 \(f_j(x)\),则将 \(f_i(x)\) 放在外侧更优等价于:
因此,只需要按照 \(\frac{(A_i - 1)}{B_i}\) 升序排序,\(\frac{(A_i - 1)}{B_i}\) 较大的函数应该作用在外部。
下面考虑如何选择出 \(K\) 个函数,直接 dp 就可以了。定义 \(dp[i][j]\) 表示在(排序后的)前 \(i\) 个函数中选择 \(j\) 个能获得的最大值,显然有 \(dp[i][j] = \max(dp[i-1][j], A_j(dp[i-1][j-1]) + B_j)\)
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
struct Fun
{
LL a, b;
bool operator>(const Fun &other) const { return (a - 1) * other.b < (other.a - 1) * b; }
};
int main()
{
int n, k;
cin >> n >> k;
vector<Fun> f(n);
for (int i = 0; i < n; i++)
cin >> f[i].a >> f[i].b;
sort(f.begin(), f.end(), greater<Fun>());
vector<LL> dp(k + 1);
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = k; j; j--)
dp[j] = max(dp[j], f[i].a * dp[j - 1] + f[i].b);
cout << dp[k] << endl;
return 0;
}
G - XOR Neighbors¶
题目大意
给你一个 \(N(1 \le N \le 60)\) 个点 \(M(0 \le M \le N(N-1)/2)\) 的无向简单图。你需要给图中的每个点都写上一个 \([1, 2^{60}-1]\) 之间的数字,同时满足以下条件:
- 对于图中每个点 \(u\),点 \(u\) 的所有邻居的数字的异或和为 \(0\)
如果存在一种方案能满足这个条件,输出 Yes
,同时输出每个点的数字。否则输出 No
解题思路
高斯消元解异或方程组的模板题,前置知识:高斯消元 - OI Wiki、P3389 【模板】高斯消元法 - 洛谷、P2455 [SDOI2006] 线性方程组 - 洛谷、P2447 [SDOI2010] 外星千足虫 - 洛谷。
图中有 \(N\) 个点,每个点的邻居的数字的异或和都为 \(0\),因此我们可以得到一个异或方程组。但这里要注意每个点的数字不能是 \(0\),也就是说这个异或方程组是有无穷多个解的。由于最多 \(60\) 个点,取值范围也是 \(60\) 位,可以强行指定第 \(i\) 个点的第 \(i\) 位为 \(1\),这样就可以保证每个点都非 \(0\)。然后就是枚举每一位,求解出异或方程即可。
参考代码
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int MAXN = 64;
int n, m;
bool gauss(vector<LL> &ans, vector<bitset<MAXN>> mat, int pos)
{
bitset<MAXN> spec;
spec[pos] = spec[n] = 1;
mat.push_back(spec);
for (int i = 0; i < n; i++)
{
for (int r = i; r <= n; r++)
if (mat[r][i])
{
swap(mat[i], mat[r]);
break;
}
if (!mat[i][i])
continue;
for (int r = 0; r <= n; r++)
if (r != i && mat[r][i])
mat[r] ^= mat[i];
}
if (mat[n][n])
return false;
for (int c = 0; c < n; c++)
ans[c] |= ((long long)mat[c][n]) << pos;
return true;
}
int main()
{
cin >> n >> m;
vector<bitset<MAXN>> mat(n);
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
u--, v--;
mat[u][v] = mat[v][u] = 1;
}
vector<LL> ans(n);
for (int i = 0; i < n; i++)
if (!gauss(ans, mat, i))
{
cout << "No" << endl;
return 0;
}
cout << "Yes" << endl;
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
return 0;
}
创建日期: 2024-11-04