AtCoder Beginner Contest 285
A - Edge Checker 2
题意
判断一个完全二叉树，两个节点是否直接相连
分析
\(a=b*2 或者 a=b*2+1(a<b) a、b\)相连
void solve() {
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
if (a * 2 == b || a * 2 + 1 == b) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
B - Longest Uncommon Prefix
题意
字符串s(len(s)=N)；对于每一个\(i(1 \leq i \leq N-1)\)都找出满足：
- \(l+i \leq N\)
- \(1 \leq k \leq l, s[k] != s[k + 1]\)
的最大\(l\)。
分析
5000数据范围，直接暴力对每一位i从1开始向后一位一位匹配。
const int N = 5010;
string s;
int a[N], n;
void solve() {
cin >> n;
cin >> s;
s = "#" + s;
for (int i = 1; i <= n - 1; i++) {
int len = 0;
for (int j = 1; j + i <= n;j++) {
if (s[j] != s[j + i]) len++;
else break;
}
cout << len << '\n';
}
}
C - abc285_brutmhyhiizp
题意
A~Z: 1~26
AA~ZZ: 27~...
AAA~ZZZ: ...~...
分析
将字符串当成26进制数，直接进行进制转换，我们先将字符串转化为数字，题目中的最大只会到1e16，longlong可存。
ll x;
int num[20], len;
void solve() {
string s; cin >> s;
int len = SZ(s);
for (int i = 0; i < len; i++) {
x = x * 26 + s[i] - 'A' + 1;
}
cout << x << "\n";
}
D - Change Usernames
题意
有n个人，每个人手上有个字符串s，他们想将字符串改成t，t可能在别人手上，问每个人是否可以都拿到自己想要的。
分析
很明显的图联通问题，抽象成给定一个有向图，图中是否有环，可以用并查集或者拓扑序来考虑判环，这里采取了并查集写法。
const int N = 200010; // 二倍点数
int p[N], n, m, id;
map<string, int> mp;
int find(int x) {
return x != p[x] ? p[x] = find(p[x]) : x;
}
void solve() {
cin >> n;
bool f = 1;
for (int i = 1; i <= 2 * n; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
string x, y;
cin >> x >> y;
if (!mp[x]) mp[x] = ++id;
if (!mp[y]) mp[y] = ++id;
int px = find(mp[x]);
int py = find(mp[y]);
if (px != py) {
p[px] = py;
} else {
f = false;
}
}
puts(f ? "Yes" : "No");
}
E - Work or Rest
题意
定义一周有n天，其中可能有m天休息日，n-m天工作日，周是连续的，第一周第二周第三周...排下去。注意这个m题目未要求，但m必须大于1
给定一个序列A[N], 下标从一开始
现在工作日会有产能，定义为工作日d产能: \(B_d = A_{min(pre, suf)}\)，pre为d距离上一次休息日的天数，suf为距离最近后一次休息日的距离，如果d为休息日则\(B_d=0\)。
问如何安排休息日，可以使一周的产能最大，求出最大产能。
分析
参考了官方题解
不复制粘贴了。简单来说，就是定义dp[i][j]：考虑完前i天后，目前有j天连续的工作日的最大产能，例如：
状态dp[5][2]: _ _ 1 0 0,前面的 _ 我们不关心，我们只看最后有多少天连续。
转移方程：
\[dp[i+1][j+1] = dp[i][j] \]\[dp[i+1][0] = dp[i][j] + B[j] \]\(B_j\)为这j个数产生的产能，可以找规律发现，
\(j = 1, B_j = A_1\)
\(j = 2, B_j = A_1 * 2\)
\(j = 3, B_j = A_1 * 2 + A_2\)
\(j = 4, B_j = A_1 * 2 + A_2 * 2\);
...
综上 \(B_j = \sum_{i=1}^{j}A_{\frac{i+1}{2}}\)
const int N = 5010;
ll dp[N][N], n, m;
ll a[N], b[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] + a[(i+1)/2];
}
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++)
dp[i][j] = -1e18;
dp[1][0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= n; j++) {
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + b[j]);
}
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[n][i] + b[i]);
}
cout << ans << '\n';
}
F - Substring of Sorted String
题意
给定一个字符串s，以及两个操作：
- 1 x c 将s[x]改为c
- 2 l r 询问s[l-r]是否为t的字串，t为将s升序排列后的字符串
\(|s| \leq 1e5, q \leq 1e5\)
分析
首先s[l, r]是t的字串，那么s[l, r]一定升序，且\(min \leq x \leq max\)这部分仅在[l, r]中出现，如果在[l, r]之外出现，那么排序之后，一定会取代某些字符，从而[l, r]区间排完序之后发生改变。
如何维护？ 我们的目标是快速求出区间信息：
- 是否升序
- 区间字符出现的次数
具体来说： 我们容易维护s中每种字符出现的次数，我们只需要求出区间[l, r]，每种字符出现的次数，然后再进行比较，因为如果只在l, r出现，那么对于字符x， \(s[1, n].cnt[x]=s[l, r].cnt[x]\)。
以上区间信息可以使用线段树维护，不懂怎么优雅的维护区间字符出现次数，好在字符集很小，为26，我们可以直接在线段树中记录一个数组，来统计每种字符出现的次数。详细的看代码。
const int N = 100010;
int n, m;
char S[N];
int cnt[30]; // S中每种字符出现次数
struct Seg{
char mx, mn; // 区间最小最大值
int cnt[30], tag; // 区间每种字符出现次数，以及是否升序tag
Seg operator + (const Seg& B) const {
Seg res;
res.mx = max(mx, B.mx);
res.mn = min(mn, B.mn);
res.tag = tag | B.tag;
for (int i = 1; i <= 26; i++) res.cnt[i] = cnt[i] + B.cnt[i];
return res;
}
} tr[N * 4];
void pushup(int p) {
tr[p] = tr[lp] + tr[rp];
if (tr[lp].mx > tr[rp].mn) tr[p].tag = 1; // 更新tag
}
void build(int p, int l, int r) {
if (l == r) {
tr[p].mx = tr[p].mn = S[l];
tr[p].cnt[S[l] - 'a' + 1] = 1, tr[p].tag = 0;
} else {
int mid = (l + r) / 2;
build(lp, l, mid), build(rp, mid + 1, r);
pushup(p);
}
}
void modify(int p, int l, int r, int x, char d) {
if (l == r) {
tr[p].cnt[tr[p].mx - 'a' + 1] = 0;
tr[p].mx = tr[p].mn = d;
tr[p].cnt[d - 'a' + 1] = 1;
return ;
}
int mid = (l + r) / 2;
if (x <= mid) modify(lp, l, mid, x, d);
if (x > mid) modify(rp, mid + 1, r, x, d);
pushup(p);
}
Seg query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tr[p];
}
int mid = (l + r) / 2;
if (L > mid) return query(rp, mid + 1, r, L, R);
else if (R <= mid) return query(lp, l, mid, L, R);
else {
auto LL = query(lp, l, mid, L, R);
auto RR = query(rp, mid + 1, r, L, R);
auto res = LL + RR;
if (LL.mx > RR.mn) res.tag = 1;
return res;
}
}
int main() {
cin >> n >> S + 1 >> m;
for (int i = 1; i <= n; i++) {
cnt[S[i] - 'a' + 1]++;
}
build(1, 1, n);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x; char c;
cin >> x >> c;
modify(1, 1, n, x, c);
cnt[S[x] - 'a' + 1]--;
S[x] = c;
cnt[c - 'a' + 1]++;
} else {
int l , r;
cin >> l >> r;
Seg x = query(1, 1, n, l, r);
bool f = 0;
for (int i = 1; i <= 26; i++) {
if (x.mn - 'a' + 1 < i && i < x.mx - 'a' + 1) {
if (cnt[i] != x.cnt[i]) {
f = 1;
break;
}
}
}
if (x.tag || f) {
cout << "No\n";
} else {
cout << "Yes\n";
}
}
}
return 0;
}