A
发现长度为 \(2\) 的一定是最好的。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
#define int long long
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
signed main(){
int T; cin>>T;
while(T--){
int n; cin>>n;
int a=0, b=0, res=0;
rep(i,1,n){
a=b; cin>>b;
res=max(res, a*b);
}
cout<<res<<endl;
}
return 0;
}
B
暴力
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=3e5+5;
int w[N];
int main(){
int T; cin>>T;
while(T--){
int n, k; read(n), read(k);
rep(i,1,n) read(w[i]);
ll res=-INF;
rep(i, max(1, n-2000), n) rep(j, i+1, n){
res=max(res, 1LL*i*j-1LL*k*(w[i]|w[j]));
}
cout<<res<<endl;
}
return 0;
}
C
什么样的数 \(k\) 一定会出现在序列 \(n\oplus 0 ... n\oplus m\) 中？
换句话说，就是 \(k = n\oplus x\)，其中 \(x\in [0,m]\)。
进一步得到应有 \(n\oplus k \leq m\)，这样的 \(k\) 一定会出现在序列中。
我们的目标是找到一个最小的 \(k\) 使得 \(n\oplus k \geq m+1\)。
从而转化为一个经典问题：给出 \(a, c\) 求最小的 \(b\) 使得： \(a \oplus b \geq c\)
#pragma GCC optimize("O3")
#include<bitsdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
int main(){
int T; cin>>T;
while(T--){
int n, m; read(n), read(m);
int a=n, b=0, c=m+1;
dwn(i,30,0){
int x=a>>i&1, y=c>>i&1;
if(y && !x) b+=(1<<i);
if((a^b)>=c) break;
}
cout<<b<<endl;
}
return 0;
}
D
构造，就在中间插个 b，然后如果是奇数就在尾部插个 c，其它全部选 a，见代码：
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=1e5+5;
char res[N];
int main(){
int T; cin>>T;
while(T--){
int n; read(n);
rep(i,1,n){
res[i]=‘a‘;
if(i==(n+1)/2) res[i]=‘b‘;
}
if(n&1) res[n]=‘c‘;
rep(i,1,n) cout<<res[i];
cout<<endl;
}
return 0;
}