Codeforces Round #703 (Div. 2)（A ~ F）超高质量题解【每日亿题2 / 19】_你和你的朋友们住在n栋房子里。每个房子都位于二维平面的整数坐标点上。同一点可

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

A. Shifting Stacks

Translation

你有 $n$ 堆积木。第 $i$ 个堆栈包含 $h_i$ 块，它的高度是这堆积木的数量。在一次移动中，你可以从第 $i$ 个堆栈中取出一个积木（如果至少有一个积木的话）并将其放入第 $i+1$ 个堆积木中。问你能否将让积木的高度序列严格递增？

注意，堆栈的数量始终保持不变，也就是说哪怕这堆里没有积木了，这个堆也不会消失。

Solution

签到题 ~

很明显我们只需要构造出一个 $0,1,2,\cdots n+好多$ 的序列即可，就是前面的都堆到最后面，中间不够的话也可以借给他，然后就没了 ~

AC Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e5 + 7;
const ll INF = 4e18;
 

int n, m, t;
int a[N], b, k1, k2;


bool solve()
{
   
    ll ans = 0;
    
    scanf("%d", &n);
    for(int i = 1;i <= n; ++ i) {
   
        scanf("%d", &a[i]);
    }
    int x = 0;
    for(int i = 1; i <= n; ++ i, x ++ ) {
   
        if(a[i] > x) {
   
            ans += a[i] - x;
            a[i] = x;
        }
        else {
   
            ll tmp = x - a[i];
            if(ans < tmp) {
   
                puts("NO");
                return ;
            }
            else ans -= tmp;
        }
    }
    puts("YES");
}

int main()
{
   
    scanf("%d", &t);
    while(t -- ) {
   
        solve();
    }
}

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

B - Eastern Exhibition

Problem

Translation

你和你的朋友住在 $n$ 个房子里（？）。每个房子都位于一个二维的平面上，在一个点上有整数坐标。同一地点可能有好多个不同的房子挤一块（）。市长问你展览馆要建到哪里，请你输出所有房子到这个展览馆的距离最近的点的数量（必须是整数点），注意展览馆同样可以建在其他房子头上（雾）。定义两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的距离为 $|x_1-x_2|+|y_1-y_2|$。

Solution

签到题 ~

很明显这就是中位数的板子题，但是它把一维拓展到了二维，但是没什么区别

首先考虑一维怎么算，首先若 $n$ 是奇数，很明显答案就一定是 $1$，中位数固定了。

若是偶数，那么中间的那两个点之间的坐标都可以建（包括两个点，因为可以建到房子头上），那么对于二维来说，就是这个矩形里的所有的点都可以建呗，就乘起来 ~ 没了…

AC Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e4 + 7;
const ll INF = 4e18;

 

int n, m, t;

int x[N], y[N];

void solve()
{
   
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
   
        scanf("%d%d", &x[i], &y[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