[赛记] 暑假集训CSP提高模拟16
$ Peppa \ Pig $ 都有时间写赛记了，看来现在这题是真不好改了
今天又是一题没切；
九次九日九重色 0pts
原题：现找的
赛时理解错了子序列，给理解成了字串（$ HDK $ 给我说的，要不我可能还不知道），导致大样例咋手模都出不来，干了45min，整了个不像暴力的暴力然后走了；
赛后证明，我的乱胡搞到了 $ 20pts $ ，但手欠后来把T2代码交到了T1里，导致 $ 0pts $；
这题和Luogu P2782 友好城市 挺像的；
依据调和级数（我的理解是：$ 1 + \frac12 + \frac13 + \ ... \ + \frac1n $ 是 $ \log n $ 级别的），可得 $ 1 $ 到 $ n $ 的倍数不超过 $ n \log n $，所以可以暴力预处理；
具体来讲，我们对 $ a_i $ 的每个在 $ B $ 中出现的倍数（不妨设为 $ b_j $ ），连一条从 $ i $ 到 $ j $ 的边（这里不用真的连，只需要用一个二元组存一下就行）；
这样连完边后，不难发现我们要找的就是最多的边，使其两两不相交，那么排完序后对 $ j $ 做一个最长上升子序列即可；
对于排序，我们可以将每一个二元组按以 $ i $ 升序为第一关键字，$ j $ 降序为第二关键字排序，前者很显然，因为我们要从左往右选嘛，后者是为了避免 $ i $ 被重复选择，因为这样的话 $ i $ 在由以前的状态转移而来时就不会被以前的 $ i $ 转移而来，反之则有可能；
最后要用 $ \Theta(n \log n) $ 的最长上升子序列求，总时间复杂度为 $ \Theta(n \log n \log(n \log n)) $，空间复杂度 $ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int a[200005], b[200005];
int pos[200005];
int ans, cnt;
struct sss{
int id, mat;
bool operator <(const sss &A) const {
if (id == A.id) return mat > A.mat;
else return id < A.id;
}
}e[5000005];
int c[5000005];
int d[5000005], len;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
pos[b[i]] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j * a[i] <= n; j++) {
e[++cnt] = {i, pos[j * a[i]]};
}
}
sort(e + 1, e + 1 + cnt);
len = 1;
for (int i = 1; i <= cnt; i++) {
c[i] = e[i].mat;
}
d[1] = c[1];
for (int i = 1; i <= cnt; i++) {
if (c[i] > d[len]) {
d[++len] = c[i];
} else {
d[lower_bound(d + 1, d + 1 + len, c[i]) - d] = c[i];
}
}
cout << len;
return 0;
}
另记：TM的什么输入法
天色天歌天籁音 50pts
原题：Luogu P3709 大爷的字符串题
赛时分块 + 莫队 + 线段树没卡过去，赛后证明确实不用线段树（为啥一遇到分块赛时就死活过不去啊。。。）；
首先转化题意：找区间众数的出现次数；
用一下回滚莫队，因为发现删除操作比较不好做 （其实挺好做，只不过我不会。。。），所以用只加不减的莫队即可；
对于回滚莫队，之前学的时候没时间练，导致约等于没学，所以今天赛时的时候忘了，用的普通莫队也没对，赛后用1h+手造出来一个回滚莫队，貌似是对了（反正题库和洛谷过了），而且跑的还挺快。。。
代码仅供参考；
点击查看代码
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
int a[500005];
int b[500005];
int cnt;
int sq;
int st[500005], ed[500005];
int belog[500005];
int ans[500005];
map<int, int> mp;
struct sss{
int l, r, id;
bool operator <(const sss &A) const {
if (belog[l] == belog[A.l]) {
return r < A.r;
} else {
return l < A.l;
}
}
}e[500005];
int ma, sum[500005];
int t[500005];
bool vis[500005];
inline void add(int x) {
sum[x]++;
ma = max(ma, sum[x]);
}
inline void del(int x) {
sum[x]--;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++) {
cin >> a[i];
if (!mp[a[i]]) {
mp[a[i]] = ++cnt;
}
b[i] = mp[a[i]];
}
sq = sqrt(n);
for (register int i = 1; i <= sq; i++) {
st[i] = (i - 1) * sq + 1;
ed[i] = i * sq;
}
ed[sq] = n;
for (register int i = 1; i <= sq; i++) {
for (register int j = st[i]; j <= ed[i]; j++) {
belog[j] = i;
}
}
for (register int i = 1; i <= m; i++) {
cin >> e[i].l >> e[i].r;
e[i].id = i;
}
sort(e + 1, e + 1 + m);
int l = 1;
int r = 0;
int ls = 0;
for (register int i = 1; i <= m; i++) {
ma = 0;
if (belog[e[i].l] == belog[e[i].r]) {
for (int j = e[i].l; j <= e[i].r; j++) {
t[b[j]]++;
ma = max(ma, t[b[j]]);
}
ans[e[i].id] = -ma;
for (int j = e[i].l; j <= e[i].r; j++) {
t[b[j]] = 0;
}
vis[i] = true;
continue;
}
if (i == 1 || belog[e[i].l] != belog[e[i - 1].l] || vis[i - 1]) {
ls = 0;
while(l < ed[belog[e[i].l]]) del(b[l++]);
while(r < ed[belog[e[i].l]] - 1) add(b[++r]);
while(r > ed[belog[e[i].l]] - 1) del(b[r--]);
}
while(l < ed[belog[e[i].l]]) del(b[l++]);
while(r < e[i].r) add(b[++r]);
ls = max(ls, ma);
while(l > e[i].l) add(b[--l]);
ans[e[i].id] = -max(ls, ma);
}
for (register int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
T3，T4还没改，等等吧；