本场链接: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
",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
",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
",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;
}