摘要
Title: Acwing 第 41 场周赛
Tag: 树的DFS、字典序、精度

第 41 场周赛

A AcWing 4308. 组合字符串

思路

尽可能延长s1, 判断是否取s2第一个即可
字典序：
- a, b每一位比较，如果a[i] < b[i]，那么a<b
- 如果a是b的非平凡前缀，那么a<b

代码

'''
Author: NEFU AB-IN
Date: 2022-03-05 18:59:48
FilePath: \ACM\Acwing\41\a.py
LastEditTime: 2022-03-05 19:03:50
'''
s1, s2 = input().split()

res = s1[0]
for i in range(1, len(s1)):
    if s1[i] > s2[0]:
        res += s2[0]
        print(res)
        exit(0)
    res += s1[i]
if res == s1:
    res += s2[0]
print(res)

B AcWing 4309. 消灭老鼠

思路

枚举斜率即可
精度尽可能大！！

代码

'''
Author: NEFU AB-IN
Date: 2022-03-05 19:07:41
FilePath: \ACM\Acwing\41周赛\b.py
LastEditTime: 2022-03-05 19:25:24
'''

s = list()

n, x0, y0 = map(int, input().split())
for i in range(n):
    x, y = map(int, input().split())
    if x == x0:
        s.append(int(2e9))
    else:
        s.append((y - y0) / (x - x0))

res = 1
s.sort()
for i in range(1, len(s)):
    if s[i] - s[i - 1] > 1e-10: #1e-10以下才够
        res += 1

print(res)

C AcWing 4310. 树的DFS

思路

采用vector存树，dfs根节点得到res答案序列，cnt记录每个点的子节点数量，从res中找即可

递归问题别用python，太容易爆了

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-03-05 19:51:04
* @FilePath: \ACM\Acwing\41\c.cpp
* @LastEditTime: 2022-03-05 21:28:03
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 2e5 + 100;
vector<int> g[N];
vector<int> res(0);

int cnt[N], vis[N];

int dfs(int u)
{
    res.push_back(u);
    for (auto v : g[u])
    {
        int s = dfs(v);
        cnt[u] += s;
    }
    return cnt[u];
}

signed main()
{
    IOS;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n - 1; ++i)
    {
        int x;
        cin >> x;
        g[x].push_back(i + 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        cnt[i] = 1;
    }
    dfs(1);
    for (int i = 1; i <= n; ++i)
    {
        vis[res[i]] = i; //反向标记res
    }
    for (int i = 1; i <= q; ++i)
    {
        int u, k;
        cin >> u >> k;
        if (k > cnt[u])
        {
            cout << "-1\n";
            continue;
        }
        cout << res[vis[u] + k - 1] << '\n';
    }
    return 0;
}

第 41 场周赛

A AcWing 4308. 组合字符串

思路

代码

B AcWing 4309. 消灭老鼠

思路

代码

C AcWing 4310. 树的DFS

思路

代码