首页 > 其他分享 >CSP 模拟 4

CSP 模拟 4

时间：2024-07-25 14:41:18浏览次数：14  
标签：typedef ch int bmod long CSP 模拟 getchar

T1 White and Black

原题 ARC148C Lights Out on Tree
最小和无解都不用管，不能下改上，所以从上往下，遇到就反转。
一定的观察后发现，当这个点的颜色与父亲不同时，会有贡献，然后直接就做完了。

点击查看代码 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,q,s[N],f[N],son[N],head[N],tot;
bool vis[N];
struct EDGE{int v,next;}e[N<<1];
inline void add(int u,int v){
	e[++tot]={v,head[u]};head[u]=tot;	
}
inline void dfs(int u,int fa){
	f[u]=fa;
	for(int i=head[u];i;i=e[i].next){
		dfs(e[i].v,u);
	}
}
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),q=read();
    for(int i=2;i<=n;++i){
        int x=read();
        add(x,i);
        son[x]++;
    }
    dfs(1,0);
    for(int i=1;i<=q;++i){
    	int num=read();
        int res=0;
        for(int j=1;j<=num;++j){
        	s[j]=read();
        	res+=son[s[j]];
        	vis[s[j]]=1;
        }
        for(int j=1;j<=num;++j){
        	if(vis[f[s[j]]])res--;
        	else res++;
        }
        for(int j=1;j<=num;++j){
        	vis[s[j]]=0;
        }
        std::cout<<res<<'\n';
    }
}

T2 White and White

原题 CF958C3 Encryption(hard)
有个无脑 \(\mathcal{O}(nk\log p)\) 做法，然后给卡了。
设 \(f_{i,k}\) 表示到 \(i\) 分成 \(k\) 段的最小价值。
\(f_{i,k}=min\{f_{j,k-1}+(s_i-s_j)\bmod p\}\) 瓶颈在转移，是 \(\mathcal{O}(n)\) 的。
考虑两个决策点的转移

\[f_{j,k-1}+(s_i-s_j)\bmod p\equiv s_i \ (\bmod p) \]

\[f_{w,k-1}+(s_i-s_w)\bmod p\equiv s_i\ (\bmod p) \]

他们的结果在模 \(p\) 意义下是同余的，所以当 \(f_{j,k-1}\le f_{w,k-1}\) 时，总有 \(f_{j,k-1}+(s_i-s_j)\bmod p\le f_{w,k-1}+(s_i-s_w)\bmod p\)，因为它们的增加量是小于 \(p\) 的，不足以反超。
所以对于每个 \(k\) 转移点就是之前的最小值，每个 \(k\) 记一下就可以 \(\mathcal{O}(1)\) 转移了。

点击查看代码 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,f[N][105],k,mod,a[N];
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	// std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),k=read(),mod=read();
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)a[i]=(read()+a[i-1])%mod,f[i][1]=a[i];
	for(int j=2;j<=k;++j){
		int min=2e9,minpos=0;
		for(int i=1;i<=n;++i){
			f[i][j]=f[minpos][j-1]+(a[i]-a[minpos]+mod)%mod;
			if(min>f[i][j-1]){
				min=f[i][j-1];minpos=i;
			}
		}
	}
	std::cout<<f[n][k];    
}

T3 Black and Black

原题 ARC153C ± Increasing Sequence
套路的构造，先赋好满足递增初值后考虑调整，调整过程满足递增，所以考虑前后缀加减，直接看看前后缀和有没有 \(\pm 1\) 即可。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int a[N],n,pre[N],suf[N],ans,w[N];
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();pre[i]=pre[i-1]+a[i];
		ans+=a[i]*i;
		w[i]=i;
	}
	for(int i=n;i;--i){suf[i]=suf[i+1]+a[i];}
	if(ans==0){
		std::cout<<"Yes\n";
		for(int i=1;i<=n;++i)std::cout<<i<<' ';std::cout<<'\n';
		exit(0);
	}
	if(ans<0){
		for(int i=1;i<=n;++i){
			if(pre[i]==-1){
				std::cout<<"Yes\n";
				int k=-ans;
				for(int j=1;j<=i;++j)w[j]-=k;
				for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
				exit(0);
			}
		}
		for(int i=n;i;--i){
			if(suf[i]==1){
				std::cout<<"Yes\n";
				int k=-ans;
				for(int j=i;j<=n;++j)w[j]+=k;
				for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
				exit(0);
			}
		}
		std::cout<<"No\n"<<'\n';exit(0);
	}
	for(int i=1;i<=n;++i){
		if(pre[i]==1){
			std::cout<<"Yes\n";
			int k=ans;
			for(int j=1;j<=i;++j)w[j]-=k;
			for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
			exit(0);
		}
	}
	for(int i=n;i;--i){
		if(suf[i]==-1){
			std::cout<<"Yes\n";
			int k=ans;
			for(int j=i;j<=n;++j)w[j]+=k;
			for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
			exit(0);
		}
	}
	std::cout<<"No\n";
}

