码题集周赛1

第一题

使用cpp来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cmath>
#include <complex>
#include <iomanip>

int main() {
    int n;
    std::cin >> n;
    std::complex<double> modules[200];
    for (int i = 0; i < n; ++i) {
        int a, b;
        std::cin >> a >> b;
        modules[i] = std::complex<double>(a, b);
    }
    double max_power = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double power = std::abs(modules[i] * modules[j]);
            if (power > max_power) {
                max_power = power;
            }
        }
    }
    std::cout << std::fixed << std::setprecision(9) << max_power << std::endl;
    return 0;
}

第二题

使用python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
n, m = map(int, input().split())
roads = [set() for _ in range(n+1)]  

for _ in range(m):
    u, v = map(int, input().split())
    roads[u].add(v)
    roads[v].add(u)

def map_state(roads):
    state = []
    for i in range(1, n+1):
        for j in roads[i]:
            if i < j:
                state.append((i, j))
    return frozenset(state)

seen_states = set()  
seen_states.add(map_state(roads))  

q = int(input()) 

for _ in range(q):
    operation = input().split()
    
    if operation[0] == 'add': 
        u, v = map(int, operation[1:])
        roads[u].add(v)
        roads[v].add(u)
    
    elif operation[0] == 'del':  
        u, v = map(int, operation[1:])
        roads[u].remove(v)
        roads[v].remove(u)
    
    elif operation[0] == 'pop':  
        u = int(operation[1])
        for v in list(roads[u]):  
            roads[v].remove(u)
        roads[u].clear()  
    
    current_state = map_state(roads)
    
    if current_state in seen_states:
        print("old")
    else:
        print("new")
        seen_states.add(current_state)

第三题

题目稍微有点复杂，但是仔细想想还是挺简单的一题，需要换一种思路，不要太关注具体细节，盯着结果看会想通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from collections import deque

n, m = map(int, input().split())

# 创建图的邻接表
graph = [[] for _ in range(n + 1)]

# 输入每条边的信息
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

# 输入小码弟和小码妹的初始位置
x, y = map(int, input().split())

def bfs(start):
    q = deque([(start, 0)])
    visited = [False] * (n + 1)
    visited[start] = True

    while q:
        curr, turns = q.popleft()
        if curr == n:
            return turns 
        for next_node in graph[curr]:
            if not visited[next_node]:
                visited[next_node] = True
                q.append((next_node, turns + 1))
    return -1

a = bfs(x)  # 小码弟需要的最短回合
b = bfs(y)  # 小码妹需要的最短回合

if(a!=-1 and b!=-1):
    if(a>b):
        print(2*b)
    else:
        print(2*a-1)
else:
    if(a==-1):
        print(2*b)
    if(b==-1):
        print(2*a-1)

第四题

下面的代码可以实现，但是时间复杂度不满足题目要求，确实想不到怎么优化了...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
n = int(input())
s = input()
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def is_balanced(string):
    stack = []
    for char in string:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack:
                return False
            top = stack.pop()
            if char == ')' and top!= '(':
                return False
            elif char == '}' and top!= '{':
                return False
            elif char == ']' and top!= '[':
                return False
    return not stack

def dfs(node, parent, path):
    count = 0
    path += s[node - 1]
    # 提前判断，如果当前路径明显不平衡，直接返回 0
    stack = []
    for char in path:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack:
                return 0
            top = stack.pop()
            if char == ')' and top!= '(':
                return 0
            elif char == '}' and top!= '{':
                return 0
            elif char == ']' and top!= '[':
                return 0
    if is_balanced(path):
        count += 1
    for neighbor in graph[node]:
        if neighbor!= parent:
            count += dfs(neighbor, node, path)
    return count

total_count = 0
for i in range(1, n + 1):
    total_count += dfs(i, -1, '')

print(total_count)

第四题官方提供的解法:

题解：

从树上的每个结点开始都进行一次dfs，求出以该结点为出发点的平衡路径数量，最终的答案就是每个结点出发的路径数量之和。

在dfs时，使用一个栈维护括号序列的匹配。搜索到一个结点时，把该节点上的字符压入栈顶；当栈顶的两个元素发生匹配时，将栈顶的两个元素弹出。在dfs回溯时撤销对栈的操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;
string s;
vector<vector<int> >g(maxn);
vector<int> stk;
int ans = 0;
void dfs(int u, int fa) 
{    
    int poped = -1;
    if (stk.empty()) 
    {        
        stk.push_back(u);
    }
    else if (s[stk.back()] == '(' && s[u] == ')') 
    {        
        poped = stk.back();        
        stk.pop_back();    
    }
    else if (s[stk.back()] == '[' && s[u] == ']') 
    {        
        poped = stk.back();        
        stk.pop_back();    
    }
    else if (s[stk.back()] == '{' && s[u] == '}') 
    {        
        poped = stk.back();        
        stk.pop_back();    
    }
    else
    {        
        stk.push_back(u);    
    }    
    if (stk.empty()) 
    {        
        ans++;    
    }    
    for (int v : g[u])  if (v != fa)
    {        
        dfs(v, u);    
    }    
    if (poped == -1) 
    {        
        stk.pop_back();    
    }
    else
    {        
        stk.push_back(poped);    
    }
}
int main(){    
    int n;    
    cin >> n;    
    cin >> s;    
    for (int i = 1; i < n; i++) 
    {        
        int u, v;        
        cin >> u >> v;        
        u--;        
        v--;        
        g[u].push_back(v);        
        g[v].push_back(u);    
    }    
    for (int i = 0; i < n; i++)
    {        
        dfs(i, -1);    
    }    
    cout << ans << endl;}

