$ 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
赛时分块 + 莫队 + 线段树没卡过去,赛后证明确实不用线段树(为啥一遇到分块赛时就死活过不去啊。。。);
首先转化题意:找区间众数的出现次数;
用一下回滚莫队,因为发现删除操作比较不好做 (其实挺好做,只不过我不会。。。),所以用只加不减的莫队即可;
对于回滚莫队,之前学的时候没时间练,导致约等于没学,所以今天赛时的时候忘了,用的普通莫队也没对,赛后用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还没改,等等吧;
标签:赛记,log,16,int,500005,id,include,莫队,CSP From: https://www.cnblogs.com/PeppaEvenPig/p/18349587