题目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;
}
网友评论