A
题意：
给定 n 个整数，可以交换任意两个数二进制上的某一位。求任意操作次数后数组中最大值与最小值的最大差。
核心思路：这个思路还是很显然的大胆的猜结论，贪心的考虑每一个位置。也就是&和|操作.
#include<iostream>
#include<unordered_map>
using namespace std;
void solve()
{
int n;
cin >> n;
int sum1 = 0;
int sum2 = 2047;
for (int i = 0;i < n;i++)
{
int x;
cin >> x;
sum1 |= x;
sum2 &= x;
}
cout << sum1 - sum2 << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
B
题意：
给定n个怪兽，每个怪兽有两个属性 hi,di ， hi 表示怪物的血量， di 表示怪物的护甲。你的初始伤害为 k ，每一次攻击都是对全体活着的怪兽造成伤害。但是每次攻击后，伤害会减弱，减弱的值为活着的怪物的 di 最小值，请问能否击杀所有怪物。
核心思路：其实找了半天发现就是一个模拟题，按照题意模拟就好了。唯一需要注意的是每一个di只可以使用一次.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 200010;
int n, k;
pair<int, int> a[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 0;i < n;i++)
cin >> a[i].second;
for (int i = 0;i < n;i++)
cin >> a[i].first;
int cur = 0;
int sum = 0;
sort(a, a + n);
while (k > 0 && cur < n)
{
sum += k;
while (k>0&&sum >= a[cur].second)
{
cur++;
}
if (cur < n)
{
k -= a[cur].first;
}
}
if (k > 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
C
给定一个长度为n的数组，每次操作可以选择一个区间[i, j]，使得区间范围内的所有数变为\(abs(a_i - a_j)\)，求若干次操作后数组所有元素的最大值。
核心思路：我们这里需要注意的是我们是可以进行多次操作的。所以我们先模拟几个样例观察规律。当n=4,a={1,6,8,3}.我们发现先对下标1和2操作之后：a={5.5.8.3},再对1和2操作：a={0,0,8,3}.再对1,2,3操作。再对3,4操作两次。于是变成了:a={8,8,0,0}.最对2,3,4.操作就好了。
于是我们发现一个结论：当n>3的时候我们总可以对数组操作，先将其变为相同的，然后再操作一次，就把那里变为了0.于是最后我们肯定是可以把我们数组中都替换为整个数组中的最大值的.
但是我们发现当n=3时有点不一样，因为数组中的最大值在中间的话我们是无法替换的。所以我们可以对每一种情况特判一下。因为i情况 也不是很多。
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 200010;
int n, k;
LL a[N];
void solve()
{
int n;
cin >> n;
LL mx = -0x3f3f3f;
for (int i = 1;i <= n;i++)
{
cin >> a[i];
mx = max(mx, a[i]);
}
if (n > 3)
{
cout << mx * n<<endl;
}
else if (n == 3)
{
LL t = 0;
t = max(t, a[1] * 3);
t = max(t, a[3] * 3);
t = max(t, abs(a[3] - a[1]) * 3);
t = max(t, abs(a[2] - a[1]) * 3);
t = max(t, abs(a[3] - a[2]) * 3);
t = max(t, a[1] + a[2] + a[3]);
cout << t << endl;
}
else if (n == 2)
cout << max(a[1] + a[2], abs(a[2] - a[1]) * 2) << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
D
给定5个数 n,i,j,x,y(3≤n≤100,1≤i,j,x,y≤n,i<j,x≠y)
请问有多少种长度为 n 双调排列 B 满足 Bi=x,Bj=y 。
定义双调排列
- 首先是个排列
- 满足先升序后降序，拐点的下标为 k(2≤k≤n−1)
核心思路：首先有一个需要注意的点是这个排列里面的数是\(1\sim n\).然后我们怎么去挖掘这个性质呢。这个双调数列其实有点像那个开口向下的二次函数。而我们函数上面的点又是\(1\sim n\).所以我们最后的拐点一定是n;知道这个之后我们就会发现可以随便往那个拐点的左右插入数，只需要保持单调就好了.
因为这一题的数据范围比较小，所以我们是可以使用dp的
集合定义：\(dp[i][j]是区间i\sim j的满足双调数列的性质的方案数\)
集合划分：我们发现i-1是可以放在左边或者右边的，j+1也是。不懂得可以看下下面那张图.
状态转移方程：\(dp[i][j]+=dp[i-1][j],dp[i][j]+=dp[i][j-1]\).
由着这一张图可以看出，我们对于任何一个长度为len的序列，他的一个区间变化范围是\([n-len+1,n]\),这就是我们挖掘出来的第二个性质，于是我们判断某种情况是否非法就很容易判断了。因为我们接下来需要放置的数就是n-len+1.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
int mod = 1e9 + 7;
const int N = 1e2+10;
int n, i, j, x, y;
int dp[N][N];
int check(int pos, int val)
{
if (pos == i && val != x)
return false;
if (pos == j && val != y)
return false;
else
return true;
}
void solve()
{
cin >> n >> i >> j >> x >> y;
memset(dp, 0, sizeof dp);
for (int i = 2;i <= n - 1;i++)
if (check(i, n))
dp[i][i] = 1;
for (int i = n;i >= 1;i--)
{
for (int j = i;j <= n;j++) {
int val = n - (j - i + 1);
if (check(i - 1, val))
(dp[i - 1][j] += dp[i][j]) %= mod;
if (check(j+1, val))
(dp[i][j + 1] += dp[i][j]) %= mod;
}
}
cout << dp[1][n] << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}