noip 考前专训
（来自弱省弱校的挣扎）
T1 专训
38 题，在一个小时内写出正解。
P11186 三目运算
体现出我不会递归的牛逼情况。
照着题目模拟，类似对一段区间进行染色。
因为递归成一颗二叉树形状，故从最深处返回的下标为紧挨下一次递归开始的下标。
点击查看代码
#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
typedef long long LL;
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
void WT() {}
template<typename T> void WT(T &x) {
if (x < 0) { putchar('-'); x = -x; };
if (x > 9) WT(x / 10);
putchar(x % 10 + '0');
}
const int N = 2e6 + 5;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int m, q, ans[N / 10];
char s[N];
int gi(int pos, int &x) {
x = 0;
while (s[pos] >= '0' && s[pos] <= '9') {
x = x * 10 + (s[pos] ^ '0'); pos++;
}
return pos;
}
int dfs(int pos, int l, int r) {
if (s[pos] >= '0' && s[pos] <= '9') {
int t;
int num = gi(pos, t);
LF(i, l, r) ans[i] = t;
return num;
}
int s1;
int s2 = gi(pos + 2, s1);
if (s[pos + 1] == '>') {
int nx = dfs(s2 + 1, s1 + 1, r);
return dfs(nx + 1, l, s1);
} else {
int nx = dfs(s2 + 1, l, s1 - 1);
return dfs(nx + 1, s1, r);
}
}
int main()
{
#ifdef FRZ_29
freopen("z_example.in", "r", stdin);
freopen("z_example.out", "w", stdout);
#endif
RD(m, q); cin >> s;
dfs(0, 1, m + 1);
while (q--) {
int x; RD(x);
printf("%d\n", ans[min(x, m + 1)]);
}
return 0;
}
// START:2024/11/01 21:25:21;
耗时约 45min，体现出我不会递归的牛逼状况。
P11187 配对序列
简单动态规划。
首先写了 \(O(n^2)\) 的暴力验证想法，像维护最长上升子序列那样。
设 \(f_{i, 0}\) 表示以 \(i\) 为结尾的子序列结尾两字符相等的最长长度，\(f_{i, 1}\) 表示以 \(i\) 结尾的子序列结尾两字符不相等的最长长度。
显然:
\[f_{i, 0} = \max_{j \in [1, i), a_i = a_j}(f_{j, 1} + 1, f_{i, 0}) \]\[f_{i, 1} = \max_{j \in [1, j), a_i \not= a_j}(f_{j, 0} + 1, f_{i, 1}) \]\(f_{i, 0}\) 的转移可以记录 \(a_i\) 上一次出现的位置，因为决策区间单调。
\(f_{i, 1}\) 的转移可以记录前缀最大值和次大值，因为要避免重复。
点击查看代码
#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
typedef long long LL;
using namespace std;
void read() {}
template<typename T, typename... U> void read(T &x, U&... arg) {
x = 0; int f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; read(arg...);
}
void write() {}
template<typename T> void write(T x) {
if (x < 0) { putchar('-'); x = -x; };
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int N = 5e5 + 5;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int n, a[N], lst[N];
int f[N][2];
int main() {
#ifdef FRZ_29
freopen("z_example.in", "r", stdin);
freopen("z_example.out", "w", stdout);
#endif
read(n);
LF(i, 1, n) read(a[i]);
LF(i, 1, n) f[i][1] = 1;
pair<int, int> Max[2] = {{0, 0}, {0, 0}};
LF(i, 1, n) {
if (Max[0].second == a[i]) f[i][1] = max(f[i][1], f[i][1] + Max[1].first);
else f[i][1] = max(f[i][1], f[i][1] + Max[0].first);
if (!lst[a[i]]) { lst[a[i]] = i; continue; }
f[i][0] = max(f[i][0], f[lst[a[i]]][1] + 1);
lst[a[i]] = i;
if (f[i][0] > Max[0].first) {
if (Max[0].second == a[i]) { Max[0].first = f[i][0]; continue; }
else {
Max[1] = Max[0];
Max[0] = { f[i][0], a[i] };
}
} else if (f[i][0] > Max[1].first){
if (Max[0].second == a[i]) continue;
Max[1] = { f[i][0], a[i] };
}
}
int ans = 0;
LF(i, 1, n) ans = max(ans, f[i][0]);
// LF(i, 1, n) printf("f[%d]: 0 %d 1 %d\n", i, f[i][0], f[i][1]);
write(ans);
return 0;
}
// START:2024/11/02 13:04:05;
耗时 30min，还行。
标签：ch,NOIP,int,Max,void,else,include From： https://www.cnblogs.com/FRZ29/p/18527685