Location>code7788 >text

P1081 [NOIP2012 Improvement Group] Traveling by Car

Popularity:938 ℃/2024-07-30 09:28:58

Thoughts:

premise sth.\(nxt1_i\) denotes the distance to the nearest city on the right (\(id1_i\) (for numbering), so that\(nxt2_i\) denotes the second closest city number on the right (\(id2_i\) (for numbering); it is possible to useset Find the nearest city to this\(4\) cities (two in the front and two in the back).

Definition:

  • \(f_{i,j}\) denote\(i\) leave at 1:00 p.m. and go\(2^j\) The wheel arrives at the last position.

  • \(dp1_{i,j}\) denote\(i\) leave at 1:00 p.m. and go\(2^j\) The last A of the round traveled the distance.

  • \(dp2_{i,j}\) denote\(i\) leave at 1:00 p.m. and go\(2^j\) Round the distance traveled by the last B.

Initialization:

\[f_{i,0} = id1_{id2_i} \]

\[dp1_{i,0} = nxt2_{i} \]

\[dp2_{i,0} = nxt1_{id2_i} \]

The state transfer equation is:

\[f_{i,j} = f_{f_{i,j-1},j-1} \]

\[dp1_{i,j} = dp1_{i,j-1} + dp1_{f_{i,j-1},j-1} \]

\[dp2_{i,j} = dp2_{i,j-1} + dp2_{f_{i,j-1},j-1} \]

At this point for inquiries\(1\) and inquiries\(2\)

  • Essentially, it's finding out that after traveling from each city\(A\) Distance traveled vs.\(B\) Walking distance.

  • Then consider greed from high to low, i.e. set the current jump to the\(s\) point, if\(dp1_{s,i} + dp2_{s,i} \le x\)can be obtained from the\(s\) jump to\(f_{s,i}\)The need to make\(x \gets x - (dp1_{s,i} + dp2_{s,i})\)and then continue traversing\(i-1\) Bit.

  • Since A drove first, A may be able to drive again at the end of the last round, requiring a special judgment.

The time complexity is\(O((N+Q) \log N)\)

Full Code:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10,M=18,INF=1e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll a,b;
	ll id;
	bool operator<(const Node&rhs)const{
		if(a!=)
		  return a<;
		return b<;
	}
};
ll n,m,s,x,x0,s0,cnt,dis1,dis2,disa,disb;
ll a[N],nxt1[N],nxt2[N],id1[N],id2[N];
ll f[N][M],dp1[N][M],dp2[N][M];
Node h[N];
vector<Node> V;
multiset<Node> S;
void solve(ll s,ll x){
	dis1=dis2=0;
	for(int i=M-1;i>=0;i--){
		if(dp1[s][i]+dp2[s][i]<=x&&f[s][i]){
			dis1+=dp1[s][i],dis2+=dp2[s][i];
			x-=dp1[s][i]+dp2[s][i];
			s=f[s][i];
		}
	}
	if(nxt2[s]<=x)
	  dis1+=nxt2[s];
}
bool End;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		h[i]={a[i],a[i],i};
	}
	({INF,INF,0});
	({INF-1,INF-1,0});
	({-INF,-INF,0});
	({-INF+1,-INF+1,0});
	for(int i=n;i>=1;i--){
		();
		V.push_back(*--S.lower_bound(h[i]));
		V.push_back(*--S.lower_bound(V[0]));
		V.push_back(*S.upper_bound(h[i]));
		V.push_back(*S.upper_bound(V[2]));
		for(auto &v:V)
		  =abs(h[i].);
		sort((),());
		nxt1[i]=V[0].a,nxt2[i]=V[1].a;
		id1[i]=V[0].id,id2[i]=V[1].id;
		cerr<<id1[i]<<' '<<id2[i]<<'\n';
		(h[i]);
	}
	for(int i=1;i<=n;i++){
		f[i][0]=id1[id2[i]];
		dp1[i][0]=nxt2[i];
		dp2[i][0]=nxt1[id2[i]];
	}
	for(int j=1;j<M;j++){
		for(int i=n;i>=1;i--){
			f[i][j]=f[f[i][j-1]][j-1];
			dp1[i][j]=dp1[i][j-1]+dp1[f[i][j-1]][j-1];
			dp2[i][j]=dp2[i][j-1]+dp2[f[i][j-1]][j-1];
		}
	}
	x0=read();
	for(int i=1;i<=n;i++){
		solve(i,x0);
		if(dis2&&(!s0||disa*dis2>disb*dis1)){
			s0=i;
			disa=dis1,disb=dis2;
		}
	}
	write(s0);
	putchar('\n');
	m=read();
	while(m--){
		s=read(),x=read();
		solve(s,x);
		write(dis1);
		putchar(' ');
		write(dis2);
		putchar('\n');
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}