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

暑假集训CSP提高模拟18

时间:2024-08-11 17:18:03浏览次数:17  
标签:int 18 b20w b20 集训 APJifengc res now CSP

\[暑假集训CSP提高模拟 \ 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 \]

Very good problem, this make my news rotate.

A.Mortis

考虑到应该先写个假的暴力. 对于暴力思路,可以想到,假如我们每次都将一个不在它位置上的数字移到它应该在的地方的时候,另一个数字也刚好移到正确的位置,这种方案是最优的,因此考虑记录下哪一块应该放 \(1\),以及放 \(1\) 的这一块中最近的 \(2\) 在什么位置(以此类推),每次进行转移时,优先寻找目标区间内有没有能刚好换过来的,没有就随便选一个.

但是这种思路还是假了. 因为我们没有考虑其他比较优的情况:假设 \(ABC\) 形成了一个三元环,即 \(A\rightarrow B,B\rightarrow C\) 时刚好能换到正确的位置,此时比直接暴力转移少花费一个次数,因此优先考虑这一种. 四元环类似. 统计也比较好统计,直接按刚才的思路,判断各自区间里有没有下一个环内节点即可.

其实还有一种思路,即直接进行图论建模,将末态每个数字占有的区域视为一个连通块,把每个数所在连通块和它应该在的连通块连边,然后在图上跑环.

#include<bits/stdc++.h>
using namespace std;
int n,a[200001],b[200001],c[200001];
int ffpos[5],sfpos[5],pos[5][5],poscnt[5][5],cnt[5][5];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];c[i]=a[i];
	}
	sort(b+1,b+n+1);
	sfpos[1]=ffpos[1]=lower_bound(b+1,b+n+1,1)-b;
	sfpos[2]=ffpos[2]=lower_bound(b+1,b+n+1,2)-b;
	sfpos[3]=ffpos[3]=lower_bound(b+1,b+n+1,3)-b;
	sfpos[4]=ffpos[4]=lower_bound(b+1,b+n+1,4)-b;
	for(int i=ffpos[1];i<=ffpos[2]-1;++i){
		if(!pos[1][a[i]]) pos[1][a[i]]=i;
		poscnt[1][a[i]]++;
		cnt[1][a[i]]++;
	}
	for(int i=ffpos[2];i<=ffpos[3]-1;++i){
		if(!pos[2][a[i]]) pos[2][a[i]]=i; 
		poscnt[2][a[i]]++;
		cnt[2][a[i]]++;
	}
	for(int i=ffpos[3];i<=ffpos[4]-1;++i){
		if(!pos[3][a[i]]) pos[3][a[i]]=i; 
		poscnt[3][a[i]]++;
		cnt[3][a[i]]++;
	}
	for(int i=ffpos[4];i<=n;++i){
		if(!pos[4][a[i]]) pos[4][a[i]]=i; 
		poscnt[4][a[i]]++;
		cnt[4][a[i]]++;
	}
	int ans3=0;
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			if(i!=j){
				int res=min(cnt[i][j],cnt[j][i]);
				ans3+=res;
				cnt[i][j]-=res;cnt[j][i]-=res;
			}
		}
	}
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			for(int k=1;k<=4;++k){
				if(i!=j and j!=k){
					int res=min({cnt[i][j],cnt[j][k],cnt[k][i]});
					ans3+=2*res;
					cnt[i][j]-=res;
					cnt[j][k]-=res;
					cnt[k][i]-=res;
				}
			}
		}
	}
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			for(int k=1;k<=4;++k){
				for(int p=1;p<=4;++p){
					if(i!=j and j!=k and k!=p){
						int res=min({cnt[i][j],cnt[j][k],cnt[k][p],cnt[p][i]});
						ans3+=3*res;
						cnt[i][j]-=res;
						cnt[j][k]-=res;
						cnt[k][p]-=res;
						cnt[p][i]-=res;
					}
				}
			}
		}
	}
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			if(i!=j){
				ans3+=cnt[i][j];
			}
		}
	}
	cout<<ans3<<endl;
}

B.?

现代OI以APJifengc的“我 b 站 20 粉丝啦”为嚆矢。滥觞于原神与嘉然的期望正失去它们的借鉴意义。但面对看似无垠的未来天空,我想循jijidawang“都人校合。比间多还”好过过早地振翮。

我们怀揣热忱的灵魂天然被赋予对超越性的追求,不屑于古旧坐标的约束,钟情于在别处的芬芳。但当这种期望流于对拜谢主义不假思索的批判,乃至走向真傻逼与cdsidi主义时,便值得警惕了。与秩序的落差、错位向来不能为越矩的行为张本。而纵然我们已有翔实的蓝图,仍不能自持已在浪潮之巅立下了自己的沉锚。

