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

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

时间:2024-08-11 21:18:24浏览次数:15  
标签:赛记 int 18 ne son vis now mma CSP

T2 T4不太可做,所以没改

Mortis 20pts

原题:Luogu [ABC302G] Sort from 1 to 4

赛时用 $ set $ 乱搞拿了20pts,事实证明确实是乱搞;

考虑交换只有三种情况:

  1. a在b上,b在a上,需要一次;

  2. a在b上,b在c上,c在a上,需要两次;

  3. a在b上,b在c上,c在d上,d在a上,需要三次;

这里的在什么什么上是指原数组排序后的位置;

开个二维数组统计一下即可;

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int a[500005];
int b[500005];
int cnt[15][15];
int ans;
int tot;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++) {
		if (a[i] != b[i]) {
			cnt[b[i]][a[i]]++;
			tot++;
		}
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (i == j) continue;
			while(cnt[i][j] && cnt[j][i]) {
				ans++;
				cnt[i][j]--;
				cnt[j][i]--;
				tot -= 2;
			}
		}
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				if (i == j || i == k || j == k) continue;
				while(cnt[i][j] && cnt[j][k] && cnt[k][i]) {
					ans += 2;
					cnt[i][j]--;
					cnt[j][k]--;
					cnt[k][i]--;
					tot -= 3;
				}
			}
		}
	}
	cout << ans + tot / 4 * 3;
	return 0;
}

嘉然今天吃什么 10pts

原题:Luogu P8511 [Ynoi Easy Round 2021] TEST_68

$ \Theta(n^3) $ 暴力很好写;

考虑找出一个全局最大异或点对 $ p, q $(用 $ 01 \ trie $ 处理),可以发现除了它们到根路径上的所有点以外其它点的答案都是这个最大值;

所以分别处理;

第二次处理时,需要边插入边查询,同时需要特判 $ p, q $ 的 $ lca $(分两次处理);

也是复习了一下 $ 01 \ trie $;

完事;

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n;
struct sss{
	int t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int fa[500005], dep[500005];
long long a[500005], ans[500005];
int tot;
long long ma;
namespace trie{
	int son[30000005][2];
	int id[30000005];
	void ins(int x) {
		int now = 1;
		for (int i = 59; i >= 0; i--) {
			if (!son[now][(a[x] >> i) & 1]) son[now][(a[x] >> i) & 1] = ++tot;
			now = son[now][(a[x] >> i) & 1];
		}
		id[now] = x;
	}
	int ask(int x) {
		int now = 1;
		for (int i = 59; i >= 0; i--) {
			if (son[now][((a[x] >> i) & 1) ^ 1]) now = son[now][((a[x] >> i) & 1) ^ 1];
			else if (son[now][((a[x] >> i) & 1)]) now = son[now][((a[x] >> i) & 1)];
			else return 0;
		}
		return id[now];
	}
	void clear() {
		for (int i = 1; i <= tot; i++) {
			son[i][0] = son[i][1] = id[i] = 0;
		}
		tot = 1;
	}
}
using namespace trie;
void dfs(int x) {
	dep[x] = dep[fa[x]] + 1;
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		dfs(u);
	}
}
int p, q;
bool vis[500005];
int llc[5];
int lc;
int lca(int x, int y) {
	vis[x] = true;
	vis[y] = true;
	if (x == y) return x;
	if (dep[x] < dep[y]) swap(x, y);
	while(dep[x] > dep[y]) {
		x = fa[x];
		vis[x] = true;
	}
	while(x != y) {
		x = fa[x];
		y = fa[y];
		vis[x] = true;
		vis[y] = true;
	}
	int ans = x;
	while(x != 1) {
		x = fa[x];
		vis[x] = true;
	}
	return ans;
}
void afs(int x) {
	if (!vis[x]) ans[x] = ma;
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		afs(u);
	}
}
long long mma;
void efs(int x) {
	ins(x);
	mma = max(mma, a[x] ^ a[ask(x)]);
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		efs(u);
	}
}
void cfs(int x, int o) {
	ans[x] = mma;
	ins(x);
	mma = max(mma, a[x] ^ a[ask(x)]);
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if (!vis[u] || u == llc[o]) {
			efs(u);
		}
	}
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if (vis[u] && u != llc[o]) {
			cfs(u, o);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int x;
	for (int i = 2; i <= n; i++) {
		cin >> x;
		fa[i] = x;
		add(x, i);
	}
	tot = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ins(i);
		int y = ask(i);
		if ((a[i] ^ a[y]) > ma) {
			ma = (a[i] ^ a[y]);
			p = i;
			q = y;
		}
	}
	dfs(1);
	lc = lca(p, q);
	for (int i = h[lc]; i; i = e[i].ne) {
		int u = e[i].t;
		if (vis[u]) {
			llc[1] = llc[0];
			llc[0] = u;
		}
	}
	afs(1);
	clear();
	cfs(1, 0);
	mma = 0;
	clear();
	cfs(1, 1);
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

