ABC353(A-G)
我的评价是：A-E 非常简单，\(F\) 比 \(G\) 难
A - Buildings¶
题目大意
给你 \(N\) 个数字 \(H = (H_1, H_2, \cdots, H_N)\)，找到第一个比 \(H_1\) 大的位置，如果不存在这样的数，输出 -1。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, h1, hi;
cin >> n >> h1;
for(int i = 2; i <= n; i++)
{
cin >> hi;
if(hi > h1)
{
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
B - AtCoder Amusement Park¶
题目大意
有一个娱乐设施最多能容纳 \(K\) 个人同时游玩。有 \(N\) 个旅行团正在排队，第 \(i\) 个旅行团有 \(A_i(A_i \le K)\) 个人。一个旅行团的人要么一起进去游玩，要么都不进去游玩。\(N\) 个旅行团正在排队，轮到一个旅行团的时候，如果设施内还有足够的空位，则这个旅行团一起进去游玩，否则他们会等到下一轮。问：最少需要多少轮才能让所有旅行团都游玩？
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, h1, hi;
cin >> n >> h1;
for(int i = 2; i <= n; i++)
{
cin >> hi;
if(hi > h1)
{
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
C - Sigma Problem¶
题目大意
对于正整数 \(x\) 和 \(y\)，定义 \(f(x, y)\) 为 \(x+y\) 除以 \(10^8\) 的余数。
给你 \(N(2 \le N \le 3 \times 10^5)\) 个正整数，第 \(i\) 个数是 \(A_i(1 \le A_i < 10^8)\)，求出 \(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^{N} f(A_i, A_j)\)
解题思路
将数字排序，然后枚举 \(A_j\)，在枚举时因为数组已经有序，且所有数字都小于 \(10^8\)，可以二分出最后一个相加后不会溢出的位置 \(mid\)，则 \([1, mid]\) 以及 \([mid+1, j-1]\) 都可以通过前缀和来快速计算出答案。
参考代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int mod = 1E8;
int main()
{
int n;
cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a.begin(), a.end());
vector<LL> s(n+1);
for(int i = 1; i <= n; i++)
s[i] = s[i-1] + a[i];
auto get_sum = [&](int l, int r) -> LL {return s[r] - s[l-1];};
LL ans = 0;
for(int i = 2; i <= n; i++)
{
int mid = lower_bound(a.begin()+1, a.begin() + i, mod-a[i]) - a.begin();
if(mid)
ans += get_sum(1, mid-1) + (LL)(mid-1) * a[i];
if(mid < i)
ans += get_sum(mid, i-1) + (LL)(i-mid) * (a[i] - mod);
}
cout << ans << endl;
return 0;
}
D - Another Sigma Problem¶
题目大意
对于正整数 \(x\) 和 \(y\)，定义 \(f(x, y)\)：
- 设 \(X\) 表示正整数 \(x\) 对应的字符串，\(Y\) 表示正整数 \(y\) 对应的字符串，则 \(X\) 和 \(Y\) 字符串拼接的结果对应的正整数就是 \(f(x, y)\) 的结果。
例如，\(f(3, 14) = 314\)，\(f(100, 1) = 1001\)
给你 \(N(2 \le N \le 2 \times 10^5)\) 个正整数，第 \(i\) 个数是 \(A_i(1 \le A_i < 10^9)\)，求出 \(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^{N} f(A_i, A_j)\)，答案对 \(998244353\) 取模。
解题思路
显然 \(f(x, y)\) 是没有交换律的，所以不能排序。
设 \(|Y|\) 表示数字 \(y\) 对应的字符串的长度，则有 $f(x, y) = 10 ^ {|Y|} \times x + y $，我们可以枚举 \(j\)，则对于 \(A_j = y\)，贡献就是 \(\sum\limits_{i=1}^{j-1} f(A_i, A_j) = \sum\limits_{i=1}^{j-1}(10 ^ {|A_j|} \times A_i + A_j) = 10 ^ {|A_j|} \sum\limits_{i=1}^{j-1}A_i + (j-1) \times A_j\) 。
维护前缀和，上式可在 \(O(1)\) 时间内计算。
参考代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int mod = 998244353;
int main()
{
int n;
cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; i++)
cin >> a[i];
vector<LL> s(n+1);
for(int i = 1; i <= n; i++)
s[i] = (s[i-1] + a[i]) % mod;
auto get_sum = [&](int l, int r) -> LL {return (s[r] - s[l-1] + mod) % mod;};
auto cal_len = [](int x) -> int {
int len = 0;
while(x)
{
len++;
x /= 10;
}
return len;
};
vector<int> p{1};
for(int i = 1; i <= 10; i++)
p.emplace_back(p[i-1] * 10 % mod);
LL ans = 0;
for(int j = 2; j <= n; j++)
{
int k = cal_len(a[j]);
ans += get_sum(1, j-1) * p[k] % mod + (LL)(j-1) * a[j] % mod;
ans %= mod;
}
cout << ans << endl;
return 0;
}
E - Yet Another Sigma Problem¶
题目大意
对于字符串 \(x\) 和 \(y\)，定义 \(f(x, y)\) 为 \(x\) 和 \(y\) 的最长公共前缀的长度。
给你 \(N(2 \le N \le 2 \times 10^5)\) 个字符串，第 \(i\) 个字符串是 \(S_i(\sum\limits_{i=1}^N|S_i| \le 3 \times 10^5)\)，求出 \(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^{N} f(S_i, S_j)\)
解题思路
考虑如何计算 \(f(S_i, S_j)\)，暴力的算法无非就是一个下标开始枚举，找到第一个不相等的位置。我们会发现，在这个过程中，每有一个字符相等，那么答案就会 \(+1\)。
因此，我们按以此将所有字符串插入一棵 Trie 树，插入字符串会让这个字符串对应的路径上的所有节点的权值都 \(+1\)，则查询相当于查询字符串对应路径的权值之和。
实际写法更简单，只需要管插入，在插入时顺便把答案也查询出来就好了。
参考代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn = 3E5 + 10;
class Trie
{
public:
auto insert(const string &s) -> int
{
int ans = 0, p = 1;
for(auto ch : s)
{
int id = ch - 'a';
if(!next[p][id])
next[p][id] = idx++;
p = next[p][id];
ans += cnt[p]++;
}
return ans;
}
private:
int next[maxn][26], cnt[maxn], idx = 2;
}t;
int main()
{
int n;
cin >> n;
LL ans = 0;
string s;
while(n--)
{
cin >> s;
ans += t.insert(s);
}
cout << ans << endl;
return 0;
}
F - Tile Distance¶
题目大意
在二维平面上，有两种砖块，一种是 \(1 \times 1\) 的小砖块，另一种是 \(K \times K\) 的大砖块。对于某个左下角坐标 \((i, j)\)，如果 \(\lfloor\frac{i}{K}\rfloor + \lfloor\frac{j}{K}\rfloor\) 是偶数，则以 \((i, j)\) 作为左下角的 \(1 \times 1\) 范围是小砖块，否则以 \((i, j)\) 作为左下角的 \(K \times K\) 范围是大砖块。
砖块与砖块之前间互不重叠。
例如下图是 \(K=3\) 的情况下的例子：
在这个平面上，你可以进行移动，每一次移动从上下左右选择一个方向，移动 \(1\) 单位的距离。在大砖块内部移动无需花费金钱。当你从一个小砖块移动到相邻的大砖块，或者从大砖块移动到相邻的小砖块时，需要花费 \(1\) 元。
现在，你的起点是 \((S_x+0.5, S_Y+0.5)\)，终点是 \((T_x+0.5, T_Y+0.5)\)，问：最少花费多少元才能到达？
数据范围：
- 所有的输入都是整数。
- \(0 \le S_x, S_Y, T_x, T_Y \le 2 \times 10^{16}\)
解题思路
可以发现 \(k=1\) 时曼哈顿距离就是答案。
当 \(k > 3\) 时，可以发现斜着走到一个大格子只需要花费 \(2\)，如下图所示。而使用这种方法，可以用 \(4\) 的花费走到一个直线相邻的格子，因此比较好的走法就是优先走斜的大格子，然后再走直线的小格子。
但是有一个特例是 \(k = 2\) 时，此时走直线也是 \(2\) 花费。
所以关键就是枚举起点和终点的大格子，按照大格子的计算方式即可。
代码赛时没有写出来。
G - Merchant Takahashi¶
题目大意
有 \(N(1 \le N \le 2 \times 10^5)\) 个 城镇，从城镇 \(i\) 移动到城镇 \(j\) 需要花费 \(C \times |i-j|\) 元，你是一个商人，初始的时候在城镇 \(1\)。接下里按照时间顺序有 \(M(1 \le M \le 2 \times 10^5)\) 个集会，第 \(i\) 个集会在城镇 \(T_i\) 举行，你可以决定参加这场集会，你将支付在城镇间移动的费用，同时收获 \(P_i\) 元。这些集会是按照时间顺序进行的，且任意两场集会的时间都不重合，城镇间移动所耗费的时间忽略不计。
初始时你有 \(0\) 元，在任意时刻，你的现有资金可以为负，问：在 \(M\) 次集会结束之后，你最多能拥有多少钱？
解题思路
每次集会只有去或者不去两种决策，如果按照线性 \(dp\) 的方式考虑，无法确定上一次的位置，因此 \(dp\) 的状态需要考虑商人的位置。
定义 \(dp[i][j]\) 表示前 \(i\) 场集会后商人的位置在城镇 \(j\) 的最佳答案，显然如果不参加第 \(i\) 场集会， \(dp[i][j]\) 的状态直接继承 \(dp[i-1][j]\)，而如果参加，也仅仅会影响到 \(dp[i][T_i]\) 的值，其他的值仍然继承。因此可优化成一维的 \(dp[j]\)。
对于第 \(i\) 场集会，令 \(j = T_i\) ，如果参加，则需要枚举上一次的位置 \(k\)，转移式为： $$ dp[j] = \max_{k=1}^N(dp[k] + C \times |j-k| + P_i) $$ 拆开绝对值可得： $$ \begin{aligned} dp[j] & = \max(\max_{k=1}^j(dp[k] + C \times (j-k) + P_i), \max_{k=j}^N(dp[k] + C \times (k-j) + P_i)) \ & = \max{(\max_{k=1}^j(dp[k] - C \times k) + C \times j), (\max_{k=j}^N(dp[k] + C \times k) - C \times j)} + P_i \end{aligned} $$ 关键就是如何算出 \(\max\limits_{k=1}^j(dp[k] - C \times k)\) 和 \(\max\limits_{k=j}^N(dp[k] + C \times k)\)，只需要把 \(dp[k] - C \times k\) 和 \(dp[k] + C \times k\) 都存到线段树里即可（所有节点都存两种值）。
计算出 \(dp[j]\) 之后，计算出新的 \(dp[j]-C \times j\) 和 \(dp[j] + C \times j\)，单点修改即可。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL pinf = -1E15;
class SegmentTree
{
public:
SegmentTree(int n, LL C) : C(C), add(4*n), sub(4*n)
{
build(1, 1, n);
update(1, 1, n, 1, 0);
}
void build(int p, int beg, int end)
{
if(beg == end)
{
add[p] = sub[p] = pinf;
return;
}
int mid = (beg + end) / 2;
int lch = p * 2, rch = p * 2 + 1;
build(lch, beg, mid);
build(rch, mid+1, end);
push_up(p);
}
LL get_add(int p, int beg, int end, int l, int r)
{
if(end < l || beg > r)
return pinf;
if(beg >= l && end <= r)
return add[p];
int mid = (beg + end) / 2;
int lch = p * 2, rch = p * 2 + 1;
return max(get_add(lch, beg, mid, l, r), get_add(rch, mid+1, end, l, r));
}
LL get_sub(int p, int beg, int end, int l, int r)
{
if(end < l || beg > r)
return pinf;
if(beg >= l && end <= r)
return sub[p];
int mid = (beg + end) / 2;
int lch = p * 2, rch = p * 2 + 1;
return max(get_sub(lch, beg, mid, l, r), get_sub(rch, mid+1, end, l, r));
}
void update(int p, int beg, int end, int pos, LL k)
{
if(beg == end)
{
add[p] = k + C * beg;
sub[p] = k - C * beg;
return;
}
int mid = (beg + end) / 2;
int lch = p * 2, rch = p * 2 + 1;
pos <= mid ? update(lch, beg, mid, pos, k) : update(rch, mid+1, end, pos, k);
push_up(p);
}
private:
LL C;
vector<LL> add, sub;
void push_up(int p)
{
int lch = p * 2, rch = p * 2 + 1;
add[p] = max(add[lch], add[rch]);
sub[p] = max(sub[lch], sub[rch]);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
LL C;
cin >> N >> C;
vector<LL> now(N+1, pinf);
now[1] = 0;
SegmentTree t(N, C);
int M, T;
LL P;
cin >> M;
while(M--)
{
cin >> T >> P;
LL val = max(t.get_add(1, 1, N, 1, T) - C * T, t.get_sub(1, 1, N, T, N) + C * T) + P;
if(val > now[T])
{
now[T] = val;
t.update(1, 1, N, T, now[T]);
}
}
cout << *max_element(now.begin(), now.end()) << endl;
return 0;
}
创建日期: 2024-05-22