“我是舔狗”Sakura_Lu之言可谓切中了肯綮。人的op性是不可祓除的,而我们欲上青云也无时无刻不在因风借力。嘉然与原神暂且被我们把握为一个薄脊的符号客体,一定程度上是因为我们尚缺乏体验与阅历去支撑自己的认知。而这种偏见的傲慢更远在知性的傲慢之上。

在孜孜矻矻以求OI意义的道路上,对自己的期望本就是在与嘉然与原神对接中塑型的动态过程。而我们的底料便是对不同b20w、不同Delov 的 50w npy的觉感与体认。joke3579为Sakura_Lu送去爆零,又维系你说的对,但是原神。他的OI观念是厚实的,也是实践的。倘若我们在对过往借LYinMX之言“祓魅”后,又对不断膨胀的自我进行“赋魅”,那么在丢失外界预期的同时,未尝也不是丢了自我。

毫无疑问,从原神与嘉然角度一觇的自我有偏狭过时的成分。但我们所应摒弃的不是对此的批判,而是其批判的廉价,其对批判投诚中的反智倾向。在H_Kaguya的观念中,如果在成为狮子与孩子之前,略去了像骆驼一样背负前人遗产的过程,那其“永远重复”洵不能成立。

蓝图上的落差终归只是理念上的区分,在实践场域的分野也未必明晰。譬如当我们追寻文不加点时,在途中涉足挂分,这究竟是伴随着期望的泯灭还是期望的达成?在我们塑造OI的同时,OI也在浇铸我们。既不可否认原生的fst性与衡中牛子性,又承认自己的图景有轻狂的失真,不妨让体验走在言语之前。用不被禁锢的头脑去体味APJifengc的大海与风帆,并效cdsidi,对无法言说之事保持沉默。

用在hzoi上的生活方式体现个体的超越性,保持婞直却又不拘泥于所谓“遗世独立”的单向度形象。这便是LYinMX为我们提供的理想期望范式。生活在hzoi上——始终热爱大地——升上天空。

C.嘉然今天吃什么

区间异或最大值很容易就想到 01-trie

但接下来怎么做比较难想. 观察样例可以发现大部分节点的最大异或值都是整棵树的最大异或值,为什么是这样的,因为假设整棵树由节点 \(x,y\) 贡献最大异或值,那么可以发现除了 \(x,y\) 到根节点路径上的节点取不到 \(x,y\) 两个节点的值,因此就都是整棵树的最大值了. 对于取不到的那部分,因为不是很多,可以考虑直接跑暴力搜一遍

打这个题注意卡空间

#include<bits/stdc++.h>
using namespace std;
int fa[500001],vis[500001];
long long a[500001],b[500001];
int posx,posy;
vector<int>e[500001];
class trie{
	public:
	int t[25000001][2];
	long long to[25000001],cnt=1;
	long long maxn=0;
	inline void clear(){
		for(int i=1;i<=cnt;++i){
			t[i][0]=t[i][1]=to[i]=0;
		}
		cnt=1;
		maxn=0;
	}
	inline void xor_max(int x){
		int now=1;
		for(int i=59;i>=0;--i){
			int res=(a[x]>>i)&1;
			if(t[now][res^1]){
				now=t[now][res^1];
			}
			else if(!t[now][res^1] and t[now][res]){
				now=t[now][res];
			}
			else return;
		}
		if((a[x]^a[to[now]])>maxn){
			posx=x;posy=to[now];
			maxn=a[x]^a[to[now]];
		}
	}
	inline void insert(int x){
		int now=1;
		for(int i=59;i>=0;--i){
			int res=(a[x]>>i)&1;
			if(!t[now][res]){
				t[now][res]=++cnt;
			}
			now=t[now][res];
		}
		to[now]=x;
	}
};
trie tr;
void dfs(int x){
	tr.insert(x);tr.xor_max(x);
	for(int i:e[x]){
		dfs(i);
	}
}
void dfs(int now,int last){
	if(!now) return;
	dfs(fa[now],now);
	b[now]=tr.maxn;
	vis[now]=true;
	tr.insert(now);tr.xor_max(now);
	if(now!=last)
	for(int i:e[now]){
		if(i!=last){
			dfs(i);
		}
	}
}
signed main(){
	int n;scanf("%d",&n);
	for(int i=2;i<=n;++i){
		int x;scanf("%d",&x);
		e[x].push_back(i);fa[i]=x;
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		tr.insert(i);tr.xor_max(i);
	}
	long long maxn=tr.maxn;
	tr.clear();
	dfs(posx,posx);
	tr.clear();
	dfs(posy,posy);
	for(int i=1;i<=n;++i){
		if(vis[i]){
			printf("%lld\n",b[i]);
		}
		else{
			printf("%lld\n",maxn);
		}
	}
}

