游记
理所当然VP了
秒速过A，打B犯了一天的傻逼看错条件
理所当然的只过了一道愉快开启改题生活
当然改题也挺那啥的
题解
A
挺简单的
找\(X,Y\)的最小值，即找到长方形可框住的最大的正方形
直接输出此正方形的顶点坐标即可
证明考虑超出此正方形的点在旋转平移以后都会超出长方形范围
B
如果是只能白点染成黑点，
那其实只能是\(A\)中元素两两一组且不重复出现
那其实要求的就是所有配对元素两两之间间隔最大值
考虑到如果出现不相邻的元素配对一定可以通过换成相邻元素配对来减小最大间隔
所以肯定是相邻配对
偶数的话就是\((2k-1,2k)\)这样，
否则会出现两个元素不满足最优决策落单，就会涂两个\(A\)以外的格子
奇数的话就是随便删一个元素，看看剩下\(n-1\)个元素两两配对最大值
枚举每一个删掉的元素，再按照偶数情况解决，时间复杂度\(O(n^2)\)
其实删一个元素，只有\((i-1,i+1)\)动了，其余的不动
可以直接维护前后缀，看看会发生什么变化
如果删一个奇数，配对情况还是前后缀和维护范围以内
如果删偶数，就需要用上下一个偶数的信息加上中间缝隙维护
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int o=222222;
int t,n,k,ans,a[o],f[o],s[o];
void in(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
}
void work(){
if(n==1){
ans=1;
return;
}
if(n%2){
ans=1e18;
for(int i=2;i<=n;i+=2)
f[i]=max(f[i-2],a[i]-a[i-1]);//前缀，偶数
for(int i=n-1;i>=1;i-=2)
s[i]=max(s[i+2],a[i+1]-a[i]);//后缀，偶数头上
for(int i=1,now=0;i<=n;i++){
now=0;
if(i%2)now=max(f[i-1],s[i+1]);
else{
// printf("i=%d,%d %d %d",i,a[i+1]-a[i-1],f[i-2],s[i+2]);
now=max(now,a[i+1]-a[i-1]);
now=max(now,f[i-2]);
now=max(now,s[i+2]);
}
//printf("now=%d i=%d\n",now,i);
ans=min(ans,now);
}
}
else{
for(int i=1;i<=n/2;i++)ans=max(a[2*i]-a[2*i-1],ans);
}
}
void out(){
cout<<ans<<endl;
}
void clear(){
for(int i=1;i<=n;i++){
f[i]=0,s[i]=0,a[i]=0;
}
n=ans=0;
}
#undef int
int main(){
cin>>t;
while(t--){
in();
work();
out();
clear();
}
return 0;
}
C
如果可以的话，能分开多买几次就不要集中买
否则可能会亏一次免费名额
其次，如果可以的话，用尽可能便宜的东西和贵的东西组一队拿下
倒序扫整个串，这样比较简单，出去肯定回不来了
对于\(s_i=0\)的情况，因为能多买就多买，买的那天的货物才会优惠，
所以\(i\)不可能会沾到优惠，直接加到答案里就行
否则，\(s_i=1\)的情况，既可能是直接免费拿下，也还可能是单着不急着配对
维护一个deque，把\(i\)扔到队头
如果碰上一个\(s_j=0\)把队尾最大的那个\(i\)出去买下
（队列空那就是没办法了）
如果最后剩下，那就是队头配队尾
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int o=222222*2;
int T,n,ans,f[o];
char s[o];
deque<int>c;
int sum(int l,int r){
return (l+r)*(r-l+1)/2;
}
void in(){
cin>>n;
scanf("%s",s+1);
}
void work(){
for(int i=n;i>=1;i--){
if(s[i]=='1')c.push_front(i);
else{
if(!c.empty())c.pop_back();
ans+=i;
}
}
while(!c.empty()){
if(c.size()==1){
ans+=c.front();
break;
}
ans+=c.front();
c.pop_front();
c.pop_back();
}
}
void out(){
cout<<ans<<'\n';
}
void clear(){
for(int i=1;i<=n;i++)s[i]=0;
n=0,ans=0;
c.clear();
}
#undef int
int main(){
cin>>T;
while(T--){
in();
work();
out();
clear();
}
return 0;
}
D
这个\(D\)就是无脑爆拆数学题了
首先前缀和惯例就是拆成\((1,l-1)\)和\((1,r)\)两部分做差
然后考虑\((1,x)\)的部分
由于\(\sum\limits^{x}_{i=1}b_i\)这个形式不太好做
我们倾向于拆成整的\(\sum\limits^{a}_{i=1}\sum\limits^{n}_{j=i}S(i,j)\)和零的\(\sum\limits^{c}_{i=a+1}S(a+1,i)\)两部分
发现第一部分的第二层累加和第二部分累加相似，
所以用前缀和方式预处理第一部分的第一层累加，从而预处理第一部分
接下来考虑第二部分，还是前缀和化法
（对于这一部分，\(x\)和\(y\)都是参数，视情况填入\(1\)或\(n\)或其他）
\(\sum\limits^{y}_{i=x}S(x,i)\\=\sum\limits^{y}_{i=x}（s_{i}-s_{x-1}）\\=(\sum\limits^{y}_{i=x}s_i)-(y-x+1)*s_{x-1}\)
再来个数组\(T\)维护\(s\)的前缀和，也就是\(T_{y}-T_{x-1}=(\sum\limits^{y}_{i=x}s_i)\)即可
剩下的就是填参数的事了
点击查看代码