第五题

直接让ai写的代码没有问题，但是会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
n = int(input())
parent_list = list(map(int, input().split()))
q = int(input())

def find_san_value_for_collapse(node):
    san_value = 0
    for i in range(2, n + 1):
        if parent_list[i - 2] == node:
            san_value += 1
    return san_value

def collapse(u):
    parent = parent_list[u - 2]
    san_value = find_san_value_for_collapse(u)
    for i in range(2, n + 1):
        if parent_list[i - 2] == u:
            parent_list[i - 2] = parent
    return san_value

def find_san_value_for_reconstruct(u, v):
    san_value = 0
    for i in range(2, n + 1):
        if parent_list[i - 2] == u:
            san_value += 1
    return san_value

def reconstruct(u, v):
    san_value = find_san_value_for_reconstruct(u, v)
    parent_list[u - 2] = v
    return san_value

for _ in range(q):
    operation = list(map(int, input().split()))
    if operation[0] == 1:
        u = operation[1]
        print(collapse(u))
    elif operation[0] == 2:
        u, v = operation[1], operation[2]
        print(reconstruct(u, v))

官方题解如下：

题解：

建立双向链表维护邻接表。对于一次坍塌操作，相当于把当前结点的链表接到父结点的链表上。对于一次重构操作，相当于从父结点的链表中删除当前结点，再把当前结点加入另一个链表中。

儿子结点的个数比较容易维护，同时我们还需要维护每个结点的父节点。在坍塌操作后，当前结点的所有儿子结点的父节点都会发生变化，如果暴力修改这些结点的父节点会导致超时。

这里我们使用一个巧妙的解决方法：在坍塌操作后，我们建立一个新的结点u'，拷贝被坍塌结点u的所有信息，最后使用并查集将被坍塌结点u合并入父亲结点fa中。之后所有关于u的操作都在u'上进行。

如果遇到了对u的儿子的操作，首先在并查集中查找其真正的父结点fa，随后再进行链表操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int nex[maxn], pre[maxn], h[maxn], t[maxn], sz[maxn], f[maxn];
int vf[maxn], id[maxn];
int find(int x)
{    
    return vf[x] == x ? x : vf[x] = find(vf[x]);
}
int main()
{    
    ios::sync_with_stdio(false);    
    cin.tie(0);    
    int n;    
    cin >> n;    
    int tot = 0;    
    for (int i = 2; i <= n; i++) {        
        int fa;        
        cin >> fa;        
        f[i] = fa;        
        nex[i] = h[fa];        
        pre[h[fa]] = i;        
        if (!t[fa]) t[fa] = i;         
        h[fa] = i;        
        sz[fa]++;    
    }    
    int ids = n;    
    for (int i = 1; i <= n; i++) vf[i] = i, id[i] = i;    
    int q;    
    cin >> q;    
    while (q--) {        
        int opt;        
        cin >> opt;        
        if (opt == 1) 
        {            
            int _u;            
            cin >> _u;            
            int u = id[_u];            
            cout << sz[u] << '\n';            
            int fa = find(f[u]); // 需要通过find的方式找到真实的父亲 
            if (t[u]) { // u 有儿子，否则不进行操作                
                nex[t[u]] = h[fa];                
                pre[h[fa]] = t[u];                
                h[fa] = h[u];                
                sz[fa] += sz[u];                
                vf[u] = fa; // 将所有儿子的父节点设置为 fa                
                id[_u] = ++ids; // 丢弃结点u，建立新结点                
                nex[pre[u]] = ids;                
                pre[ids] = pre[u];                
                pre[nex[u]] = ids;                
                nex[ids] = nex[u];                
                sz[ids] = 0; // 新的u不存在儿子结点，sz为0                
                f[ids] = fa;                
                vf[ids] = ids;            
            }       
        }else{            
            int _u, _v;            
            cin >> _u >> _v;            
            int u = id[_u], v = id[_v];            
            cout << sz[u] << '\n';            
            int fa = find(f[u]); // 需要通过find的方式找到真实的父亲            
            nex[pre[u]] = nex[u];            
            pre[nex[u]] = pre[u];            
            sz[fa] -= 1;            
            sz[v] += 1;            
            f[u] = v;            
            nex[u] = h[v];            
            pre[h[v]] = u;            
            if (!t[v]) t[v] = u;            
            h[v] = u;        
        }
    }
}
码蹄集
码题集周赛1
http://jrhu0048.github.io/2024/10/15/ma-ti-ji-zhou-sai-1/
作者
JR.HU
发布于
2024年10月15日
更新于
2024年10月18日
许可协议