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

暑假集训CSP提高模拟4

时间:2024-07-21 17:29:17浏览次数:14  
标签:le tol 集训 int sum CSP tor 暑假 id

A.White and Black

暴力的 \(O(nq)\) 做法比较显然,因为对于根节点来说,只有它自己可以改变自己的颜色,因此如果它是黑色则一定需要更改自己,同时把更改传下去(应该没有那种每次真的更改所有节点然后写 \(O(nqn^{n})\) 的吧),同理,假如根节点更改结束,次级节点就同理了,这是一个连锁的反应,因此搜一遍下来就行了.

这道题的优化点主要是在减少白点的枚举次数上,注意到数据范围中给出的黑点数量非常少,因此我们考虑将枚举白点变成枚举子节点总数减去黑点总数,这样就能把复杂度降下来.

这样还是不好做,考虑预处理出每个节点的儿子总数,如果节点变黑,则其每个儿子对它作 \(1\) 的贡献,如果儿子也是黑色的,说明该儿子不再对该父节点做贡献,临时减掉即可.

这道题写了部分分但是没拿到,因为题目里只说了是菊花,没说根节点是谁,判断的时候漏判了.

#include<bits/stdc++.h>
using namespace std;
int n,q;
int sons[200001],fa[200001],black[200001],isblack[200001];
int main(){
	scanf("%d %d",&n,&q);
	for(int i=2;i<=n;++i){
		scanf("%d",&fa[i]);
		sons[fa[i]]++;
	}
	for(int i=1;i<=q;++i){
		int x;
		scanf("%d",&x);
		int ans=0;
		for(int j=1;j<=x;++j){
			scanf("%d",&black[j]);
			isblack[black[j]]=true;
		}
		for(int j=1;j<=x;++j){
			ans+=sons[black[j]];
		}
		for(int j=1;j<=x;++j){
			if(!isblack[fa[black[j]]]) ans++;
			else ans--;
		}
		printf("%d\n",ans);
		for(int j=1;j<=x;++j){
			isblack[black[j]]=false;
		}
	}
}

B.White and White

还是比较显然的 \(O(n^2 k)\) 暴力,对于此题显然可以设计 \(f_{i,j}\) 表示选到第 \(j\) 位,上次划分在 \(i\) 位置的最小值,可以得到:

\[f_{i,j}=\min_{1\le k\lt j} \{ f_{i-1,k}+(\sum^{x}_{k+1\le x\le j} a_{x})\mod p \} \]

发现这个 \(\mod p\) 非常恶心,阻止我们进一步使用优先队列进行优化.

因此考虑从这个 \(\mod p\) 入手,因为我们每次进行取模都只是剪掉了一个 \(kp\ (k\in Z)\),即 \(f_{i,j}\equiv \sum^{x}_{1\le x\le j} a_{x}\pmod p\)

在我们进行状态转移时(即上式),对于两个 \(k=a,b\),将同余式传递,有

\[f_{i,j}\equiv f_{i-1,a}+\sum^{x}_{a\le x\le j}a_{x}\equiv f_{i-1,b}+\sum^{x}_{b\le x\le j}b_{x}\pmod p \]

假设当 \(f_{i-1,a}+\sum^{x}_{a\le x\le j}a_{x}\lt f_{i-1,b}+\sum^{x}_{b\le x\le j}b_{x}\) 时,有 \(f_{i-1,a}\lt f_{i-1,b}\),此时移项有:

\[\sum^{x}_{a\le x\le j}a_{x}\lt f_{i-1,b}+\sum^{x}_{b\le x\le j}b_{x}-f_{i-1,a} \]

刚才我们知道

\[\sum^{x}_{a\le x\le j}a_{x}\equiv f_{i-1,a}-f_{i-1,b}+\sum^{x}_{b\le x\le j}b_{x}\pmod p \]

这两个方程联立无解,因此假设不成立,我们得到:

\[f_{i-1,a}+\sum^{x}_{a\le x\le j}a_{x}\lt f_{i-1,b}+\sum^{x}_{b\le x\le j}b_{x}\rightarrow f_{i-1,a}\ge f_{i-1,b} \]

通过此式判断最优决策点即可

此外本题卡空间,需要用滚动数组进行优化

