首页 计算机科学 算法 ACM

还没玩转 Shoka 主题，有些东西使用 markdown 或者 latex 语法不能完全显示，本文可参考我的 bilibili 专栏。

# 头文件

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include<functional>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <sstream>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <regex>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int MOD = 1e9 + 7;
using namespace std;
# A - Roaming Romans
The English word "mile" derives from the Latin "mille passus", meaning "a thousand paces". A Roman mile was the distance a soldier would walk in 1000 paces (a pace being two steps, one with each foot).
Over time, the actual distance referred to as a "mile" has changed. The modern English mile is 5280 (modern) feet. The Roman mile is believed to have been about 4854 (modern) feet. Therefore a distance of English miles would correspond to 1000⋅100048541000 · \frac{1000}{4854}  Roman paces.
Write a program to convert distances in English miles into Roman paces.
Input
Input will consist of a single line containing a single real number 0≤X≤10000 \leq X \leq 1000 denoting a distance in English miles. The number XX has at most 3 digits of precision after the decimal point.
Output
Print an integer denoting the closest number of Roman paces equivalent to XX. Your answer should be rounded to the closest integer (with an exact .5 decimal part rounded up).
Sample
InputOutput
1.01088
20.26722046
标准模拟题，按照公式转换即可。
int main() {
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    double x;
    double ans;
    cin >> x;
    ans = x * 1000 / 4854 * 5280;
    printf("%.0f\n",ans);
    return 0;
}
# B - Harshad Numbers
We're all familiar with harshad numbers. For this problem, you will ... what's that? You aren't familiar with harshad numbers? They're also known as Niven numbers – does that ring a bell?? Anything???
Well, it's a simple enough concept. A harshad number is a number which is evenly divisible by the sum of its digits. For example, 24 is a harshad number: the sum of its digits is 2+4=62+4=6 and 24 is divisible by 6. 156 is also a harshad number, since 1+5+6=121+5+6=12 and 156=(12)(13)156=(12)(13). 157 is NOT a harshad number since it is not divisible by 1+5+7=131+5+7=13.
OK, let's start over.
We're all familiar with harshad numbers. For this problem, you will be given a number nn and must find the smallest harshad number≥nnumber \geq n.
Input
Input consists of a single line containing a positive integer $ n \leq 1, 000, 000, 000$.
Output
Display the smallest harshad number greater than or equal to nn.
Sample
InputOutput
2424
2527
987654321987654330
模拟题。如果一个数可以整除其每位数之和，这个数就称为 Harshad Number。给一个数，让求大于等于这个数的 Harshad Number。
bool find(int n){
    int sum_digits = 0, path = n;
    while(path){
        int temp = path % 10;
        sum_digits += temp;
        path /= 10;
    }
    if(n % sum_digits == 0)
        return true;
    else
        return false;
}
int main() {
	std::ios::sync_with_stdio(false);std::cin.tie(0);
    int n;
    cin>>n;
    for(int i = n; i <= 1000000000; i++){
        if(find(i)){
            cout << i << endl;
            break;
        }
    }
    return 0;
}
# C - Increasing Array
You are given an array of nn integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum number of moves required?
Input
The first input line contains an integer nn: the size of the array.
Then, the second line contains nn integers x1,x2,…,xnx_1,x_2,\ldots,x_n: the contents of the array.
Output
Print the minimum number of moves.
Constraints
1≤n≤2⋅105,1≤xi≤1091 \le n \le 2 \cdot 10^5, 1 \le x_i \le 10^9
Sample
InputOutput
5 </br> 3 2 5 1 75
模拟题。题意将输入的数组修改为递增数组，每次仅修改一个值将其加一。不是排序！
int main() {
	std::ios::sync_with_stdio(false);std::cin.tie(0);
    long long n, ans = 0;
    long long x[200005];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    for(int i = 1; i < n; i++){
        if(x[i] < x[i-1]){
            ans += x[i-1] - x[i];
            x[i] = x[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}
# D - So I’ll Max Out My Constructive Algorithm Skills
BaoBao the Witch is stuck in a maze with n rows and n columns, where the height of the cell in the ii-th row and the jj-th column is hi,jh_{i,j}. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down. More formally, you need to find a sequence $ (x_1, y_1),(x_2, y_2), · · · ,(x_{n2} , y_{n2}) $ such that:
  • For all 1≤i≤n2,1≤xi,yi≤n;1 \leq i \leq n^2, 1 \leq x_i, y_i \leq n;;
  • For all 1≤i,j≤n2,i≠j,(xi,yi)≠(xj,yj);1 \leq i,j \leq n^2, i \neq j, (x_i,y_i) \neq (x_j,y_j);;
  • For all 2≤i≤n2,∣xi−xi−1∣+∣yi−yi−1∣=1;2 \leq i \leq n^2, | x_i - x_{i-1}|+|y_i-y_{i-1}|=1;;
  • ∑i=2n2[hxi−1,yi−1<hxi,yi]≤∑i=2n2[hxi−1,yi−1>hxi,yi],\sum_{i=2}^{n^2}[h_{x_{i-1},y_{i-1}} < h_{x_{i},y_{i}} ] \leq \sum_{i=2}^{n^2}[h_{x_{i-1},y_{i-1}} > h_{x_{i},y_{i}} ],, where [P][P] equals 1 when [P][P] is true, and equals 0 when it is false.
Additionally, you discover that the heights in all cells are a permutation of n2n^2, so you just need to output the height of each cell in a valid path.
Input
There are multiple test cases. The first line of the input contains an integer T(1≤T≤100)T (1 \leq T \leq 100) indicating the number of test cases.
For each test case: The first line contains an integer n(2≤n≤64)n (2 \leq n \leq 64) indicating the size of the maze.
For the following nn lines, the ii-th line contains n integers hi,1,hi,2,⋅⋅⋅,hi,n(1≤hi,j≤n2)h_{i,1}, h_{i,2}, · · · , h_{i,n} (1 \leq h_{i,j} \leq n^2 ) where hi,nh_{i,n} indicates the height of the cell in the ii-th row and the jj-th column. It’s guaranteed that all integers in the input make up a permutation of n2n^2.
Output
For each test case output one line containing n2n^2 separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It’s easy to prove that an answer always exists.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
Sample
InputOutput
1 </br> 2 </br> 4 3 </br> 2 1</br>4 3 1 2
本题为 2021 ICPC Asia Macau 区域赛 A 题（签到题）。题目大意为一个n∗nn*n 矩阵，其中的值代表高度，每个各不相同，只能上下左右移动，求一条路下降次数大于等于上升次数。最开始想用 DFS，WA 四次之后发现只用看最后 up 和 down 谁大就好，蛇形矩阵遍历一遍，如果不符合要求翻转一遍就是结果。
int main(){
 	std::ios::sync_with_stdio(false);std::cin.tie(0);
    int T, n;
    int a[65][65];
    vector<int> res;
    cin >> T;
    while(T--){
        res.clear();
        cin>>n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> a[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) {
                for (int j = 1; j <= n; j++) {
                    res.push_back(a[i][j]);
                }
            } else {
                for (int j = n; j >= 1; j--) {
                    res.push_back(a[i][j]);
                }
            }
        }int up = 0, down = 0;
        for (int i = 1; i < res.size(); i++) {
            if (res[i] > res[i - 1])
                up++;
            else
                down++;
        }
        if (up > down)
            reverse(res.begin(), res.end());
        for (int i = 0; i < res.size(); i++) {
            if (i == res.size() - 1) {
                cout << res[i];
            } else {
                cout << res[i] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}
BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with nn vertices and mm edges, where the length of the ii-th edge equals 2i2^i. She needs to find a simple cycle with the smallest length.
A simple cycle is a subgraph of the original graph containing $ k (3 \leq k \leq n) $ vertices a1,a2,⋅⋅⋅,aka_1, a_2, · · · , a_k and kk edges such that for all 1≤i≤k1 \leq i \leq k there is an edge connecting vertices aia_i and a(imodk)+1a_{(i mod k)+1} in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.
Input
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases.
For each test case: The first line contains two integers n and m(3≤n≤105,1≤m≤105)m (3 \leq n \leq 10^5 , 1 \leq m \leq 10^5 ) indicating the number of vertices and edges in the original graph. For the following mm lines, the ii-th line contains two integers uiu_i and vi(1≤ui,vi≤n)v_i (1 \leq u_i , v_i \leq n) indicating an edge connecting vertices uiu_i and viv_i with length 2%5Ei.
There are no self loops nor multiple edges. Note that the graph is not necessarily connected.
It’s guaranteed that neither the sum of nn nor the sum of m of all test cases will exceed 10610^6.
Output
For each test case output one line. If there are no simple cycles in the graph output “-1” (without quotes); Otherwise output kk integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
Sample
本题为 2021 ICPC Asia Macau 区域赛 K 题（签到题），人菜没做出来。解法应该是并查集判环，DFS 或者 BFS 遍历输出。上个 AC 代码下来研究。
const int N = 100010;
int a[N],b[N],p[N];
int n,m;
vector<pair<int,int>>g[N];
vector<int>res;
void solve()
{
	res.clear();
	cin >> n >> m;
    for(int i = 1; i <= m; i++)	cin >> a[i] >> b[i];
    
    function<int(int)> find = [&](int x)
    {
    	if(p[x] != x)	p[x] = find(p[x]);
    	return p[x];
	};
	
	for(int i = 0;i <= n; i++)	p[i] = i, g[i].clear();
	
	function<bool(int,int,int)> dfs = [&](int u,int fa,int ed)->bool
	{
		if(u == ed)	return true;
		for(auto [v,i] : g[u])
		{
			if(v == fa)	continue;
			if(dfs(v,u,ed))
            {
                res.push_back(i);
                return true;
            }
		}
        return false;
	};
	
	for(int i = 1; i <= m; i++)
	{
		int pa = find(a[i]),pb = find(b[i]);
		if(pa != pb)
		{
			p[pb] = pa;
			g[a[i]].push_back({b[i], i});
			g[b[i]].push_back({a[i], i});
		}
		else
		{
			res.push_back(i);
			dfs(a[i], -1, b[i]);
			break;
		}
	}
	sort(res.begin(), res.end());
	if(res.empty())
	{
		cout << -1 << '\n';
		return ;
	}
	for(auto x : res)	cout << x << ' ';
	cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	int T;	cin >> T;
	while(T--)	solve();
	return 0;
}
# F - Random Permutation
An integer sequence with length nn, denoted by a1,a2,⋯,ana_1,a_2,\cdots,a_n, is generated randomly, and the probability of being 1,2,⋯,n1,2,\cdots,n are all 1n\frac{1}{n} for each ai(i=1,2,⋯,n)a_i(i=1,2,\cdots,n).
Your task is to calculate the expected number of permutations p1,p2,⋯,pnp_1,p_2,\cdots,p_n from 1 to n such that pi≤aip_i \le a_i holds for each i=1,2,⋯,ni=1,2,\cdots,n.
Input
The only line contains an integer n(1≤n≤50)n(1 \leq n \leq 50).
Output
Output the expected number of permutations satisfying the condition. Your answer is acceptable if its absolute or relative error does not exceed 10−910^{-9}.
Formally speaking, suppose that your output is x and the jury's answer is y. Your output is accepted if and only if ∣x−y∣max⁡(1,∣y∣)≤10−9\frac{|x - y|}{\max(1, |y|)} \leq 10^{-9}.
Sample
InputOutput
21.000000000000
31.333333333333
50104147662762941310907813025277584020848013430.758061352192
本题为 2020 ICPC Asia Macau 区域赛 L 题（签到题）数学推论题。题意大概为长度为nn 的数组 a$$，每个数都为1,2,3,⋅⋅⋅,n1,2,3,\cdot\cdot\cdot,n 的概率都为1n\frac{1}{n}，对于其全排列数组pp，对任意的ii，pi≤aip_i \le a_i 都成立的概率为多少。
int main() {
	std::ios::sync_with_stdio(false);=std::cin.tie(0);
    long double res = 1, n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        res *= i * i / n;
    }
    printf("%.15Lf\n", res);
    return 0;
}
# G - Prince and Princess
线性 DP 题。题目说了一大串，但实际上就是求n+1n+1 个数字和m+1m+1 个数字的最长公共子序列。但用普通的 LCS 算法复杂度直接变成n4n^4，所以要换思路。题目中说每一个数都不相同，可以使序列 a 有序，使序列 b 按照相同的法则进行映射，转化成 LIS。
const int maxn = 62505;
int n, m, t, p, q, f[maxn], a[maxn], b[maxn], low[maxn];
int main(){
	std::ios::sync_with_stdio(false);std::cin.tie(0);
    cin >> t;
    int cnt = 0;
    while(++cnt <= t){
        cin >> n >> p >> q;
        int maxmax = 0;
        memset(low, 0, sizeof(low));
        map<int,int> mp;
        for(int i = 1; i <= p + 1; i++)	cin >> a[i], mp[a[i]] = i;
        int len = 0;// 这里对第一组序列进行对应
        for(int i = 1; i<= q + 1; i++){
            cin >> b[++len];// 如果第二组序列中出现了前一组序列的数的位置就加到数组里
            if(mp.find(b[len]) == mp.end())	len--;// 没有就删除
            else b[len] = mp[b[len]];
        }
        //for(int i=1;i<=len;i++)cout<<b[i]<<" ";
        int len1 = 1;
        low[1] = b[1];
        for(int i = 2; i <= len; i++){
            if(low[len1] < b[i])	low[++len1] = b[i];
            else low[lower_bound(low + 1, low + len1 + 1, b[i]) - low] = b[i];
        }// 找一下新序列中最长上升子序列就是结果
        printf("Case %d: %d\n",cnt, len1);
    }
}