NOIP 2017提高组复赛试题及解题报告(3)

-Day2-
1.奶酪 (cheese.cpp/c/pas)

【问题描述】
现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为z = 0,奶酪的上表面为z = h。

现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

空间内两点P(x ,y ,z )、P(x ,y ,z )的距离公式如下:

【输入格式】
输入文件名为 cheese.in。

每个输入文件包含多组数据。

输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。

接下来是 T 组数据,每组数据的格式如下:

第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。

接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x, y, z)。

【输出格式】
输出文件名为 cheese.out。

输出文件包含 T 行,分别对应 T 组数据的答案,如果在第 i 组数据中,Jerry 能从下表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。

【输入输出样例 1】
cheese.in
3
2  4  1
0  0  1
0  0  3
2  5  1
0  0  1
0  0  4
2  5  2
0  0  2
2  0  4
cheese.out
Yes
No
Yes

【数据规模与约定】
对于 20%的数据,n = 1,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 40%的数据,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 80%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20,坐标的绝对值不超过 1,000,000,000。

【题目解答】
真正的T1,并查集+高二数学常识。

用并查集做,将位置相距小于等于2倍半径的归为一个集合。注意:Z位置+半径>=H的,与1001归为一个集合。Z位置-半径<=0的,与0归为一个集合。最后看0和1001是否在一个集合中。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
int t,n,h,r,x,y,z,f,fa[1002],t1,t2;
struct sb
{
int x;
int y;
int z;
}a[1001];
intfind(int k)
{
if(fa[k]!=k)
fa[k]=find(fa[k]);
return fa[k];
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>h>>r;
for(int i=1;i<=n;i++)
fa[i]=i;
fa[0]=0;
fa[1001]=1001;
for(int j=1;j<=n;j++)
{
cin>>a[j].x>>a[j].y>>a[j].z;
if(a[j].z+r>=h)
{
t1=find(j);
t2=find(1001);
fa[t1]=t2;
}
if(a[j].z-r<=0)
{
t1=find(j);
t2=find(0);
fa[t1]=t2;
}
for(int w=1;w<j;w++)
{
if(sqrt((a[j].x-a[w].x)*(a[j].x-a[w].x)+(a[j].y-a[w].y)*(a[j].y-a[w].y)+(a[j].z-a[w].z)*(a[j].z-a[w].z))<=2*r)
{
t1=find(j);
t2=find(w);
fa[t1]=t2;
}
}
}
t1=find(0);
t2=find(1001);
if(t1==t2)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}

2. 宝藏 (treasure.cpp/c/pas)

【问题描述】
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 n 个深埋在地下的宝藏屋,也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。

在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是:

这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋)。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代价最小,并输出这个最小值。

【输入格式】
输入文件名为 treasure.in。

第一行两个用空格分离的正整数 n 和 m,代表宝藏屋的个数和道路数。

接下来 m 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为 1~n),和这条道路的长度 v。

【输出格式】
输出文件名为 treasure.out。

输出共一行,一个正整数,表示最小的总代价。

【输入输出样例 1】
treasure.in
4  5
1  2  1
1  3  3
1  4  1
2  3  4
3  4  1
treasure.out
4

【样例输入输出 2】
treasure.in
4  5
1  2  1
1  3  3
1  4  1
2  3  4
3  4  2
treasure.out
5

【数据规模与约定】
对于 20%的数据:
保证输入是一棵树,1≤n≤8,v≤5000 且所有的 v 都相等。
对于 40%的数据:
1≤n≤8,0≤m≤1000,v≤5000 且所有的 v 都相等。
对于 70%的数据:
1≤n≤8,0≤m≤1000,v≤ 5000
对于 100%的数据:
1≤n≤12,0≤m≤1000,v≤ 500000

【题目解答】
状压DP

