NOI2019

发表于 更新于 分类于 评论数： 阅读次数：

NOI2019
还没填完（d2t1在uoj上尚未通过，有空填）
d2题解

D1T1 回家路线

请先思考后再展开

本题不知什么原因没有和mq区分开
好像分差只有5，让我想起狗血的「优秀的拆分」
（数据是人出的，人是懒的……）

在我看来权值的计算方式几乎是赤果果的暗示斜率优化
把每个点按时间拆分，然后每个时间拆入和出
那么点内部的等待就是斜率优化模板（有助于帮助老年文化课选手恢复水平……）
点间的移动就是朴素的dag上dp，用map处理有用的点即可
c++11下算法复杂度下限为线性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
namespace mine
{
	typedef long long ll;
	#define pr pair<int,ll>
	#define FR first
	#define SE second
	#define MP make_pair
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) putchar('-'),num=-num;
		if(num>=10) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	const int INF=0x3f3f3f3f;
	const int MOD=1e9+7;
	void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
	ll qpower(ll x,int e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int MAX_N=1e6+10;

	map<int,int> pt[MAX_N][2];//pt[x][op]=id
	int cnt=0,pos[MAX_N];
	int newid(int x,int t,int op)
	{
		if(pt[x][op][t]>0) return pt[x][op][t];
		pos[++cnt]=x;return pt[x][op][t]=cnt;
	}
	vc<int> fm[MAX_N];//fm[id]=id
	vc<int> in[MAX_N],out[MAX_N];//in[time]=id

	ll dis[MAX_N];//dis[id]
	double slope(pr a,pr b)
	{
		return (b.SE-a.SE)*1.0/(b.FR-a.FR);
	}
	struct qq
	{
		vc<pr> q;int tou,wei;
		qq(){tou=0;wei=-1;}
		void insert(pr now)
		{
			while(tou<wei and slope(q[wei-1],q[wei])>=slope(q[wei],now)) wei--;
			wei++;if((int)q.size()-1<wei) q.PB(now); else q[wei]=now;
		}
		void popf(ll k)
		{
			while(tou<wei and slope(q[tou],q[tou+1])<=k) tou++;
		}
		ll getb(ll k)
		{
			if(tou>wei) return (ll)INF*INF;
			return q[tou].SE-k*q[tou].FR;
		}
	}pp[MAX_N];//凸壳pp[x]=(x,y)
	void main()
	{
		int n=qread(),m=qread();ll A=qread(),B=qread(),C=qread();
		for(int i=1;i<=m;i++)
		{
			int x=qread(),y=qread(),p=qread(),q=qread();
			int a=newid(x,p,1),b=newid(y,q,0);fm[b].PB(a);
			out[p].PB(a);in[q].PB(b);
		}
		memset(dis,0x3f,sizeof dis);ll ans=dis[0];
		dis[ newid(1,0,1) ]=0;pp[1].insert(MP(0,0ll));
		for(int ti=1;ti<=1000;ti++)
		{
			sort(in[ti].begin(),in[ti].end());
			in[ti].resize(unique(in[ti].begin(),in[ti].end())-in[ti].begin());
			for(int t=0;t<(int)in[ti].size();t++)
			{
				int x=in[ti][t],ps=pos[x];//id
				for(int t2=0;t2<(int)fm[x].size();t2++) dis[x]=min(dis[x],dis[fm[x][t2]]+C);
				// printf("in ti=%d ps=%d dis=%lld\n",ti,ps,dis[x]);
				pp[ps].insert(MP(ti,(ll)ti*ti*A+dis[x]));
				if(ps==n) ans=min(ans,dis[x]+ti);
			}
			sort(out[ti].begin(),out[ti].end());
			out[ti].resize(unique(out[ti].begin(),out[ti].end())-out[ti].begin());
			for(int t=0;t<(int)out[ti].size();t++)
			{
				int x=out[ti][t],ps=pos[x];//id
				pp[ps].popf(A*2*ti+B);
				dis[x]=pp[ps].getb(A*2*ti+B)+A*ti*ti+B*ti;
				// printf("out ti=%d ps=%d dis=%lld\n",ti,ps,dis[x]);
			}
		}
		write(ans);
	}
};
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	srand(time(0));
	mine::main();
}

D1T2 机器人

请先思考后再展开

