蛤实验胡策20171013题解

OI
  1. 1. OBC
    1. 1.1. 题意
    2. 1.2. 题解
      1. 1.2.1. 10分
      2. 1.2.2. 50分
      3. 1.2.3. 100分
        1. 1.2.3.1. $k=1$
        2. 1.2.3.2. $k=2$
  2. 2. 自动AC机
    1. 2.1. 题解
  3. 3. ZF爱打call
  4. 4. std
    1. 4.1. OBC

吾辈是蒟蒻,标程嘛,还没有

出题人mk。

OBC

题意

二维平面上有若干点,现在可以用$k$条长度为$l$的同方向的,与$x,y$轴平行的线段去覆盖这些点,求最大覆盖数

题解

10分

$k=0$的情况,直接输出0

50分

二维前缀和预处理,然后$O(n^2)$枚举一下所有起点

100分

$k=1$

将所有点以$x$为第一关键字,$y$为第二关键字sort一下,然后将sort后的序列分成若干段,使得每一段内的点的$x$值相等,然后用一个单调队列把每一段都扫一遍,具体就是先push一个点到队尾,再比对一下队头与队尾的$y$值之差是否大于$l$ ,如果是,那就pop,否则什么都不干。

在这个过程中,不断更新最大值。

操作完之后swap一下$x,y$,再操作一遍

$k=2$

考虑$k=2$有两种情况,一种是两条线段在同一“段”内选,另一种是两条线段在不同“段”内选,我们先考虑后一种情况。

这种很简单,只需要在扫的同时维护最大值和次大值即可

考虑两条线段在同一段内的情况,不妨设这一段是$[l,r]$

我们用$f(i)$表示一段内$[l,i]$的最大的答案,$g(i)$表示$[i,r]$内的最大答案

显然这两个函数都是可以用队列扫一遍预处理出来的

然后我们枚举一下分隔点,

$$
ans=\max_{i=l}^{r-1}{f(i) + g(i+1)}
$$

就是这样。。。原理也很显然

然后对于这两种情况取个max就是答案啦

自动AC机

题解

先化简一下题目的公式

$$
\left(\sum_{k=i}^js[k]\right)^2+\left(\sum_{k=1}^{i-1}s[k]+\sum_{k=1}^js[k]\right)^2-3\left(\sum_{k=1}^{i-1}s[k]\right)^2-\left(\sum_{k=1}^js[k]\right)^2
$$

这是原公式

我们注意到$\sum_{k=i}^js[k]=-\sum_{k=1}^{i-1}s[k]+\sum_{k=1}^js[k]$,于是进行一波变换,最后得到这样的式子

$$
\left(\sum_{k=i}^js[k]\right)^2+\left(\sum_{k=1}^{i-1}s[k]+\sum_{k=1}^js[k]\right)^2-3\left(\sum_{k=1}^{i-1}s[k]\right)^2-\left(\sum_{k=1}^js[k]\right)^2=\
\left(\sum_{k=1}^js[k]\right)^2-\left(\sum_{k=1}^{i-1}s[k]\right)^2
$$

嗯。。前缀和。。

我们令$s(i)=\sum_{k=1}^i$,那么如果我们令$f(i,j)$为区间$[i,j]$的贡献,有$f(i,j)=s(j)^2-s(i-1)^2$。

我们可以预处理出来前缀和以及前缀和的平方,以及每个数的不大于它的最大素数,然后就可以写一个暴力dp。

令$dp(i)$为前$i$道题的最大贡献,那么$dp(i)$显然可以从$[i-k+1,i-1]$更新过来,然后取一个最大值就可以了。

取最大值的操作可以优化,如果用线段树/堆,可以拿75分,如果用单调队列,可以拿100分。

然后考虑一种更骚的写法,分成若干段之后的贡献值会互相抵消,最终的贡献值是$s(n)^2$, 只需要考虑bug值的影响,这样就更加容易了。

ZF爱打call

首先对每个点的毒瘤值离线,然后记录一下是属于哪一个询问的,然后在从小到大用并查集维护一波,统计一下贡献,然后就没了。

还没写只能xjb口胡

std

OBC

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
#include <bit/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct point
{
int x, y;
point() { x = y = 0; }
point(int x, int y) : x(x), y(y){};
void rev() { swap(x, y); }
bool operator<(const point &a) const
{
return x == a.x ? y < a.y : x < a.x;
}
};
typedef pair<int, int> pii;
vector<point> s;
int n, k, l;
int f[maxn], g[maxn];
int dp(const vector<point> &mv)
{
vector<point> q = mv;
vector<pii> same;
sort(q.begin(), q.end());
if (q.size() == 1)
same.push_back(pii(0, 0));
else
{
int i, lst;
for (i = 1, lst = 0; i < q.size(); ++i)
{
if (q[i].x != q[i - 1].x)
{
same.push_back(pii(lst, i - 1)); // [lst, i - 1]
lst = i;
}
}
if (lst != i)
same.push_back(pii(lst, i - 1));
}
int ans1 = 0, ans2 = 0;
if (k == 1)
{
for (int i = 0; i < same.size(); ++i)
{
deque<point> que;
int rl = same[i].first, rr = same[i].second;
for (int j = rl; j <= rr; ++j)
{
que.push_back(q[j]);
if (!que.empty() && q[j].y - que.begin()->y > l)
que.pop_front();
ans1 = max(ans1, (int)que.size());
}
}
}
if (k == 2)
{
int mx = 0, se = 0;
for (int i = 0; i < same.size(); ++i)
{
deque<point> que;
int rl = same[i].first, rr = same[i].second, an = 0;
for (int j = rl; j <= rr; ++j)
{
que.push_back(q[j]);
if (!que.empty() && q[j].y - que.begin()->y > l)
que.pop_front();
an = max(an, (int)que.size());
}
if (an > mx)
se = mx, mx = an;
else if (an > se)
se = an;
}
ans1 = mx + se;
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for (int i = 0; i < same.size(); ++i)
{

deque<point> que;
int rl = same[i].first, rr = same[i].second;
for (int j = rl; j <= rr; ++j)
{
que.push_back(q[j]);
if (!que.empty() && q[j].y - que.begin()->y > l)
que.pop_front();
f[j] = max(max(f[j], f[j - 1]), (int)que.size());
}
que.clear();
for (int j = rr; j >= rl; --j)
{
que.push_back(q[j]);
if (!que.empty() && que.begin()->y - q[j].y > l)
que.pop_front();
g[j] = max(max(g[j], g[j + 1]), (int)que.size());
}
for (int j = rl; j < rr; ++j)
ans2 = max(ans2, f[i] + g[i + 1]);
}
}
return max(ans1, ans2);
}
int main()
{
cin >> n >> k >> l;
if (k == 0)
return 0 * puts("0");
for (int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
s.push_back(point(x, y));
}
int xod, yod;
xod = dp(s);
for (int i = 0; i < s.size(); ++i)
s[i].rev();
yod = dp(s);
cout << max(xod, yod) << endl;
}