目录
A - STring
用栈模拟一下即可，具体的，当栈顶出现形如 ST 时，将其弹出。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
int main() {
string s;
cin >> s;
stack<char> st;
int i, n = s.size();
for(i = 0; i < n; i++) {
if(s[i] == 'T' && !st.empty() && st.top() == 'S') {
st.pop();
}
else {
st.emplace(s[i]);
}
}
Write(st.size());
return 0;
}
B - Minimum Sum
考虑将每个数的贡献拆开，从最小的数开始考虑，包括这个最小数的区间的最小值一定是该数，而剩下的区间正好被最小值拆成两半，可以递归地去做。
具体的，用 ST 表维护区间内最小值的位置，设这个最小值的位置为第 \(x\) 位，当前区间为 \([l, r]\)，则贡献为 \(a_x \cdot (r - x + 1) \cdot (x - l + 1)\)，再递归区间 \([l, x - 1]\) 及 \([x + 1, r]\)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 200005, lgN = 20;
int n, a[N], lg[N];
void Init_lg() {
int i;
for(i = 2; i < N; i++) {
lg[i] = lg[i >> 1] + 1;
}
}
struct ST_Table {
int f[lgN][N], g[lgN][N];
void Init() {
int i, j;
for(i = 1; i <= n; i++) {
f[0][i] = a[i], g[0][i] = i;
}
for(i = 1; i <= lg[n]; i++) {
for(j = 1; j + (1 << i) - 1 <= n; j++) {
if(f[i - 1][j] < f[i - 1][j + (1 << (i - 1))]) {
f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
}
else {
f[i][j] = f[i - 1][j + (1 << (i - 1))], g[i][j] = g[i - 1][j + (1 << (i - 1))];
}
}
}
}
int Query(int l, int r) {
int len = lg[r - l + 1];
int x = f[len][l], y = f[len][r - (1 << len) + 1];
return x < y ? g[len][l] : g[len][r - (1 << len) + 1];
}
}st;
ll Solve(int l, int r) {
if(l > r) {
return 0;
}
int x = st.Query(l, r);
return Solve(l, x - 1) + Solve(x + 1, r) + 1ll * (x - l + 1) * (r - x + 1) * a[x];
}
int main() {
int i;
n = Read();
for(i = 1; i <= n; i++) {
a[i] = Read();
}
Init_lg(), st.Init();
Write(Solve(1, n));
return 0;
}
C - Tree Restoring
回忆直径的定义，注意到 \(\max a_i\) 即为直径长度 \(d\)，因此我们先建出这个直径。
设直径的两个端点为 \(u, v\)，根据直径的性质，\(a_x = \max\{\operatorname{dis}(u, x), \operatorname{dis}(v, x)\}\)。
对于 \(d\) 的奇偶性分类讨论，对于 \(k\) 是偶数的情况，需要 \(\frac{d}{2} + 1 \sim d\) 的 \(a_i\) 各两个，\(\frac{d}{2}\) 的 \(a_i\) 一个；对于 \(k\) 是奇数的情况，需要 \(\frac{d + 1}{2} \sim d\) 的 \(a_i\) 各两个。于是 \(a_i\) 不够可以直接判无解。
对于剩下的点，我们可以在直径上挂着，可以证明，当 \(k\) 是偶数时，挂的点 \(a_i\) 的取值范围为 \([\frac{d}{2} + 1, d]\)；当 \(k\) 是奇数时，挂的点 \(a_i\) 的取值范围为 \([\frac{d + 3}{2}, d]\)。
注意特判 \(d = 1\) 的情况。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 105;
int n, a[N], cnt[N];
int main() {
int i, d = 0;
n = Read();
for(i = 1; i <= n; i++) {
int a = Read();
d = max(d, a);
cnt[a]++;
}
if(d == 1) {
printf(n > 2 ? "Impossible" : "Possible");
return 0;
}
for(i = d; i > d / 2; i--) {
if(cnt[i] < 2) {
printf("Impossible");
return 0;
}
}
if(d % 2 == 0 && cnt[d / 2] != 1) {
printf("Impossible");
return 0;
}
if(d & 1 && cnt[(d + 1) / 2] != 2) {
printf("Impossible");
return 0;
}
for(i = 1; i < (d + 1) / 2; i++) {
if(cnt[i]) {
printf("Impossible");
return 0;
}
}
printf("Possible");
return 0;
}