第二题还是比较中规中矩的NOI题，暴力DP有50分
然后考虑离散化，同一段里面用CF995F的处理方式，插值或者维护下降幂多项式
不过插值会被卡常数到85~95分，下降幂多项式能过
代码有些复杂，可以区分出一些基本功扎实的选手

50分dp：
考虑最右边的最大值，发现可选位置很少，以此为基础dp(l,r,mx)然后枚举mx的位置来转移
复杂度为大常数MB，M为实际访问到的区间（记忆化），据说本题M最大2000
10分无限制：枚举实际用了多少个数即可

1
2


D1T3 序列

请先思考后再展开

暴力DP有32分，然后我一开始想了一个错结论，以为上面取最大的K个（记为X），下面取最大的K个（记为Y），X∩Y定全选，然后2个小时调不出来。。。
实际上是X∩Y要么上下都选要么上下都不选，X-Y选了下面就要选上面，Y-X选了上面就要选下面。。。
这样就可以分成三块搞了。
由于我不擅长贪心，用网络流的思想做的。一共做了3个小时。
我猜现役选手应该会比我熟练地多吧。

1
2


D2T1 弹跳

请先思考后再展开

这道题其实有点像树上的最短路
不同之处在于省去了取出路径的部分，然后把树上路径改为了矩形
但本质上是一样的，至少在工具上，从树上压缩的并查集改为 数状数组套权值线段树或者kdtree维护0/1
空间上都是足够的，时间的话二维线段树调用次数是弹跳装置个数，复杂度为 $O(mlog^2H)$

