前言
听不懂了, 看到故人了
看题
\(\rm{T1}\)
串串
像 \(\rm{dp}\) , 做一下才知道
\(\rm{T2}\)
构构造造
困难
\(\rm{T3}\)
听不懂了
\(\rm{T4}\)
看不懂了
应该很困难
放平心态多打部分分
时间管控好, 然后就是做题
\(\rm{T1}\)
能不能给一个好一点的样例?
思路
首先转化题意
选出一堆人中的一个子集, 使得可以对这个子集进行排序, 满足不存在一个 \(j < i\) 使得 \(s_j > s_i\) 或 \(s_j^r > s_i^r\) , 其中 \(>\) 表示字典序更大
抄了一遍题
因为可以对子集进行排序所以不好处理, 先找「不存在一个 \(j < i\) 使得 \(s_j > s_i\) 或 \(s_j^r > s_i^r\)」的性质
因为字典序只在完全相同时才相等, 所以我们先按照 \(s_i\) 的字典序为第一关键字升序排序, 这样子所有可能的排序在原序列中都已经按序, 只是需要保证连续两个名字中必须恰有一个包含 m 和 \(s_i^r\) 的约束
这里有一个误区是, 如果存在两个相同的 \(s_i\) 如何处理
你发现可能的排序在原序列中不一定按序, 但是我们可以把相同的串串合并处理
反正不影响答案
m 的约束好处理, 考虑 \(s_i^r\) 的约束
你发现在按照 \(s_i\) 的字典序为第一关键字升序排序之后, 我们可以知道每一个字符串按照 \(s_i^r\) 的字典序排序的编号, 容易知道只有递增选取才是合法的
好吧不太会做, 先暴力打满
\(\mathcal{O}(n^2)\)
这样方便用 \(\rm{dp}\) 处理
考虑令 \(dp_{i, j, 0/1}\) 表示当前考虑到了第 \(i\) 个位置, 之前选择的字符串, 其逆序排名最大为 \(j\) , 上一个位置是否包含 m , 最多选取的人数
这样每次转移就简单了
\[\begin{align*} \begin{cases} \textrm{case } \nexists \text{m} \in s_i , \begin{cases} dp_{i, j, 0} \gets dp_{i - 1, j, 0} \\ dp_{i, j, 1} \gets dp_{i - 1, j, 1} \\ dp_{i, \textrm{order}_{s_i}, 0} \gets dp_{i - 1, k, 1} + 1 , k \leq \textrm{order}_{s_i} \\ \end{cases} \\ \textrm{case } \exists \text{m} \in s_i , \begin{cases} dp_{i, j, 0} \gets dp_{i - 1, j, 0} \\ dp_{i, j, 1} \gets dp_{i - 1, j, 1} \\ dp_{i, \textrm{order}_{s_i}, 1} \gets dp_{i - 1, k, 0} + 1 , k \leq \textrm{order}_{s_i} \\ \end{cases} \\ \end{cases} \end{align*} \]最终的答案即为 \(\max\limits_{j = 1}^{n} dp_{n, j, 0/1}\)
特殊性质 \(\rm{A}\)
这种情况下正反字符串字典序都按序, 直接 \(\rm{dp}\) 即可
正解
你发现 \(\mathcal{O} (n^2)\) 的转移, 只需要滚一维然后前缀和优化一下即可
前缀和并不好做, 考虑丢到线段树上去做
操作可以简化为
\(\textrm{case } \nexists \text{m} \in s_i\)
把 \(\textrm{order}_{s_i} , 0\) 位置替换成 \(1\) 中的前缀最大值 \(+1\) , 其他不变
\(\textrm{case } \exists \text{m} \in s_i\)
把 \(\textrm{order}_{s_i}, 1\) 位置替换成 \(0\) 中的前缀最大值 \(+1\) , 其他不变
也就是说, 我们开两个树状数组表示 \(01\) 位置的前缀最大值, 然后每次单点修改
实现
框架
按照上面的打即可
在这里造几组数据
6
abcmdef
acdef
bmbkkl
basd
jmzy
lssy
代码
#include <bits/stdc++.h>
// #define testcase
#define int long long
const int MAXN = 1e5 + 20;
#define lowbit(x) ((x) & (-x))
int n;
std::string name[MAXN], bin[MAXN];
std::unordered_map<std::string, int> order; // 逆序排名 ∈ [1, n]
std::unordered_map<std::string, bool> have; // 是否带有 m
void init() {
for (int i = 1; i <= n; i++) {
std::cin >> name[i];
for (int j = 0; j < name[i].length(); j++) {
if (name[i][j] == 'm') have[name[i]] = true;
bin[i] += name[i][name[i].length() - j - 1];
}
}
std::sort(bin + 1, bin + n + 1);
std::sort(name + 1, name + n + 1);
int cnt = std::unique(bin + 1, bin + n + 1) - (bin + 1);
for (int i = 1; i <= cnt; i++) {
std::string ret = "";
for (int j = 0; j < bin[i].length(); j++) ret += bin[i][bin[i].length() - j - 1];
order[ret] = i;
}
}
class BIT
{
private:
int tree[MAXN << 1]; // 保险一点
public:
/*初始化*/ void init() { memset(tree, 0, sizeof tree); }
/*单点修改*/ void update(int x, int d) { while (x <= n) tree[x] = std::max(tree[x], d), x += lowbit(x); }
/*前缀最大值*/ int query(int x) { int ans = 0; while (x > 0) ans = std::max(tree[x], ans), x -= lowbit(x); return ans; }
} p0, p1;
void solve() {
p0.init(), p1.init();
for (int i = 1; i <= n; i++) {
if (have[name[i]]) {
int p = order[name[i]];
p1.update(p, p0.query(p) + 1);
} else {
int p = order[name[i]];
p0.update(p, p1.query(p) + 1);
}
}
int ans = std::max(p0.query(n), p1.query(n));
printf("%lld", ans);
}
signed main()
{
#ifdef testcase
freopen("queue_ex.in", "r", stdin);
freopen("myans.out", "w", stdout);
#endif
scanf("%lld", &n);
init();
solve();
return 0;
}
常数太大, 不知道会卡掉多少分
把 \(\rm{map}\) 改了快了不少, 丢了
虽然还是有点悬, 应该 \(2000 \ \rm{ms}\) 过得去, 吧
\(\rm{T2}\)
有点慌, 先看这个
又一次简单题想半天, 归根结底还是太菜了, 你说我还给别人说是读错题了是不是有点小丑, 哎哎
这题肯定是暴力, 或者说因为时间, 后面的肯定都是暴力
思路
特殊性质 \(\rm{A}\)
这种情况下, \(s [n - i + 1 : n]\) 的排名是 \(i\) , 也就是说其字典序第 \(i\) 小
这是一个非常明显的性质, 也就是说后缀的字典序单调递增
怎么利用, 你发现「后缀的字典序单调递增」保证了最后字符串中, 字母按照字典序从大到小排序
这个时候再去考虑 \(b\) 数组
在这个性质下, \(b\) 数组相当于约束了任意两个相邻后缀的最长公共子前缀
考虑怎么按照 \(b\) 数组去构造
对于每一个 \(s [i : n] , s [i + 1 : n]\) 的约束, 你标记它应该在哪里断开, 然后最后填上数即可
这里给出一组样例
11
11 10 9 8 7 6 5 4 3 2 1
-1 -1 2 -1 0 -1 -1 -1 2 -1 -1
zzzzzyyxxxxx
class subtask2
{
private:
bool flag[MAXN];
public:
void Main() {
memset(flag, false, sizeof flag);
for (int i = 2; i <= n; i++) {
if (b[i] == -1) continue;
int x = a[i - 1], y = a[i];
flag[x + b[i]] = true;
}
int now = 0;
char str[MAXN];
for (int i = n; i >= 1; i--) {
if (flag[i]) now++;
str[i] = (now + 'a');
}
for (int i = 1; i <= n; i++) std::cout << str[i];
}
} sub2;
特殊性质 \(\rm{B}\)
这个约束很强, 没时间想了
暴力
枚举判断即可
/*纯暴力*/
class subtask1
{
private:
std::string ans = "zzzzzz";
bool check(std::string str) {
std::string suf[10];
suf[n + 1] = "";
for (int i = n; i >= 1; i--) suf[i] = str[i] + suf[i + 1];
std::sort(suf + 1, suf + n + 1);
for (int i = 1; i <= n; i++) if (a[n - suf[i].length() + 1] != i) return false;
suf[n + 1] = "";
for (int i = n; i >= 1; i--) suf[i] = str[i] + suf[i + 1];
for (int i = 2; i <= n; i++) {
if (b[i] == -1) continue;
int x = a[i - 1], y = a[i];
std::string sx = suf[x], sy = suf[y];
int lsy = 0;
for (int j = 0; j < sy.length(); j++) {
if (sx[j] == sy[j]) lsy++;
else break;
}
if (lsy != b[i]) return false;
}
return true;
}
void dfs(int now, std::string str) {
if (now == n + 1) {
if (check(str)) {
ans = std::min(ans, str);
return;
} else {
return;
}
}
for (int i = 0; i < 26; i++) {
dfs(now + 1, str + (char)(i + 'a'));
}
}
public:
void Main() {
dfs(1, " ");
for (int i = 1; i <= n; i++) std::cout << ans[i];
}
} sub1;
要被卡成 \(0\) 分
\(\rm{T3}\)
直接打送的 \(40 \ \rm{pts}\)
总结
继续每日一练, 复习
策略没问题, 注重马力锻炼
标签：std,赛时,int,1.19,textrm,rm,CW,dp,name From： https://www.cnblogs.com/YzaCsp/p/18679463