2022icpc 济南站 持续补题
链接：Dashboard - 2022 International Collegiate Programming Contest, Jinan Site - Codeforces
签到题：k
K. Stack Sort
You are given a permutation with nn numbers, a1,a2,…,an(1≤ai≤n,ai≠aj when i≠j).
You want to sort these numbers using m stacks. Specifically, you should complete the following task:
Initially, all stacks are empty. You need to push each number aiai to the top of one of the mm stacks one by one, in the order of a1,a2,…,an. After pushing all numbers in the stacks, you pop all the elements from the stacks in a clever order so that the first number you pop is 1, the second number you pop is 2, and so on. If you pop an element from a stack S, you cannot pop any element from the other stacks until S becomes empty.
What is the minimum possible mm to complete the task?
Input
The first line contains one integer T (1≤T≤10^5), the number of test cases.
For each test case, the first line contains one positive integer n (1≤n≤5×10^5). The next line contains nn integers a1,…,an (1≤ai≤n) denoting the permutation. It is guaranteed that a1,…,an form a permutation, i.e. ai≠ajj for i≠j.
It is guaranteed that the sum of nn over all test cases is no more than 5×10^5.
Output
For each test case, output the minimum possible mm in one line.
Example
input
3
3
1 2 3
3
3 2 1
5
1 4 2 5 3
output
3 1 4
只需考虑每次输入一个数时比他大1的数是否已经进栈，若否则栈加一
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <unordered_map>
using namespace std ;
const int N = 5e5+10 ;
int n , m ;
int k ;
int cnt[N];
int main()
{
cin >> k ;
while(k--){
int res = 0;
unordered_map<int , int > ump ;
scanf("%d",&n);
for(int i = 0 ; i < n ; i ++){
int t ;
scanf("%d",&t);
if(!ump[t+1]) res ++ ;
ump[t] = 1 ;
}
cout << res <<endl;
}
return 0;
}
签到题：M （当时用的高精度加法一直超时，脑子抽抽了）
M.Best Carry Player
Prof. Pang is given n numbers a1, . . . , an. It is easy to add the numbers up using a computer. But Prof. Pang treasures his computer so much and wants to reduce its workload. He decides to simulate the following program by hand.
Algorithm 1 Sum of elements
1: s ← 0
2: for i from 1 to n do
3: s ← s + a[i]
4: end for
Unlike a computer, the time needed for Prof. Pang to simulate the program is proportional to the total number of carries（1） when calculating s+a[i] for each i from 1 to n. Prof. Pang adds numbers by column addition in base-ten, just like what we normally do in primary school. For example, there are two carries in the following addition.
Please permute the array a1, . . . , an so that the total number of carries when Prof. Pang simulates the program is as small as possible. (By “permute an array”, we mean that you can change the order of the elements arbitrarily.)
Input
The first line contains one integer T (1 ≤ T ≤ 10^5 ), the number of test cases. For each test case, the first line contains one positive integer n (1 ≤ n ≤ 10^5 ). The next line contains n integers a1, . . . , an (1 ≤ ai ≤ 10^9 ) denoting the numbers Prof. Pang is given. It is guaranteed that the sum of n over all test cases is no more than 10^5 .
Output
For each test case, output one line containing the minimum amount of carries.
Example
input
2
3
9 99 999
1
12345
output
5
0
(1)which means “进位” in Chinese
其实不管计算进位次数都是一样的，所以直接计算总的进位次数就行了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std ;
typedef long long ll;
int n , m ;
int k , t;
int res ;
ll add(ll a , ll b){
ll p = a + b ;
int a1 = 0 ;
int b1 = 0 ;
while(a || b){
a1 += a % 10 ;
a /= 10;
b1 = b % 10 ;
b /= 10;
a1 = a1 + b1 >= 10 ? 1 : 0 ;
res += a1 ;
}
return p;
}
int main()
{
ios::sync_with_stdio(false );
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
res = 0 ;
cin >> n ;
ll a , b ;
cin >> a ;
for(int i = 0 ; i < n - 1 ; i++){
cin >> b;
a = add(a , b );
}
cout << res << endl;
}
return 0;
}