程序员进阶之算法练习（七十七）
题目1
题目链接
题目大意：
给出n个整数的数组a，数组的元素可能是1或者2；
现在想要找到一个最小的位置k满足：
𝑎1⋅𝑎2⋅…⋅𝑎𝑘=𝑎𝑘+1⋅𝑎𝑘+2⋅…⋅𝑎𝑛
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例2行，第一行整数𝑛 (2≤𝑛≤1000）
第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤2).
输出：
每个样例一行，输出最小的位置k；如果不存在k，则输出-1；
Examples
input
3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1
output
2
-1
1
题目解析：
由于题目数字取值范围只有1和2，1不影响乘积，那么只需要考虑2；
如果数组中有偶数个整数，那么题目有解；
注意如果是0个数字2，那么答案是1；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> pos;
for (int i = 1; i <= n; ++i) {
int tmp;
cin >> tmp;
if (tmp == 2) pos.push_back(i);
}
int ans = 1;
if (pos.size() % 2) ans = -1;
else if (pos.size() > 0) ans = pos[pos.size() / 2 - 1];
cout << ans << endl;
}
}
}
题目2
题目链接
题目大意：
给出一个整数n，将整数n拆成两个整数A和B，要求满足：
A+B=n；
A和B的数字和最多相差1；
数字和的意思就是将整数A的各个位置数字相加，比如说198就是1+9+8=18，208就是2+0+8=10；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例1行，第一行整数𝑛 (2≤𝑛≤1e9）
输出：
每个样例一行，输出A和B，题目保证结果存在；
Examples
input
5
1
161
67
1206
19
output
1 0
67 94
60 7
1138 68
14 5
题目解析：
当n是偶数的时候，A=B=n/2，必然满足要求；
当n是奇数时，我们可以令A=n/2, B=n - n/2，这样有A和B必然满足A+B=n情况，接下来讨论AB数字和相差1的的情况：
1、当A的个位数小于9时，A和B必然数字和只差1，比如说81和82，78和79；
2、当A的个位数等于9时，由于B会进位，最终A和B的数字和会产生一个差值，比如说9和10，39和40，99和100；
由此我们可以产生一个朴素的做法：令A--，B++，最终肯定能够找到符合要求的数字；
但是这么做的话，会出现超时（TLE）的情况，我们来分析下复杂度。
当数字为999和1000时，数字和相差(9+9+9) - 1 = 26的情况，那么要A的数字和-13，B的数字和+13；
我们知道获得数字和13最快的情况是十位数4+个位数9，那么结果为A=999-49=950，B=1000+49=1049；
如果采用枚举的复杂度，需要枚举49次；
最坏的情况，数字n为199999999，A=99999999，B=100000000，A和B的数字和相差(9 * 8) - 1=71，也就是说A需要减去数字和35，B需要加上数字和36；
最终数字A为 99999999 - 8999 = 99991000，数字和是72-35=37；
最终数字B为100000000 + 8999 = 1000089999，数字和是1+36=37；
枚举的复杂度是10000左右，加上每次计算数字和的复杂度 和 样例数量，最终复杂度为10000 * 10 * 10000 = 1e9，复杂度偏高；
优化方式1：每次在计算A--和B++的时候，直接按照数字和一半进行操作，比如说数字和一半是37，那么A-=37，B+=37，这样效率能加快一些；因为最终数字和会逐步收敛，结果保证是正确的；
优化方式2：直接按照数字和之差，从个位数开始往高位填9，直到数字和小于9，则在当前位数填下剩余数字，比如说37就得到8999，13就得到49；这样可以O(1)得到最优解。
class Solution {
static const int N = 201010;
int digSum(int x) {
int ret = 0;
while (x) {
ret += x % 10;
x /= 10;
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x = n / 2, y = n - x;
while (abs(digSum(x) - digSum(y)) > 1) {
int dif = abs(digSum(x) - digSum(y)) / 2;
x -= dif;
y += dif;
}
cout << x << " " << y << endl;
}
}
}
题目3
题目链接
题目大意：
给出n个整数的数组，从数组中选择两个数字a[i]和a[j]，要求满足：
i和j不相同；
| a[i] - a[j] |的值，等于数组中最大值与最小值的差；
问，最多能选出多少个组合。
输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例2行，第一行整数 𝑛 (2≤𝑛≤1e5)
第二行整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e5)
输出：
每个样例一行，输出满足要求的组合数。
Examples
input
2
5
6 2 3 8 1
6
7 2 8 3 2 10
output
2
4
样例解释：
样例1，满足要求的有[1, 8]和[8, 1]；
样例1，满足要求的有[2, 10]和[10, 2]，其中2可以为第2个数字、第5个数字；
题目解析：
因为选出来的数字要满足差的绝对值最大，那么必然是最大值和最小值的组合。
假设最小值x，最大值y，首先看x和y是否相同。
如果x==y，则看x的总数，答案就是A(n, 2)，即是从n个整数中选择2个数字的组合排列数；
如果x!=y，那么结果就是x的数量与y的数量的乘积。
trick：
两个情况都可能超int32。
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] == a[n - 1]) cout << n * 1LL * (n - 1) << endl;
else {
int x = 0, y = 0;
while (a[x] == a[0]) {
++x;
}
while (a[n - 1 - y] == a[n - 1]) {
++y;
}
cout << x * 1LL * y * 2 << endl;
}
}
}
}
题目4
题目链接
题目大意：
给出1到n的n个整数的数组，现在需要从数组里面选择新的数组，但是已知有m对整数是不能共存：
比如说整数2和4不能共存，则新的数组里面不能同时存在2和4，比如说整数数组[1,2,3,4,5]，其中[2,3]和[3,4]都是合法的，[2,3,4]是不合法的；
现在想知道，能选出多少个子数组，里面不存在不合法的整数对。
输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤2⋅1e4),
每个样例第一行整数 𝑛 and 𝑚 (2≤𝑛≤1e5, 0≤𝑚≤1e5)
接下来m行整数 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖,𝑦𝑖≤𝑛, 𝑥𝑖≠𝑦𝑖)，表示两个不能相互相处的整数。
输出：
每个样例一行，输出满足要求的组合数。
Examples
input
2
3 2
1 3
2 3
4 2
1 2
2 3
output
4
5
样例解释：
样例1，满足要求的有整数[1],[2],[3],[1,2]；
样例2，满足要求的有整数[1],[2],[3],[4],[3,4]；
题目解析：
对于子数组[x, y]，我们可以枚举做区间x，再考虑y的取值；
首先y要满足x <= y，考虑所有y的取值，只要包括一个不能相处整数对，那么后续的整数就不用考虑，比如说样例2：
x=1，我们考虑y=1,2,3,4的情况，当我们发现整数1和2是不能相处的，那么2以及2后面的整数就不用考虑；
也即是说，我们只需要向右遍历到第一个出现的最小不能相处整数对的右区间y，[x, x]到[x, y-1]的区间都是合法的；
现在的问题变成了，对于选定整数x，如何快速得到右边区间最小的整数对；
假设我们把所有不合法整数对都按照左区间归类，然后从右到左遍历整数数组。
比如说遍历到整数i，那么对于所有做左区间≥i的整数对，都是在i的右边；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
int tmp = 0;
while (t--) {
++tmp;
int n, m;
map<int, vector<int> > mp;
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
if (x < y) {
mp[x].push_back(y);
}
else {
mp[y].push_back(x);
}
}
lld sum = 0;
int leftMin = n + 1;
for (int i = n; i > 0; --i) {
if (mp[i].size()) {
sort(mp[i].begin(), mp[i].end());
leftMin = min(leftMin, mp[i][0]);
}
sum += leftMin - i;
}
cout << sum << endl;
}
}
}
题目5
题目链接
题目大意：
给出n个整数，询问是否存在两个整数，最大公约数不是1；
如果存在则输出YES，如果不存在则输出NO；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e5)；
每个样例第一行整数 𝑛 (2≤𝑛≤1e5).
接下来n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9).
输出：
每个样例一行，输出是否满足要求。
Examples
input
2
3
32 48 7
3
14 5 9
output
YES
NO
题目解析：
先不考虑复杂度，最直接的做法，就是求出每个整数的因子，复杂度是O(M)，M是整数的大小的根，10^9需要遍历1w+次；
然后用map管理每个整数的因子，遍历每一个整数求是否有相同的因子，整体复杂度在O(NM)左右，map的复杂度可以暂时忽略；
总的复杂度会到达10^5 * 10^5 = 10^10量级，时间上是不允许的。
分析这个里面的优化空间，每个整数的因子最终都可以拆分为若干素数，这样就可以大幅度减少因子数量；
先预处理1-sqrt(10^9)的素数，再用这个素数去筛选n个整数，这样速度会更加快。
trick：这个如果遇到两个相同数字，就会出现异常。
另外在拆解的时候，一定要拆解数字到x = a * b * c这样的形式。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int m = sqrt(1e9) + 1;
vector<int> vec;
for (int i = 2; i<= sqrt(m); ++i) {
if (!a[i]) {
int tmp = i;
while (tmp <= m) {
tmp += i;
a[tmp] = 1;
}
}
}
for (int i = 2; i <= m; ++i) {
if (!a[i]) {
vec.push_back(i);
// cout << i << " ";
}
}
int t;
cin >> t;
while (t--) {
int n;
map<int, int> mp;
cin >> n;
bool ok = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
vector<int> tmp;
for (int j = 0; j < vec.size(); ++j) {
if (k % vec[j] == 0) {
tmp.push_back(vec[j]);
while (k % vec[j] == 0) k /= vec[j];
}
}
if (k != 1) {
tmp.push_back(k);
}
for (int j = 0; j < tmp.size(); ++j) {
if (mp[tmp[j]]) ok = 1;
mp[tmp[j]] = 1;
}
}
cout << (ok ? "YES" : "NO") << endl;
}
}
}
