前言
果然还是要刷题，而且要刷难题，好久不刷题找不到思考的感觉了，看到题目有无从下手的感觉。
第一题
题目： Problem - 1631A - Codeforces
题意：
给两个数组a和b，可以任意交换ai和bi，求最后两个数组各自的最大值乘积。
输入格式
输入包含多个样例，第一行是一个整数t，代表有t个样例。
每个样例第一行是一个整数，代表数组中的元素个数。
每个样例的第二行和第三行均是n个整数。
数据范围
1 ≤ t ≤ 100
1 ≤ n ≤ 100
1 ≤ ai ≤ 10000，1 ≤ bi ≤ 10000
输出格式
输出一个整数。
输入样例：
3
6
1 2 6 5 1 2
3 4 3 2 2 5
3
3 3 3
3 3 3
2
1 2
2 1输出样例：
18
9
2思路：
- 无论怎么交换，两个数组中所有元素的最大值是无法避免被乘的，所以我们可以先确定总体的最大值，然后再依次遍历两个数组，看是否有两个同一位置的元素大于与总体最大值同一位置的元素，尽量将总体最大值对应位置的另一个数的值变小。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010;
int n;
pair<int, int>p[N];
bool cmp1(pair<int, int>a, pair<int, int>b)
{
return a.second < b.second;
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
int x=0, y=0;
for (int i = 1; i <= n; ++i)
{
cin >> p[i].first;
x = max(x, p[i].first);
}
for (int i = 1; i <= n; ++i)
{
cin >> p[i].second;
y = max(y, p[i].second);
}
if (x > y) sort(p + 1, p + n + 1);
else sort(p + 1, p + n + 1, cmp1);
int m1,m2;
if (p[n].first > p[n].second)m1 = p[n].first,m2=p[n].second;
else m1 = p[n].second,m2=p[n].first;
for (int i = n - 1; i >= 1; --i)
{
if (p[i].first > m2 && p[i].second > m2)
m2 = min(p[i].first, p[i].second);
}
cout << m1 * m2 << endl;
}
return 0;
}第二题
题目： Problem - 1631B - Codeforces
题意：
给定我们一个数组，每次可以选择两个数字l和k，然后将数组的[l, l+k-1]依次赋值为[l+k,l+2k-1]，要让数组中所有元素均相同最少需要几步。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n，代表数列有n个整数。
每个样例第二行是n个整数，代表整个 数列。
输出格式
一个整数，表示第几个字符串。
数据范围
1 ≤ t ≤ 2×104
1 ≤ n ≤ 2×105
1 ≤ ai ≤ n
输入样例：
5
3
1 1 1
2
2 1
5
4 4 4 2 4
4
4 2 1 3
1
1输出样例：
0
1
1
2
0思路：
- 因为我们在将区间赋值时，只能从后向前赋值，所以如果整个数列所有元素均相同，那么值一定等于最后一个数。
- 所以我们从倒数第二个数出发，每次遇到与最后一个数不同的数，就将已经遍历的数组赋值到前面。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200010;
int n;
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];
int cnt = 0;
for (int i = n-1; i >= 1;--i)
{
if (a[i] != a[n])
{
cnt++;
i = i - (n - i) + 1;
}
}
cout << cnt << endl;
}
return 0;
}第三题-赛后补题
题目： Problem - 1631C - Codeforces
题意:
给我们两个整数n和k，n表示我们有0到n-1个整数，要求我们找到 n/2 对整数，使每一对数进行与操作后的和等于k。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例只有两个整数n和k。
输出格式
每个样例如果能找到符合条件的 n/2 对整数，则每行输出一对，共 n/2 行。否则输出 -1 。
数据范围
1 ≤ t ≤ 400
4 ≤ n ≤ 216, 0 ≤ k ≤ n−1
输入样例：
4
4 0
4 1
4 2
4 3输出样例：
0 3
1 2
0 2
1 3
0 1
2 3
-1思路：
- 分类讨论。
- 第一种情况，当
k==0时，我们可以从[0, n-1]区间两侧开始向内一一配对。每对与操作后和为0。 - 第二种情况，当k不为0时：
- 如果
k<n-1，那么我们显然可以将k与n-1放到一组，这时与的操作结果为k，我们只需要将剩下的数配对后与操作之和结果为0即可，我们会发现k<n-1和k==0实际上只有两组不同，涉及到{0, n-1, k, n-k-1}四个数，而去除k和n-1后，0和n-k-1进行与操作结果同样为0，那么剩下的数和k==0进行相同操作即可。 - 如果
k==n-1，我们需要凑出k，那么我们可以先用n-1和n-2与操作得到n-2，然后用n-3和1进行与操作得到1，然后将0和2配对得到0，这时我们会发现n-2+1=k，之后剩下的数和k==0时操作相同。
- 如果
- 注意需要特判当n==4&&k==3时这种情况，因为：n-1和n-2配对，n-3和0配对，还剩一个1无法实现
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200010;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
//当n==4&&k==3时，n-1和n-2配对，n-3和0配对，还剩一个1无法实现
if (n == 4 && k == 3)cout << "-1" << endl;
else if (k == 0)
for (int i = 0; i < n / 2; ++i) cout << i << " " << n - 1 - i << endl;
else if (k < n - 1)
{
//让k与n-1与操作，结果还是k
cout << k << " " << n - 1 << endl;
//0和n-k-1本来应该分别与n-1和k配对
cout << 0 << " " << n - k - 1 << endl;
for (int i = 0; i < n / 2; ++i)
{
if (i == k || i == 0 || i == n - k - 1 || i == n - 1)continue;
else cout << i << " " << n - 1 - i << endl;
}
}
else
{
cout << n - 1 << " " << n - 2 << endl;//n-2
cout << n - 3 << " " << 1 << endl;//1 n是偶数，所以n-3是奇数
cout << 0 << " " << 2 << endl;//0
for (int i = 3; i < n / 2; ++i)cout << i << " " << n - i - 1 << endl;
}
}
return 0;
}
