NOIP2017提高组 day2

2023-12-17 14:41:40

1.奶酪

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

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

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

空间内两点 P 1 ( x 1 , y 1 , z 1 ) P_1(x_1,y_1,z_1) P1(x1,y1,z1)、 P 2 ( x 2 , y 2 , z 2 ) P_2(x_2,y_2,z_2) P2(x2,y2,z2) 的距离公式如下：

d i s t ( P 1 , P 2 ) = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 + ( z 1 − z 2 ) 2 \mathrm{dist}(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2

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

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

接下来是 T T T 组数据，每组数据的格式如下：第一行包含三个正整数 n , h , r n,h,r n,h,r 两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

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

输出格式
T T T 行，分别对应 T T T 组数据的答案，如果在第 i i i 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。

输入输出样例

输入 #1

输出 #1

Yes
No
Yes

说明/提示

【输入输出样例 1 1 1 说明】

第一组数据,由奶酪的剖面图可见：

第一个空洞在 ( 0 , 0 , 0 ) (0,0,0) (0,0,0) 与下表面相切；

第二个空洞在 ( 0 , 0 , 4 ) (0,0,4) (0,0,4) 与上表面相切；

两个空洞在 ( 0 , 0 , 2 ) (0,0,2) (0,0,2) 相切。

输出 Y e s Yes Yes。

第二组数据,由奶酪的剖面图可见：

两个空洞既不相交也不相切。

输出 N o No No。

第三组数据,由奶酪的剖面图可见：

两个空洞相交，且与上下表面相切或相交。

输出 Y e s Yes Yes。

【数据规模与约定】

对于 20 % 20\% 20% 的数据， n = 1 n = 1 n=1， 1 ≤ h 1 \le h 1≤h， r ≤ 1 0 4 r \le 10^4 r≤104 ，坐标的绝对值不超过 1 0 4 10^4 104。
对于 40 % 40\% 40% 的数据， 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8， 1 ≤ h 1 \le h 1≤h， r ≤ 1 0 4 r \le 10^4 r≤104 ，坐标的绝对值不超过 1 0 4 10^4 104。
对于 80 % 80\% 80% 的数据， 1 ≤ n ≤ 1 0 3 1 \le n \le 10^3 1≤n≤103， 1 ≤ h 1 \le h 1≤h , r ≤ 1 0 4 r \le 10^4 r≤104 ，坐标的绝对值不超过 1 0 4 10^4 104。
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 × 1 0 3 1 \le n \le 1\times 10^3 1≤n≤1×103， 1 ≤ h , r ≤ 1 0 9 1 \le h , r \le 10^9 1≤h,r≤109， T ≤ 20 T \le 20 T≤20，坐标的绝对值不超过 1 0 9 10^9 109。

分析

我做这道题的思路是dfs深搜，每次从能经过下表面的洞开始，遍历每一个洞，如果两洞圆心距离小于 2 r 2r 2r 则标记+转移，终止条件为该洞圆心坐标+半径大于奶酪最高点。代码也就呼之欲出了。

AC代码

#include<bits/stdc++.h> //奶酪 
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
double x[1005],y[1005],z[1005],h,r;
int t,n,vis[1005];
bool flag=0;
double dis(double x,double y,double z,double x1,double y1,double z1){  //距离函数
	return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1));
}
void dfs(double x1,double y1,double z1){                               //深搜
	if(z1+r>=h){
		flag=1;
		return;
	}
	if(flag){
		return;
	}
	for(int i=1;i<=n;++i){
		double derta=dis(x1,y1,z1,x[i],y[i],z[i]);
		if(derta<=2*r&&!vis[i]){
			vis[i]=1;
			dfs(x[i],y[i],z[i]);
		}
	}
}
int main(){
	//freopen("cheese.in","r",stdin);
	//freopen("cheese.out","w",stdout);
	t=read();
	for(int k=1;k<=t;++k){
		flag=0;
		memset(vis,0,sizeof(vis));
		n=read();
		cin>>h>>r;
		for(int l=1;l<=n;++l){
			cin>>x[l]>>y[l]>>z[l];
		}
		for(int l=1;l<=n;++l){
			if(z[l]<=r){
				vis[l]=1;
				dfs(x[l],y[l],z[l]);
				if(flag){
					printf("Yes\n");
					break;
				}
				vis[l]=0;
			}
		}
		if(!flag){
		printf("No\n");
	   }
	}
	return 0;
}

