@KirinBill
2018-03-08T23:14:49.000000Z
字数 5872
阅读 1324
套题
目录
#include <cstdio>
#include <algorithm>
using std::max;
const int MAXN=30005;
const long long OFFSET=1e12;
int n,k,r;
long long sufa[MAXN],sufb[MAXN],sufc[MAXN];
class CMT{
private:
int cnt;
int rt[MAXN];
struct node{int ls,rs,cnt;}d[MAXN*45];
int copy_nd(int u){
d[++cnt]=d[u];
return cnt;
}
void ist(int pre,int &now,long long l,long long r,long long val){
now=copy_nd(pre);
++d[now].cnt;
if(l==r) return;
long long mid=(l+r)/2;
if(val<=mid) ist(d[pre].ls,d[now].ls,l,mid,val);
else ist(d[pre].rs,d[now].rs,mid+1,r,val);
}
int lt_cnt(int pre,int now,long long l,long long r,long long val){
if(r<val) return d[now].cnt-d[pre].cnt;
long long mid=(l+r)/2;
int ret=lt_cnt(d[pre].ls,d[now].ls,l,mid,val);
if(val>mid+1) ret+=lt_cnt(d[pre].rs,d[now].rs,mid+1,r,val);
return ret;
}
public:
void ist(int pre,int now,long long val){ist(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
int lt_cnt(int pre,int now,long long val){return lt_cnt(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
}T1,T2;
inline void prepare(){
for(int i=1;i<=n;++i){
sufc[i]-=sufb[i];
sufb[i]-=sufa[i];
}
for(int i=n-1;i;--i){
sufa[i]+=sufa[i+1];
sufb[i]+=sufb[i+1];
sufc[i]+=sufc[i+1];
}
for(int i=1,lim=n-r+1;i<=lim;++i){
T1.ist(i-1,i,sufb[i]-sufb[i+r]);
T2.ist(i-1,i,sufb[i]-sufc[i+r]);
}
}
//不重叠
inline int cal1(long long mid){
int ret=0;
mid-=sufa[1];
for(int i=r+1,lim=n-r+1;i<=lim;++i)
ret+=T1.lt_cnt(0,i-r,mid-sufb[i]+sufb[i+r]);
return ret;
}
//重叠
inline int cal2(long long mid){
int ret=0;
mid-=sufa[1];
for(int i=2,lim=n-r+1;i<=lim;++i)
ret+=T2.lt_cnt(max(0,i-r),i-1,mid+sufb[i+r]-sufc[i]);
return ret;
}
inline int rank(long long mid){
return cal1(mid)+cal2(mid);
}
inline long long bin_chop(long long l,long long r){
long long mid;
while(l<=r){
mid=l+r>>1;
if(rank(mid)<k) l=mid+1;
else r=mid-1;
}
return r;
}
int main(){
freopen("fst.in","r",stdin);
freopen("fst.out","w",stdout);
scanf("%d%d%d",&n,&r,&k);
long long minans=0;
for(int i=1;i<=n;++i){
scanf("%d",&sufa[i]);
minans+=sufa[i];
}
for(int i=1;i<=n;++i)
scanf("%d",&sufb[i]);
long long maxans=0;
for(int i=1;i<=n;++i){
scanf("%d",&sufc[i]);
maxans+=sufc[i];
}
prepare();
printf("%lld",bin_chop(minans,maxans));
return 0;
}
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <cstring>
#include <climits>
using std::sort;
using std::min;
using std::max;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=3005,MAXM=3005;
int n,m,k;
int he[MAXN],w[MAXM];
struct line{int to,nex,w;}ed[MAXM<<1];
struct node{
int id;
long long dis;
node(int _id=0,long long _dis=0):id(_id),dis(_dis){}
bool operator >(const node &that)const{
return dis>that.dis;
}
};
inline void addE(int u,int v,int w){
static int cnt;
ed[++cnt]=(line){v,he[u],w};
he[u]=cnt;
}
inline long long Dijkstra(int dta){
static long long dis[MAXN];
static bool use[MAXN];
static priority_queue<node,vector<node>,greater<node> > hp;
memset(dis,0x7f,sizeof(dis));
memset(use,false,sizeof(use));
dis[1]=0;
hp.push(node(1,0));
int u;
long long d;
while(hp.size()){
u=hp.top().id;
hp.pop();
if(use[u]) continue;
use[u]=true;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to,d=dis[u]+max(0,ed[i].w-dta);
if(dis[v]>d){
dis[v]=d;
hp.push(node(v,d));
}
}
}
return dis[n];
}
inline long long solve(){
long long ret=LLONG_MAX;
for(int i=0;i<=m;++i)
ret=min(ret,Dijkstra(w[i])+(long long)k*w[i]);
return ret;
}
int main(){
freopen("skd.in","r",stdin);
freopen("skd.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d%d",&u,&v,&w[i]);
addE(u,v,w[i]),addE(v,u,w[i]);
}
printf("%lld",solve());
return 0;
}
spj
,他求的貌似是字典序最小解,我的不是,现在也没看我WA的那几个是不是合法解,有空再说吧;先不放了,改完再说。