Atcoder Beginner Contest 353
A
问题陈述
有 \(N\) 幢楼房排列成一排。左起的 \(i\) th楼高 \(H_i\) 。
请判断是否有比左起第一座高的建筑物。如果存在这样的建筑物，请找出从左边起最左边的建筑物的位置。
思路
签到题。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, mx = -1, id = -1;
cin >> n;
for (int i = 1, a; i <= n; i ++) {
cin >> a;
if (i == 1) mx = a;
if (a > mx) {
mx = a, id = i;
break;
}
}
cout << id << endl;
return 0;
}
B
问题陈述
AtCoder 游乐园有一个可容纳 \(K\) 人的景点。现在，有 \(N\) 组游客在排队等候进入该景点。
排在最前面的 \(i\) 组有 \((1\leq i\leq N)\) 人。对于所有 \(i\) \((1\leq i\leq N)\) ，都成立 \(A_i \leq K\) 。
高桥作为该景点的工作人员，将按照以下程序引导各组游客排队。
最初，没有人被引导到景点，有 \(K\) 个空座位。
- 如果排队队伍中没有团体，则启动景点并结束引导。
-
- 将景点中的空座位数量与排队队伍前方的团队人数进行比较，然后执行以下操作之一：
- 如果空座位数量少于排在队伍前列的人数，则启动景点。然后，空座位数量再次变为 \(K\) 。
- 否则，引导排在队伍最前面的整组人前往景点。排在最前面的那组游客将被移出队列，空座位数量将按照该组游客的人数减少。
- 返回步骤 1。
在此，引导开始后不会再有其他小组排队。在这些条件下，可以证明这一过程将在有限步数内结束。
确定在整个引导过程中要启动多少次吸引力。
思路
模拟。
代码
#include <bits/stdc++.h>
using namespace std;
int n, k, a[105], ans = 1, now, p = 1;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> a[i];
now = k;
while (1) {
if (p == n + 1) break;
if (a[p] > now) {
ans ++;
now = k;
continue;
}
now -= a[p], p ++;
}
cout << ans << endl;
return 0;
}
C
问题陈述
对于正整数 \(x\) 和 \(y\) ，定义 \(f(x, y)\) 为 \((x + y)\) 除以 \(10^8\) 的余数。
给你一个长度为 \(N\) 的正整数序列 \(A = (A_1, \ldots, A_N)\) 。求下面表达式的值：
\(\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)\)
\(1 \le A_i < 10^8\)
思路
注意到每个数都小于模数，所以 \((A_i+A_j) \mod 10^8\) 只可能等于 \(A_i+A_i\) 或 \(A_i+A_j-10^8\) 。
注意到每个数都会与其他的数做一次加法，而加法具有交换律，所以可以将原数列排序而不影响答案。
排序后，对于每个 \(A_i\)，把它和 \(A_{1,\ldots,i-1}\) 求和，减去的 \(10^8\)，可以通过二分求出大于等于 \(10^8-A_i\) 的数的个数。剩余部分可用前缀和完成。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e8;
const int N = 3e5 + 5;
ll n, a[N], ans, sum;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1);
sum = a[1];
for (int i = 2, pos; i <= n; i ++) {
pos = upper_bound(a + 1, a + i, mod - a[i] - 1) - a;
ans += (i - 1) * a[i] + sum - (i - pos) * mod;
sum += a[i];
}
cout << ans << endl;
return 0;
}
D
问题陈述
对于正整数 \(x\) 和 \(y\) ，定义 \(f(x, y)\) 如下：
- 将 \(x\) 和 \(y\) 的十进制表示解释为字符串，并按此顺序连接，得到字符串 \(z\) 。将 \(f(x, y)\) 解释为十进制整数时，其值就是 \(z\) 的值。
例如， \(f(3, 14) = 314\) 和 \(f(100, 1) = 1001\) 。
给你一个长度为 \(N\) 的正整数序列 \(A = (A_1, \ldots, A_N)\) 。求下面表达式取模 \(998244353\) 的值：
\(\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)\)
思路
记 \(c(A_i)\) 为 \(A_i\) 位数，\(w(A_i)\) 为 \(A_i\) 的位权，\(w(A_i)=10^{c(A_i)}\)。
有 \(f(A_i,A_j)=A_i·w(A_j)+A_j\)。
原式
\(=\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)\)
\(=\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N A_i·w(A_j)+A_j\)
\(=\displaystyle\sum_{i=1}^{N-1}A_i·\sum_{j=i+1}^N w(A_j)+\sum_{j=i+1}^N A_j\)
分别用两个前缀和维护位权以及和即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 3e5 + 5;
ll n, a[N], b[N], c[N], ans;
ll getw(ll x) {
ll res = 1;
while (x) res *= 10, res %= mod, x /= 10;
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = n; i >= 1; i --) {
b[i] = b[i + 1] + a[i], b[i] %= mod;
c[i] = c[i + 1] + getw(a[i]), c[i] %= mod;
}
for (int i = 1; i < n; i ++)
ans += b[i + 1] + a[i] * c[i + 1] % mod, ans %= mod;
cout << ans << endl;
return 0;
}
E
问题陈述
对于字符串 \(x\) 和 \(y\) ，定义 \(f(x, y)\) 如下：
- \(f(x, y)\) 是 \(x\) 和 \(y\) 的最长公共前缀的长度。
给定由小写英文字母组成的 \(N\) 字符串 \((S_1, \ldots, S_N)\) 。求以下表达式的值：
\(\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)\)
思路
看到最长公共前缀，想到使用Trie维护。把 \(N\) 个字符串建在一颗Trie里，维护经过每条边的字符串的个数 \(c_i\) ，则每条边对答案的贡献为 \(\frac{c_i(c_i-1)}{2}\) 。因为每个字符串都会与其它字符串产生 \(1\) 的贡献，会重复一次，故除二。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, son[N][27], cnt = 1; ll sum[N], ans;
void insert(const string& s) {
int p = 1;
for (int i = 0; i < s.size(); i ++) {
char c = s[i];
if (!son[p][c - 'a']) son[p][c - 'a'] = ++ cnt;
sum[son[p][c - 'a']] ++;
p = son[p][c - 'a'];
}
}
void dfs(int p) {
if (p ^ 1) ans += sum[p] * (sum[p] - 1) / 2;
for (int i = 0; i < 26; i ++) {
if (!son[p][i]) continue;
dfs(son[p][i]);
}
}
int main() {
cin >> n;
string s;
for (int i = 1; i <= n; i ++) {
cin >> s;
insert(s);
}
dfs(1);
cout << ans << endl;
return 0;
}
F
未做出，待补。
G
问题陈述
AtCoder 王国有 \(N\) 个城镇：城镇 \(1\) 、 \(2\) 、 \(\ldots\) 、 \(N\) 。从 \(i\) 镇到 \(j\) 镇，必须支付 \(C \times |i-j|\) 日元的过路费。
商人高桥正在考虑参加 \(M\) 个或更多即将到来的市场。
\(i\) /-市场 \((1 \leq i \leq M)\) 由一对整数 \((T_i, P_i)\) 描述，其中市场在城镇 \(T_i\) 举行，如果他参加将赚取 \(P_i\) 日元。
在所有 \(1 \leq i < M\) 中， \(i\) (次)市场在 \((i+1)\) (次)市场开始之前结束。他移动的时间可以忽略不计。
他从 \(10^{10^{100}}\) 日元开始，最初在 \(1\) 镇。通过优化选择参与哪些市场以及如何移动，确定他可以获得的最大利润。
从形式上看，如果他在 \(M\) 个市场后拥有的资金量最大，那么 \(10^{10^{100}} + X\) 就是他的最终资金量。求 \(X\) 。
思路
定义 \(dp_{T_i}\) 表示考虑到前 \(i\) 个市场的最大收益。
\[dp_{T_i}=\max_{1\le j < i} dp_{T_j}-C·|T_i-T_j|+P_i \]变形后可得：
\[dp_{T_i}=\max (\max_{1\le j <i,1\le T_j \le T_i} dp_{T_j}-CT_i+CT_j+P_i) (\max_{1\le j <i,T_i\le T_j \le n} dp_{T_j}+CT_i-CT_j+P_i) \]移除与 \(j\) 无关的项，可以发现取 \(\max\) 的式子有 \(dp_{T_j}+CT_j\) \(dp_{T_j}-CT_j\) 。
用线段树维护这两个内容即可。时间复杂度 \(O(m\log n)\) 。
代码
#include <bits/stdc++.h>
#define INF LONG_LONG_MAX
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, c, m, t[N], p[N], ans;
struct segt {
struct node {
int l, r, mx;
} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].mx = -INF;
if (l == r) return ;
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
int query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p].mx;
int res = -INF;
if (t[ls].r >= l) res = max(res, query(ls, l, r));
if (t[rs].l <= r) res = max(res, query(rs, l, r));
return res;
}
void modify(int p, int id, int v) {
if (t[p].l == t[p].r) {
t[p].mx = v;
return ;
}
if (id <= t[ls].r) modify(ls, id, v);
else modify(rs, id, v);
t[p].mx = max(t[ls].mx, t[rs].mx);
}
} F, B;
signed main() {
cin >> n >> c >> m;
for (int i = 1; i <= m; i ++) cin >> t[i] >> p[i];
F.build(1, 1, n), B.build(1, 1, n);
F.modify(1, 1, c), B.modify(1, 1, -c);
for (int i = 1, x; i <= m; i ++) {
x = F.query(1, 1, t[i]) - c * t[i] + p[i];
x = max(x, B.query(1, t[i], n) + c * t[i] + p[i]);
ans = max(ans, x);
F.modify(1, t[i], x + c * t[i]);
B.modify(1, t[i], x - c * t[i]);
}
cout << ans << endl;
return 0;
}