Codeforces Round #735 (Div. 2) 题解
只有 ABCD 的题解，E 不会。
比赛地址：https://codeforces.com/contest/1554。
只有 ABCD 的题解，E 不会。
A
答案是 \(\max_i\{a_ia_{i+1}\}\)。证明：（反证）如果我们取 \(a_i,a_{i+1},a_{i+2}\) 作为答案，那么取这三个数中最大的两个数作为答案一定更优。
typedef long long ll;
const int N=3e5;
int n,a[N+10];
void mian(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
ll ans=0;
for(int i=1;i<n;i++)
ans=std::max(ans,1LL*a[i]*a[i+1]);
printf("%lld\n",ans);
}
B
当 \(i,j\) 很大时，\(i\cdot j\) 是 \(\mathcal O(n^2)\) 级别的，而 \(k\cdot (a_i\operatorname{OR}a_j)\) 是 \(\mathcal O(100n)\) 级别的，所以只枚举后面几项即可。
typedef long long ll;
const int N=1e5;
int n,k,a[N+10];
void mian(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
ll ans=-ll(1e18);
for(int i=std::max(1,n-140);i<=n;i++)
for(int j=i+1;j<=n;j++)
ans=std::max(ans,1LL*i*j-1LL*k*(a[i]|a[j]));
printf("%lld\n",ans);
}
C
结论：当 \(i\) 取遍 \(0\sim 2^k-1,k\in\mathbb N\) 中的所有数时，\(n\oplus i\) 的值一定是一个连续的区间。
所以我们遍历 \(m\) 在二进制下的每一位，如果第 \(i\) 位是 \(1\)，那么我们就把 \(0\sim 2^i-1\) 所对应的连续区间搞出来，最后把这些区间合并即可。
代码非常难看：
void mian(){
int n,m;
scanf("%d%d",&n,&m);
std::pair<int,int> a[40];
for(int i=0;i<=35;i++)a[i].first=a[i].second=0x3f3f3f3f;
int ans=0,now=0; // now 表示只考虑第 i 位和比它高的位时 n xor m 的值
for(int i=30;i>=0;i--){
if((m>>i)&1)
a[i].first=now|(n&(1<<i)),a[i].second=now|(n&(1<<i))|(((1<<i)-1));
now|=(n&(1<<i))^(((m>>i)&1)<<i);
}
a[31].first=now,a[31].second=now;
std::sort(a,a+35);
if(a[0].first>0)puts("0");
else{
for(int i=1;i<=30;i++)
if(a[i-1].second!=a[i].first-1){
printf("%d\n",a[i-1].second+1);
break;
}
}
}
D
如果 \(n\) 是偶数，那么答案为：\(\underbrace{\texttt{aa}\cdots\texttt{a}}_{\frac n2-1\ \text{times}}\!\texttt{b}\underbrace{\texttt{aa}\cdots\texttt{a}}_{\frac n2\ \text{times}}\)。
如果 \(n\) 是奇数，那么答案为：\(\underbrace{\texttt{aa}\cdots\texttt{a}}_{\left\lfloor\frac n2\right\rfloor-1\ \text{times}}\!\!\!\texttt{bc}\underbrace{\texttt{aa}\cdots\texttt{a}}_{\left\lfloor\frac n2\right\rfloor\ \text{times}}\)。
void mian(){
int n;
scanf("%d",&n);
if(n==1)puts("a");
else if(n&1){
for(int i=1;i<=(n-2)/2;i++)
printf("a");
printf("bc");
for(int i=1;i<=(n-2)/2+1;i++)
printf("a");
puts("");
}
else{
for(int i=1;i<=(n-1)/2;i++)
printf("a");
printf("b");
for(int i=1;i<=n/2;i++)
printf("a");
puts("");
}
}