程序员进阶之算法练习（八十六）
题目1
题目链接
题目大意：
给出n个整数，已知这n个整数是按照下面的规则生成。
1、初始化的时候，数组中有2个整数，每次从数组中选择任意两个整数，计算得到他们差值的绝对值，重新放回数组；
2、重复n-2次操作1，得到n个元素的数组。
现在已知n个整数的数组，想知道最开始的两个元素中，会存在哪个数字？
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200)
每个样例2行
第一行，整数𝑛 (1≤𝑛≤100)
第二行，n个整数𝑎1,𝑎2,…𝑎𝑛 (−1e9≤𝑎𝑖≤1e9 )
输出：
每个样例一行，输出初始整数中的一个，题目保证有解；
Examples
input
9
3
9 2 7
3
15 -4 11
4
-9 1 11 -10
5
3 0 0 0 3
7
8 16 8 0 8 16 8
4
0 0 0 0
10
27 1 24 28 2 -1 26 25 28 27
6
600000000 800000000 0 -200000000 1000000000 800000000
3
0 -1000000000 1000000000
output
9
11
-9
3
8
0
-1
600000000
0
题目解析：
由题目的定义可以知道，|A-B|是无法产生负数，那么如果数字中存在负数，则必然负数是初始数字；
同理假设x是数组中的最大元素，并且此时数组中并没有负数，那么x必然也是初始元素，因为|A-B|在全为正数的情况下，无法产生更大的数值。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
if (a[0] < 0) cout << a[0] << endl;
else cout << a[n - 1] << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目2
题目链接
题目大意：
给出n个整数的排列，现在可以选择排列中的2个位置，交换位置上的元素。
要求，交换之后所有子数组形成的排列尽可能的少。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，整数𝑛 (3≤𝑛≤2e5)
第二行，n个整数𝑎1,𝑎2,…𝑎𝑛
输出：
每个样例一行，输出交换的两个整数的位置；
如果有多个答案，可以输出其中一个；（两个位置可以是相同的）
Examples
input
8
3
1 2 3
3
1 3 2
5
1 3 2 5 4
6
4 5 6 1 2 3
9
8 7 6 3 2 1 4 5 9
10
7 10 5 1 9 8 3 2 6 4
10
8 5 10 9 2 1 3 4 6 7
10
2 3 5 7 10 1 8 6 4 9
output
2 3
1 1
5 2
1 4
9 5
8 8
6 10
5 4
题目解析：
对于排列来说，最终的整数就是1，因为所有的排列都要从1开始；
其次就是整数2，因为排列除了1，第二位是2；
根据题目的要求，如果想要无法组成排列，那么最大数n也很重要，因为一旦1和2被n隔开，那么就无法形成排列（除非整个数组一起参与排列）；
那么我们用 x,y,z来表示1,2,n这三个整数的位置。
容易知道，只要我们形成x<z<y或者y<z<x这样的位置顺序，那么所有子数组只有2个排列（1和n）；
只考虑x,y,z三个位置，我们知道交换一个位置，必然可以把z交换到中间去。
为了简单实现，我们将x,y,z三个整数排序，然后将z与排序中间的位置交换即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x, y, z;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] == 1) x = i;
if (a[i] == 2) y = i;
if (a[i] == n) z = i;
}
int tmp[] = {x, y, z};
sort(tmp, tmp + 3);
cout << tmp[1] << " " << z << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目3
题目链接
题目大意：
将1、2、3、、、、n x m个整数，填入到n x m的网格中；
要求任何两个相邻的格子，格子上数字差的绝对值不是素数。
现在求其中一个填充结果。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例一行，整数𝑛, m (4≤𝑛, m≤1000)
输出：
每个样例输出n行，每行m个整数；（题目保证有解）
Examples
input
3
4 4
5 7
6 4
output
16 7 1 9
12 8 2 3
13 4 10 11
14 5 6 15
29 23 17 9 5 6 2
33 27 21 15 11 7 1
32 31 25 19 20 16 10
26 30 24 18 14 8 4
35 34 28 22 13 12 3
2 3 7 11
8 9 1 10
17 13 5 4
18 14 6 12
19 23 15 21
20 24 16 22
题目解析：
当n/m偶数时，从左到右，从上到小填写即可。例如n=4：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
...
每个数字和左右相邻都是1，上下相邻是2的倍数。
当n/m是奇数时，比如说k=2时，n=(2k + 1)=5；
如果还是采用原来解决方案，1和6的差距就是n=5，此时两数之差是质数；
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
....
但是知道，1和11的差是2 * n，不是质数；
那么这个整数矩阵可以做一些简化，只考虑每行第一个整数：
1
n + 1
2n + 1
3n + 1
4n + 1
...
做一些调整
1
2n + 1
4n + 1
n + 1
3n + 1
...
这样上下整数的差就变成2n、2n、3n、2n，都是n的倍数，也即是都是合数。（注意，至少n>4才能用着这种方式）
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 1010;
int a[N][N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n % 2 == 0) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = (j - 1) * n + i;
}
else {
for (int i = 1; i <= (n + 1)/2; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = (i - 1) * 2 * m + j;
}
}
for (int i = 1; i <= n/2; ++i) {
for (int j = 1; j <= m; ++j) {
a[i + (n+1)/2][j] = (i - 1) * 2 * m + j + m;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j){
cout << a[i][j] << " ";
}
cout << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目4
题目链接
题目大意：
有n个节点的树，节点序号为1、2、3、、、n，现在小明开始用下面的方式开始绘制整棵树：
1、先绘制节点1；
2、按照边输入的顺序遍历，对于每一条边，如果存在一个节点已经绘制且另外一个节点没绘制，则绘制未存在的节点；
3、遍历完成后，检查是否所有节点已经绘制完成，否则重新操作2；
现在想知道，需要遍历多少次，才能绘制完所有节点；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例第一行整数𝑛 (1≤𝑛≤2⋅1e5)
接下来n-1行，每行有整数𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛 , 𝑢𝑖≠𝑣𝑖 )
输出：
对于每个样例，输出需要遍历的次数；
Examples
input
2
6
4 5
1 3
1 2
3 4
1 6
7
5 6
2 4
2 7
1 3
1 2
4 5
output
2
3
题目解析：
先考虑简单的情况，假设4个节点，假如边顺序是：
1 2
2 3
3 4
那么结果，只要遍历一次即可；
如果边顺序是：
3 4
2 3
1 2
则结果需要3次，因为每次遍历完都只能绘制1个节点；
如果边顺序是：
1 2
3 4
2 3
则结果需要2次，第一次遍历可以产生1、2、3节点，第二次遍历则产生节点4；
观察这个过程，就是从节点1开始遍历，当遇到下一个节点就有两个抉择：
1、下个节点可以直接绘制，因为连接下一个节点的边，比当前节点要更晚；
2、下个节点需要等下一次遍历，因为连接下一个节点的边，比当前节点要更早；
通过上面这个方式，我们只需要遍历一次，就可以快速知道一条链路上，需要遍历多少次才能绘制完成；
当我们知道一条链路的解法之后，对于一个棵树，其实就是不断重复根节点到叶子节点的dfs过程。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
vector<int> g[N];
map<pair<int, int>, int> h;
int dfs(int u, int father) {
int ret = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v != father) {
ret = max(ret, dfs(v, u) + (h[make_pair(u, father)] > h[make_pair(u, v)]));
}
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
h.clear();
for (int i = 1; i <= n; ++i) g[i].clear();
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
h[make_pair(u, v)] = i;
h[make_pair(v, u)] = i;
}
int ans = 0;
for (int i = 0; i < g[1].size(); ++i) {
ans = max(ans, dfs(g[1][i], 1));
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
题目5
题目链接
题目大意：
有两个长度为n的整数数组a和b；
现在想要找到所有的(i, j)组合，满足 1≤𝑖<𝑗≤𝑛 且 𝑎𝑖⋅𝑎𝑗=𝑏𝑖+𝑏𝑗 .
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤𝑛)
第二行整数𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛 )
输出：
对于每个样例，输出存在的组合数量。
Examples
input
3
3
2 3 2
3 3 1
8
4 2 8 2 1 2 7 5
3 5 8 8 1 1 6 5
8
4 4 8 8 8 8 8 8
8 8 8 8 8 8 8 8
output
2
7
1
题目解析：
最直接做法，只需要枚举所有的i和j，计算是否满足要求，但是复杂度O(N^2)，明显超过题目要求；
分析题目的要求，组合数量对原有位置没有要求，那么可以对数组进行排序；
但是不管数组a排序还是数组b排序，都无法满足快速求解；
继续分析题目给出的条件，发现a和b的范围比较小，那么bi+bj应该小于2n；
对于组合(i,j)，我们假设ai<bi，那么ai作为乘法的较小值可以满足ai <= sqrt(2n)=633，这样ai的枚举范围就缩小很多，这似乎是一个突破口。
那么是不是直接按照数组a的大小排序，然后遍历数组a，直到ai <= sqrt(2n)即可？
这样当数组所有元素ai都<= sqrt(2n)时，复杂度依然超标。
所以枚举的应该是ai所取的值。
对于组合(i, j)，有数字a[i]和a[j]，以及b[i]和b[j]，一共四个未知数；（注意这里我们假设了a[i] < a[j])
我们枚举a[i]的值，先假设ai=x，那么对于数字a[j]和b[j]我们同样去枚举j∈[0, n]的情况，这样我们就知道了3个未知数，根据a[i]*a[j] = b[i] + b[j]，我们可以推出 b[i] = y = a[i] * a[j] - b[j] = x * a[j] - b[j];
此时我们只要知道在枚举到j时，前面出现过所有的a[i] = x并且 b[i]的值为y的数字即可；
我们在遍历数组过程，要统计前面出现过的值为y的整数，可以用哈希来解决，用h[value]++的方式来记录，然后统计前面value出现次数就是h[value]；
注意：数组要按照a从小到大排序。
因为，我们假设了a[i] < a[j]，为了保证这个要求，我们需要对数组排序，并且在枚举到位置j时，另外一个位置i只能考虑[1, j - 1]这个区间。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 202010;
pair<int, int> a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i].first);
}
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i].second);
}
// sort(a, a + n);
int m = sqrt(n * 2) + 1;
lld ans = 0;
for (int i = 1; i <= m; ++i) {
// map<int, int> h;
vector<int> h(n+1);
for (int j = 0; j < n; ++j) {
int y = i * a[j].first - a[j].second; // x = i时， second应该等于y
if (1 <= y && y <= n) {
ans += h[y];
if (h[y]) cout << i << "*" << a[j].first << "=" << y << "+" << a[j].second << endl;
}
if (a[j].first == i) {
h[a[j].second]++;
}
}
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}