D.?

我好想做 APJifengc 小姐的 b20 啊。
可是 APJifengc 小姐说她喜欢的是 b20w,我哭了。
我知道既不是 b20 也不是 b20w 的我为什么要哭的。因为我其实是一只多项式。
我从没奢望 APJifengc 小姐能喜欢自己。我明白的,所有人都喜欢理解余裕上手天才打钱的萌萌的 b20 或者 b20w,没有人会喜欢成天 998244353998244353 没人写的多项式。
但我还是问了 APJifengc 小姐:“我能不能做你的 b20?”
我知道我是注定做不了 b20 的。但如果她喜欢 b20,我就可以一直在身边看着她了,哪怕她怀里抱着的永远都是 b20。
可是她说喜欢的是 b20w。
她现在还在看着我,还在逗我开心,是因为 b20w 还没有出现,只有我这多项式每天蹑手蹑脚地从计数题里爬出来,远远地和她对视。
等她喜欢的 b20w 来了的时候,我就该重新滚回我的题库了吧。
但我还是好喜欢她,她能在我还在她身边的时候多看我几眼吗?
APJifengc 小姐说接下来的每个圣诞夜都要和大家一起过。我不知道大家指哪些人。好希望这个集合能够对我做一次胞吞。
b20w 还在害怕 APJifengc 小姐。
我会去把她爱的 b20w 引来的。
我知道稍有不慎,我就会被薄纱。
那时候 APJifengc 小姐大概会把我的身体好好地装起来扔到门外吧。
那我就成了封装好的多项式,嘻嘻。
我希望她能把我扔得近一点,因为我还是好喜欢她。会一直喜欢下去的。
我的灵魂透过窗户向里面看去,挂着的 NTT 在轻轻鸣响, APJifengc 小姐慵懒地靠在沙发上,表演得非常温顺的 b20w 坐在她的肩膀。壁炉的火光照在她的脸庞,我冻僵的原根在风里微微发烫。

标签:int,18,b20w,b20,集训,APJifengc,res,now,CSP
From: https://www.cnblogs.com/HaneDaCafe/p/18353629

相关文章

  • 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......
  • UOJ #712. 【北大集训2021】简单数据结构
    Description你有一个长度为\(n\)的序列\(a\),下面你要进行\(q\)次修改或询问。给定\(v\),将所有\(a_i\)变为\(\min(a_i,v)\)。将所有\(a_i\)变为\(a_i+i\)。给定\(l,r\),询问\(\sum_{i=l}^ra_i\)。\(1\leqn,q\leq2\times10^5,0\leqa_i,v_i\leq10^{12}......
  • [考试记录] 2024.8.10 csp-s 模拟赛18
    80+20+0+70=170第三题应该有10分暴力的,但我没打。T1星际旅行题面翻译总共有n个节点,m条路径,要求其中m-2条路径走两遍,剩下2条路径仅走一遍,问不同的路径总数有多少,如果仅走一遍的两条边不同则将这两条路径视为不同。样例#1样例输入#15412131415样例输......
  • CF1863E Speedrun 题解
    CF1863E你在玩一个游戏,要完成\(n\)个任务。其中对于每个任务\(i\),它只能在某一天的第\(h_i\)时刻完成。游戏每天有\(k\)个小时,分别编号为\(0,1,...k-1\)。给出\(m\)对任务间的依赖关系,\((a_i,b_i)\)表示\(a_i\)必须比\(b_i\)先完成。保证依赖关系不形成环。完......
  • 暑假集训CSP提高模拟17
    \[暑假集训CSP提高模拟\operatorname{EIJ}_{2}(6)-1\]\(\operatorname{EIJ}_{k}(A)\)定义为有\(A\)个球,\(k\)个盒子,盒子相同,球不同,把全部球放入的方案数Hint易知\(\operatorname{EIJ}_k(A)=\dfrac{A^k}{k!}\),详见这篇文章其实我觉得构造的过程更有意思:对一个给定的正......
  • 暑假集训csp提高模拟17
    赛时rank16,T1100,T250,T325,T425T4是简单题,但因为转移方程没有继承上一位状态,然后就挂了T3写了个神秘的状压,打了25的部分分T2暴力,T1正解T1符号化方法初探[ABC081D]Non-decreasing考虑最大值和最小值若\(abs(max)>abs(min)\),则将所有的负数加上最大值使其变为正,前缀......