2.宝藏

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

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

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

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

新开发一条道路的代价是 L × K \mathrm{L} \times \mathrm{K} L×K。其中 L L L 代表这条道路的长度， K K K 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

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

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

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

输出格式
一个正整数，表示最小的总代价。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

【样例解释 1 1 1】

小明选定让赞助商打通了 1 1 1 号宝藏屋。小明开发了道路 1 → 2 1 \to 2 1→2，挖掘了 2 2 2 号宝藏。开发了道路 1 → 4 1 \to 4 1→4，挖掘了 4 4 4 号宝藏。还开发了道路 4 → 3 4 \to 3 4→3，挖掘了 3 3 3 号宝藏。

工程总代价为 1 × 1 + 1 × 1 + 1 × 2 = 4 1 \times 1 + 1 \times 1 + 1 \times 2 = 4 1×1+1×1+1×2=4。

【样例解释 2 2 2】

小明选定让赞助商打通了 1 1 1 号宝藏屋。小明开发了道路 1 → 2 1 \to 2 1→2，挖掘了 2 2 2 号宝藏。开发了道路 1 → 3 1 \to 3 1→3，挖掘了 3 3 3 号宝藏。还开发了道路 1 → 4 1 \to 4 1→4，挖掘了 4 4 4 号宝藏。

工程总代价为 1 × 1 + 3 × 1 + 1 × 1 = 5 1 \times 1 + 3 \times 1 + 1 \times 1 = 5 1×1+3×1+1×1=5。

【数据规模与约定】

对于 20 % 20\% 20% 的数据：保证输入是一棵树， 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8， v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103 且所有的 v v v 都相等。
对于 40 % 40\% 40% 的数据： 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8， 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103， v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103 且所有的 v v v 都相等。
对于 70 % 70\% 70% 的数据： 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8， 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103， v ≤ 5 × 1 0 3 v \le 5\times 10^3 v≤5×103。
对于 100 % 100\% 100% 的数据： 1 ≤ n ≤ 12 1 \le n \le 12 1≤n≤12， 0 ≤ m ≤ 1 0 3 0 \le m \le 10^3 0≤m≤103， v ≤ 5 × 1 0 5 v \le 5\times 10^5 v≤5×105。

分析
这道题我在考试的时候用的深搜（结果爆了只有40分），好像最优化剪枝可以0ms过这道题。但正解应该是状压DP

题目简而言之就是
给定一个 N 个点 M 条边的无向图，
要求在图中找出一颗生成树，
满足树上的节点到根节点的深度 d 与该点连到树中的边的权值 w 之积的和最小。

可以使用dfs遍历状态空间，
对于每一个状态state ,摘出其中选定的点，
遍历该点的所有出边，维护一个记录当前点到选定根节点的 dis 数组，
一旦得到当前状态的更优方案，就对 f 数组进行更新，
如此往复直到所有状态都被更新完毕为止。

AC代码