T4 Black and White

原题 P2056 [ZJOI2007] 捉迷藏
点分树板子，写的线段树上暴力合并。
直径有一个性质，两个点集合并后的直径端点一定是两个点集直径端点组成的。
然后线段树上维护端点和最大距离后直接暴力枚举情况合并即可。时间复杂度 \(\mathcal{O}(n\log n)\)

点击查看代码 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10;
int n,st[20][N],sum[N],dfn[N],dfncnt,dep[N],sm;
std::vector<int> e[N];
struct Tree{int l,r,len,vis;}t[N<<2];
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void dfs(int u,int fa){
	st[0][dfn[u]=++dfncnt]=fa;
	for(int v:e[u])if(v!=fa)dep[v]=dep[u]+1,dfs(v,u);
}
inline int get_dis(int u,int v){
	int x=u,y=v;
	if(u==v)return u;
	if((u=dfn[u])>(v=dfn[v]))std::swap(u,v);
	int d=std::__lg(v-u++);
	int lca=get(st[d][u],st[d][v-(1<<d)+1]);
	return dep[x]+dep[y]-2*dep[lca];
}
inline void update(int p){
	int ls=p<<1,rs=p<<1|1;
	if(t[ls].vis&&t[rs].vis){t[p]={0,0,0,1};return;}
	if(t[ls].vis){t[p]=t[rs];return;}
	if(t[rs].vis){t[p]=t[ls];return;}
	int max=0;
	if(max<t[ls].len){t[p]=t[ls];max=t[ls].len;max=t[ls].len;}
	if(max<t[rs].len){t[p]=t[rs];max=t[rs].len;max=t[rs].len;}
	int w=get_dis(t[ls].l,t[rs].l);
	if(max<w){t[p]={t[ls].l,t[rs].l,w,0};max=w;}
	w=get_dis(t[ls].l,t[rs].r);
	if(max<w)t[p]={t[ls].l,t[rs].r,w,0},max=w;
	w=get_dis(t[ls].r,t[rs].l);
	if(max<w)t[p]={t[ls].r,t[rs].l,w,0},max=w;
	w=get_dis(t[ls].r,t[rs].r);
	if(max<w)t[p]={t[ls].r,t[rs].r,w,0},max=w;
}
inline void build(int p,int l,int r){
	if(l==r){t[p]={l,r,0,0};return;}
	int mid=l+r>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	update(p);
}
inline void change(int p,int l,int r,int pos){
	if(l==r){t[p].vis^=1;if(t[p].vis)sm--;else sm++;return;}
	int mid=l+r>>1;
	if(pos<=mid)change(p<<1,l,mid,pos);
	else change(p<<1|1,mid+1,r,pos);
	update(p);
}
inline void ask(){

	if(sm==1){std::cout<<0<<'\n';return;}
	if(sm==0){std::cout<<-1<<'\n';return;}
	std::cout<<t[1].len<<'\n';
}
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	sm=n=read();
	for(int i=2;i<=n;++i){
		int u=read(),v=read();
		e[u].push_back(v);e[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=std::__lg(n);++i)
		for(int j=1;j+(1<<i)-1<=n;++j)
			st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
	build(1,1,n);
	int q=read();
	for(int i=1;i<=q;++i){
		char ch=getchar();
		while(ch!='C'&&ch!='G')ch=getchar();
		if(ch=='G')ask();
		else change(1,1,n,read());
	}
}
点击查看

T1

感觉像树剖维护。
等会冲一下

T2

简单分讨后，开值域线段树维护即可。
male，这题这么 \(O(nk\log p)\) 跑不动，白忙活。

T3

只会 30
一定有值域不是很大的方案，

T4

