A Cherry

题目大意

给一个长度为n的数组，让你求所有l，r区间的 最大值*最小值 的最大值

主要思路

假设目前有3个数，a1，a2，a3，那么最大值一定存在于（a1，a2）或者（a2，a3）中。

假设原序列为a1，a2，添加a3并不会使最小值变大，只能使最大值变大，那么如果添加a3后，更新(a1, a2, a3)为最优解，那么a3为最大值，于是(a2, a3)不会比最优解差，a2是最小值与最优解相同，a1是最小值优于最优解，所以长度为3的序列的答案一定存在于长度为2的序列。

同理长度为4的序列一定存在于长度为3的序列

综上：答案一定存在于长度为2的序列中

AC代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define debug(a) cout << #a << " = " << a << endl;
  5. #define x first
  6. #define y second
  7. typedef long long ll;
  8. const int N = 200010;
  9. int n, a[N], maxa[N], mina[N];
  11. int main(void)
  12. {
  13.     int T;
  14.     cin >> T;
  15.     while(T--)
  16.     {
  17.         cin >> n;
  18.         ll ans = 0;
  19.         for(int i = 1; i <= n; i++)
  20.         {
  21.             cin >> a[i];
  22.         }
  23.         for(int i = 2; i <= n; i++) ans = max(ans, (ll)a[i] * a[i - 1]);
  24.         cout << ans << endl;
  25.     }
  26.     return 0;
  27. }

B Cobb

题目大意

给一个长度为n的数组，求所有 i j - k (a[i] | a[j])的最大值

主要思路

首先思考f(i, )，i 在哪种情况所取的值最大，f(i, n) = i n - k 0 = i * n，这种情况时最大，

接下来考虑f(n - 1, n)在哪种情况下最小，f(n - 1, n) = n (n - 1) - k (a[n] | a[n - 1])，由于a[i]范围为1~n，两个a[i]取|的最大值不超过2 * n, 所以f(n - 1, n)的最小值为，n^2 - n - 2kn

f(i, n) < f(n - 1, n) -> i < n - 2k - 1，所以当i小于n - 2k时，f(n - 1, n)是最大的，所以考虑(n - 2k, n)区间的最大值即可

AC代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int32_t main() {
  5.   ios_base::sync_with_stdio(0);
  6.   cin.tie(0);
  7.   int t; cin >> t;
  8.   while (t--) {
  9.     int n, k; cin >> n >> k;
  10.     vector<int> a(n + 1);
  11.     for (int i = 1; i <= n; i++) {
  12.       cin >> a[i];
  13.     }
  14.     long long ans = -1e12;
  15.     int l = max(1, n - 2 * k);
  16.     for (int i = l; i <= n; i++) {
  17.       for (int j = i + 1; j <= n; j++) {
  18.         ans = max(ans, 1LL * i * j - 1LL * k * (a[i] | a[j]));
  19.       }
  20.     }
  21.     cout << ans << '\n';
  22.   }
  23.   return 0;
  24. }

C Mikasa

题目大意

给定一个数n和m，将n^1, nm放到一个集合中，求没有出现的最小非负整数

主要思路

假设答案为k，n ^ k > m -> n ^ k >= m + 1,，令p = m + 1 -> n ^ k >= p

那么我们考虑k如何最小，假设第i位ni == pi, 那么ki取0，如果ni = 1, pi = 0，那么ki取0即可，因为ni ^ ki大于等于pi，当ni = 0, pi = 1时，ki = 1

接下来考虑顺序，我们贪心从高位往低位判断，因为要异或后的值大于等于p，假设从低位往高位判断，那么即使低位的数变大了，高位小依然不行，所以从高位往低位依次判断即可

AC代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define debug(a) cout << #a << " = " << a << endl;
  5. #define x first
  6. #define y second
  7. typedef long long ll;
  8. const int N = 200010;
  9. int n, a[N], m;
  11. int main(void)
  12. {
  13.     int T;
  14.     cin >> T;
  15.     while(T--)
  16.     {
  17.         cin >> n >> m;
  18.         m++;
  19.         int ans = 0;
  20.         for(int k = 30; k >= 0 && n < m; k--)
  21.         {
  22.             if((n >> k & 1) == (m >> k & 1)) continue;
  23.             if(m >> k & 1) ans |= 1 << k, n |= 1 << k;//n维护的时异或后的值，大于m即可
  24.         }
  25.         cout << ans << endl;
  26.     }
  27.     return 0;
  28. }

D Diane

题目大意

让你用小写字母组成一个长度位n的字符串，使得字符串的所有相同子串个数为奇数

主要思路

先考虑一个字符串aaaa子串的个数，a的个数为4，aa的个数为3，aaa的个数为2，aaaa的个数为1，顺序为偶数，奇数，偶数，奇数

那么考虑如何使所有子串都为奇数呢，奇数+偶数 = 奇数，所以我们用x个a和1个b和x - 1个a凑长度为n的字符串，如果少一位则补c

AC代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define debug(a) cout << #a << " = " << a << endl;
  5. #define x first
  6. #define y second
  7. typedef long long ll;
  8. const int N = 200010;
  9. int n, a[N], m;
  11. int main(void)
  12. {
  13.     int T;
  14.     cin >> T;
  15.     while(T--)
  16.     {
  17.         cin >> n;
  18.         string ans;
  19.         for(int i = 0; i < n / 2; i++) ans += 'a';
  20.         ans += 'b';
  21.         for(int i = 0; i < n / 2 - 1; i++) ans += 'a';
  22.         if(ans.size() < n) ans += 'c';
  23.         cout << ans << endl;
  24.     }
  25.     return 0;
  26. }