一看n<=12,明显是状压DP的数据范围。于是令f[i][S]表示当前与根连通的点的状态为S,并且最深的点的深度为i的最小代价。转移时,我们枚举所有不在S中的点,处理出每个点与S中的某个点连通所需要的最小代价。然后枚举这些点构成的所有集合S',用S'中所有点的代价+f[i][S]去更新f[i+1][S|S']即可。时间复杂度:O(n3n)。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
int n,m,tot,ans;
int map[110][110],dis[110][110],Log[4100];
int f[15][4100],g[4100],ref[4100],v[15],p[15];
inline int min(const int &a,const int &b)
{
return a<b?a:b;
}
int main()
{
scanf("%d%d",&n,&m);
register int i,j,a,b,c,x;
for(i=0;i<n;i++) for(j=0;j<n;j++)map[i][j]=60000000;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c),a--,b--;
map[a][b]=map[b][a]=min(map[a][b],c);
}
for(i=0;i<n;i++) Log[1<<i]=i;
memset(f,0x3f,sizeof(f));
for(i=0;i<n;i++) f[0][1<<i]=0;
for(i=0;i<n;i++)for(x=0;x<(1<<n);x++)
{
tot=0;
for(a=0;a<n;a++) if(!(x&(1<<a)))
{
v[tot]=60000000,p[tot]=1<<a;
for(j=x;j;j-=j&-j)
{
b=Log[j&-j];
v[tot]=min(v[tot],map[a][b]*(i+1));
}
tot++;
}
for(j=1;j<(1<<tot);j++)
{
g[j]=g[j-(j&-j)]+v[Log[j&-j]];
ref[j]=ref[j-(j&-j)]|p[Log[j&-j]];
f[i+1][x|ref[j]]=min(f[i+1][x|ref[j]],f[i][x]+g[j]);
}
}
ans=1<<30;
for(i=0;i<=n;i++)    ans=min(ans,f[i][(1<<n)-1]);
printf("%d",ans);
return 0;
}

3.列队 (phalanx.cpp/c/pas)

【问题描述】
Sylvia是一个热爱学习的女孩子。

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。Sylvia 所在的方阵中有n × m名学生,方阵的行数为 n,列数为 m。

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码(参见后面的样例)。即:初始时,第 i 行第 j 列的学生的编号是(i−1)×m+j。

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了q件这样的离队事件。每一次离队事件可以用数对(x,y) (1≤x≤n, 1≤y≤m)描述,表示第 x 行第 y 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:

1.向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 x 行第 m列。

2.向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 n 行第 m列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。

【输入格式】
输入文件名为 phalanx.in。

输入共 q+1 行。

第 1 行包含 3 个用空格分隔的正整数 n, m, q,表示方阵大小是n行 m 列,一共发生了 q 次事件。

接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。

【输出格式】
输出文件名为 phalanx.out。

按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。

【输入输出样例 1】
phalanx.in
2  2  3
1  1
2  2
1  2
phalanx.out
1
1
4

【数据规模与约定】

数据保证每一个事件满足 1≤x≤n,1≤y≤m。

【题目解答】
离线+平衡树

由于操作是可逆的,所以将所有操作反过来做,将人的移动改成询问的反向移动,那么只需要维护这些询问点的移动即可,不难想到用数据结构。将操作顺序反过来,那么一次操作(x,y)可以看成:

1.(n,m)的学生出队;

2.第n列中,第x行及以下的所有学生下移一格;

3.第x行中,第y列及右面的所有学生右移一格;

4.将当前询问的学生放到(x,y)处。

