首页 > 其他分享 >[赛记] 暑假集训CSP提高模拟16

[赛记] 暑假集训CSP提高模拟16

时间:2024-08-08 20:29:23浏览次数:14  
标签:赛记 log 16 int 500005 id include 莫队 CSP

$ 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的什么输入法

image

image

天色天歌天籁音 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还没改,等等吧;

标签:赛记,log,16,int,500005,id,include,莫队,CSP
From: https://www.cnblogs.com/PeppaEvenPig/p/18349587

相关文章

  • CSP16
    这题,唯一坑点,子序列是不连续的注意,子序列可以不连续,子串必须连续。有一个很显然的暴力点击查看代码intdp[N][N],n,p[N],q[N];intmain(){ speed(); freopen("in.in","r",stdin); freopen("out.out","w",stdout); cin>>n; for(inti=1;i<=n;i++)cin>>......
  • 暑假集训CSP提高模拟16
    \(\color{skyblue}9-nine-\)专场(小阳历最水的一回。日常RE挂分。我这是不是风水不好?(逃)9-nine-九次九日九重色赛时以为是连续的...大样例模了半天没模懂...按连续的思路打了个二分上去...还骗了30pts?(官方题解按照官方题解写的Code,但WA#1,不知道哪错了...intn,a[N],b[N......
  • 暑假集训CSP提高模拟16
    1.九次九日九重色一开始做的时候被题面给迷惑住了,没想到可以跳着匹配(样例太水)。那我们来考虑如何做,首先思路肯定是把能匹配的暴力求出来,根据不知道怎么搞的调和计数,这样的复杂度还不是很高,是\(O(NlogN)\),可以搞。观察一下预处理出来的序列,是不是很熟悉。没错剩下的就是求最......
  • Xcode 16 beta 5 (16A5221g) 发布 - Apple 平台 IDE
    Xcode16beta5(16A5221g)发布-Apple平台IDEIDEforiOS/iPadOS/macOS/watchOS/tvOS/visonOS请访问原文链接:https://sysin.org/blog/apple-xcode-16/,查看最新版。原创作品,转载请保留出处。Xcode16的新功能使用预测代码补全功能和更快的预览功能,将奇思妙想转化为代码......
  • CSP模拟 小 trick 总结 (持续施工中)
    虽然这篇博客来的有点晚,但还是写了,欢迎dalao补充(1、分块、莫队有关:(1):一个真正的回滚莫队(感谢Qyun的讲解)$\\\\\\\\$学习回滚莫队的时候,我们经常会在回滚时使用memcpy来恢复以前的版本,但众所周知--memset和memcpy常数巨大,破坏了莫队$O(n\sqrtn)$的时间复杂度,导......
  • 暑假集训csp提高模拟16
    赛时rank38,T120,T250,T30,T40T2挂分原因:莫队n,m写反了,但样例中这俩一样,遂寄T1九次九日九重色\[\color{Green}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Red}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Blue}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Yellow}{\......
  • 「模拟赛」暑期集训CSP提高模拟15(8.7)
    赛时记录:开场看T1,一眼\(manacher\)求子串回文串,听课是听了,但是不会啊。跳了。看T2,发现结论题,推了会结论打上走了。打完T2想了会T3、T4,无思路,回来打了T1暴力和特殊性质,\(30pts\),又去想T3,还是不会,这时还剩一个小时。不行,现在才\(130pts\),包打祭的啊,能不能翻盘看我T1......
  • 暑假集训CSP提高模拟16
    暑假集训CSP提高模拟16组题人:@Muel_imj\(T1\)P216.九次九日九重色\(100pts\)部分分\(30pts\):设\(f_{i,j}\)表示当前处理到\(P\)的第\(i\)位,\(Q\)的第\(j\)位时最大的\(k\),状态转移方程为\(f_{i,j}=\begin{cases}\max(f_{i,j-1},f_{i-1,j})&p_{i}\nmid......
  • SublimeText 4.4169 中文授权版
    SublimeText是编辑器中的一款神级IDE,非常有名,虽然比较轻量,但是呢软件拓展性非常强大,适用于多种编程语言,当然,当一个编辑器,也是非常不错的。SublimeText支持但不限于C,C++,C#,CSS,D,Erlang,HTML,Groovy,Haskell,HTML,Java,JavaScript,LaTeX,Lisp,Lua,Markdown,......
  • [CSP-J 2023] 小苹果
    [CSP-J2023]小苹果【官方数据】题目描述小Y的桌子上放着 nn 个苹果从左到右排成一列,编号为从 11 到 nn。小苞是小Y的好朋友,每天她都会从中拿走一些苹果。每天在拿的时候,小苞都是从左侧第 11 个苹果开始、每隔 22 个苹果拿走 11 个苹果。随后小苞会将剩下......