首页 > 其他分享 >NOIP模拟2总结

NOIP模拟2总结

时间:2023-08-20 20:55:17浏览次数:38  
标签:总结 NOIP int dp EGOI 2021 300005 模拟 dis

NOIP模拟2总结

目录

整体上:

T1非常简单,但是在简单的T2耗费了大量的时间用于证明,导致简单的T3题都没看就跳过,T4暴力没得分

个体上

第一题:zeros EGOI 2021 day1 t1

统计2/5数量即可,非常好想,也非常简单

第二题:luna EGOI 2021 day1 t2

我用了1h的时间去证明每一次选择距离最小的区间然后进行操作肯定是最优秀的,但是没有想到如何nlogn时间解决。
虽然思路上我自己也想用线段树搞定,但不知道这种类型怎么写。
其实呢,这是因为我没有发现更多的性质导致的,有点悲伤。其实这个性质我也是想过(交错的区间不影响),但没想到会对算法有优化作用

第三题:cows EGOI 2021 day2 t3

很可惜,因为字太多直接跳过了,但其实比较好打的。
首先看到什么最大的最小/最小的最大这些,肯定二分答案,然后判断合理性。
先判断是否存在答案:我考虑所有二分的答案,如果牛能到达人的区域,或者建立墙后人无法互相到达,G。
然后对于判断是否合理:
肯定存在单调性:要是我把修理值放宽(变大)的话,人的活动范围肯定就可以扩大,更有利于答案合理,反之亦然。

好,确定算法后,考虑如何实现。
1.预处理所有可建墙点到所有人活动点的最短距离。(可以用'0'作为虚拟源点链接所有人活动点跑dj),跑完后令其为dis_i。
2.二分答案x。
3.对于所有的dis_i比x小的点染上颜色1。(新建一个颜色数组来搞)
4.对牛跑bfs,到颜色1或者3就不能继续bfs(但是要处理到),对于所有能到达的颜色1标记为颜色3
(此时颜色3就是你最大能扩展的区域)
5.对任意一个人的节点,跑dfs,碰到颜色3就返回,所有dfs到的点vis标记为1。
6.遍历所有点,对于人的区域查看他的vis是否为1来判断所有人的区域是否联通。
代码如下:
注意初始化的long long


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
int col[300005];
int dp[300005];
int dis[300005];
bool vis[300005];
vector<int>choose;
int n,m;
struct pr{
	int ans;
	int id; 
	bool operator <(const pr &x)const{
        return x.ans<ans;
    }
};
struct node{
	int to;
	int dis;
}; 
vector<node>mp[300005];
void dj(int s){
	priority_queue<pr>q;
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=0;	
	}
	dis[s]=0;
	q.push((pr){0,s});
    while(!q.empty()){
        pr temp=q.top();
        q.pop();
        int u=temp.id;//这是出发点 
        if(!vis[u]){
        	vis[u]=1;
	        for(int i=0;i<mp[u].size();i++){
				int to=mp[u][i].to;
				int val=mp[u][i].dis;
				if (dis[to]>dis[u]+val) {
					dis[to]=dis[u]+val;
//					dp[to]=min(dis[to],dp[to]);/////////////////////////////////////
					q.push((pr){dis[to],to});
				}
	        }
		}
    }
}
int pin[300005];
bool vvis[300005];
bool viss[300005];
void dfs(int x){
	viss[x]=1;
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i].to;
		if(viss[to]==1||pin[to]==3||to==0){
			continue;
		}
		dfs(to);
	}
}
bool check(int x){//logn
	memset(pin,0,sizeof(pin));//nlogn
	memset(vvis,0,sizeof(vvis));
	memset(viss,0,sizeof(viss));
	queue<int>q;
	for(int i=1;i<=n;i++){//nlogn
		if(col[i]==0&&dp[i]<=x){
			pin[i]=1;//筑墙点 
		}
		if(col[i]==-1){
			q.push(i);
		}
		if(col[i]==1){
			pin[i]=2;
		}
	}
	while(q.size()){
		int tmp=q.front();
		q.pop();
		vvis[tmp]=1;
		for(int i=0;i<mp[tmp].size();i++){
			int to=mp[tmp][i].to;
			if(vvis[to]||to==0){
				continue;
			}
			else if(pin[to]==1||pin[to]==3){
				pin[to]=3;//真正的筑墙点 
				continue;
			}
			else if(col[to]==1){
				return 0;
			}
			else{
				vvis[to]=1;
				q.push(to);
			}
		}
	} 
	for(int i=1;i<=n;i++){
		if(col[i]==1){
			dfs(i);
			break;
		}
	}
	bool yes=1;
	for(int i=1;i<=n;i++){
		if(col[i]==1&&viss[i]==0){
			yes=0;
			break;
		}
	}
	return yes;
}




void findans(int x){//logn
	memset(pin,0,sizeof(pin));//nlogn
	memset(vvis,0,sizeof(vvis));
	memset(viss,0,sizeof(viss));
	queue<int>q;
	for(int i=1;i<=n;i++){//nlogn
		if(col[i]==0&&dp[i]<=x){
			pin[i]=1;//筑墙点 
		}
		if(col[i]==-1){
			q.push(i);
		}
		if(col[i]==1){
			pin[i]=2;
		}
	}
	while(q.size()){
		int tmp=q.front();
		q.pop();
		vvis[tmp]=1;
		for(int i=0;i<mp[tmp].size();i++){
			int to=mp[tmp][i].to;
			if(vvis[to]||to==0){
				continue;
			}
			else if(pin[to]==1||pin[to]==3){
				if(pin[to]==1){
					choose.push_back(to);
				}
				pin[to]=3;//真正的筑墙点 
				continue;
			}
			else if(col[to]==1){
				continue;
			}
			else{
				vvis[to]=1;
				q.push(to);
			}
		}
	} 
}
signed main(){
//	freopen("cows.in","r",stdin);
//	freopen("cows.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&col[i]); 
		dp[i]=inf;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		mp[u].push_back((node){v,w});
		mp[v].push_back((node){u,w});
	}
	int l=inf;
	int r=0;
	for(int i=1;i<=n;i++){
		if(col[i]==1){
//			dj(i);
//			for(int j=1;j<=n;j++){
//				dp[j]=min(dp[j],dis[j]); 
//			} 这里可以视为一个点化简修改
			mp[0].push_back((node){i,0}); 
			mp[i].push_back((node){0,0}); 
		} 
	}
	dj(0);
	
	for(int i=1;i<=n;i++){
		dp[i]=dis[i];
	}
