ACGO 挑战赛 #26 题解

· · 题解

acgo 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)，如果：

则将该点设置为 -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)