15th.Feb.2019
T1
-
呵呵，题解很简单吧，简单吧，单吧，吧。
-
我写的时候快哭了。怎么说，这算是一个性质题，你需要发现冒泡排序的一些性质，这过程中需要用到贪心的思路。一直在想这是不是个很复杂的性质题，猜想这个猜想那个。
-
woc身旁的神犇A掉了，看了看表才不到十分钟吧，压力山大。一个半小时过去，终于发现了性质。如同醍醐灌顶，啊，oi就是这么吸引人的学科。
-
（有些啰嗦下面步入正题）题目给了你一个1~n的排列，问你：按照冒泡排序的方式，需要多少次排序可以让序列变成有序的：
1、不要搭理那个构造排列的方式，没什么卵用，研究大半天发现本题和它没关系。
2、显然有一个n^2的暴力写法（不要觉得没用，先打上再说，可以用来对拍）。
3、然后你发现，假如说当前在第i个位置，然后序列里的数a【i】小于i，那么a【i】想要回到自己的位置，至少需要i-a【i】轮交换。手写几组数据你发现确实如此，我们只需要求一个max{i-a【i】}就好了。
-
代码就不用了吧。。。
T3
- (T2不太会啊，先咕了)
- T3是原题啊，但是并没有美滋滋。因为上回没有订正这道题，所以仍然不是很会。
- 显然，我们不管n，把每一个值都当成一个点，跑单调队列DP，O（M）的算法，20分。
- 但是其实对我们有用的点只有n个，然后我们是要在前面的点里面找一个最优的点来更新当前最优值。
- 本题涉及到的调的代价是（t【i】-t【j】）/d，当然如果余数不为0，还要+1。其实可以转化成，t【i】/d-t【j】/d，不过涉及到向下取整问题。所以我们分类讨论一下，发现当i的余数大于j的余数的时候，我们转化为t【i】/d-t【j】/d+1，否则就是t【i】/d-t【j】/d。
- 我们每次更新状态，是求f【i】=max{f【j】-（t【i】/d-t【j】/d+1）（当然+1或者不+1跟余数有关）}。那我们可以维护一个max f【i】+t【j】/d，这样的话就一定是对当前状态来说最优的。
- 晚上突然觉得好像可以O（n）写，也就是不对余数分类，结果发现脑残了，不讨论余数就无法保证你找到的j是对i来说最优的。
- 所以本题思路就是对余数进行分类，把余数的范围当成线段树区间范围，每次查询最优值进行更新，当然，还需要动态开点。
- 复杂度O（nlogD）。
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+10;
const ll inf=1e15;
ll n,K,M,D,A,t[N],f[N],a[N],rt,tot;ll k[N],b[N];
ll minn[N<<2],ls[N<<2],rs[N<<2];
char buf[1<<15],*fs,*ft;
inline char getc(){
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:* fs++;
}
inline ll read(){
char ch=getc();ll num=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getc();}
while(isdigit(ch)){num=num*10+ch-'0';ch=getc();}
return num*f;
}
inline void update(ll l,ll r,ll x,ll val,ll &o){
if(!o){
o=++tot;
}
if(l==r){
minn[o]=min(minn[o],val);
return ;
}
ll mid=l+r>>1;
if(x<=mid) update(l,mid,x,val,ls[o]);
else update(mid+1,r,x,val,rs[o]);
minn[o]=min(minn[ls[o]],minn[rs[o]]);
}
inline ll query(ll l,ll r,ll L,ll R,ll &rt){
if(!rt) return 1e15;
if(l>=L&&r<=R) return minn[rt];
if(l>r||r<L) return 1e15;
ll mid=l+r>>1;
ll temp=1e15;
if(L<=mid)
temp=min(temp,query(l,mid,L,R,ls[rt]));
if(mid<R)
temp=min(temp,query(mid+1,r,L,R,rs[rt]));
return temp;
}
int main(){
freopen("reading.in","r",stdin);
freopen("reading.out","w",stdout);
K=read(),M=read(),D=read(),A=read(),n=read();
memset(f,0x3f,sizeof(f));
memset(minn,0x3f,sizeof(minn));
for(ll i=1;i<=n;++i) t[i]=read(),a[i]=read();
t[0]=K;t[++n]=M;k[0]=K/D,b[0]=K%D;
//ll x,v,y,k,ans;
ll ans;
for(ll i=1;i<=n;++i){
k[i]=t[i]/D,b[i]=t[i]%D;
}
k[n]=M/D,b[n]=M%D;
update(0,D-1,b[0],-k[0]*A,rt);
for(ll i=1;i<=n;++i){
ans=query(0,D-1,0,b[i]-1,rt);
f[i]=min(f[i],ans+A+k[i]*A-a[i]);
ans=query(0,D-1,b[i],D-1,rt);
f[i]=min(f[i],ans+k[i]*A-a[i]);
update(0,D-1,b[i],f[i]-k[i]*A,rt);
}
printf("%lld\n",-f[n]);
return 0;
}
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。