第135章 连下四城（1 / 6）
题目锁定。
对於来到攻擂方的师大附中，他们有两分钟时间，决定派哪位选手迎战。
值得一提的是，虽说擂台赛不允许正式竞赛生参加。
但信息学这门，本身就不是主课。愿意钻研的人，或多或少，都带著点竞赛属性。
只不过。
临安中学的编程队水平，实在一言难尽。
师大附中稍好一些，但也好不到哪去。
——说白了，都是拿不上檯面的业余选手，半斤八两。
师大附方阵里。
因为人不多，几十號人，乾脆全都坐在了一起。
此刻，所有人的目光，都死死盯著大屏幕上锁定的那道题。
【给定n个点，每个点有三维坐標（x， y， z），求连接这些点的最小总代价，边的代价是曼哈顿距离（|x1-x2|+|y1-y2|+|z1-z2|）】
编程队的几个人，看完题目，几乎是下意识地——
“嘶——”
一整排人，齐刷刷倒吸了一口凉气。
题面简短。
但一眼就能看出来，和先前的几道题，难度完全不是一个级別的。
这题偏向考察基础图论算法 mst（並查集+ kruskal）。
如果题目定义，n小於1000，这道题还算是比较简单的。
可以直接暴力枚举所有两两之间的曼哈顿距离。
但是.....题目標註了，n小於10的五次方。
这他妈怎么搞？
时间复杂度不得爆炸？
而且，十分钟能完成编码、调试、运行、提交吗？
能不能下手都是个大问题。
时间一分一秒地流逝。
带队老师看著学生。
学生看著老师。
——面面相覷。
没人吭声。 ↑返回顶部↑
对於来到攻擂方的师大附中，他们有两分钟时间，决定派哪位选手迎战。
值得一提的是，虽说擂台赛不允许正式竞赛生参加。
但信息学这门，本身就不是主课。愿意钻研的人，或多或少，都带著点竞赛属性。
只不过。
临安中学的编程队水平，实在一言难尽。
师大附中稍好一些，但也好不到哪去。
——说白了，都是拿不上檯面的业余选手，半斤八两。
师大附方阵里。
因为人不多，几十號人，乾脆全都坐在了一起。
此刻，所有人的目光，都死死盯著大屏幕上锁定的那道题。
【给定n个点，每个点有三维坐標（x， y， z），求连接这些点的最小总代价，边的代价是曼哈顿距离（|x1-x2|+|y1-y2|+|z1-z2|）】
编程队的几个人，看完题目，几乎是下意识地——
“嘶——”
一整排人，齐刷刷倒吸了一口凉气。
题面简短。
但一眼就能看出来，和先前的几道题，难度完全不是一个级別的。
这题偏向考察基础图论算法 mst（並查集+ kruskal）。
如果题目定义，n小於1000，这道题还算是比较简单的。
可以直接暴力枚举所有两两之间的曼哈顿距离。
但是.....题目標註了，n小於10的五次方。
这他妈怎么搞？
时间复杂度不得爆炸？
而且，十分钟能完成编码、调试、运行、提交吗？
能不能下手都是个大问题。
时间一分一秒地流逝。
带队老师看著学生。
学生看著老师。
——面面相覷。
没人吭声。 ↑返回顶部↑