标签：typedef,ch,int,bmod,long,CSP,模拟,getchar
From： https://www.cnblogs.com/Ishar-zdl/p/18323017

相关文章

  • CSP 模拟 3
    joke3579场，T1abc猜想([ARC111A]SimpleMath2)直接\(\bmod\c\)，很难做，不难想到换一个和\(c\)有关的模数，\(c^2\)很好，因为它除以\(c\)再模上\(c\)后为\(0\)。求\(x=a^b(\bmod\c^2)\)，\(a^b=k\cdotc^2+x\)，除以\(c\)模\(c\)后，前面那个东西没了，只剩\(x\)，所以答......
  • eve-NG网络环境模拟神器
    一个看着很像计网实验的一个万能模拟工具。下载https://www.eve-ng.net/index.php/download/安装导入eve镜像之前需要安装一些软件。SecureCRT:用来连接telnet的MobaXterm：类似xshell的工具EVE-NG-Win-Client-Pack-2.0：主要是用于Wireshark抓包直接去官网下载即可https://e......
  • can环境模拟+重放攻击+逆向分析
    安装ICSimsudoaptinstalllibsdl2-devlibsdl2-image-devcan-utilsmavenautoconf-y#下载ICSimgitclonehttps://github.com/zombieCraig/ICSim.git#编译安装cdICSim/sudomake安装socketcand#下载socketcandgitclonehttps://github.com/linux-can/socket......
  • ccfcsp 201803.2 碰撞的小球 100分代码
    本题是一道小模拟规模小难度在碰撞检测在写模拟题时的思路应该是先找到应该储存的信息是哪些，抽象出来，应该模拟的方法是哪些。类似oop。includeusingnamespacestd;constintL=1000;structball{intp;chard=1;//只可能为1或-1，表示方向}b[L+1];intmain(){int......
  • YC322A [ 20240724 CQYC NOIP 模拟赛 T4 ] 庫的 序计数(counting)
    题意给定一棵树\(T\)，每次操作在某个点下方接上\(k\)个儿子。询问期望多少次排列，使得\(a_{fa_i}<a_i\)。保证\(k\)是偶数，对\(65536\)取模。\(n\le10^5,k\le2\times10^9\)。Sol考虑假如已经确定了一棵树的形态，如何求出最终的答案？可以发现对于每一个节点......
  • 「模拟赛」暑期集训CSP提高模拟4（7.21）
    很祭的一次比赛，啥也不会。题目列表：A.WhiteandBlackB.WhiteandWhiteC.BlackandBlackD.BlackandWhiteA.WhiteandBlack\(0pts\)题意：给你一颗树，树根为1，初始所有点都是白色，每次询问给出一个点集，若把点集中的点全部染成黑色，问至少需要翻转多少个节点才能使整......
  • 2024.7.22模拟赛5
    模拟赛咕了两天才发现少了一天的题解。T1MakeItIncreasing水。code#include<bits/stdc++.h>usingnamespacestd;constintN=40;#defineLLlonglongintt,n;LLa[N];intmain(){// freopen("in.in","r",stdin);// freopen("out.out",&......
  • 暑假集训CSP提高模拟6
    赛时在\(T2\)浪费时间太多，导致\(T4\)暴力没时间想了，总是想把\(T2\)这种题当大型分讨来做A.花间叔祖[ARC148A]modM观察性质可以发现，答案要么是1，要么是2，把是1的情况找出来剩下的就是2。考虑什么时候是1，如果一个数列模上一个数结果相同，那么他们的差一定是这个模数的整......
  • 暑假集训CSP提高模拟3
    暑假集训CSP提高模拟32/35反向挂了若干分又正向挂了若干T1abc猜想水，随便变形推个柿子糊个快速幂就好了T2简单的排列最优化题考虑只计算每次右移的\(delta\)，我们发现一个点只会在到贡献为\(0\)的位置和序列开头会改变对\(delta\)的贡献，直接算就好，\(O(n)\)的T3简单......
  • [题解]P9755 [CSP-S 2023] 种树
    P9755[CSP-S2023]种树迟来的补题本题是让最小化所有树长到指定高度日期的最大值，于是想到二分答案。那么，对于一个给定的期限\(x\)，如何判断是否能在这个日期内完成任务呢？首先我们发现前\(n\)天每天都要种树，那么假设我们已经知道了每个地块最晚哪个日期种树，能保证在期限\(x\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99