Fork me on GitHub

Uoj#355.【JOI2017春季合宿】Cultivation

Uoj#355.【JOI2017春季合宿】Cultivation 题解

题意:

  • $W\times H$田地上有$n$颗种子,每天可以选择上下左右一个方向吹风,使得种子对应方向上最近那个格子变成有种子(如果有就无效)。
  • $1\le W,H\le 10^9,1\le n\le 300$。

题解:

  • 显然上下跟左右之间的前后顺序对于最后结果并没有影响。
  • 我们考虑先进行上下操作。
  • 对于向上$x$步,向下$y$步,可以变为向下$x+y$步,然后再将网格整体向下移$x$步。
  • 我们可以先枚举上下总共走了$len$步。
  • $len$似乎是有$O(n^2)$种选择。
  • 定义一行的$a_i$第$i$行代表最左边的种子离边界还要几步,$b_i$表示第$i$行相距最远的两个种子的距离,$c_i$表示最右边的种子离边界还要几步。
  • 显然最后答案就是$len+max\{max\{a_i\}+max\{c_i\},max\{b_i\}\}$。
  • 根据$n$个点和$n$个点的拓展到的点,可以将不同的行分为$O(n)$段。
  • 而每段的$a_i,b_i,c_i$都是相同的,而且每段存在的点的横坐标必定连续。
  • 所以我们可以预处理出横坐标排序后,$[l,r]$区间内的点的纵坐标构成的序列的$a,b,c$值。
  • 然后用一个单调队列类似移动窗口维护最大的$a_i,b_i,c_i$,然后更新答案。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 1009
#define pii pair<int,int>
#define inf 0x3f3f3f3f
using namespace std;
int w,h,n,a[N][N],b[N][N],c[N][N],Min=inf;
pii pos[N];
multiset<int> st;
multiset<int>::iterator it,It;
multiset<int,greater<int> > St;
vector<int> q;
int Q[3][N],d[N];
struct node
{
int l,r,a,b,c;
node(int l=0,int r=0,int a=0,int b=0,int c=0):l(l),r(r),a(a),b(b),c(c){}
};
vector<node> dl;
int read()
{
char ch;
int x=1;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
int main()
{
w=read(),h=read(),n=read();
pos[0].first=0;
for (int i=1;i<=n;i++)
pos[i].first=read(),pos[i].second=read(),Min=min(Min,pos[i].first);
for (int i=1;i<=n;i++) pos[i].first-=Min-1;
pos[n+1].first=w+1;
sort(pos+1,pos+n+1);
for (int i=1;i<=n;i++)
{
st.clear(),St.clear();
st.insert(0),st.insert(h+1);
b[i][i-1]=a[i][i-1]=c[i][i-1]=inf;
for (int j=i;j<=n;j++)
{
It=it=st.insert(pos[j].second);
if ((*(--it))==0) a[i][j]=pos[j].second-1;
else a[i][j]=a[i][j-1];
if ((*(++It))==h+1) c[i][j]=h-pos[j].second;
else c[i][j]=c[i][j-1];
if ((*It)!=h+1) St.insert(max(0,(*It)-pos[j].second-1));
if ((*it)!=0) St.insert(max(0,pos[j].second-(*it)-1));
if ((*It)!=h+1&&(*it)!=0) St.erase(St.find(max(0,(*It)-(*it)-1)));
if (j>i) b[i][j]=(*St.begin());
else b[i][j]=0;
}
}
for (int i=0;i<=n+1;i++)
a[n+1][i]=b[n+1][i]=c[n+1][i]=inf;
q.clear();
q.push_back(0),q.push_back(w-1);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (pos[i].first<pos[j].first) q.push_back(pos[j].first-pos[i].first-1);
q.push_back(w+pos[j].first-pos[i].first-1);
}
sort(q.begin(),q.end());
q.erase(unique(q.begin(),q.end()),q.end());
ll Ans=w+h;
for (int id=0;id<(int)q.size();id++)
{
int len=q[id],num=0;
d[++num]=1;
for (int i=1,j=1;i<=n||j<=n;)
{
if (i<=n&&(j>n||pos[i].first<pos[j].first+len+1)) d[++num]=pos[i++].first;
else d[++num]=pos[j++].first+len+1;
}
d[++num]=inf;
dl.clear();
int l=1,r=1;
for (int i=1;i<num;i++)
if (i==num-1||d[i]!=d[i+1])
{
while (l<=n&&pos[l].first+len+1<=d[i]) l++;
while (r<=n&&pos[r].first<=d[i]) r++;
dl.push_back(node(d[i],d[i+1]-1,a[l][r-1],b[l][r-1],c[l][r-1]));
}
//cerr<<"debug:"<<endl;
//for (auto i:dl) cerr<<i.l<<" "<<i.r<<" "<<i.a<<" "<<i.b<<" "<<i.c<<endl;
//cerr<<"end"<<endl;
int head[3]={1,1,1},tail[3]={0,0,0},now=0;
for (int i=0;i<(int)dl.size();i++)
{
if (dl[i].l>len+1) break;
int l=dl[i].l,r=dl[i].l+w-1;
while (now<(int)dl.size()&&dl[now].l<=r)
{
while (head[0]<=tail[0]&&dl[Q[0][tail[0]]].a<=dl[now].a) tail[0]--;
Q[0][++tail[0]]=now;
while (head[1]<=tail[1]&&dl[Q[1][tail[1]]].b<=dl[now].b) tail[1]--;
Q[1][++tail[1]]=now;
while (head[2]<=tail[2]&&dl[Q[2][tail[2]]].c<=dl[now].c) tail[2]--;
Q[2][++tail[2]]=now;
now++;
}
while (head[0]<=tail[0]&&dl[Q[0][head[0]]].r<l) head[0]++;
while (head[1]<=tail[1]&&dl[Q[1][head[1]]].r<l) head[1]++;
while (head[2]<=tail[2]&&dl[Q[2][head[2]]].r<l) head[2]++;
//if (len<=600000000&&len>=200000000)
//cerr<<len<<" "<<dl[Q[0][head[0]]].a<<" "<<dl[Q[2][head[2]]].c<<" "<<dl[Q[1][head[1]]].b<<endl;
Ans=min(Ans,max((ll)dl[Q[0][head[0]]].a+(ll)dl[Q[2][head[2]]].c,(ll)dl[Q[1][head[1]]].b)+(ll)len);
}
}
printf("%lld\n",Ans);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#355.【JOI2017春季合宿】Cultivation

文章作者:wzf2000

发布时间:2018年03月14日 - 15:03

最后更新:2018年03月14日 - 18:03

原始链接:https://wzf2000.github.io/2018/03/14/Uoj355/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。