福 建 电 脑 Journal of Fujian Computer
Vol. 35 No.10
Oct. 2019
CSP-J 2019 模拟认证第2试详解
戴哥玲 谭方芳
(福建省长汀县第一中学 福建 龙岩 366300)
摘 要 题目来源于第2轮CSP-J 2019模拟赛第2试。本文对模拟赛第2试的四个问题的解题思路及算法设计作了较为详细的描述，并给出相应的代码。 关键词 题解；分析；算法；代码
中图法分类号 TP31 DOI:10.16707/j.cnki.fjpc.2019.10.038
The Solutions of the Simulated Contest Day 2 of CSP-J 2019
DAI Geling, TAN Fangfang
(Fujian Changting County No.1 Middle School, Longyan, China, 366300)
1分数化小数
1.1问题描述
写一个程序，输入一个形如N/D的分数（N是分子，D是分母），输出它的小数形式。如果小数有循环节的话，把循环节放在一个对括号中，例如： 1/3=0.33333333 写成0.(3)，
41/333=0.123123123 写成0.(123)。 用xxx.0表示整数。 典型的转化例子： 1/3=0.(3) 22/5=4.4 2/2=1.0 3/8=0.375
45/56=0.803(571428) 1<=N,D<=100000。 1.2涉及的知识点
高数度除法。
有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，计算机的计算数度因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的
———————————————
方法去实现这样的高精度计算[1]。 1.3解题思路
很显然是一道高精度除法题目，难点在于如何判断循环节。
首先观察一下手算除法的过程，如图1。
图1 手算除法过程 图2除不尽的算式
每次将被除数除以除数，当前位的商即为该步操作的商。若余数为0则结束（除得尽）；否则，将余数乘以10，再作为被除数，重复进行上一步操作。对于除不尽的式子（如图2），我们发现出现了相同的被除数40。也就是说，若过程中发现了相同的被除数，则产生了循环。
至此，可以设计出具体做法：对于当前在第k位进行的除法，每次求得余数（记为t）时，若为0则已经除尽，输出答案结束即可；若未出现过，用
戴哥玲，男，1966年生，福州大学。Email: lyctyz@163.com。谭方芳，女，1982年生，长春师范学院。Email: 172205553@qq.com。
2019年 福 建 电 脑 121
数组记录下它出现的位置；若已经出现过，说明出现了循环。我们已经记录下了它第一次出现的位置（记为b[t]），则商的b[t] ~ (k - 1)位为循环节。 1.4参考代码 #include int b[1000001], k; int ans[1000001]; int main() { scanf(\"%d%d\ printf(\"%d.\ if(n % d == 0) { printf(\"0\"); return 0; } int t = (n % d) * 10; //b[t] 表示 t作为除数的情况是否出现过 //若不为0, 表示该情况的结果对应商的小数点后第b[t]位 while(t && !b[t]) { b[t] = ++k; ans[k] = t / d; t = (t % d) * 10; } if(b[t])//出现循环 { for(int i = 1; i < b[t]; ++i) printf(\"%d\ printf(\"(\"); for(int i = b[t]; i <= k; ++i) printf(\"%d\ printf(\")\"); } else for(int i = 1; i <= k; ++i) printf(\"%d\ } 2 最长路 2.1问题描述 设G为有n个顶点的有向无环图，G中各顶点 的编号为1到n。设w[i，j]为边 20%的数据，n≤100，m≤1000， 40%的数据，n≤1,000，m≤10000， 100%的数据，n≤1,500，m≤50000。 2.2涉及的知识点 最短路算法。 观察一下题目，很容易联想到最短路算法。根据题目分析，总点数不大，图比较稀疏，没有负环，只有一个起点，则SPFA是一种比较优秀的算法。首先回顾一下SPFA求最短路的主要思想： 建立一个队列，初始时将起点加入队列[1]。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。SPFA在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一点修改过其他的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其他的点，这样反复进行下去。 2.3解题思路 题目要求的是最长路。是否与最短路算法类似呢？答案是肯定的，只需作一点修改。主要的不同在于松弛操作：我们用队头点更新其他点的最长路。用dis[]数组表示起点到各点的最长路径，val[i][j]表示从i到j的边权，则最长路算法中松弛操作可以表示为： if(dis[x] + v[x][y] > dis[y]) { 122 戴哥玲等：CSP-J 2019 模拟认证第2试详解 第10期 dis[y] = dis[x] + w[x][y]; //更新为更长路径 … } 2.4参考代码 #include int a[max_n][max_n]; int dis[max_n]; int t, w, h[100010]; bool in[max_n]; int main() { scanf(\"%d%d\ memset(a, -1, sizeof(a)); for(int i = 1; i <= m; ++i) { int x, y, z; scanf(\"%d%d%d\ a[x][y] = max(a[x][y], z); } memset(dis, -1, sizeof(dis)); dis[1] = 0; //求最长路,则初值置最小 t = 0, w = 0; h[++w] = 1; memset(in, 0, sizeof(in)); in[1] = 1; do { int u = h[++t]; for(int v = 1; v <= n; ++v) if(a[u][v] != -1) if(a[u][v] + dis[u] > dis[v]) { dis[v] = a[u][v] + dis[u]; // 更新成更大的值 if(!in[v]) { h[++w] = v; in[v] = 1; } } in[u] = 0; }while(t < w); printf(\"%d\ return 0; } 3兽径管理 3.1问题描述 约翰农场的牛群希望能够在 N 个(1<=N<=200) 草地之间任意移动。草地的编号由 1到 N。草地之间有树林隔开。牛群希望能够选择草地间的路径，使牛群能够从任一片草地移动到任一片其它草地。牛群可在路径上双向通行。 牛群并不能创造路径，但是他们会保有及利用已经发现的野兽所走出来的路径(以下简称兽径)。每星期他们会选择并管理一些或全部已知的兽径当作通路。 牛群每星期初会发现一条新的兽径。他们接着必须决定管理哪些兽径来组成该周牛群移动的通路，使得牛群得以从任一草地移动到任一草地。牛群只能使用当周有被管理的兽径做为通路。 牛群希望他们管理的兽径长度和为最小。牛群可以从所有他们知道的所有兽径中挑选出一些来管理。牛群可以挑选的兽径与它之前是否曾被管理无关。兽径决不会是直线，因此连接两片草地之间的不同兽径长度可以不同。此外虽然两条兽径或许会相交，但牛群非常的专注，除非交点是在草地内，否则不会在交点换到另外一条兽径上。 在每周开始的时候，牛群会描述他们新发现的兽径。如果可能的话，请找出可从任何一草地通达另一草地的一组需管理的兽径，使其兽径长度和最小。 3.2涉及的知识点 最小生成树kruskal算法[2]。 3.3解题思路 假设我们只需要询问一次（即第w周的选取兽径长度和），很明显要求一遍最小生成树。 如果每周都要询问一次的话，就要做m次kruskal，时间复杂度为O(m*m log m)，这显然是承受不了的。 3.3.1 方法1 2019年 福 建 电 脑 123 在储存边的时候，可以多维护一个信息“该边是第几周被发现的”，我们可以在所有的边全读入完之后，将所有边按权值从小到大排序，每次做kruskal，我们只需关心时间在该周以内的边，就不需要重新排序了，时间复杂度为O(m*m)，可以通过此题。 3.3.2 方法2 设当前处理的边所连向的点分别为u和v，权值为w。 若u和v不联通，就可以直接将该边加到最小生成树当中；若u和v联通，如果添加这条边到最小生成树后，就会出现一个包含u和v的环，有环定不是最优的，我们就需要删除这个环上面权值最大的边，就可以断环为链，且权值和最小。 于是就能够以u或v为根遍历该树，找出u到v的路径中权值最大的边（将该边权值记为MAXedge），若MAXedge≤w，则不将当前边加入最小生成树当中，若MAXedge>w，则将u到v的路径中权值最大的边删去，将当前边加入最小生成树当中。每次读入一条边，我们都可以通过一次遍历来更新最小生成树，来达到在线计算最小生成树的目的 用链表实现时间复杂度为O(n*m)；用邻接矩阵实现时间复杂度为O(n*n*m)，实际效率却远远小于O(n*n*m)。[3]两种实现方法均可以通过此题。 3.4参考代码 //方法1： #include int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } const int N=210,M=6010; int n,m; struct Node{ int u; int v; int w; int T; }t[M]; int cmd(Node a,Node b)//按权值从小到大排序 { return a.w int kruskal(int TIME) { for(RI i=1;i<=n;i++) fa[i]=i; int sum=0,ans=0; for(RI i=1;i<=m;i++) { if(t[i].T>TIME)continue; //时间不在范围内，跳过 int x=get(t[i].u),y=get(t[i].v); if(x!=y) { sum++; ans+=t[i].w; fa[x]=y; } } return sum==n-1?ans:-1; } int main() { n=read(),m=read(); for(RI i=1;i<=m;i++) { t[i].u=read(),t[i].v=read()； t[i].w=read(),t[i].T=i; } sort(t+1,t+1+m,cmd); for(RI i=1;i<=m;i++) printf(\"%d\\n\ return 0; } //方法2：邻接矩阵实现 #include 124 戴哥玲等：CSP-J 2019 模拟认证第2试详解 第10期 #define RI register int using namespace std; inline int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } const int N=210; int n,m; int weight[N][N]; int fa[N]; int get(int x) { if(fa[x]==x)return x; return fa[x]=get(fa[x]); } void merge(int x,int y) { fa[get(x)]=get(y); } int ans,sum; int MAXedge,node1,node2; int dfs(int u,int v,int fa,int now_u,int now_v,int now_w) //u表示当前节点，v表示目标节点，fa表示u的父亲 //now_u,now_v和now_w表示起点到当前节点的路径中最大的边的信息 { if(u==v)//找到目标 { node1=now_u,node2=now_v,MAXedge=now_w;//赋给最大值 return 1; } for(RI i=1;i<=n;i++) if(weight[u][i])//若u和i有边相连 { if(i==fa)continue;//不可原路返回 if(weight[u][i]>now_w) //更新目前最大边继续遍历 if(dfs(i,v,u,u,i,weight[u][i])) return 1; if(weight[u][i]<=now_w) //原样继续遍历 if(dfs(i,v,u,now_u,now_v,now_w)) return 1; } return 0; } int main() { n=read(),m=read(); for(RI i=1;i<=n;i++) fa[i]=i; for(RI i=1;i<=m;i++) { int u=read(),v=read(),w=read(); if(get(u)!=get(v)) { ans+=w,sum++; weight[u][v]=weight[v][u]=w; merge(u,v); } else { dfs(u,v,0,0,0,0);//找u到v的路径中权值最大的边 if(MAXedge>w)//若替换更优 { weight[node1][node2]=weight[node2][node1]=0; weight[u][v]=weight[v][u]=w; ans-=MAXedge; ans+=w; } } printf(\"%d\\n\ } return 0; } 4炮击坦克 4.1问题描述 在一个坐标轴上，有M辆坦克，第i辆坦克在 时刻0处于pos[i]（pos[i]>0），speed[i]个单位，在时刻k就处于pos[i]+speed[i]*k。 原点上有一炮台。炮台有N颗炮弹，在时刻0开始就可以发射炮弹，而且发射的顺序是你来确定 2019年 福 建 电 脑 125 的，每次只能发射一颗，一颗炮弹只能用一次。每个炮弹都有一个休息时间rest[i]，如果在某次发射了第i颗炮弹，要间隔rest[i]后才能在发射。一颗炮弹只能消灭范围D(0到D)内的一辆坦克。 最多能消灭多少辆坦克？(N,M≤1000) 4.2涉及的知识点 贪心算法。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 4.3解题思路 难度较大的贪心。 这道题乍看毫无头绪。首先想到的必定是搜索，但是庞大的数据范围使其不能胜任。于是考虑寻找最优策略，省去不必要的枚举。 显然，使用炮弹时先使用休息时间少的一定更不差；并且在使用某个炮弹时，优先选择余下逃出攻击范围时间最短且未被毁的最佳，模拟上述过程，即可获得最优解，正确性显然。 4.4参考代码 #include int rest[1001],Time[1001],biao[1001],ans; int main() { int n=read(),m=read(),d=read(); for(re int i=1;i<=n;i++) rest[i]=read(); stable_sort(rest+1,rest+1+n);//炮弹按休息时间升序排序，保证正确性 for(re int i=1;i<=m;i++) { int a=read(),b=read(); if(a>d)Time[i]=-1; //特判坦克初始位置在攻击范围外 else { int c=d-a; Time[i]=c/b; //计算每辆坦克逃离攻击范围的时间-1 } } stable_sort(Time+1,Time+1+m);//排序，保证正确性 int now=0,flag=-1,num=1; //now为时间戳，num为当前炮弹编号，flag记录是否有坦克被击毁 while(flag==-1&&num<=n) //如果在一轮循环中没有坦克被击毁，或弹药用尽，结束计算 { flag=1; for(re int i=1;i<=m;i++) { if(biao[i]==0&&Time[i]>=now) //击毁该坦克 { ans++;//计入答案 biao[i]=1;//记为已被击毁 flag=-1;//有坦克被击毁 break; } } now+=rest[num];//加上休息时间 num++;//换下一个弹药 } cout< [1] 董永建,等.信息学奥赛一本通.第5版.北京:科学技术文献出版 社,2016 [2] 王晓东.数据结构:C语言描述.北京:电子工业出版社,2011 [3] 吴文虎.世界大学生程序设计竞赛教程.北京:中国铁道出版社,2012 因篇幅问题不能全部显示，请点此查看更多更全内容