ACGO 挑战赛 #26 题解

yanghongzheng

2025-12-30 20:01:44

发布于：北京

23阅读

0回复

0点赞

luogu link

难度估计

红，红+，橙，橙，黄-，黄

T1

思路

签到题。

如果 $x - \lfloor x \rfloor < 0.5$ ，则小数部分 $< 0.5$ ，答案为 $\lfloor x \rfloor$ ，否则答案为 $\lfloor x \rfloor + 1$ 。

代码

x = float(input())
if x - int(x) >= 0.5:
    print(int(x) + 1)
else:
    print(int(x))

T2

思路

一道二分题。

对于第 $i$ 个学生，其可能获得的最高分为 $s_{i,1} + s_{i,2} + s_{i,3} + 300$ ，最低分为 $s_{i,1} + s_{i,2} + s_{i,3}$ 。

先排序使得数组有单调性，然后用循环，对于每个学生计算他们的最高分，然后用二分查找出有多少人的最低分 $> t$ ，如果超过或等于 $k$ 个，说明就算这个学生考了最高分，也进不了前 $k$ 。

代码

n,k = map(int,input().split())
a = []
for i in range(n):
    x,y,z = map(int,input().split())
    a.append(x + y + z)

b = sorted(a)

for i in range(len(a)):
    x = a[i]
    t = x + 300
    l,r = 0,n
    while l < r:
        m = (l + r) // 2
        if b[m] <= t:
            l = m + 1
        else:
            r = m
    cnt = n - l
    if cnt < k:
        print("Yes")
    else:
        print("No")

T3

思路

模拟题。

按照类似于双向链表的方法模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id;
	int pr = 0,ne = 0;
}a[100010];
int main(){
	int n,q;
	cin >> n >> q;
	for(int i = 1;i <= n;i++){
		a[i].id = i;
	}
	for(int i = 1;i <= q;i++){
		int o,x,y;
		cin >> o;
		if(o == 1 || o == 2){
			cin >> x >> y;
			if(o == 1){
			    a[x].ne = y;
			    a[y].pr = x;
			}else{
				a[x].ne = 0;
				a[y].pr = 0;
			}
		}else{
			cin >> x;
			y = x;
			while(a[y].pr != 0){
				y = a[y].pr;
			}
			int cnt = 0;
			int t = y;
			while(t){
			    cnt++;
			    t = a[t].ne;
			}
			cout << cnt << ' ';
			while(y){
			    cout << y << ' ';
			    y = a[y].ne;
			}
			cout << endl;
		}
	}
	return 0;
}

T4

思路

一道二分题。

和 T2 思路类似，排序 + 二分即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,q,h[2100010],x;
	cin >> n >> q;
	for(int i = 0;i < n;i++) cin >> h[i];
	sort(h,h+n);
	for(int i = 0;i < q;i++){
		cin >> x;
		int l = 0,r = n,mid;
		while(l < r){
			mid = (l + r) >> 1;
			if(h[mid] < x){
				l = mid + 1;
			}else{
				r = mid;
			}
		}
		cout << n - l << endl;
	}
	return 0;
}

T5（非正解）

思路

从技能 $n$ 开始，学它之前，先把它所有前置技能都学完（每个前置技能再递归处理），最后加上当前技能的学习时间。

代码

n = int(input())
t = [0] * (n + 1)
pre = [[] for i in range(n + 1)]

for i in range(1,n + 1):
    a = list(map(int,input().split()))
    t[i] = a[0]
    m = a[1]
    for j in range(m):
        pre[i].append(a[2 + j])

def dfs(x):
    s = 0
    for y in pre[x]:
        s += dfs(y)
    s += t[x]
    return s

print(dfs(n))

T6

思路

一道 dp 题。

对于一组坐标 $(i,j)$ ，如果：

地图上该点为 #
$= (0,0)$

则将该点设置为 $-1$ （可以在初始化时设置）并 continue 该点。

否则两条路，dp[i-1][j] 和 dp[i][j-1] 到达该点，转移方程为 dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + 1。

代码

n,m = map(int,input().split())
g = []
for i in range(n):
    ts = input()
    tl = []
    for j in range(m):
        tl.append(ts[j])
    g.append(tl)

dp = [[-1] * m for i in range(n)]

dp[0][0] = 1

for i in range(n):
    for j in range(m):
        if g[i][j] == '#':
            continue
        if i == 0 and j == 0:
            continue
        a = -1
        b = -1
        if i > 0:
            a = dp[i-1][j]
        if j > 0:
            b = dp[i][j-1]
        if a != -1 or b != -1:
            dp[i][j] = max(a,b) + 1

ans = 0
for i in range(n):
    for j in range(m):
        if dp[i][j] > ans:
            ans = dp[i][j]

print(ans)