#include<bits/stdc++.h>
using namespace std;
int n,k,p;
const int mod=1e9+7,inf=0x3f3f3f3f;
int sum[500001];
int f[500001][101];
int g[2][101];
int main(){
	cin>>n>>k>>p;
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=n;++i){
		int x;cin>>x;
		sum[i]=(sum[i-1]+x)%p;
		f[0][0]=0;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=k;++j){
			f[i][j]=f[g[i&1][j-1]][j-1]+((sum[i]-sum[g[i&1][j-1]])%p+p)%p;
		}
		for(int j=0;j<=k;++j){
			if(f[i][j]<f[g[i&1][j]][j]) g[!(i&1)][j]=i;
			else g[!(i&1)][j]=g[i&1][j];
		}
	}
	cout<<f[n][k]<<endl;
}

C.Black and Black

TBA

D.Black and White

最暴力的做法是单次 \(n^{2}\) 枚举点对求距离最大值. \(O(qn^{3}\log n)\)

比较暴力的显然是直接单次两遍 DFS 求树的直径. \(O(qn^{3})\)

直接说正解,考虑到根据原树的 DFS 序将整棵树压缩成一个括号序列. \(O(qn\log n)\)

注意到,自身封闭的括号序列一定是一颗完整的子树,因此,当我们需要求解 \(x,y\) 之间的距离时,应该考虑分别找到 \(x,y\) 的位置,然后提取出 \([pos_{x},pos_{y}]\) 之间的括号序列. 假如该序列中存在封闭的子括号序列,说明最短路径显然不会进入这颗子树(因为 \(x,y\) 均不在这个子树内,因此走进去是多余的),所以考虑消去路径上全部封闭的子括号序列,余下的括号个数即为路径长.

显然,这样的复杂度不够优秀,注意到区间括号序列是具有可合并性的,当我们合并两个括号序列的时候,根据上述所需,我们完全可以预先消去两个子区间内的全部封闭子括号序列,其次进行合并,再将新形成的括号序列继续与其他括号序列进行合并.

基于这样的思想,我们使用线段树来维护消除完毕的括号序列(即任意两点间距离,通过查询 \([l,r]\) 区间和即可获得 \(dis_{l,r}\)).

显然我们需要维护的有:DFS 序,各点在 DFS 序列上的位置,线段树(存储每个区间的左括号数目,右括号数目(特别地,由于维护跨区间距离的需要,我们还需要维护该树的子树的括号情况),以及该区间左右端点间距离(即剩余括号数)).

此外还需要判 \(-1\) 和 \(0\),记一个 \(cnt\) 即可.

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int num,s[3000001],pos[1000001];
int n,m;
int cnt,tot;
bool c[100001];
vector<int>e[200001];
void dfs(int now,int fa){
	s[++tot]=-1;
	s[++tot]=now;
	pos[now]=tot;
	for(int i:e[now]){
		if(i!=fa){
			dfs(i,now);
		}
	}
	s[++tot]=-2;
}
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
struct tree{
	int a,b;
	int l1,l2,r1,r2;
	int dis;
}t[1200005];
void push(int id,int x){
	t[id].a=t[id].b=0;
	t[id].l1=t[id].l2=t[id].r1=t[id].r2=t[id].dis=-inf;
	if(s[x]==-1){
		t[id].b=1;
	}
	else if(s[x]==-2){
		t[id].a=1;
	}
	else if(!c[s[x]]){
		t[id].l1=t[id].r1=t[id].r2=t[id].l2=0;
	}
}
void merge(int id){
	if(t[tol].b>t[tor].a){
		t[id].a=t[tol].a,t[id].b=t[tol].b-t[tor].a+t[tor].b;
	}
	else{
		t[id].a=t[tol].a+t[tor].a-t[tol].b,t[id].b=t[tor].b;
	}
	t[id].l1=max({t[tol].l1,t[tor].l1+t[tol].a-t[tol].b,t[tor].l2+t[tol].a+t[tol].b});
	t[id].l2=max(t[tol].l2,t[tor].l2-t[tol].a+t[tol].b);
	t[id].r1=max({t[tor].r1,t[tol].r1-t[tor].a+t[tor].b,t[tol].r2+t[tor].a+t[tor].b});
	t[id].r2=max(t[tor].r2,t[tol].r2+t[tor].a-t[tor].b);
	t[id].dis=max({t[tol].r1+t[tor].l2,t[tol].r2+t[tor].l1,t[tol].dis,t[tor].dis});
}
void build(int id,int l,int r){
	if(l==r){
		push(id,l);
		return;
	}
	int mid(l,r);
	build(tol,l,mid);
	build(tor,mid+1,r);
	merge(id);
}
void modify(int id,int l,int r,int x){
	if(l==r){
		push(id,l);
		return;
	}
	int mid(l,r);
	if(x<=mid){
		modify(tol,l,mid,x);
	}
	else{
		modify(tor,mid+1,r,x);
	}
	merge(id);
}
int main(){
	scanf("%d",&n);
	cnt=n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	build(1,1,tot); 
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		char op='\n';int x;
		while(op!='G' and op!='C') op=getchar();
		if(op=='C'){
			scanf("%d",&x);
			if(c[x]){
				c[x]=0;
				cnt++;
			}
			else{
				c[x]=1;
				cnt--;
			}
			modify(1,1,tot,pos[x]);
		}
		else if(cnt==0){
			printf("-1\n");
		}
		else if(cnt==1){
			printf("0\n");
		}
		else{
			printf("%d\n",t[1].dis);
		}
	}
}

