NOIP模拟2总结
NOIP模拟2总结
目录
- NOIP模拟2总结
- 整体上：
- 个体上
- 第一题：zeros EGOI 2021 day1 t1
- 第二题：luna EGOI 2021 day1 t2
- 第三题：cows EGOI 2021 day2 t3
- 第四题：lanterns EGOI
整体上：
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难搞（考场上肯定暴力）
洁身自好，不抄题解代码，就不补了。