没有合适的资源?快使用搜索试试~ 我知道了~
2023“钉耙编程”中国大学生算法设计超级联赛(3)-题目集.pdf
需积分: 5 0 下载量 56 浏览量
2023-07-27
20:59:01
上传
评论
收藏 193KB PDF 举报
温馨提示
试读
12页
2023“钉耙编程”中国大学生算法设计超级联赛(3)-题目集
资源推荐
资源详情
资源评论
Super League of Chinese College Students Algorithm Design 2023 # 3
Tuesday, July 25, 2023
Problem A. Magma Cave
Input file: standard input
Output file: standard output
Time limit: 12 seconds
Memory limit: 512 megabytes
Little Q is researching an active volcano. There are n caves inside the volcano, labeled by 1, 2, . . . , n. At
the very beginning, before the first volcanic activity event, there is no magma path between these caves.
You will be given q operations, each operation is one of the following:
• “1 u v w” (1 ≤ u, v ≤ n, u 6= v, 1 ≤ w ≤ q): A volcanic activity event comes such that a new
magma path between the u-th cave and the v-th cave occurs, whose length is w. Here w is used for
identifying the magma path, so w will always be pairwise different.
• “2 k w ” (1 ≤ k < n, 1 ≤ w ≤ q): Assume it is a undirected graph with n vertices, each magma path
denoting an edge, Little Q is wondering whether there exists a spanning tree whose k-th shortest
edge is of length w. You are the partner of Little Q, please write a program to answer his question.
Input
The first line contains a single integer T (1 ≤ T ≤ 100), the number of test cases. For each test case:
The first line contains two integers n and q (2 ≤ n ≤ 50 000, 1 ≤ q ≤ 200 000), denoting the number of
caves and the number of operations.
Each of the next q lines describes an operation in formats described in the statement above.
It is guaranteed that the sum of all n is at most 300 000, and the sum of all q is at most 1 000 000.
Output
For each question, print a single line. If it is possible, print “YES”, otherwise print “NO”.
Example
standard input standard output
2
3 7
1 1 2 1
2 1 1
1 2 3 5
1 1 3 4
2 2 4
2 2 5
2 2 3
2 4
1 1 2 1
1 1 2 2
2 1 1
2 1 2
NO
YES
YES
NO
YES
YES
Page 1 of 12
Super League of Chinese College Students Algorithm Design 2023 # 3
Tuesday, July 25, 2023
Problem B. King’s Ruins
Input file: standard input
Output file: standard output
Time limit: 15 seconds
Memory limit: 512 megabytes
The first king of Byteland was buried with his n knights a thousand years ago. In the ruins, the
archaeologists have found n stone tablets in a row, labeled by 1, 2, . . . , n from left to right. Each stone
tablet belongs to a knight. On the surface of the k-th stone tablet, five numbers are describing the ability
of the k-th knight in five aspects:
• The wind ability w, denoting how fast the knight is.
• The guard ability g, denoting how many attacks can be defended by the knight.
• The ice ability i, denoting the power of ice crystal cast by the knight.
• The flame ability f, denoting the power of fire cast by the knight.
• The light ability l , denoting the power of thunder cast by the knight.
Little Q is visiting the stone tablets from left to right, according to the labels from 1 to n. After visiting
a stone tablet, before moving right to the next one, he can choose to take a photo with it or do nothing.
Little Q estimates the value of each stone tablet, he wants to maximize the total value that he takes
photos with, and the knight corresponding to the next photo is always not weaker than the current one.
Here the x-th knight is considered not to be weaker than the y-th knight if and only if w
x
≥ w
y
, g
x
≥ g
y
,
i
x
≥ i
y
, f
x
≥ f
y
and l
x
≥ l
y
.
There are so many stone tablets that Little Q can not determine which to take photos with. Please write
a program to help him.
Input
The first line contains a single integer T (1 ≤ T ≤ 5), the number of test cases. For each test case:
The first line contains a single integer n (1 ≤ n ≤ 50 000), denoting the number of stone tablets.
In the next n lines, the k-th line contains six integers w
k
, g
k
, i
k
, f
k
, l
k
and v
k
(1 ≤ w
k
, g
k
, i
k
, f
k
, l
k
≤ n,
1 ≤ v
k
≤ 10 000), describing the k-th stone tablet, v
k
denoting the value of the photo with it.
Output
For each test case, output n lines, the k-th (1 ≤ k ≤ n) of which containing an integer, denoting the
maximum total value when the last photo is taken with the k-th stone tablet.
Example
standard input standard output
1
4
1 2 1 2 1 30
2 1 2 1 2 40
3 3 3 3 3 50
2 3 3 2 4 100
30
40
90
140
Page 2 of 12
Super League of Chinese College Students Algorithm Design 2023 # 3
Tuesday, July 25, 2023
Problem C. Leshphon
Input file: standard input
Output file: standard output
Time limit: 5 seconds
Memory limit: 512 megabytes
Leshphon was a peaceful and beautiful village in Byteland until the nasty disease came here. There are
n districts in Leshphon, connected by m directed roads such that you can reach every other district from
any district via these directed roads. In other words, it is strongly connected.
To control the sources of infection and cut off the channels of transmission, the government of Byteland
decides to close exactly three directed roads in Leshphon, such that the village is not strongly connected
anymore. There may be many possible solutions, can you figure out the total number of them?
Input
The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. For each test case:
The first line contains two integers n and m (3 ≤ n ≤ 50, 3 ≤ m ≤ n(n − 1)), denoting the number of
districts and the number of roads.
Each of the following m lines contains two integers u
i
and v
i
(1 ≤ u
i
, v
i
≤ n, u
i
6= v
i
), describing a
directed road from the u
i
-th district to the v
i
-th district.
It is guaranteed that the village is strongly connected, and all the given m roads are pairwise different.
Output
For each test case, output a single line containing an integer, denoting the number of solutions.
Example
standard input standard output
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
3 1
34
Page 3 of 12
剩余11页未读,继续阅读
资源评论
小嗷犬
- 粉丝: 2w+
- 资源: 1334
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebCrawler.scr
- 【计算机专业毕业设计】大学生就业信息管理系统设计源码.zip
- YOLO 数据集:8种路面缺陷病害检测【包含划分好的数据集、类别class文件、数据可视化脚本】
- JAVA实现Modbus RTU或Modbus TCPIP案例.zip
- 基于YOLOv8的FPS TPS AI自动锁定源码+使用步骤说明.zip
- JAVA实现Modbus RTU或Modbus TCPIP案例.zip
- 基于yolov8+streamlit的火灾检测部署源码+模型.zip
- 测试aaaaaaabbbbb
- VID20240521070643.mp4
- Android系统原理与开发学习要点详解-培训课件.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功