A. Cherry

题目描述：

给你一个数组a, 找到$max(a_l,a_{l + 1},\cdots，a_{r-1},a_r) * min(a_l,a_{l + 1},\cdots，a_{r-1},a_r)$​的最大值，其中$1\leq{l}<r\leq{n}$​

思路：

我们考虑一个子数组($a_i,a_{i + 1},\cdots,a_{j-1},a_j$​),添加a_j+1后构成的新的子数组($a_i,a_{i + 1},\cdots,a_{j-1},a_j,a_{j + 1}$​),什么时候能产生更好的结果？

当且仅当a_j+1是一个大于之前子数组的max的值时才会产生一个更好的结果，但是我们真的需要检查整个子数组来判断a_j+1是不是真的这样吗，这复杂度根本说不过去……

这里我们分析一下a_i，如果a_i是min，那么最优值一个是取决于子数组($a_{i + 1},\cdots,a_{j-1},a_j,a_{j + 1}$)的值，如果不是min，那就说明a_i没有影响，相当于最优值还是($a_{i + 1},\cdots,a_{j-1},a_j,a_{j + 1}$)产生的，也就是说，我们需要取($a_i,a_{i + 1},\cdots,a_{j-1},a_j$)和($a_{i + 1},\cdots,a_{j-1},a_j,a_{j + 1}$)中最大的那个即可

但是这子数组长度不定，对于每种长度都循环去判断的话也不行，我们就得考虑能不能缩小子数组的大小，观察以后会发现(a₁,a₂,a₃)产生的结果不会有比(a₁,a₂)、(a₂,a₃)更好的结果，同样的，(a₁a₂a₃a₄)产生的结果不会有比(a₁a₂a₃)(a₂a₃a₄)更好的结果，这样就可以只计算子数组长度为2的

最终只需要循环对所有的a[i] * a[i - 1]取max即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x;
int tr[MAX];

int main(){
    scanf("%d", &t);
    while (t--) {
        cin>>n;
        ll ans = -1e18;
        for(int i = 1; i <= n; ++i){
            scanf("%d",&tr[i]);
        }
        for(int i = 2; i <= n; ++i){
            ans = max(ans, 1ll * tr[i] * tr[i - 1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

B. Cobb

题目描述：

给你一个数组a，一个k，让你找到$i*j - k * (a_i|a_j)$​的最大值，其中$1\leq{i}<j\leq{n}$

思路：

对于$i*j - k * (a_i|a_j)$中起决定性作用的是$i*j$,所以我们只需要从最后面开始暴力枚举即可，大概100*100差不多了

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod1 1000000007
#define mod2 1000000009
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x, k;
int tr[MAX];

int main(){
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        ll ans = -1e18;
        for(int i = 1; i <= n; ++i)scanf("%d", &tr[i]);
        for(int i = n; i >= n - 100 && i >= 1; --i){
            for(int j = i - 1; j >= n - 100 && j >= 1; --j){
                ans = max(ans, 1ll * i * j - 1ll * k * (tr[i] | tr[j]));
            }
        }
        cout<<ans<<endl;
        
        
    }
    return 0;
}

C. Mikasa

题目描述：

定义MEX为未出现的最小的非负数

给你n和m，通过$n\bigoplus{i}，0\leq{i}\leq{m}$​得到一个序列，问你该序列的MEX是多少

思路：

设k是序列的一个数，则存在一个x使得$n\bigoplus{x} = k,0\leq{x}\leq{m}$​

根据异或的自反性

得到$n\bigoplus{k} = x,0\leq{x}\leq{m}$​​，即$n\bigoplus{k}\leq{m}$

而我们需要求的是一个不在该序列中的最小的k满足$n\bigoplus{k}\geq{m}$

从高位到低位进行构造，如果n_i = k_i 则k_i是0

如果n_i =0, k_i = 1, 则k_i = 1

如果n_i = 1,k_i = 0, 则k_i即后面的都是

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod1 1000000007
#define mod2 1000000009
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x, k, m;

int main(){
    cin>>t;
    while (t--) {
        cin>>n>>m;
        ++m;
        k = 0;
        for(int i = 30; i >= 0 && n < m; --i){//如果n>m就跳出了，这里判断的是第三点
            if((n >> i & 1) == (m >> i & 1))continue;//低一点
            else if((m >> i & 1)){//第二点
                k |= 1<<i;
                n |= 1<<i;
            }
        }
        cout<<k<<endl;
    }
    return 0;
}

D. Diane

题目描述：

给你一个数字n，你需要构造出长度为n的字符串s，使得s的所有子串出现的个数都是奇数次

思路

很简单的构造题（这题绝对绝对没有1800，顶多900，放在A题的位置差不多

对于bbbb，出现四次b，三次bb，两次bbb，一次b

对于bbb，出现三次b，两次bb，一次bbb

可以观察得到，上面两个串只需要在中间差一个字符，就能使得所有串出现的次数为奇数，这样一共是偶数个字符

如果是奇数，就再开头加一个不是上述任一一种的字符即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod1 1000000007
#define mod2 1000000009
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x;

int main(){
    scanf("%d", &t);
    while (t--) {
        n = IntRead();
        if(n == 1)printf("b\n");
        else {
            if(n % 2 == 1)printf("c");
            for(int i = 1; i <= n / 2 - 1; ++i)printf("b");
            printf("a");
            for(int i = 1; i <= n / 2; ++i)printf("b");
            printf("\n");
        }
    }
    return 0;
}