标签:赛记,int,18,ne,son,vis,now,mma,CSP
From: https://www.cnblogs.com/PeppaEvenPig/p/18353909

相关文章

  • P9751 [CSP-J 2023] 旅游巴士
    原题链接分析很逆天的一道题设\(dp[i][j]\)为到达第\(i\)个点的时刻\(t\)且满足\(t\modk=j\)的最小\(t\)则有答案为\(dp[n][0]\)更新也很简单,设当前点为\(u\),当前时间为\(t\)需要遍历的下一个点\(v\),则有\(dis[v][(t+1)\%k]=dis[u][t\%k]+1\)如果道路还没开......
  • 【ESP01开发实例】- ISD1820录音控制
    ISD1820录音控制文章目录ISD1820录音控制1、ISD1820模块介绍2、硬件准备及接线3、代码以实现录音技术已经取得了长足的进步,它已成为从语音助手到安全系统的各种应用不可或缺的一部分。如果您有兴趣构建自己的录音系统,将ISD1820模块与ESP01微控制器相结......
  • 『模拟赛』暑假集训CSP提高模拟18
    Rank致敬传奇不挂分Rank5模拟赛A.Mortis原[ABC302G]Sortfrom1to4签,致敬传奇abc_g作签到题。虽然但是还是想了1h,好在最后成功切了。具体解释看看题解,求个赞。点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintRatio=0;constintN=2......
  • 暑假集训CSP提高模拟18
    \[暑假集训CSP提高模拟\1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1\]Verygoodproblem,thismakemynewsrotate.A.Mortis考虑到应该先写个假的暴力.对于暴力思路,可以想到,假如我们每次都将一个不在它位置上的数字移到它应该在的地方的时候,另一个数字也刚好移到正确的位置,这......
  • csp-j2023第四题 旅游巴士
    旅游巴士这道题在一年之前的csp-j中并没有做(我是一个蒟蒻)回看本题,又有了新的想法对于每一层i我们将其看成走到这是的时间jmodk的余数很显然,为了让我们更快的通过,等待时间+当前时间>=限制时间是最优的/*使用分层图,跑dijkstra堆优化的最短路在限制时间那部分,若小于限制时间,......
  • CSP17
    请注意:题目背景与题目可能没有关系第一题,性质题,找到序列的最大值与最小值,我们发现如果只有正数的话和只有负数的话都很好处理,正数正序处理类似前缀加,负数后缀加,那如果正负都有,该怎么办呢?其实我们可以吧序列全变为正的或负的吧,但是需要比较一下最大值最小值,如果都变成正的话,对......
  • ISO 26262中的失效率计算:IEC TR 62380-Section 18-Protection devices
    目录概要1元器件分类2失效率的计算2.1失效率预测模型2.2Base失效率的选取2.3λoverstress的计算2.3.1πI的选取2.3.2电过应力失效率的选取概要IECTR62380《电子组件、PCBs和设备的可靠性预计通用模型》是涵盖电路、半导体分立器件、光电组件、电阻器、电......
  • [赛记] 暑假集训CSP提高模拟17
    符号化方法初探100pts签到题?做了得有1.5h+;考虑全是正数或全是负数的情况,那么我们可以对其做一次类似于前缀和或后缀和的操作,需要$n-1$次;所以我们只需将数列中的数全部转化成正数或负数即可,具体地,找出所有正数的和和所有负数的和,如果前者比后者要大,那么就将所有正数加起......
  • 018.Vue3入门,sytle中加入scoped只在这个文件中生效
    1、全局代码App.vue如下<scriptsetup>importTestpage001from'./view/Testpage001.vue'importTestpage002from'./view/Testpage002.vue'</script><template><divclass="style1">测试1</div><Testp......
  • [考试记录] 2024.8.10 csp-s 模拟赛18
    80+20+0+70=170第三题应该有10分暴力的,但我没打。T1星际旅行题面翻译总共有n个节点,m条路径,要求其中m-2条路径走两遍,剩下2条路径仅走一遍,问不同的路径总数有多少,如果仅走一遍的两条边不同则将这两条路径视为不同。样例#1样例输入#15412131415样例输......