Loading... > CodeForces Contest: http://codeforces.com/contest/977 > 官方英文题解: http://codeforces.com/blog/entry/59281 ## A. Wrong Subtraction Little girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm: - if the last digit of the number is non-zero, she decreases the number by one; - if the last digit of the number is zero, she divides the number by 10 (i.e. removes the last digit). You are given an integer number $n$. Tanya will subtract one from it $k$ times. Your task is to print the result after all $k$ subtractions. It is guaranteed that the result will be positive integer number. ### Input The first line of the input contains two integer numbers n and k $2 \le n \le 10^9$ — the number from which Tanya will subtract and the number of subtractions correspondingly. ### Output Print one integer number — the result of the decreasing $n$ by one $k$ times. It is guaranteed that the result will be positive integer number. ### Examples #### case 1: | input |output | | :------------ | :------------ | | 512 4 | 50 | #### case 2: | input |output | | :------------ | :------------ | | 1000000000 9 | 1 | ### Note The first example corresponds to the following sequence: $512 \rightarrow 511 \rightarrow 510 \rightarrow 51 \rightarrow 50$. --- ### Solve 这是一道500分的签到题 官方标签：`implementation` 题意很简单，给出两个数n, k，同时定义一个操作： - 当一个数末尾为非零时，该数-1， - 当末尾是零时，该数去除最后一个零。 问：一个数n经过k次操作后，n为几。 只需要简单的循环即可得出答案 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { std::ios::sync_with_stdio(false); cin.tie(0); // freopen("in","r",stdin); // freopen("out","w",stdout); int a; int n; cin >> a >> n; while (n--) { if (a % 10 == 0) { a /= 10; } else { a--; } } cout << a << endl; return 0; } ``` --- ## B. Two-gram Two-gram is an ordered pair (i.e. string of length two) of capital Latin letters. For example, "AZ", "AA", "ZA" — three distinct two-grams. You are given a string $s$ consisting of $n$ capital Latin letters. Your task is to find **any** two-gram contained in the given string **as a substring** (i.e. two consecutive characters of the string) maximal number of times. For example, for string $s$ = "BBAABBBA" the answer is two-gram "BB", which contained in $s$ three times. In other words, find any most frequent two-gram. Note that occurrences of the two-gram can overlap with each other. ### Input The first line of the input contains integer number $n$ ($2 \le n \le 100$) — the length of string $s$. The second line of the input contains the string $s$ consisting of $n$ capital Latin letters. ### Output Print the only line containing exactly two capital Latin letters — **any** two-gram contained in the given string $s$ **as a substring** (i.e. two consecutive characters of the string) maximal number of times. ### Examples #### case 1: | input |output | | :------------ | :------------ | |7ABACABA | AB | #### case 2: | input |output | | :------------ | :------------ | | 5ZZZAA | ZZ | ### Note In the first example "BA" is also valid answer. In the second example the only two-gram "ZZ" can be printed because it contained in the string "ZZZAA" two times. --- ### Solve 这是一道900分的字符串题。 官方标签：`implementation`，`strings` 给出一个字符串长度n和字符串s，求该字符串出现频率最高的子串（子串长度为2）。 比如字符串 “ABC” 中含有两个子串“AB”，“BC”。 这题使用string和map即可快速得出结果。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); // freopen("in","r",stdin); // freopen("out","w",stdout); int n; string s; cin >> n >> s; map<string, int> m; for (int i = 0; i < n - 1; i++) { string ss = s.substr(i, 2); m[ss]++; } map<string, int>::iterator it, maxx; maxx = m.begin(); for (it = m.begin(); it != m.end(); it++) { if (it->second > maxx->second) { maxx = it; } } cout << maxx->first << endl; return 0; } ``` --- ## C. Less or Equal You are given a sequence of integers of length $n$ and integer number $k$. You should print **any integer** number $x$ in the range of $[1; 10^9]$ (i.e. $1 \le x \le 10^9$) such that exactly $k$ elements of given sequence are less than or equal to $x$. Note that the sequence can contain equal elements. If there is no such $x$, print "-1" (without quotes). ### Input The first line of the input contains integer numbers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le n$). The second line of the input contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the sequence itself. ### Output Print **any integer** number $x$ from range $[1; 10^9]$ such that exactly $k$ elements of given sequence is less or equal to $x$. If there is no such $x$, print "-1" (without quotes). ### Examples #### case 1: | input |output | | :------------ | :------------ | | 7 43 7 5 1 10 3 20 | 6 | #### case 2: | input |output | | :------------ | :------------ | | 7 23 7 5 1 10 3 20 |-1 | ### Note In the first example $5$ is also a valid answer because the elements with indices $[1, 3, 4, 6]$ is less than or equal to $5$ and obviously less than or equal to $6$. In the second example you cannot choose any number that only $2$ elements of the given sequence will be less than or equal to this number because $3$ elements of the given sequence will be also less than or equal to this number. --- ### Solve 这是一道1200分的排序题。 官方标签：`sortings` 给定一个数组长度n和一个数k，接下来一行给你长度为n的数组a[ ] 问：是否存在一个数x，使数列中恰好有k个数小于等于x。 这里直接使用STL函数sort将序列从小到大排，接下来判断即可。 ```cpp #include <bits/stdc++.h> using namespace std; int a[1000000]; int main() { int n, k; while (cin >> n >> k) { for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); if (k == 0) { if (a[0] <= 1) cout << -1 << endl; else cout << 1 << endl; } else { if (n == k) { cout << a[n - 1] << endl; } else if (a[k - 1] < a[k]) { cout << a[k - 1] << endl; } else { cout << -1 << endl; } } } return 0; } ``` --- ## D. Divide by three, multiply by two Polycarp likes to play with numbers. He takes some integer number $x$, writes it down on the board, and then performs with it $n - 1$ operations of the two kinds: - divide the number $x$ by $3$ ($x$ must be divisible by $3$); - multiply the number $x$ by $2$. After each operation, Polycarp writes down the result on the board and replaces $x$ by the result. So there will be $n$ numbers on the board after all. You are given a sequence of length $n$ — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board. Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp's game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number. It is guaranteed that the answer exists. ### Input The first line of the input contatins an integer number $n$ ($2 \le n \le 100$) — the number of the elements in the sequence. The second line of the input contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3 \cdot 10^{18}$) — rearranged (reordered) sequence that Polycarp can wrote down on the board. ### Output Print $n$ integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board. It is guaranteed that the answer exists. ### Examples #### case 1: | input | output | | :------------ | :------------ | | 64 8 6 3 12 9 | 9 3 6 12 4 8 | #### case 2: | input | output | | :------------ | :------------ | | 442 28 84 126 | 126 42 84 28 | #### case 3: | input | output | | :------------ | :------------ | | 21000000000000000000 3000000000000000000 | 3000000000000000000 1000000000000000000 | ### Note In the first example the given sequence can be rearranged in the following way: $[9, 3, 6, 12, 4, 8]$. It can match possible Polycarp's game which started with $x = 9$. --- ### Solve 这是一道1400分的题，涉及到深度优先搜索、排序。 官方标签：`dfs and similar`，`math`，`sortings` 首先第一行给你一个数组长度n，接下来一行给出一串长度为n的数组a[ ]. 问：使该序列按照一定的规则进行排序，规则需要满足以下两条的任意一条 - $a_{i+1} = 2 * a_i$ - $a_{i} = 3 * a_{i+1}$ 题目保证有解 简单的搜索，直接使用深度优先搜索即可，模板题。从$a_0$到$a_{n-1}$，看能否搜到最深处，搜不到立刻剪枝返回上层进行下一个搜索，搜到最底层就直接打印然后退出程序即可。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[1005]; bool vis[1005]; int n; bool found = false; vector<ll> v; void print() { for (int i = 0; i < v.size(); i++) { if (i != 0) cout << " "; cout << v[i]; } } void dfs(int deep, ll last) { if (deep == n) { print(); found = true; return; } if (found) return; for (int i = 0; i < n; i++) { if (vis[i]) continue; if ((a[i] / 2 == last && a[i] % 2 == 0) || a[i] * 3 == last) { vis[i] = true; v.push_back(a[i]); dfs(deep + 1, a[i]); v.pop_back(); vis[i] = false; } } } int main() { std::ios::sync_with_stdio(false); cin.tie(0); // freopen("in","r",stdin); // freopen("out","w",stdout); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { vis[i] = true; v.push_back(a[i]); dfs(1, a[i]); v.pop_back(); vis[i] = false; if (found) break; } return 0; } ``` --- ## E. Cyclic Components You are given an undirected graph consisting of $n$ vertices and $m$ edges. Your task is to find the number of connected components which are cycles. Here are some definitions of graph theory. An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $a$ is connected with a vertex $b$, a vertex $b$ is also connected with a vertex $a$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices. Two vertices $u$ and $v$ belong to the same connected component if and only if there is at least one path along edges connecting $u$ and $v$. A connected component is a cycle if and only if its vertices can be reordered in such a way that: - the first vertex is connected with the second vertex by an edge, - the second vertex is connected with the third vertex by an edge, - ... - the last vertex is connected with the first vertex by an edge, - all the described edges of a cycle are distinct. ![There are $6$ connected components, $2$ of them are cycles: $[7, 10, 16]$ and $[5, 11, 9, 15]$.](/usr/uploads/2021/07/2687075451.png) There are $6$ connected components, $2$ of them are cycles: $[7, 10, 16]$ and $[5, 11, 9, 15]$. A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices. ### Input The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — number of vertices and edges. The following $m$ lines contains edges: edge $i$ is given as a pair of vertices $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$). There is no multiple edges in the given graph, i.e. for each pair ($v_i, u_i$) there no other pairs ($v_i, u_i$) and ($u_i, v_i$) in the list of edges. ### Output Print one integer — the number of connected components which are also cycles. ### Examples #### case 1: | input |output | | :------------ | :------------ | | 5 41 23 45 43 5 | 1 | #### case 2: | input |output | | :------------ | :------------ | | 17 151 81 125 1111 99 1515 54 133 134 310 167 1016 714 314 417 6| 2 | ### Note In the first example only component $[3, 4, 5]$ is also a cycle. The illustration above corresponds to the second example. --- ### Solve 这是一道1500分的图论题。 官方标签：`dfs and similar` `dsu` `graphs` 题目说了很长一串，其实目标很简单。给你一对点和一堆边，求出单链环（所有点的度都为２）的个数。 既然求个数，那么这题用并查集做绝对是最方便的选择之一。也是套用模板即可。 前半段常规操作，输入并建立并查集。最后查询个数时只需要查找对应点所在的集合，并将集合中的所有点进行度的计算，只要有一个点的度不为２则不符合单链环要求。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 200000 + 50; vector<int> G[MAXN]; int Par[MAXN]; int Rank[MAXN]; void init(int n) { for (int i = 0; i < n; i++) { Par[i] = i; Rank[i] = 0; } } int Find(int x) { if (Par[x] == x) { return x; } else { return Par[x] = Find(Par[x]); } } void Unite(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; if (Rank[x] < Rank[y]) { Par[x] = y; } else { Par[y] = x; if (Rank[x] == Rank[y]) Rank[x]++; } } bool same(int x, int y) { return Find(x) == Find(y); } int main() { std::ios::sync_with_stdio(false); cin.tie(0); // freopen("in", "r", stdin); // freopen("out","w",stdout); int n, T; cin >> n >> T; for (int i = 0; i < T; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } init(n); for (int i = 0; i < T; i++) { for (int j = 0; j < G[i].size(); j++) { Unite(i, G[i][j]); } } bool vis[MAXN]; map<int, bool> m; int cnt = 0; memset(vis, true, sizeof(true)); for (int i = 0; i < n; i++) { int t = Find(i); if (m.count(t) == 0) m[t] = true; if (G[i].size() != 2) m[t] = false; } map<int, bool>::iterator it; for (it = m.begin(); it != m.end(); it++) { if (it->second) cnt++; } cout << cnt << endl; return 0; } ``` --- ## F. Consecutive Subsequence You are given an integer array of length $n$. You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to $[x, x + 1, \dots, x + k - 1]$ for some value $x$ and length $k$. Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $[5, 3, 1, 2, 4]$ the following arrays are subsequences: $[3]$, $[5, 3, 1, 2, 4]$, $[5, 1, 4]$, but the array $[1, 3]$ is not. ### Input The first line of the input containing integer number $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array. The second line of the input containing $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the array itself. ### Output On the first line print $k$ — the maximum length of the subsequence of the given array that forms an increasing sequence of consecutive integers. On the second line print the sequence of the indices of the **any** maximum length subsequence of the given array that forms an increasing sequence of consecutive integers. ### Examples #### case 1: | input |output | | :------------ | :------------ | | 73 3 4 7 5 6 8 | 42 3 5 6 | #### case 2: | input |output | | :------------ | :------------ | | 61 3 5 2 4 6| 21 4 | #### case 3: | input |output | |:------------ | :------------ | | 410 9 8 7| 11 | #### case 4: | input |output | |:------------ | :------------ | | 96 7 8 3 4 5 9 10 11| 61 2 3 7 8 9 | ### Note All valid answers for the first example (as sequences of indices): - $[1, 3, 5, 6]$ - $[2, 3, 5, 6]$ All valid answers for the second example: - $[1, 4]$ - $[2, 5]$ - $[3, 6]$ All valid answers for the third example: - $[1]$ - $[2]$ - $[3]$ - $[4]$ All valid answers for the fourth example: - $[1, 2, 3, 7, 8, 9]$ --- ### Solve 这是一道1700分的动态规划题。 官方标签：`dp` 其实这个动态规划还是挺简单的，类似于求LCS ，只不过这里要求相差１，并且输出下标罢了。 我们可以很轻松的根据题目推出递推公式： $$ dp[i] = \text{MAX} \lbrace dp[i - 1] + 1, dp[i] \rbrace $$ 当然，这题的另外一个难点就是存储最长子序列的下标。其实这里可以使用一个投机取巧的方法：首先取出$[dp , dp_n]$中最大值和最大值的下标，通过下标得到这个数字ａ。因为这个最长子序列是相差１，所以我可以直接输出a-dp[maxi] ~ a的所有值。具体可以套样例。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); // freopen("in", "r", stdin); // freopen("out", "w", stdout); int n; int a[200000 + 50]; int maxi = 0; int maxdp = 0; map<int, int> dp; map<int, vector<int>> res; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { dp[a[i]] = max(dp[a[i] - 1] + 1, dp[a[i]]); if (dp[a[i]] > maxdp) { maxdp = dp[a[i]]; maxi = i; } } int cnt = a[maxi] - maxdp + 1; cout << maxdp << endl; for (int i = 0; i <= maxi; i++) { if (a[i] == cnt) { cout << i + 1 << " "; cnt++; } } } ``` 最后修改：2021 年 07 月 26 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