社区讨论

蒟蒻求助

hhighkj
P5892 [IOI 2014] holiday 假期参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m34jwlhw
此快照首次捕获于
2024/11/05 22:34
去年
此快照最后确认于
2024/11/06 12:54
去年
查看原帖
此题有两种情况一种是向右走折回来一种是向左走再折回来，但是我实现用了一种很神奇的方法过了，但是我将数组 reverse 之后再重新跑一遍却没过，有无大佬帮忙解答？
CPP
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=1e5+10,M=1e9;
int rt[N],idx,n,s,d;
struct node{
	int l,r;
	int cnt,sum;
}tr[N<<5];
void up(int x) {
	tr[x].cnt=tr[tr[x].l].cnt+tr[tr[x].r].cnt;
	tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum;
}
int res,b[N];
int modify(int u,int l,int r,int k) {
	int p=++idx;
	tr[p]=tr[u];
	if(l==r) {
		tr[p].cnt++;
		tr[p].sum+=b[l];
		return p;
	}
	int mid=l+r>>1;
	if(mid>=k) tr[p].l=modify(tr[p].l,l,mid,k);
	else tr[p].r=modify(tr[p].r,mid+1,r,k);
	up(p);
	return p;
}
int Ans(int u,int lst,int l,int r,int k) {
	if(l==r) {
		return b[l]*min(tr[u].cnt-tr[lst].cnt,k);
	}
	int mid=l+r>>1;
	if(tr[tr[u].r].cnt-tr[tr[lst].r].cnt>=k) return Ans(tr[u].r,tr[lst].r,mid+1,r,k);
	return tr[tr[u].r].sum-tr[tr[lst].r].sum+Ans(tr[u].l,tr[lst].l,l,mid,k-(tr[tr[u].r].cnt-tr[tr[lst].r].cnt));
}
void get(int l,int r,int ql,int qr) {
	if(l>r) return;
	int mid=l+r>>1;
	int R=min(qr,mid);
	int pos=false,now=false;
	rep(i,ql,R) {
		int ll=i,rr=mid;
		int dis=min(rr-s,s-ll)+rr-ll;
		if(dis>d) continue;
		int yu=d-dis,kk=Ans(rt[rr],rt[ll-1],1,n,yu);
		if(kk>=now) {
			pos=i;
			now=kk;
		}
	}
	if(pos==0) return;
	res=max(res,now);
	get(l,mid-1,ql,pos);
	get(mid+1,r,pos,qr);
}
int a[N];
void solve() {
	in(n),in(s),in(d);
	s++;
	rep(i,1,n) {
		in(a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int mm=unique(b+1,b+1+n)-b-1;
	rep(i,1,n) {
		rt[i]=rt[i-1];
		a[i]=lower_bound(b+1,b+1+mm,a[i])-b;
		rt[i]=modify(rt[i],1,n,a[i]);
	}
	get(s,n,1,s);
	printf("%lld\n",res);
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}
上面为神奇方法。
CPP
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=1e5+10,M=1e9;
int rt[N],idx,n,s,d;
struct node{
	int l,r;
	int cnt,sum;
}tr[N<<5];
void up(int x) {
	tr[x].cnt=tr[tr[x].l].cnt+tr[tr[x].r].cnt;
	tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum;
}
int res,b[N];
int modify(int u,int l,int r,int k) {
	int p=++idx;
	tr[p]=tr[u];
	if(l==r) {
		tr[p].cnt++;
		tr[p].sum+=b[l];
		return p;
	}
	int mid=l+r>>1;
	if(mid>=k) tr[p].l=modify(tr[p].l,l,mid,k);
	else tr[p].r=modify(tr[p].r,mid+1,r,k);
	up(p);
	return p;
}
int Ans(int u,int lst,int l,int r,int k) {
	if(l==r) {
		return b[l]*min(tr[u].cnt-tr[lst].cnt,k);
	}
	int mid=l+r>>1;
	if(tr[tr[u].r].cnt-tr[tr[lst].r].cnt>=k) return Ans(tr[u].r,tr[lst].r,mid+1,r,k);
	return tr[tr[u].r].sum-tr[tr[lst].r].sum+Ans(tr[u].l,tr[lst].l,l,mid,k-(tr[tr[u].r].cnt-tr[tr[lst].r].cnt));
}
void get(int l,int r,int ql,int qr) {
	if(l>r) return;
	int mid=l+r>>1;
	int R=min(qr,mid);
	int pos=false,now=false;
	rep(i,ql,R) {
		int ll=i,rr=mid;
		int dis=rr-s+rr-ll;
		if(dis>d) continue;
		int yu=d-dis,kk=Ans(rt[rr],rt[ll-1],1,n,yu);
		if(kk>=now) {
			pos=i;
			now=kk;
		}
	}
	if(pos==0) return;
	res=max(res,now);
	get(l,mid-1,ql,pos);
	get(mid+1,r,pos,qr);
}
int a[N];
void solve() {
	in(n),in(s),in(d);
	s++;
	rep(i,1,n) {
		in(a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int mm=unique(b+1,b+1+n)-b-1;
	rep(i,1,n) {
		rt[i]=rt[i-1];
		a[i]=lower_bound(b+1,b+1+mm,a[i])-b;
		rt[i]=modify(rt[i],1,n,a[i]);
	}
	get(s,n,1,s);
	idx=false;
	rep(i,1,n) rt[i]=false;
	reverse(a+1,a+1+n);
	rep(i,1,n) {
		rt[i]=rt[i-1];
		rt[i]=modify(rt[i],1,n,a[i]);
	}
	s=n-s+1;
	get(s,n,1,s);
	printf("%lld\n",res);
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...