#include<bits/stdc++.h>
using namespace std;
int g[13][13],dis[13],f[1<<13];
int n,m,ans = 0x3f3f3f3f;
void dfs(int state){
    for(int i=1;i<=n;i++){
      if(!((1<<(i-1))&state))  continue;   //如果没被挖                              
        for(int j=1;j<=n;j++){
            if(g[i][j]==0x3f3f3f3f||j==i) continue;                  
            if(f[state|(1<<j-1)]>f[state]+g[i][j]*dis[i]){ //更新           
                int tmp=dis[j];
                dis[j]=dis[i]+1;
                f[state|(1<<(j-1))]=f[state]+g[i][j]*dis[i];
                dfs(state|(1<<(j-1)))                               
                dis[j]=tmp;       //回溯                                
            }
        }
    }
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=min(g[u][v],w);      //重边与长边处理
        g[v][u]=min(g[v][u],w);                                     
    }
    for(int i=1;i<=n;i++){
        memset(dis,0x3f,sizeof(dis));
        memset(f,0x3f,sizeof(f));
        dis[i]=1;
        f[1<<(i-1)]=0;                 //初始化                             
        dfs(1<<(i-1));
        ans=min(ans,f[(1<<n)-1]);                                   
    }
    printf("%d",ans);
    return 0;
}

这份代码能AC，但是会被hack（~~所以还是深搜好~~ ）

3.列队

题目描述

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 n × m n \times m n×m 名学生，方阵的行数为 n n n，列数为 m m m。

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

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

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

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

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

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

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

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

输入格式

输入共 q + 1 q+1 q+1 行。

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

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

输出格式

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

输入输出样例

输入 #1

输出 #1

1
1
4

【数据规模与约定】

测试点编号	n n n	m m m	q q q	其他约定
1~6	≤ 1 0 3 ≤10^3 ≤103	≤ 1 0 3 ≤10^3 ≤103	≤ 500 \leq500 ≤500	无
7~10	≤ 5 × 1 0 4 \leq5\times 10^4 ≤5×104	≤ 5 × 1 0 4 \leq5\times 10^4 ≤5×104	≤ 500 \leq500 ≤500	无
11~12	≤ 1 \leq1 ≤1	≤ 1 0 5 ≤10^5 ≤105	≤ 1 0 5 ≤10^5 ≤105	所有事件 x = 1 x=1 x=1
13~14	≤ 1 \leq1 ≤1	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	所有事件 x = 1 x=1 x=1
15~16	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	所有事件 x = 1 x=1 x=1
17~18	≤ 1 0 5 ≤10^5 ≤105	≤ 1 0 5 ≤10^5 ≤105	≤ 1 0 5 ≤10^5 ≤105	无
19~20	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	≤ 3 × 1 0 5 ≤3\times 10^5 ≤3×105	无

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

分析
关注到11~16的点 x = 1 x=1 x=1,意味着只需要操作第一行和最后一列的学生即可。
当第一行有人出队时，最后一列补上，出队的人又补上最后一列
考虑用队列，但时间复杂度在移人补人的时候极高，故不可取。
不妨用标记？初始所有位置都为1，离队后该位置记为0，只要找出离队的人原始位置就可以计算出他的编号，也就是他的前面有多少个人。
可以用树状数组来维护这个值，用二分来查找位置。

代码如下：

#include<bits/stdc++.h> //列队
using namespace std;
int k,n,m,q,c[1000010];
long long b[1000010];
void Add(int x,int v){
	for(;x<=k;x+=x&(-x))
	  c[x]+=v;
}
int Get(int x){
	int ans=0;
	for(;x;x-=x&(-x))
	  ans+=c[x];
	return ans;
}
int main(){
	k=n+m+q;
    for(int i=1;i<=m;i++)
      b[i]=i,Add(i,1);
    for(long long i=2;i<=n;i++)
      b[m+i-1]=i*m,Add(m+i-1,1);
    int nu=n+m-1; 
    for(int i=1;i<=q;i++){
    	int x,y;
    	int id=0;
    	scanf("%d%d",&x,&y);
    	int l=1,r=nu;
    	while(l+1<r){
    		int mid=(l+r)>>1;
    		if(Get(mid)>=y) r=mid;
			else l=mid+1;
    	}
    	if(Get(l)==y) id=l;
		else id=r;
    	b[++nu]=b[id]; 
		printf("%lld\n",b[id]);
    	Add(id,-1);
    	Add(nu,1);
    	b[id]=0;
    }
    return 0;
}

码农公寓

1.奶酪

2.宝藏

3.列队

相关文章