NOIP2017提高组模拟赛 10 (总结)

时间:2021-04-17 03:55:47

NOIP2017提高组模拟赛 10 (总结)##

第一题 机密信息

	FJ有个很奇怪的习惯,他把他所有的机密信息都存放在一个叫机密盘的磁盘分区里,然而这个机密盘中却没有一个文件,那他是怎么存放信息呢?聪明的你一定想到了,FJ的信息都是以文件夹名称的形式保存的。FJ给机密盘中的每一个文件夹都编了号,而FJ的机密信息是由S文件夹转到T文件夹的过程中必须经过的文件夹名称组合而成的,由于FJ的磁盘很慢,打开每个文件夹所耗费的时间等于该文件夹内下一级文件夹的数量。这次的任务是,给出每个文件夹的编号、名称以及它的父目录的编号和隐藏了FJ机密信息的起始文件夹编号和终点文件夹编号,你要计算出来的是FJ机密信息的长度以及寻找这个机密信息所需要的总时间。假设你一开始就在起始文件夹位置,此时耗费的时间为0;你每打开一个文件夹,能够知道的文件夹名除了当前这个文件夹名之外,还有该文件夹内下一级的文件夹名。

  一道简单的模拟题,暴力找S、T的lca,将路径上的点的值累加。

  是S已经打开,到看到T(也就是打开了T的父亲)的路径。

  注意一些特殊情况:

  ①S是T的祖先,或T是S的祖先。

  ②S和T的祖先不为S或T(需要减掉T打开的时间)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> #define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b)) typedef long long ll; using namespace std; const int N=10050;
int n,S,T,ti[N],tim,fa[N],out[N];
int ls[N],to[N],ne[N],h[N],tt;
int anstime,anslen;
char st[310]; void add(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; } void dfs(int x,int ff)
{
ti[x]=++tim;
for(int p=h[x];p;p=ne[p])
{
int v=to[p];
if(v==ff) continue;
dfs(v,x);
}
} int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d%d",&n,&S,&T);
n++; S++; T++; tt=1;
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d%s",&a,&b,st);
a++; b++; ls[a]=strlen(st);
fa[a]=b; out[b]++; add(b,a);
}
fa[1]=0; tim=0;
dfs(1,1);
if(S==T)
{
printf("%d\n",ls[S]);
printf("0\n");
} else
{
int fs=S,ft=T;
anstime=-out[S]; anslen=0;
if(ti[S]<ti[T]) swap(S,T);
while(ti[fa[S]]>ti[T])
{
anstime+=out[S]; anslen+=ls[S];
S=fa[S];
}
anstime+=out[S]; anslen+=ls[S];
S=fa[S];
while(T!=S)
{
anstime+=out[T]; anslen+=ls[T];
T=fa[T];
}
anstime+=out[T]; anslen+=ls[T];
if(ti[T]!=ti[ft]) anstime-=out[ft];
printf("%d\n",anslen);
printf("%d\n",anstime);
}
return 0;
}

第二题 路由器

	Farmer John最近买了些新电脑,它向为奶牛们提供上网的机会,但是上网需要路由器,FJ想尽量少买路由器。FJ 有N个(1<=N<=100,000)(编号为1..N)个农场,由N-1条长度是1的边连接起来,没有环. FJ 可以决定把路由器放在哪些农场. 每个农场只有长度为 K (0<=K<=10)的网线,该农场可以连接到距离小于等于K的路由器. 路由器本身已经可以连接到互连网,可以被放置到任意的农场.
