大鸽子我又回来了
考试经过
看T1，根本不会，值域咋枚举啊。。。思考30min无果，依然不会暴力，跳了
T2觉得不难，等等，50位小数？高。。。精？算了待会再说吧
T3这题目，原题?回忆一波开打，打完发现要对每个都求一遍，傻了，只好写了40pts，发现完全单调很可搞，于是大力推斜率优化，最后调出来小拍了一下，觉得挺稳交了
回来T2，式子不难，60到手跑路。最后莽了一个T4的假做法交了
0+60+40+4=104，T3挂了。。
原来根本不用二分……算斜率的时候没判除数位0，结果出来一堆-nan，整挺好
T1.柱状图
最终答案可以表示成几个绝对值加和的形式，因此可以三分
那么\(O(n)\)枚举加上\(log\)三分，现在问题是怎么快速求出答案
将式子拆开，分别维护\(a_i+i,a_i-i\)的值和数量，开四个树状数组
进行离散化之后在排过序的数组上二分，提前求出每个位置的排名\(rk\)
由于左右不一样，做之前先把右面的都加进去，每次扫到一个点把他从右面删除，统计答案，加入左边，分开维护
复杂度\(nlog^2\),注意MAX要足够大
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
int a[N],n;
struct bit{
int b[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
b[i]+=v;
}
inline int getsum(int p)
{
int s=0;
for(int i=p;i;i-=lowbit(i))
s+=b[i];
return s;
}
inline int get(int l,int r)
{
if(l>r)return 0;
return getsum(r)-getsum(l-1);
}
} tr1, tr2, tr3, tr4;
//size(pi-i) w(pi-i) size(pi+i) w(pi+i)
int c1[N],c2[N],rk1[N],rk2[N];
int cnt1,cnt2,lsh1[N],lsh2[N];
inline int gan(int i,int w)
{
int p=lower_bound(lsh1+1,lsh1+cnt1+1,w-i)-lsh1;
int ans=(w-i)*tr1.get(1,p-1)-tr2.get(1,p-1)+(i-w)*tr1.get(p,cnt1)+tr2.get(p,cnt1);
p=lower_bound(lsh2+1,lsh2+cnt2+1,w+i)-lsh2;
ans+=(w+i)*tr3.get(1,p-1)-tr4.get(1,p-1)+(-w-i)*tr3.get(p,cnt2)+tr4.get(p,cnt2);
return ans+abs(w-a[i]);
}
signed main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)c1[i]=a[i]-i,c2[i]=a[i]+i;
for(int i=1;i<=n;i++)lsh1[i]=c1[i],lsh2[i]=c2[i];
sort(lsh1+1,lsh1+n+1);sort(lsh2+1,lsh2+n+1);
cnt1=unique(lsh1+1,lsh1+n+1)-lsh1-1;
cnt2=unique(lsh2+1,lsh2+n+1)-lsh2-1;
for(int i=1;i<=n;i++)rk1[i]=lower_bound(lsh1+1,lsh1+cnt1+1,c1[i])-lsh1;
for(int i=1;i<=n;i++)rk2[i]=lower_bound(lsh2+1,lsh2+cnt2+1,c2[i])-lsh2;
for(int i=1;i<=n;i++)tr3.add(rk2[i],1),tr4.add(rk2[i],c2[i]);
int ans=1e16;
for(int i=1;i<=n;i++)
{
tr3.add(rk2[i],-1);tr4.add(rk2[i],-c2[i]);
int l=max(i,n-i),r=1e10;
while(r-l>5)
{
int lmid=l+(r-l)/3,rmid=l+2*(r-l)/3;
int anl=gan(i,lmid),anr=gan(i,rmid);
if(anl>=anr)l=lmid;
else r=rmid;
}
for(int j=l;j<=r;j++)ans=min(ans,gan(i,j));
tr1.add(rk1[i],1);tr2.add(rk1[i],c1[i]);
}
cout<<ans<<endl;
return 0;
}
T2.应急棍
找规律模拟，后面的高精拉倒吧
60pts
#include <bits/stdc++.h>
using namespace std;
#define int long long
int lim[35]={0,4,9,25,81,289,1089,4225,16641,66049,263169,1050625,4198401,16785409,67125249,268468225,1073807361,4295098369,17180131329,68720001025,
274878955521,1099513724929,4398050705409,17592194433025,70368760954881,281475010265089,1125899973951489,4503599761588225,18014398777917441,
72057594574798849,288230377225453569,1152921506754330625};
int ga[35]={0,2,3,5,9,17,33,65,129,257,513,1025,2049,4097,8193,16385,32769,65537,131073,262145,524289,1048577,2097153,4194305,
8388609,16777217,33554433,67108865,134217729,268435457,536870913,1073741825};
inline int ganp(int x,int p)
{
if(x%p)return x/p+1;
return x/p;
}
inline int ganmod(int x,int mod)
{
if(x%mod)return x%mod;
return mod;
}
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int c,t;cin>>c>>t;
int l;cin>>l;
for(int i=1;i<=t;i++)
{
int n;scanf("%lld",&n);
if(n==1){printf("0 0\n");continue;}
if(n==2){printf("%lld %lld\n",l,l);continue;}
if(n==3){printf("0 %lld\n",l);continue;}
if(n==4){printf("%lld 0\n",l);continue;}
int pp,gg;
for(int j=1;j<=31;j++)if(lim[j]>n){pp=j;gg=ga[j];break;}
double d=(double)l/(double)(gg-1);
int aa=n-lim[pp-1],lm=(ga[pp-1]-1)*(ga[pp-1]-1);
if(!aa)
{
printf("%.12lf %.12lf\n",(double)l,(double)(l-2*d));
continue;
}
if(aa&&aa<=lm)
{
int h=ganp(aa,(ga[pp-1]-1)),s=ganmod(aa,ga[pp-1]-1);
double x=d*h+d*(h-1),y=d*s+d*(s-1);
printf("%.12lf %.12lf\n",x,y);
}
else
{
aa-=lm;int sb=ga[pp-1]-1;
int t1=ganp(aa,sb+sb+1),t2=ganmod(aa,sb+sb+1);
if(t2<=sb)
{
double x=(t1-1)*2*d,y=t2*d+(t2-1)*d;
printf("%.12lf %.12lf\n",x,y);
}
else
{
double x=(t1-1)*2*d+d,y=(t2-sb-1)*2*d;
printf("%.12lf %.12lf\n",x,y);
}
}
}
return 0;
}
T3.擒敌拳
原题是只在最后求答案，但现在要对每个位置求一遍
正解李超树，不过可以斜率优化，似乎复杂度更优
设每一个位置他能成为最小值的区间为\(l_i,r_i\)，这个经典单调栈
首先可以写出式子\(ans_i=\max (a_j \times(i-l_j+1)),r_j>=i\)
如果没有后面的限制，即完全单调，直接能在\(O(n)\)内解决，即部分分
如果加上限制，变成了一个偏序问题，那么应该用CDQ或者以限制为下标开线段树
我用了后者，每次区间插入，单点查询（一条链，永久化），每个节点维护凸包
还有deque很费内存，实测\(N=10^5\)的时候已经248M了，应该使用vector，并记录队首元素位置
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200050;
int a[N],l[N],rr[N],b[N];
stack <int> s;
struct node{
int l,r;
vector <int> q;
int ll=0;
}tr[4*N];
void build(int id,int l,int r)
{
tr[id].l=l;tr[id].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
inline double get(int x,int y)
{
if(a[x]==a[y])return 1e16;
return (double)(b[y]-b[x])/(double)(a[y]-a[x]);
}
void add(int id,int l,int r,int i)
{
if(l<=tr[id].l&&r>=tr[id].r)
{
while(tr[id].q.size()-tr[id].ll>0&&tr[id].q.back()>rr[i])tr[id].q.pop_back();
while(tr[id].q.size()-tr[id].ll>=2&&get(tr[id].q[tr[id].q.size()-2],tr[id].q.back())>get(tr[id].q.back(),i))tr[id].q.pop_back();
tr[id].q.push_back(i);return;
}
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid)add(id*2,l,r,i);
else if(l>mid)add(id*2+1,l,r,i);
else add(id*2,l,mid,i),add(id*2+1,mid+1,r,i);
}
int get(int id,int p,int i)
{
int ans=0;
while(tr[id].q.size()-tr[id].ll>=2&&get(tr[id].q[tr[id].ll],tr[id].q[tr[id].ll+1])<i)tr[id].ll++;
if(tr[id].q.size()-tr[id].ll==0)ans=0;
else if(tr[id].q.size()-tr[id].ll==1)ans=a[tr[id].q[tr[id].ll]]*i-b[tr[id].q[tr[id].ll]];
else ans=max(a[tr[id].q[tr[id].ll]]*i-b[tr[id].q[tr[id].ll]],a[tr[id].q[tr[id].ll+1]]*i-b[tr[id].q[tr[id].ll+1]]);
if(tr[id].l==tr[id].r)return ans;
int mid=(tr[id].l+tr[id].r)>>1;
if(p<=mid)return max(ans,get(id*2,p,i));
else return max(ans,get(id*2+1,p,i));
}
signed main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
int n;cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n+1;i++)
{
while(s.size()&&a[s.top()]>a[i])
{
rr[s.top()]=i-1;
s.pop();
}
s.push(i);
}
for(int i=n;i>=0;i--)
{
while(s.size()&&a[s.top()]>a[i])
{
l[s.top()]=i+1;
s.pop();
}
s.push(i);
}
for(int i=1;i<=n;i++)b[i]=a[i]*(l[i]-1);
int ans=0;build(1,1,n);
for(int i=1;i<=n;i++)
{
add(1,l[i],rr[i],i);
ans=max(ans,get(1,i,i));
printf("%lld ",ans);
}
return 0;
}
T4.边数
还没弄明白，咕了
考试总结
灵活选择策略，应该对题型有敏感性，大致要想到正确的方向，至少暴力还是要打
根据情况决定是否肝正解，评估一下成功的概率和收益，如果要的话先保证暴力都有再说