程序员进阶之算法练习（八十二）
题目1
题目链接 题目大意： 给出一个整数n，构造一个长度为n的整数数组a，满足： 1、1≤𝑎𝑖≤1000 对于所有的 1≤𝑖≤𝑛； 2、𝑎𝑖 能整除𝑖，对于所有的 1≤𝑖≤𝑛； 3、𝑎1+𝑎2+…+𝑎𝑛 能够整除 𝑛 .
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200) 每个样例一行，整数𝑛 (1≤𝑛≤200)
输出： 对于每个样例，输出符合要求的n个整数；
Examples input 7 1 2 3 4 5 6 7
output 1 2 4 1 2 3 2 8 6 4 3 4 9 4 5 1 10 18 8 5 36 3 6 21 24 10 6 14
题目解析： 对于要求1和要求2比较容易满足，用1、2、3、4、5、、、这样的序列即可； 对于要求3比较特殊，但是可以利用位置1的任何值都能整除1特性，将数组和多余的部分累计在位置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 = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int sum = (1 + n) * n / 2;
int first = 1;
if (sum % n != 0) {
first += n - (sum % n);
}
cout << first << " ";
for (int i = 2; i <= n; ++i) cout << i << " ";
cout << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目2
题目链接 题目大意： 有1到n的n个整数数组a，现在这n个整数是unsort的状态，也就是至少存在一个整数a[i] ≠ i； 可以选择一个整数k，对于数组中任意两个整数a[i]和a[j]，只要满足i-j=k，则可以交换a[i]和a[j]； 想知道，如果想要把数组调整为有序状态（a[i] = i），整数k最大值可能为多少？
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行，第一行整数𝑛 (1≤𝑛≤2⋅1e5) 第二行 n个整数，a1,a2,…,a𝑛 (1≤a𝑖≤𝑛 )
输出： 对于每个样例，输出k的最大可能值；
Examples input 7 3 3 1 2 4 3 4 1 2 7 4 2 6 7 5 3 1 9 1 6 7 4 9 2 3 8 5 6 1 5 3 4 2 6 10 3 10 5 2 9 6 7 8 1 4 11 1 11 6 4 8 3 7 5 9 10 2
output 1 2 3 4 3 2 3
题目解析： 首先，题目一定有解，比如说k=1的时候，就可以使用冒泡排序，最终使得数组有序； 当k=2的时候，奇数位置的数字可以互相交换，偶数位置的数字可以相互交换；那么要求所有数字与所属位置的距离，应该都为2，或者2的倍数（多次交换，即可得到2的倍数距离）； 当k=3的时候，与k=2类似，位置1、2、3只能和4、5、6等位置交换； .. 这样我们将整数数组与所属位置进行匹配，就可以得到整数数组b，排除掉b[i]=0的部分（已经匹配）； 只要存在最大公约数k，对于所有的b[i]都有b[i]%k==0，那么这个k是可行的。
那么怎么找到这个k？ 有个简单的做法，我们找到最大的整数，将整数进行因数分解，再分别判断每个因素是否为最大公约数即可。 （仔细分析一下，发现这里不要最大整数，取任意整数均可）
#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], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) b[i] = abs(a[i] - i - 1);
sort(b, b + n, greater<int>());
vector<int> tmp;
tmp.push_back(1);
tmp.push_back(b[0]);
for (int i = 2; i * i <= b[0]; ++i) {
if (b[0] % i == 0) {
tmp.push_back(i);
tmp.push_back(b[0] / i);
}
}
sort(tmp.begin(), tmp.end(), greater<int>());
int ans = 0;
for (int i = 0; i < tmp.size() && !ans; ++i) {
int ok = 1;
for (int j = 0; j < n && b[j] != 0; ++j) {
if (b[j] % tmp[i] != 0) {
ok = 0;
break;
}
}
if (ok) {
ans = tmp[i];
}
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目3
题目链接 题目大意： 给出两个整数数组a和b，数组a的元素两两不相同； 现在可以对数组a的元素任意排序，要求： 对于数组a每一个元素a[i]，都满足a[i]>b[i]； 问最多有多少种选择？
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行，第一行整数𝑛 (1≤𝑛≤2⋅1e5) 第二行 n个整数， 𝑎1 , 𝑎2, …, 𝑎𝑛 (1≤𝑎𝑖≤1e9) 第三行 n个整数，𝑏1 , 𝑏2 , … , 𝑏𝑛 (1≤𝑏𝑖≤1e9 )
输出： 对于每个样例，输出最后的可能数，结果对1e9+7 取余；
Examples input 5 6 9 6 8 4 5 2 4 1 5 6 3 1 3 4 3 2 3 4 9 1 2 1 3 2 3 4 1 3 3 12 2 3 7 10 23 28 29 50 69 135 420 1000 1 1 2 3 5 8 13 21 34 55 89 144
output 32 0 1 0 13824
题目解析： 由题目的要求可以知道，数组的初始顺序并没有意义，那么将a和b从小到大的排序。 接下来，如果出现a[i] <= b[i]，题目就无解。因为a[i+1]<=a[i]，第i个后面的数字找不到a[x]>b[i]；（x > i） 对于每一个整数a[i]，如果满足a[i]>b[i]，那么我们还可以接着看i+1、i+2、i+3，直到a[x]>b[i]不满足，这些数字都是可选； 那么，我们可以维护一个位置pos，在a[pos]>b[i]的情况下，让pos尽可能靠右； 当我们遇到i+1时，pos同样更新a[pos]>b[i+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 = 201010;
int a[N], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
sort(a, a + n, greater<int>());
sort(b, b + n, greater<int>());
lld sum = 1;
int pos = 1;
for (int i = 0; i < n; ++i) {
if (a[i] <= b[i]) {
sum = 0;
break;
}
while (pos < n && a[pos] > b[i]) ++pos;
// cout << i << " " << pos << " " << sum << endl;
sum = (sum * (pos - i)) % 1000000007;
}
cout << sum << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目4
题目链接 题目大意： 有n个灯，编号分别为1到n，每个灯有两个参数a[i]和b[i]； 初始状态，n个灯都是关闭的状态，接下来可以进行若干个操作： 选择一个关闭状态的灯i，将其打开，得到分数b[i]; 在这个操作之后，假设亮着的灯有x盏，那么所有a[i] <= x的灯，都会坏掉；（不管是打开，还是关闭的状态）
假设可以任意选择开灯的顺序，问最多能得到多少分。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤2⋅1e5) 接下来n行，每行有整数a𝑖 and b𝑖 (1≤a𝑖,b𝑖≤𝑛 )
输出： 对于每个样例，输出最大的得分数；
Examples input 4 4 2 2 1 6 1 10 1 13 5 3 4 3 1 2 5 3 2 3 3 6 1 2 3 4 1 4 3 4 3 5 2 3 1 1 1
output 15 14 20 1
题目解析： 题目的意思比较难理解，“假设亮着的灯有x盏，那么所有a[i] <= x的灯，都会坏掉“的解释是： 假设点亮1盏灯，那么a[i] <= 1的灯会坏掉； 假设点亮2盏灯，那么a[i] <= 2的灯会坏掉； 也就是说，a[i]越小，灯就越容易坏。
那么可以知道，我们必然会先选择a[i] = 1的灯去打开，并且有且只有一盏a[i]=1的灯能够打开； 同理a[i]=2的灯，最多能打开2盏； a[i]=3的灯，最多能打开3盏； ... 这样就可以知道，a[i]=x的灯，有x盏能打开。
结果就是排序，先按照a[i]从小到大，再按b[i]从大到小即可。 实现逻辑可以用map来降低复杂度。
#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;
pair<int, int> g[N];
static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first) return a.first < b.first;
else return a.second > b.second;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> g[i].first >> g[i].second;
}
sort(g, g + n, cmp);
lld ans = 0;
map<int, int> vis;
for (int i = 0; i < n; ++i) {
if (vis[g[i].first] < g[i].first) {
++vis[g[i].first];
ans += g[i].second;
}
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目5
题目链接 题目大意： 有整数数组，初始为空数组，接下来执行n次操作： 第i次操作，可以选择整数数组b中的0到i-1，其中一个位置p；在位置p后面增加一个整数0，然后对这个位置p之前的数组b元素执行revert操作（原来0，则会变成1；原来1，则会变成0）
现在知道最终操作完的整数数组结果，我们用数组a表示； 求这n次操作中，每一次操作组成的整数素组；
比如说，已知最终整数数组为[0, 1, 0]； 那么我们第1次可以选择0，得到[0]; 第2次可以选择1，得到[1，0]； 第2次可以选择0，得到[0，1，0]； 这样操作结果组成的整数数组就是[0, 1, 0]；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤2⋅1e5) 第二行，每行有整数a𝑖 (1≤a𝑖≤𝑛 )
输出： 对于每个样例，如果无解，输出NO； 如果有解，先输出YES； 接下来一行，输出n个整数，表示n次操作的结果；（第i个元素表示第i次操作）
Examples input 4 5 1 1 0 0 0 1 1 3 0 1 1 6 1 0 0 1 1 0
output YES 0 0 2 1 3 NO NO YES 0 1 0 2 4 2
题目解析： 根据题目的限制，第i次的选择区间是[0, i-1]，那么： 第1次，选择区间是[0, 0]; 第2次，选择区间是[0, 1]; 第3次，选择区间是[0, 2]; 第4次，选择区间是[0, 3]; ... 可以发现，不管如何选择，数组的最后一个元素必然是0，如果为1就无解； 插入整数是0，假设插入的是第0位，那么就是添加元素0； 对于都是0的数组，假设插入的是第x位，那么就是前面x个整数变成1； 接下来就比较简单，对于数组[1, 1, 0]，可以用[2, 0, 0]操作结果来表示； 对于整数[0, 1，1, 0]，可以拆分为[0] + [1，1，0]，那就可以用[0，2，0，0]的操作来表示；
总结来说，就是关注1的部分，将相邻的1合并在一起；假设有x个1在一起，那么就在某个时机选择位置x来生成x个连续的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 = 201010;
int a[N];
static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first) return a.first < b.first;
else return a.second > b.second;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (a[n - 1]) cout << "NO" << endl;
else {
cout << "YES" << endl;
int pos = 0;
while (pos < n) {
if (!a[pos]) ++pos;
int cnt = 0;
int tmp = pos;
while (a[pos] == 1) {
a[pos] = 0;
++pos;
++cnt;
}
a[tmp] = cnt;
}
for (int i = n - 1; i >= 0; --i) cout << a[i] << " ";
cout << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}腾讯云开发者