FJ至少要买多少个路由器,才能让每个农场都能上网?农场想要上网的话,至少要连接到一个包含路由器的农场.

  因为这是一棵树,那么,优先处理最深的点一定是最优的,因为点x可以通过x的后代的路由器上网(而最低点不行)。

  假如最低点为x,要放路由器,尽可能将其放在比较上的地方father[x][K]。因为既然x能到达,那么father[x][K]的其他后代也一定可以到达。而且放得越上,会对上方的点产生更多的贡献。

  解法已经确立了:贪心。

  ①一种比较暴力的方法,先由最低点x开始,若vis[x]=0,则fa[x][L]装上路由器,ans++。拓展vis[],将可以用这个路由器上网的i的vis[i]标为1.

  此方法的时间复杂度较为玄学,应该是不会超时的。vis[]会筛掉很多无用的点(即使重复标记也不会标记很多次的)。

  ②记录far[]和near[],表示(后代)未联网到当前点的最远的距离,以及最近到当前点的路由器距离。若far[x]+near[x]≤K则fa[x]=-∞,若far[x]=K则必须建立一个路由器(far[x]=-∞,near[x]=0),否则far[x]=(max far[xson])+1,near=(min near[xson])+1。

  注:far[]=0,near[]=∞。(此方法是对方法①的一个优化,我也没有想到,是文同学想出来的。)

//方法①:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> #define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b)) typedef long long ll; using namespace std; const int N=100050;
int n,L,ans;
int fa[N][12],open[N],dep[N],he,ta;
int q[N],la,lb,bu[N];
int vis[N],bfstime;
bool ok[N];
int ne[N<<1],to[N<<1],h[N],tt; void add(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; } void bfs(int x)
{
he=ta=1; fa[x][1]=x;
open[1]=x; dep[x]=1; vis[x]=1;
while(he<=ta)
{
int u=open[he++];
for(int p=h[u];p;p=ne[p])
{
int v=to[p];
if(vis[v]!=0) continue;
vis[v]=1; dep[v]=dep[u]+1;
fa[v][1]=u; open[++ta]=v;
}
}
} void expand(int x)
{
la=lb=1; q[1]=x; ok[x]=1;
vis[x]=++bfstime; bu[x]=0;
while(la<=lb)
{
int u=q[la++];
if(bu[u]>=L) continue;
for(int p=h[u];p;p=ne[p])
{
int v=to[p];
if(vis[v]==bfstime) continue;
vis[v]=bfstime; bu[v]=bu[u]+1;
q[++lb]=v; ok[v]=1;
}
}
} int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%d",&n,&L); tt=1;
for(int i=1;i<n;i++)
{
int a,b; scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
bfs(1);
for(int i=1;i<=n;i++)
for(int j=2;j<=L;j++) fa[i][j]=fa[fa[i][j-1]][1];
bfstime=1;
for(int i=ta;i>=1;i--)
{
int u=open[i];
if(!ok[u])
{
ans++;
int yu=fa[u][L];
expand(yu);
}
}
printf("%d\n",ans);
return 0;
}
//PS:一开始bfs漏打了vis[x]=1,WA了两个点……
//方法②:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> #define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b)) typedef long long ll; using namespace std; const int oo=1e9;
const int N=100050;
int n,L,ans;
int open[N],he,ta;
int vis[N],fa[N],far[N],near[N];
int ne[N<<1],to[N<<1],h[N],tt; void add(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; } void bfs(int x)
{
he=ta=1; fa[x]=x;
open[1]=x; vis[x]=1;
while(he<=ta)
{
int u=open[he++]; vis[u]=2;
for(int p=h[u];p;p=ne[p])
{
int v=to[p];
if(vis[v]!=0) continue;
vis[v]=1; fa[v]=u; open[++ta]=v;
}
}
} int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%d",&n,&L); tt=1;
for(int i=1;i<n;i++)
{
int a,b; scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
bfs(1);
ans=0;
for(int i=1;i<=n;i++) far[i]=0,near[i]=oo;
for(int i=ta;i>=1;i--)
{
int u=open[i];
if(vis[u]==1) continue;
if(far[u]+near[u]<=L) far[u]=-oo;
if(far[u]==L) near[u]=0,far[u]=-oo,ans++;
far[fa[u]]=imax(far[u]+1,far[fa[u]]);
near[fa[u]]=imin(near[u]+1,near[fa[u]]);
}
if(far[1]>0) ans++;
printf("%d\n",ans);
return 0;
}

第三题 骨牌游戏

	X