2018.12.30【NOIP提高组】模拟A组

前言

去上海了，所以没有比赛，不过还是看了题目

JZOJ 5353 村通网

题目

一座建筑有网，当且仅当满足以下至少一个条件：
1、直接连网，花费为$A$。
2、连接有网的建筑，花费为$B$×两者曼哈顿距离。
有$N$座建筑，知道所有建筑的坐标，问最少要多少费用才能达到目的。

分析

那么这道题就是一道比较裸的最小生成树，由于任意点间都能连边，所以说kruskal没有什么大优势，在此用的是裸的prim，那么怎么做呢，我的想法是建立一个虚拟点，那么其他点的费用就是A，然后在其他点跑最小生成树，所连的边权和就是答案

代码

#include <cstdio>
#include <climits>
#include <cctype>
#include <algorithm>
#define rr register
#define fre(t) freopen(t".in","r",stdin),freopen(t".out","w",stdout)
using namespace std;
int n,t,ans,dis[1001],x[1001],y[1001]; bool v[1001];
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c==45)?-f:f,c=getchar();while (isdigit(c)) ans=ans*10+(c-48),c=getchar();return ans*f;
}
inline void mmin(int &a,int b){if (a>b) a=b;}
inline signed abs(int x){return x<0?-x:x;}
signed main(){fre("pupil"); dis[0]=INT_MAX; n=iut();fill(dis+1,dis+1+n,iut()); t=iut();for (rr int i=1;i<=n;++i) x[i]=iut(),y[i]=iut();for (rr int i=1;i<=n;++i){rr int k=0;for (rr int j=1;j<=n;++j)if (!v[j]&&dis[j]<dis[k]) k=j;ans+=dis[k]; v[k]=1;for (rr int j=1;j<=n;++j) if (!v[j]) mmin(dis[j],(abs(x[k]-x[j])+abs(y[k]-y[j]))*t);}printf("%d",ans);return 0;
}

JZOJ 5354 导弹拦截

题目

分析

然而，第一问的动态规划还是按原来的打，但是第二问就尴尬了，本来想照着老样子打，没想到WA了！
后来发现第二问竟然是匈牙利算法，求最大独立集，当第一问$i$点由$j$点推来，那么从$i$向$j$连边，跑匈牙利就可以输出答案了。但是还是WA了！
导弹同时飞来，这可真是要命，那么可以提前对一个坐标排序，然后按照刚才的方法，AC

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#define rr register
#define fre(t) freopen(#t".in","r",stdin),freopen(#t".out","w",stdout)
using namespace std;
struct node{int y,next;}e[500001]; 
struct rec{int x,y,z;}a[1001]; bool cover[1001];
int n,dp[1001],ans,link[1001],ls[1001],k=1;
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c==45)?-f:f,c=getchar();while (isdigit(c)) ans=ans*10+(c-48),c=getchar();return ans*f;
}
bool cmp(rec i,rec j){return i.x<j.x;}
inline signed dfs(int x){for (rr int i=ls[x];i;i=e[i].next)if (!cover[e[i].y]){rr int q=link[e[i].y];link[e[i].y]=x; cover[e[i].y]=1;if (!q||dfs(q)) return 1;link[e[i].y]=q;}return 0;
} 
signed main(){fre(missile); n=iut();for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),iut(),iut()};sort(a+1,a+1+n,cmp);for (rr int i=1;i<=n;++i){dp[i]=1;for (rr int j=1;j<i;++j)if (a[j].x<a[i].x&&a[j].y<a[i].y&&a[j].z<a[i].z)dp[i]=dp[i]>dp[j]+1?dp[i]:dp[j]+1,e[++k]=(node){j,ls[i]},ls[i]=k;//动态规划ans=ans>dp[i]?ans:dp[i];}printf("%d\n",ans); ans=0;for (rr int i=1;i<=n;++i){memset(cover,0,sizeof(cover));ans+=dfs(i);}printf("%d",n-ans);//最大独立集，用节点数-最大匹配return 0;
}

JZOJ 5355 保命

声明

因为JZOJ无人AC，且暂时不想做此题（斜率优化），所以说暂时不做

后续

未完待续