(马后炮)解题报告
Table of Contents
- A. Heist
- B. Buying a TV Set
- Description
- Solution
- C. Coffee Break
- Description
- Solution
- D. Glider
- Description
- Solution
- E. Tree Reconstruction
- Description
- Solution
- F. Ray in the tube
- Description
- Solution
A. Heist
$\ldots$
B. Buying a TV Set
Description
给你$a,b,c,d$，求满足$\frac{x}{y}=\frac{c}{d},x\le a,y\le b$的$x,y$的对数.
Translation copied from luogu.org
Solution
约分除一下……
C. Coffee Break
Description
给定$n$个数和一个$k$，这$n$个数都不超过$m$
每次从没被去掉的数里面选一个数$a$，去掉$a$，然后可以任意一个$b(b>a+k)$，然后去掉任意一个$c(c>b+k)$，以此类推.
问最少能选多少个$a$，然后输出每个数都是选第几个$a$的时候被去掉的.
Translation copied from luogu.org
Solution
贪心+二分.
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 2e+5 + 5;
int n, m, d, ans[maxn];
set<pair<int, int> > cft;
int main()
{
typedef set<pair<int,int> >::iterator iter;
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> d;
for(register int i = 1; i <= n; ++i)
{
int x; cin >> x;
cft.insert(make_pair(x, i));
}
int day = 0;
while(cft.size())
{
day++;
iter i = cft.begin();
iter j = cft.lower_bound(make_pair(i->first + d + 1, 0));
ans[i->second] = day;
cft.erase(i);
while(j != cft.end())
{
iter p = j;
j = cft.lower_bound(make_pair(j->first + d + 1, 0));
ans[p->second] = day;
cft.erase(p);
}
}
cout << day << endl;
for(int i = 1; i <= n; ++i) cout << ans[i] << " ";
return 0;
}
|
D. Glider
Description
你在玩一个吃鸡游戏，你现在要跳伞。你的飞机现在在高度为$h$的空中飞行，你每飞一个单位长度的距离，你就会下落一个单位长度的高度，当然，有些地方是上升气流，你不会下落，你会往前直飞，由于你想在空中就被人打死，求你最远的飞行距离.
第一行两个正整数$n$，$h$，代表有$n$段上升气流，飞机的高度为$h$。
接下来$n$行，每行两个数$x_{i1}$，$x_{i2}$。代表$x_{i1}$至$x_{i2}$这段区间为上升气流。
Translation copied from luogu.org
Solution
贪心+二分.
可以证明一定从上升气流的开头开始跳, 对空气做个前缀和, 对上升气流做个前缀和, 二分出落地的位置就行了.
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e+5 + 5;
struct seg
{
ll l, r;
}t[maxn];
int n;
ll len[maxn], sum[maxn], h;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> h;
for(int i = 0; i < n; ++i)
{
cin >> t[i].l >> t[i].r;
len[i] = t[i].r - t[i].l;
if(i)
sum[i] = t[i].l - t[i-1].r;
}
for(int i = 1; i < n; ++i)
len[i] += len[i-1], sum[i] += sum[i-1];
ll ans = 0;
for(int i = 0; i < n; ++i)
{
int pos = lower_bound(sum + i + 1, sum + n, sum[i] + h) - sum;
if(i)
ans = max(ans, len[pos - 1] - len[i - 1]);
else ans = max(ans, len[pos - 1]);
}
cout << ans + h << endl;
return 0;
}
|
E. Tree Reconstruction
Description
有一棵树，现在给你每条树边被去掉时，形成的两个联通块中点的最大的编号分别是多少，问满足条件的树存不存在.
Translation copied from luogu.org
Solution
有意思(没玩出来)的构造.
首先判无解, 任意一条边一定会把 $n$ 所在集合和另一个集合分开, 如果有一些边没有 $n$, 那么就死了.
然后考虑较小的一端, 对于一个 $k$, 小于等于 $k$ 的节点最多只有 $k$ 个, 所以对 $a$ 排序, 如果到了第 $i$ 个, 有$i > a_i$, 说明有多于 $a_i$ 个节点要小于 $a_i$. 这样也不合法.
最后构造答案.
最小的 $a_i$ 一定是叶子节点, 因为没有一条边会割开更小的节点.
然后顺次考虑每个 $a_i$, 如果$a_i > a_{i-1}$, 就把上一个点连到这里, 这样当前集合的最大值就变大了.
如果 $a_i = a_{i - 1}$, 就在没有用过的编号里面找一个最小的, 这样最大值不会变大, 符合相等的条件.
最后连出一条链.
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
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, a[maxn], b[maxn];
set<int> use;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
bool sol = true;
cin >> n;
for(int i = 1; i < n; ++i)
{
cin >> a[i] >> b[i];
if(b[i] != n)
sol = false;
}
if(!sol)
{
cout << "NO" << endl;
return 0;
}
sort(a + 1, a + n);
for(int i = 1; i < n; ++i) use.insert(i);
for(int i = 1; i < n; ++i)
{
if(use.find(a[i]) != use.end()) use.erase(use.find(a[i]));
if(i > a[i])
{
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
int lst = a[1];
for(int i = 2; i < n; ++i)
{
if(a[i] > a[i - 1])
{
printf("%d %d\n", lst, a[i]);
lst = a[i];
}
else
{
int u = *use.begin(); use.erase(use.find(u));
printf("%d %d\n", lst, u);
lst = u;
}
}
printf("%d %d", lst, n);
return 0;
}
|
F. Ray in the tube
Description
下边界有$n$个给定点，上边界有$m$个给定点，可以从任意一个点发出一条激光，激光碰到边界会反射
激光到达边界必须打到整数点，问最多可以打到几个给定点.
Solution
首先不用算斜率, 直接确定 $\Delta x$ 就可以计算答案.
然后二分一下? DP一下? 要么时间炸要么空间炸.
事实上, 对于同一侧的点, 如果能被攻击到一定在$(mod\,2\Delta x)$下同余, 不同侧的点坐标加上$\Delta x$ 也同余.
问题是, 怎么确定模数?
观察发现, 如果$\Delta x = 1$, 那么$3,5,7,\ldots$都没有意义, 因为1一定能到达它们能到达的所有点.
那么剩下2, 相应地$6, 10, 14\ldots$ 也都没用了.
那么剩下4, 剩下$8, 16, 32\ldots$ 模数一定是2的幂!
所以复杂度是$nlog(10^9)logn$的, map维护一下剩余系.
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e+5 + 5;
int yup, ydn, n, m, ans;
ll up[maxn], dn[maxn];
ll pow2[35];
inline void solve(int index)
{
map<ll, int> mod;
for(int i = 1; i <= n; ++i)
mod[dn[i] % (2ll * pow2[index])]++;
for(int i = 1; i <= m; ++i)
mod[(up[i] + pow2[index]) % (2ll * pow2[index])]++;
for(auto p : mod)
ans = max(ans, p.second);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> ydn;
for(int i = 1; i <= n; ++i) cin >> dn[i];
cin >> m >> yup;
for(int i = 1; i <= m; ++i) cin >> up[i];
pow2[0] = 1;
for(int i = 1; i <= 30; ++i) pow2[i] = (pow2[i-1] << 1);
for(int i = 0; i <= 30; ++i) solve(i);
if(n == 1 && m == 1 && dn[1] == up[1]) ans = max(ans, 2);
cout << ans << endl;
return 0;
}
|