标签:le,tol,集训,int,sum,CSP,tor,暑假,id
From: https://www.cnblogs.com/HaneDaCafe/p/18314713

相关文章

  • 「模拟赛」暑期集训CSP提高模拟3(7.20)
    仍在施工...$165pts,Rank18$B题挂了45分,不然可以AC两道题的,呜题目列表:A.abc猜想B.简单的排列最优化题C.简单的线性做法题D.简单的线段树题A.abc猜想题意:给定三个正整数\(a,b,c\),你需要求出\(a^b\)除以\(c\)并向下取整得到的值对\(c\)取模的结果......
  • 暑假集训CSP提高模拟2 & 暑假集训CSP提高模拟3
    暑假集训CSP提高模拟2&暑假集训CSP提高模拟3暑假集训CSP提高模拟2纯纯科普场,打的还行。T1活动投票:摩尔投票板子。T2序列:考虑枚举端点没什么前途,考虑一个点能对多少区间产生贡献。考虑一个点的\(nxt\)和\(pre\)(表示下、上一个和他相同的点),当左端点在\(pre\simi......
  • 24-暑假软件工程周报(3)
    本周,我继续深入学习Hadoop和HBase。在上次报告的基础上,我主要集中在HBase的配置和使用方面,并遇到了一些问题,通过查阅资料和调试成功解决了这些问题。1.我学习了HBase的基本概念和架构。HBase是一个基于HadoopHDFS的分布式数据库,专门用于处理大规模数据的随机读写。它通过Zookeep......
  • 2024 暑假友谊赛 2
    2024暑假友谊赛2A-......
  • 暑假集训csp提高模拟3
    赛时rank20,T10,T245,T320,T495T1粘了两遍(因为OJ卡第一次没有显示出来)CE了,挂了100,T4没卡常挂了5汤碗了!!!!!!!!!!!!!!!T1abc猜想对于任意整数\(c\)都有\[\left\lfloor\frac{a}{b}\right\rfloor+c=\left\lfloor\frac{a}{b}+c\right\rfloor=\left\lfloor\frac{a+bc}{b}\right\rf......
  • 暑假集训记录
    这里记一些从7.15开始做的NOI篇或者让人眼前一亮的题目/trick。(哦,前面的题可能忘了某些细节了。)P3452求补图连通块个数。P4555首先看到回文串,先上马拉车。然后发现马拉车双回文不好做,考虑拆成两部分。大概就是维护一个以\(i\)为左端点/右端点的最长回文串。然后......
  • 暑假学习Java第三周
    通过本周的学习我认识到了自己有很多的不足与优点,优点是我能够把问题细化逐步分析,缺点是我的意志力不够坚定。我还了解了Java的三大特性包括:面向对象:Java是一种面向对象的编程语言,它允许程序员定义一系列关于对象和类的概念,并将这些概念作为编程的基本单位。在实际内容中,面向对象......
  • 2024 暑假友谊赛 2
    A题目链接思路:枚举每个十字中心点,合法就标记,最后若还剩下点没被标记就NO#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definePIIpair<int,int>constintN=1e6+5,mod=998244353,Mod=1e9+7;intdx[4]={-1,0,1,0};intdy[4......
  • 暑假第三周总结(7.15-7.20)
    这周做了什么继续学习JAVA,做出了城堡游戏点击查看代码//RoompackagecastleV3;importjava.util.HashMap;publicclassRoom{ privateStringdescription;privateHashMap<String,Room>exits=newHashMap<String,Room>();publicRoom(String......
  • 暑假集训CSP提高模拟3
    暑假集训CSP提高模拟3\(T1\)P117.abc猜想\(100pts\)原题:[ARC111A]SimpleMath2由题,有\(\dfrac{(a^{b}-a^{b}\bmodc)\bmodc^{2}}{c}\)即为所求。证明设\(\left\lfloor\dfrac{a^{b}}{c}\right\rfloor=\dfrac{a^{b}-a^{b}\bmodc}{c}=kc+r\),其中\(r......