题号 标题 已通过代码 通过率 团队的状态
A Ancestor 点击查看 1383/3940
B Boss 点击查看 54/734
C Concatenation 点击查看 2603/9404
D Directed 点击查看 62/157
E Electrician 点击查看 18/38
F Fief 点击查看 378/2528
G Geometry 点击查看 73/1076
H Hacker 点击查看 468/3315
I Ice Drinking 点击查看 28/212
J Journey 点击查看 1236/7800
文章目录
- C.Concatenation
- A.Ancestor
- J.Journey
- H.Hacker
- F.Fief
C.Concatenation
题目描述
NIO was the king of the OIN Kingdom.
He had NN children and wanted to teach them how to count. In the OIN Kingdom, pental is used in counting, so his children can only use 0, 1, 2, 3, and 4 to represent a number.
One day, NIO asked his children to write down their favorite numbers. After that, he came out with a problem: if he concatenated these numbers into a big number, what is the smallest number he could get? However, this problem was too hard for him to solve, so can you help him?
输入描述:
The first line contains an integer N(1 \le N \le 2*10^6)N(1≤N≤2∗10
6
), denoting the number of NIO’s children.
Then follows NN lines, each line contains a string s_is
i
denotes the favorite number of the iith child. The string is composed of 0, 1, 2, 3, and 4, but may have leading zeros because NIO’s children hadn’t fully understood how to count.
\sum_{i=1}^{N} |s_i|\le 2*10^7∑
i=1
N
∣s
i
∣≤2∗10
7
输出描述:
One integer denotes the smallest number NIO can get.
示例1
输入
复制
5
121
1
12
00
101
输出
复制
00101112112
备注:
If you have designed an algorithm whose time complexity is O(|S|\log|S|)O(∣S∣log∣S∣) or so, please think twice before submitting it. Any algorithm other than linear complexity is NOT supposed to pass this problem. But of course, you can have a try. If you do so, we wish you good luck.
题意：
- 给定n个字符串，求一个将他们拼接起来的方案，使得结果的字典序最小。
思路：
- 一个简单的做法是，对n个字符串排序，a在b前面的条件是a+b<b+a。
- 使用stable_sort可以保证复杂度为O(|S|log n)。
- 为了优化速度，还可以给cmp函数加上&，const，和inline。
- 可以换int为LL，然后把变量开到外面去。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 4e6+10;
string a[maxn];
inline bool cmp(const string &x,const string &y){
return x+y<y+x;
}
int main(){
IOS;
LL n; cin>>n;
for(LL i = 1; i <= n; i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
for(LL i = 1; i <= n; i++){
cout<<a[i];
}
return 0;
}A.Ancestor
题目描述
NIO is playing a game about trees.
The game has two trees A, BA,B each with NN vertices. The vertices in each tree are numbered from 11 to NN and the ii-th vertex has the weight v_iv
i
. The root of each tree is vertex 1. Given KK key numbers x_1,\dots,x_kx
1
,…,x
k
, find the number of solutions that remove exactly one number so that the weight of the lowest common ancestor of the vertices in A with the remaining key numbers is greater than the weight of the lowest common ancestor of the vertices in B with the remaining key numbers.
输入描述:
The first line has two positive integers N,K (2 \leq K \leq N \leq 10^5)N,K(2≤K≤N≤10
5
).
The second line has KK unique positive integers x_1,\dots,x_K (x_i \leq N)x
1
,…,x
K
(x
i
≤N).
The third line has NN positive integers a_i (a_i \leq 10^9)a
i
(a
i
≤10
9
) represents the weight of vertices in A.
The fourth line has N - 1N−1 positive integers {pa_i}{pa
i
}, indicating that the number of the father of vertices i+1i+1 in tree A is pa_ipa
i
.
The fifth line has nn positive integers b_i (b_i \leq 10^9)b
i
(b
i
≤10
9
) represents the weight of vertices in B.
The sixth line has N - 1N−1 positive integers {pb_i}{pb
i
}, indicating that the number of the father of vertices i+1i+1 in tree B is pb_ipb
i
.
输出描述:
One integer indicating the answer.
示例1
输入
复制
5 3
5 4 3
6 6 3 4 6
1 2 2 4
7 4 5 7 7
1 1 3 2
输出
复制
1
说明
In first case, the key numbers are 5,4,3.
Remove key number 5, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 3.
Remove key number 4, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 1.
Remove key number 3, the lowest common ancestors of the vertices in A with the remaining key numbers is 4, in B is 1.
Only remove key number 5 satisfies the requirement.
示例2
输入
复制
10 3
10 9 8
8 9 9 2 7 9 0 0 7 4
1 1 2 4 3 4 2 4 7
7 7 2 3 4 5 6 1 5 3
1 1 3 1 2 4 7 3 5
输出
复制
2
备注:
The lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).(From Wiki.)
题意：