本场链接:Codeforces Round #735 (Div. 2)

A. Cherry

答案一定是相邻的两个数中得到的:假设有三个数\((a,b,c)\),保证有\(a \leq b \leq c\)则权为\(a * c\),而事实上\(b * c\)更大.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 1e5+7;
int a[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        forn(i,1,n) scanf("%d",&a[i]);
        ll res = 0;
        forn(i,1,n - 1) res = max(res,a[i] * 1ll * a[i + 1]);
        printf("%lld\n",res);
    }

    return 0;
}

B. Cobb

猜想当\(i,j\)偏大的时候才是答案,否则至少不劣.\(k\)最大为\(100\)是一个非常诡异的条件,这说明后者项最大最小产生的影响不过\(n*k\),远不及\(i*j\)产生的影响:所以可以只考虑后面\(k\)个元素.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 1e5+7;
int a[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,k;scanf("%d%d",&n,&k);
        forn(i,1,n) scanf("%d",&a[i]);
        ll res = -1e18;
        forn(i,max(n - 100,1),n)   forn(j,max(n - 100,1),n)   if(i != j)    res = max(res,1ll * i * j - k * (a[i] | a[j]));
        printf("%lld\n",res);
    }
    return 0;
}

C. Mikasa

原题等价于:把区间\([0,m]\)所有数异或上一个常数\(n\),区间会拆分成若干个新的区间,求其MEX.

把所有原有的数放在一颗值域线段树上(按位分割左右两个儿子),那么从上到下,若\(n\)的自高向低第\(i\)位为\(1\),则会导致第\(i\)层所有点的左右儿子发生交换(例如\([0,1]\)交换到\([2,3]\)).而若一个点下面已经是满的形态,则内部不管怎么交换都不会有影响,此时可以直接退出.其他情况找出所在的区间的左右端点即可:因为当前已知的是区间内两个已知的元素,左端点等于\(l \& r\),右端点等于\(l | r\),拆成事件维护,找到第一个覆盖数为\(0\)的点即MEX.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define l first
#define r second

vector<pii> events;

void grange(int tl,int tr,int ql,int qr,int w)
{
    if(tl >= ql && tr <= qr)
    {
        int l = tl ^ w,r = tr ^ w;
        events.push_back({l & r,1});
        events.push_back({(l | r) + 1,-1});
        return ;
    }
    int mid = tl + tr >> 1;
    if(ql <= mid)   grange(tl,mid,ql,qr,w);
    if(qr > mid)    grange(mid + 1,tr,ql,qr,w);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        events.clear();
        int n,m;scanf("%d%d",&n,&m);
        grange(0,(1 << 30) - 1,0,m,n);
        sort(events.begin(),events.end());
        int cur = 0,cnt = 0,res = m + 1;
        for(auto& e : events)
        {
            if(e.l > cur && cnt == 0)
            {
                res = cur;
                break;
            }
            cnt += e.r;
            cur = e.l;
        }
        printf("%d\n",res);
    }

    return 0;
}

D. Diane

对于一个长度为\(k\)且\(k\)为奇数的串\(aaaa...aaa\)来说,所有长度为奇数的出现奇数次,长度为偶数的出现偶数次.对于\(k-1\)来说恰好相反.那么,如果塞一个长度为\(k\)和一个长度为\(k-1\)的串,一定能保证各个子串的数量是奇数,如果取\(k = n / 2(↓)\),那么就只会剩下\(1\)或\(2\)个位置,直接塞入\(b\)或\(bc\)即可完成构造.

注意特判\(n=1\).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        if(n == 1)  
        {
            puts("a");
            continue;
        }
        int k = n / 2;
        forn(i,1,k) printf("a");
        printf("b");if(n % 2)   printf("c");
        forn(i,1,k - 1) printf("a");
        puts("");
    }
    return 0;
}