可能是没怎么写过，但迫于空间压力写了数状数组套权值线段树然后写了很久，树状数组这玩意套东西拓展起来很麻烦
现在想想感觉写四叉树随便写，空间其实也不大……果然数据结构基础知识不扎实是硬伤
upd：好像sgt套set也不错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
	typedef long long ll;
	#define pr pair<int,int>
	#define FR first
	#define SE second
	#define MP make_pair
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) putchar('-'),num=-num;
		if(num>=10) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	const int INF=0x3f3f3f3f;
	const int MOD=1e9+7;
	void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
	ll qpower(ll x,int e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int MAX_N=7e4+10,MAX_M=2e5+10;

	int n,m,w,h;
	map<pr,int> getid;pr pt[MAX_N];bool out[MAX_N];
	namespace Gao//log^2
	{
		struct Nod{int lc,rc,zz;}p[20000000];
		int id=0;int rt[MAX_N];//每棵线段树根
		#define mid ((l)+(r))/2
		void s_change(int &x,int l,int r,int pos,int op)
		{
			if(!x) x=++id,p[x]=(Nod){0,0,0};
			p[x].zz+=op;
			if(l==r) return;
			if(pos<=mid) s_change(p[x].lc,l,mid,pos,op);
			else s_change(p[x].rc,mid+1,r,pos,op);
		}
		int lowbit(int x){return x&-x;}
		void modify(int x,int y,int val){while(x<=w) s_change(rt[x],1,h,y,val),x+=lowbit(x);}
		int s_ask(int x,int l,int r,int pos)
		{
			if(!x) return 0;
			if(l==r) return p[x].zz;
			if(pos<=mid) return s_ask(p[x].lc,l,mid,pos);
			else return s_ask(p[x].rc,mid+1,r,pos);
		}
		int askx(int x1,int y)
		{
			int wt=0;x1--;while(x1>=1) wt+=s_ask(rt[x1],1,h,y),x1-=lowbit(x1);
			int now=0,left=0;//最后一个zz[now]<=wt的now+1
			for(int i=17;i>=0;i--)
			{
				now+=(1<<i);if(now>w) {now-=(1<<i);continue;}
				int tmp=s_ask(rt[now],1,h,y);
				if(left+tmp>wt) now-=(1<<i);
				else left+=tmp;
			}
			return now+1;
		}

		int u[2][MAX_N],u2[20][2][MAX_N];
		void clear(int x,int op){while(x>=1) u[op][x]=rt[x],x-=lowbit(x);}
		void turnl(int x,int op){while(x>=1) u[op][x]=p[u[op][x]].lc,x-=lowbit(x);}
		void turnr(int x,int op){while(x>=1) u[op][x]=p[u[op][x]].rc,x-=lowbit(x);}
		void backup(int x,int op,int dep){while(x>=1) u2[dep][op][x]=u[op][x],x-=lowbit(x);}
		void goback(int x,int op,int dep){while(x>=1) u[op][x]=u2[dep][op][x],x-=lowbit(x);}
		int getl(int x,int op){int sum=0;while(x>=1) sum+=p[ p[u[op][x]].lc ].zz,x-=lowbit(x);return sum;}
		int getsum(int x,int op){int sum=0;while(x>=1) sum+=p[ u[op][x] ].zz,x-=lowbit(x);return sum;}
		int asky(int dep,int x1,int x2,int l,int r,int fl,int fr)
		{
			if(l==fl and r==fr)
			{
				if(getsum(x2,1)==getsum(x1-1,0)) return 0;
				if(l==r) return l;
				if(getl(x2,1)-getl(x1-1,0)) {turnl(x1-1,0);turnl(x2,1);return asky(dep+1,x1,x2,l,mid,l,mid);}
				else {turnr(x1-1,0);turnr(x2,1);return asky(dep+1,x1,x2,mid+1,r,mid+1,r);}
			}
			if(fr<=mid) {turnl(x1-1,0);turnl(x2,1);return asky(dep+1,x1,x2,l,mid,fl,fr);}
			else if(fl>mid) {turnr(x1-1,0);turnr(x2,1);return asky(dep+1,x1,x2,mid+1,r,fl,fr);}
			else
			{
				backup(x1-1,0,dep);backup(x2,1,dep);
				turnl(x1-1,0);turnl(x2,1);
				int tmp=asky(dep+1,x1,x2,l,mid,fl,mid);
				if(tmp) return tmp;
				goback(x1-1,0,dep);goback(x2,1,dep);
				turnr(x1-1,0);turnr(x2,1);
				return asky(dep+1,x1,x2,mid+1,r,mid+1,fr);
			}
		}
	};
	struct Edge{int t,x1,x2,y1,y2;}pp[MAX_M];
	vc<int> e[MAX_N];int dis[MAX_N];
	priority_queue< pr,vc<pr>,greater<pr> > q;
	void dij()
	{
		memset(dis,0x3f,sizeof dis);dis[1]=0;q.push(MP(0,1));
		while(q.size())
		{
			pr now=q.top();q.pop();int x=now.SE;
			if(x>n)
			{
				int id=x-n;
				while(1)
				{
					Gao::clear(pp[id].x1-1,0);Gao::clear(pp[id].x2,1);
					int y=Gao::asky(0,pp[id].x1,pp[id].x2,1,h,pp[id].y1,pp[id].y2);if(y==0) break;
					y=getid[MP(Gao::askx(pp[id].x1,y),y)];
					if(out[y]==0) Gao::modify(pt[y].FR,pt[y].SE,-1),out[y]=1;
					dis[y]=now.FR;q.push( MP(dis[y],y) );
				}
			}
			else
			{
				if(dis[x]<now.FR) continue;
				if(out[x]==0) Gao::modify(pt[x].FR,pt[x].SE,-1),out[x]=1;
				for(int t=0;t<(int)e[x].size();t++)
				{
					int to=e[x][t];
					q.push( MP(dis[x]+pp[to].t,n+to) );
				}
			}
		}
	}
	void main()
	{
		scanf("%d%d%d%d",&n,&m,&w,&h);
		for(int i=1;i<=n;i++)
		{
			pt[i].FR=qread(),pt[i].SE=qread(),getid[pt[i]]=i;
			Gao::modify(pt[i].FR,pt[i].SE,1);
		}
		for(int i=1;i<=m;i++)
		{
			int x,t,x1,x2,y1,y2;scanf("%d%d%d%d%d%d",&x,&t,&x1,&x2,&y1,&y2);
			pp[i]=(Edge){t,x1,x2,y1,y2};e[x].PB(i);
		}
		dij();for(int i=2;i<=n;i++) write2(dis[i]);
	}
};
int main()
{
	freopen("a.in","r",stdin);
	// freopen("jump.in","r",stdin);
	// freopen("jump.out","w",stdout);
	srand(time(0));
	mine::main();
}

D2T2 斗主地

请先思考后再展开
1
2


D2T3 I 君的探险

请先思考后再展开
1
2


相关文章推荐

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/c0a6.html
转载请注明出处，谢谢！