NOIP PJ Training Graduation Test 2019.6 题解

cww970329 2019-06-10 15:46:10

A

众所周知,这是一道签到

B

题目要求我们使任意两台计算机都可直接或间接连通,且使连接费用最小。将计算机看作结点,题目就变成使个点直接或间接相连,且边的权值和最小,求最小和的问题。分析下来,这就是一道最小生成树问题。

最小生成树问题可使用Prime算法或Kruskal算法进行解决。

使用Kruskal算法解题。存储好边的相关信息后,按边的权值,从小到大进行排序。从权值最小的便开始遍历每条边,直至所有结点在同一集合中。对于判断两点是否连通的判断以及连通两点的操作部分,可使用并查集进行辅助处理。

kruskal算法,sort将所有node从小到大排序,再遍历每一个结构体元素,如果a[i].x的祖先不等于a[i].y的祖先,则将二者合并,并将权值累加,即:

for(int i=1;i<=m;i++){
  int fatherx = find(a[i].x);
  int fathery = find(a[i].y);
  if(fatherx != fathery){
    p[fatherx]=fathery;
    k++;
    ans+=a[i].v;
  }
  //因为是n个点的最小生成树,共有n-1条边,所以当合并了n-1条边时候停止
		if(k==n-1){
			break;
		}
	}

最终输出累加和ans,就是最少的花费

C

这道题乍一看是需要一个八维数组表示状态。仔细读题发现其中有个空格0,所有棋子都是与0进行的交换。而0的移动只能基于上下左右,上下左右我们一下子就能想到走迷宫,所以这也是一道搜索题。根据题目要求:找到一种最少步骤的移动方法。最少问题我们用BFS模版套进去。

由于数据可能存在最大值溢出问题,防止意外把数据类型声明成long long(其实int够用)。这里考虑到搜索量过大超时问题采用记忆化搜索,有两种备选map<int,int >,pair<int ,int >或者自定义结构体。

  1. 新建队列q和map容器,把初始状态n压入队列,初始化步骤为0
  2. 进入队列取出元素把数字还原为3x3数组,记录下0的坐标,由于数组是从大往小存,故而倒着写循环
for(int i=2;i>=0;i--)
     for(int j=2;j>=0;j--) {
       c[i][j]=n%10;
       n/=10;
       if(!c[i][j]){
       f=i;
       g=j;
     }
}
  1. 接下来对0进行四个方向的搜索,这里面需要注意的有两个地方。第一个这里的变换方式是交换数字形成新数字,所以这一层搜索结束时,需要再次交换还原swap(c[nx][ny],c[f][g]);<---->swap(c[nx][ny],c[f][g]);(相当于vis[i]=1->0)。第二个地方是记忆化的问题,判断这个数是否出现过,可以判断数组是否在初始化状态获取结果。这里采用了map自带的方法count() 返回指定元素出现的次数。
if(!m.count(ns)){//判断是否没出现过
  m[ns]=m[u]+1;
  q.push(ns);
}
  1. 最后在m[start]中存的便是最终解。

D

这个题目首先就是以前做过的合唱队形的原题,就是一个最长上升子序列的问题,然后数据范围变成了20万。所以我导致原来的算法时间复杂度 n^2 肯定就超了。所以只要换成二分的方法,就是降低时间复杂度。具体降低的方法呢,其实就是在。过程中把下标记成子段的长度。遍历每一个节点,然后只要这个节点的数字比之前最长的长度记录的数字要大就增加长度,把这个节点记下来。否则,就用二分查找前面所有的,最后记录节点数大于或等于当前节点数的长度更新。最后注意输出的是出队的人数

以上是怎么去找到最长上升子序列的方法,然后我在考试的时候是在找的过程中,同时顺带就记录下每个节点为结尾的。最长上升子序列的长度用作最后输出

共 1 条回复

lu_ruo_kuan

考古

AMAZE UI
Hello world!