//	for(int i=1;i<=n;i++){
//		printf("%lld ",dp[i]);
//	}
//	printf("\n");
	for(int i=1;i<=n;i++){
		if(col[i]==0){
			l=min(l,dp[i]);
			r=max(r,dp[i]);	
		}
	}
	int mx=r+1;
	r++;
	while(l<=r-1){
		int mid=(l+r)/2;
		if(check(mid)){//可以,尝试缩小这个最大值 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	if(r==mx){
		printf("-1");
		return 0;
	}
	findans(r);
	printf("%lld\n",choose.size());
	for(int i=0;i<choose.size();i++){
		printf("%lld ",choose[i]);
	} 
} 

第四题:lanterns EGOI

确实不会,区间dp难搞(考场上肯定暴力)
洁身自好,不抄题解代码,就不补了。

标签:总结,NOIP,int,dp,EGOI,2021,300005,模拟,dis
From: https://www.cnblogs.com/linghusama/p/17644553.html

相关文章

  • 假期第六周总结
    这周我学习了解了之后要完成的网站建设任务,并对其中需要用到的技术进行了一些了解和学习。然而,我发现自己和完成任务之间还存在一些差距。特别是在大数据的知识方面,我还需要进一步学习。此外,我也在网站建设的前后端技术方面努力巩固之前学习的Javaweb知识。我学习了Javaweb的基......
  • 构建高效远程团队协作网络的最佳实践分享与经验总结
    随着全球化和科技发展的推进,越来越多的企业开始采用远程办公模式。构建高效远程团队协作网络成为了提高工作效率和团队凝聚力的关键。本文将分享一些构建高效远程团队协作网络的最佳实践和经验总结,帮助团队更好地远程协作。1.选择合适的协作工具选择适合团队需求的协作工具是构......
  • 本周总结
    本周回顾这周也就是在配环境、学习啥的,还抽出了两三天和好朋友出去玩儿啦!遇到的问题hadoop启动有点儿问题,按照教程来,教程好了,我没了解决方法查找其他的教程解决对应的问题,完美解决啦!下周预计接着进行相关知识的学习,应对不久之后的开学考试!......
  • 算法总结
    前言:有关于算法的一切的大合集基本数据结构及排序方法手撸完全二叉树/满二叉树红黑树节点分为红色或者黑色;根节点必为黑色;叶子节点都为黑色,且为null;连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点);从任意节点出发,到其每个叶子节点的路径中包含相同数......
  • CSP模拟26
    可做场,拜谢fengwu老师。A.Reversi(AGC031B)题目链接一眼切了设$dp_i$表示考虑到第$i$个石头的总方案数。可由两种情况转移,不选择染色和选择染色,不染色直接由$dp_{i-1}$转移过来,染色由上一个和当前颜色相同的的石头转移过来,相当于把两个石子之间的染色。因为一......
  • 「C」2022/10/26晚学习总结
    2022/10/26晚学习总结主要内容范围:教材23章今晚浅学了一点点东西,记录一下.fma函数在math.h里,浮点数乘加,比自己手动算精度高.doublefma(doublex,doubley,doublez);返回值:x*y+zmemcpy函数在string.h里,内存复制,他和strcpy的区别是,他不仅仅能复制字符......
  • C++ 变量初始化总结
    堆空间,new操作初始化1、对于有自己写构造函数的类,不论类型名后面有没有括号()或者数组[],都用构造函数进行初始化,如果构造函数delete,则编译报错;2、如果没有构造函数,则不加括号的new只分配内存空间,不进行内存的初始化,3、而加了括号()的new会在分配内存的同时初始化为0。栈空间......
  • CSP模拟赛题解
    目录CSP模拟16T1:糖果CSP模拟17T1:弹珠游戏T2:晚会CSP模拟18T1:TheThirdLetterT2:InaoftheMountainCSP模拟19T1:StrangeFunctionT2:DZYLovesModificationCSP模拟21T1:[CEOI2016]kangarooT2:[JOI2023Final]Advertisement2T3:YourCSP模拟22T1:TheChildandToyCSP模拟16T1:......
  • LCD常见接口总结
    LCD的接口有多种,分类很细。主要看LCD的驱动方式和控制方式,目前手机上的彩色LCD的连接方式一般有这么几种:MCU接口(也写成MPU接口的),RGB接口,SPI接口VSYNC接口,MIPI接口、MDDI接口,DSI接口等。其中只有TFT模块才有RGB接口。应用比较多的就是MCU接口和RGB接口。MCU接口因为主要针对单片机......
  • FEMU模拟器学习笔记
     QEMU参数解析  QEMU的main函数进来后,首先要进行参数解析。一个启动模拟器的命令行如下:x86_64-softmmu/qemu-system-x86_64-name"FEMU-ZNSSD-VM"-enable-kvm-cpuhost-smp2-m4G-devicevirtio-scsi-pci,id=scsi0-devicescsi-hd,drive=hd0-drivefile=/home......