雅礼集训2019 Day1
three
bzoj原题
就是一道状态很妙的长链剖分优化。
permutation
毒瘤题。
考试的时候只写了的部分分。
下来直接题解了。
勉强看懂大概是这样的。
首先显然可以将升序排序,然后当数组降序排列的时候显然是最小的(排序不等式)
然后现在我们将问题转化为数组不动,只改变数组的顺序。
现在我们用类似求短路的方法,从最小值开始拓展,每次取当前最优解再次拓展一直到前大都取完。
我们如果要将一个排列变成另一个价值稍微大一点的排列,最优情况相当于对一个区间进行一次循环右移操作,代价是。
我们记表示一次将区间这段区间进行一次循环右移,表示其代价,显然有,我们只需要对每个还未确定的维护其这个属性。
然后有两种新的扩展:
- 执行完之后的新扩展,这会产生一个新的A序列,此时所有的剩下未固定位置len全部重新设为1,计算delta。
- 将位置的修改为,并且计算新的 。
于是可以用可持久化线段树来维护。
代码比较有技巧性(貌似可以可持久化博主咕掉了)
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int N=1e5+5,M=1e7+5;
const ll inf=1e17;
int n,k;
ll a[N];
struct node{int pos,len,siz;ll det;node(int pos=0,int len=0,int siz=0,ll det=inf):pos(pos),len(len),siz(siz),det(det){}};
namespace sgt{
#define lc (son[p][0])
#define rc (son[p][1])
#define mid (l+r>>1)
int son[M][2],tot=0;
node T[M];
inline void pushup(int p){
T[p].siz=T[lc].siz+T[rc].siz;
if(lc&&T[lc].det<T[rc].det)T[p].pos=T[lc].pos,T[p].len=T[lc].len,T[p].det=T[lc].det;
else T[p].pos=T[rc].pos+T[lc].siz,T[p].len=T[rc].len,T[p].det=T[rc].det;
}
inline void build(int&p,int l,int r){
p=++tot;
if(l==r){T[p]=(node){1,1,1,l^1?a[l]-a[l-1]:inf};return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void add(int&p,int o,int l,int r,int k,ll v){
T[p=++tot]=T[o],lc=son[o][0],rc=son[o][1];
if(l==r){++T[p].len,T[p].det+=v;return;}
k<=T[lc].siz?add(lc,son[o][0],l,mid,k,v):add(rc,son[o][1],mid+1,r,k-T[lc].siz,v);
pushup(p);
}
inline void delet(int&p,int o,int l,int r,int k){
if(!k)return;
T[p=++tot]=T[o],lc=son[o][0],rc=son[o][1];
if(k<T[lc].siz)delet(lc,son[o][0],l,mid,k);
else delet(rc,son[o][1],mid+1,r,k-T[lc].siz),lc=0;
pushup(p);
}
inline void update(int&p,int o,int l,int r,int k,int v1,ll v2){
T[p=++tot]=T[o],lc=son[o][0],rc=son[o][1];
if(l==r){T[p].siz=v1,T[p].det=v2;return;}
k<=T[lc].siz?update(lc,son[o][0],l,mid,k,v1,v2):update(rc,son[o][1],mid+1,r,k-T[lc].siz,v1,v2);
pushup(p);
}
inline ll query(int p,int l,int r,int k){return l==r?a[l]:(k<=T[lc].siz?query(lc,l,mid,k):query(rc,mid+1,r,k-T[lc].siz));}
#undef lc
#undef rc
#undef mid
}
struct sta{int st,ed;ll ans;friend inline bool operator>(const sta&a,const sta&b){return a.ans+sgt::T[a.ed].det>b.ans+sgt::T[b.ed].det;}};
priority_queue<sta,vector<sta>,greater<sta> >q;
inline void expand(sta u){
int nw=u.st,pos=sgt::T[u.ed].pos,len=sgt::T[u.ed].len;
if(pos+1<=sgt::T[nw].siz)sgt::update(nw,nw,1,n,pos+1,1,sgt::query(nw,1,n,pos+1)-sgt::query(nw,1,n,pos-1));
sgt::update(nw,nw,1,n,pos,0,inf);
if(pos-len>1)sgt::delet(nw,nw,1,n,pos-len-1);
sgt::update(nw,nw,1,n,1,1,inf);
q.push((sta){nw,nw,u.ans+sgt::T[u.ed].det});
nw=u.ed;
if(pos-len>1)sgt::add(nw,nw,1,n,pos,sgt::query(nw,1,n,pos)-sgt::query(nw,1,n,pos-len-1));
else sgt::update(nw,nw,1,n,pos,1,inf);
q.push((sta){u.st,nw,u.ans});
}
int main(){
n=read(),k=read();
for(ri i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
ll sum=0;
for(ri i=1;i<=n;++i)sum+=(ll)a[i]*(n-i+1);
cout<<sum<<'\n';
sta u;
sgt::build(u.st,1,n);
u.ed=u.st,u.ans=sum;
q.push(u);
for(--k;k;--k){
u=q.top();
q.pop();
cout<<u.ans+sgt::T[u.ed].det<<'\n';
expand(u);
}
return 0;
}
math
高考与的结合?
首先看出这题是一个划分问题可以用搞(然而之前考试写背包+优化爆精度了233333)
我们定义将个划分成个的总贡献为。
由于代价的计算是一种诡异的形式,因此我们只用看以下两种划分的转移。
- 个中有一个是,则
- 没有一个是,那么考虑对之前某一个加上一求出贡献,后面会乘一坨奇奇怪怪的系数,我们来算一下。
当前这个新的的贡献是
由于,注意到前面的对应了,因此只需要把后面那一坨转成可以与对应的形式即可。
我们继续做三角函数恒等变形:
这样相当于对应了一种转移:
于是
可以矩阵快速幂优化。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
#define gc getchar
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
#undef gc
}
const int N=70;
int lim;
struct Mat{
double a[N][N];
Mat(double x=0){memset(a,0,sizeof(a));for(ri i=1;i<=lim;++i)a[i][i]=x;}
friend inline Mat operator*(const Mat&a,const Mat&b){
Mat ret;
for(ri i=1;i<=lim;++i)for(ri k=1;k<=lim;++k)if(a.a[i][k])
for(ri j=1;j<=lim;++j)ret.a[i][j]+=a.a[i][k]*b.a[k][j];
return ret;
}
}ret,trans;
int n,m;
double x,t1,t2;
inline void print(double x){
if(x<0)putchar('-'),x=-x;
else putchar('+');
while(x<1)x*=10;
while(x>10)x/=10;
cout<<(int)x<<'\n';
}
int main(){
for(ri tt=read();tt;--tt){
lim=(m=read())<<1,n=read(),scanf("%lf",&x);
memset(ret.a,0,sizeof(ret.a));
memset(trans.a,0,sizeof(trans.a));
t1=sin(x),t2=2.0*cos(x);
ret.a[1][1]=t1,ret.a[1][m+1]=sin(2*x),ret.a[1][m+2]=t1*t1;
for(ri i=m+1;i<=lim;++i){
trans.a[i-m][i]=-1;
trans.a[i][i-m]=1;
trans.a[i][i]=t2;
if(i^lim)trans.a[i][i+1]=t1;
}
for(n--;n;n>>=1,trans=trans*trans)if(n&1)ret=ret*trans;
print(ret.a[1][m]);
}
return 0;
}