鉴于这些操作,可以选择平衡树,那么1操作就是单点删除,2,3操作就是区间加法,4操作就是单点加入。对每一行,以及最后一列都开一棵SBT,维护其中的所有询问即可。并且注意:每一行y的范围是[1,m),即如果一行的最右面的元素位于最后一列,要将其从这一行删除,并加入到最后一列中。还有一点,如果(n,m)处有询问,说明那个询问与当前询问是重合的,所以记录一个类似于pre的东西,将那个询问的pre指向当前询问,并将那个询问删除。输出答案的时候直接令该询问的答案等于其pre的答案即可。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=300010;
typedef long long ll;
struct node
{
int ch[2],siz,val,org,tag;
}s[maxn<<1];
int n,m,q,tot;
int rx,ry[maxn];
int bel[maxn],x[maxn],y[maxn];
ll ans[maxn];
inline int rd()
{
int ret=0; char gc=getchar();
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9')   ret=ret*10+gc-'0',gc=getchar();
return ret;
}
inline void pushdown(int x)
{
if(s[x].tag)
{
if(s[x].ch[0]) s[s[x].ch[0]].val+=s[x].tag,s[s[x].ch[0]].tag+=s[x].tag;
if(s[x].ch[1]) s[s[x].ch[1]].val+=s[x].tag,s[s[x].ch[1]].tag+=s[x].tag;
s[x].tag=0;
}
}
inline void pushup(int x)
{
s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;
}
inline void rotate(int &x,int d)
{
int y=s[x].ch[d];
pushdown(x),pushdown(y);
s[x].ch[d]=s[y].ch[d^1],s[y].ch[d^1]=x;
pushup(x),pushup(y);
x=y;
}
inline void maintain(int &x,int d)
{
if(s[s[s[x].ch[d]].ch[d]].siz>s[s[x].ch[d^1]].siz)   rotate(x,d);
else   if(s[s[s[x].ch[d]].ch[d^1]].siz>s[s[x].ch[d^1]].siz)rotate(s[x].ch[d],d^1),rotate(x,d);
else   return ;
maintain(s[x].ch[d],d),maintain(s[x].ch[d^1],d^1);
maintain(x,d),maintain(x,d^1);
}
void insert(int &x,int y,int z)
{
if(!x)
{
x=++tot,s[x].siz=1,s[x].ch[0]=s[x].ch[1]=s[x].tag=0,s[x].val=y,s[x].org=z;
return ;
}
pushdown(x);
int d=(y>s[x].val);
insert(s[x].ch[d],y,z),pushup(x);
maintain(x,d);
}
void del(int &x,int y)
{
s[x].siz--,pushdown(x);
if(s[y].val>s[x].val)    del(s[x].ch[1],y);
else if(s[y].val<s[x].val)   del(s[x].ch[0],y);
else
{
if(!s[x].ch[0]||!s[x].ch[1])
{
x=s[x].ch[0]^s[x].ch[1];
return ;
}
int u=s[x].ch[1];   pushdown(u);
while(s[u].ch[0])   u=s[u].ch[0],pushdown(u);
s[x].org=s[u].org,s[x].val=s[u].val;
del(s[x].ch[1],u);
}
}
void updata(int x,int y)
{
if(!x) return ;
pushdown(x);
if(s[x].val>=y)
{
s[x].val++;
if(s[x].ch[1])  s[s[x].ch[1]].val++,s[s[x].ch[1]].tag++;
updata(s[x].ch[0],y);
}
else   updata(s[x].ch[1],y);
}
inline int findmax(int x)
{
pushdown(x);
while(s[x].ch[1])   x=s[x].ch[1],pushdown(x);
return x;
}
inline ll point(int a,int b) {return ll(a-1)*m+b;}
void dfs(int x,int t)
{
if(!x) return ;
pushdown(x);
if(!t) ans[s[x].org]=point(s[x].val,m);
else   ans[s[x].org]=point(t,s[x].val);
dfs(s[x].ch[0],t),dfs(s[x].ch[1],t);
}
int find(int x,int y)
{
if(!x) return 0;
pushdown(x);
if(y>s[x].val)   return find(s[x].ch[1],y);
if(y<s[x].val)   return find(s[x].ch[0],y);
return x;
}
int main()
{
n=rd(),m=rd(),q=rd();
int i;
for(i=1;i<=q;i++)
{
bel[i]=i;
x[i]=rd(),y[i]=rd();
}
for(i=q;i>=1;i--)
{
int t=findmax(rx);
if(s[t].val==n)
{
bel[s[t].org]=i,del(rx,t);
}
updata(rx,x[i]);
updata(ry[x[i]],y[i]);
t=findmax(ry[x[i]]);
if(s[t].val==m)
{
del(ry[x[i]],t),insert(rx,x[i],s[t].org);
}
if(y[i]<m)   insert(ry[x[i]],y[i],i);
else   insert(rx,x[i],i);
}
dfs(rx,0);
for(i=1;i<=n;i++)    dfs(ry[i],i);
for(i=1;i<=q;i++)   printf("%lldn",ans[i]=ans[bel[i]]);
return 0;
}

本文链接:NOIP 2017提高组复赛试题及解题报告(3)

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
CSP和NOIP是什么关系?
CSP和NOIP是什么关系?
中国计算机学会推出的CSP-S/J测试或将被视为替代NOIP
中国计算机学会推出的CSP-S/J测试或将被…
NOIP 2017提高组复赛试题及解题报告(2)
NOIP 2017提高组复赛试题及解题报告(2)
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
为什么越来越多家长选择信息学竞赛?
为什么越来越多家长选择信息学竞赛?
孩子学完各个阶段的编程课程能够参加哪些比赛?
孩子学完各个阶段的编程课程能够参加哪…
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。