永世隔绝の理想乡

Garden of Avalon

0%

Codeforces-Round-783-Div-2

发表于 分类于

div2#783赛后补题

CodeForces 1668A. Direction Change—原题链接

题目标签：数学 | 贪心

思路：
首先考虑不可行的情况，在一行中只能左右走的情况如果长边大于3那自然是不可行了
紧接着，对于每张图，可以看成一个大正方形拼上了一个较小的矩形，正方形的边长是原矩形的宽
这么考虑的原因是，从正方形的左上走到右下的唯一最短路就是沿着对角线走“台阶”，即step=(n-1)^2
再考虑右侧的小矩形，走“日”一定可以走到对应的点，当然需要对奇偶性进行特判

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;

void solve()
{
    int a, b;
    cin >> a >> b;
    if(a > b) swap(a, b); //保证a能够作为矩形的宽
    if(a == 1 && b-a >= 2) //不成立情况的特判
    {
        cout << "-1" << endl;
    }
    else
    {
        int d = b-a; //小长方形的宽，判断其奇偶性
        if(d % 2 == 1) cout << (a-1)*2+2*(d-1)+1 << endl; //奇数：最后一步是从左侧走进来的
        else cout << (a-1)*2+2*d << endl; //偶数：最后一步是从上侧走进来的
    }
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

CodeForces 1668B. Social Distance—原题链接

题目标签：贪心

思路：
若要满足所有人，消耗最多的一定是最麻烦的那个人，所以我们需要对数组排序然后对于最麻烦的人讨论
对于这个最麻烦的人，当他坐下后，已经不能再坐人的包括他的范围和他自己也就是a[max]*2+1
对于其他的人，坐在上一个人不能坐的边缘是是一定满足的，因为a[i]始终小于等于前者，因此只需要考虑他的一侧，也就是a[i]+1
最后一个人比较特殊，因为他的下一个就是最麻烦的人，因此他完全可以夹在两个人不能坐的边缘之间，也就是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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int a[N];

bool cmp(int a, int b)
{
    return a>b;
}

void solve()
{
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a, a+n, cmp); //降序排序
    LL num = a[0] * 2 + 1; // 处理消耗资源最多的那个人
    for(int i=1; i<n-1; i++) num += a[i] + 1; // 中间的人只需要判断一侧即可
    num++; // 处理消耗资源最少的那个人
    if(m >= num) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main()
{
    int t;
    // scanf("%d", &t);
    cin >> t;
    while(t--)
    {
        solve();
    }
    // system("pause");
    return 0;
}

CodeForces 1668C. Make it Increasing—原题链接

题目标签：模拟 | 贪心(?)

思路：
硬核模拟，我是没看出来哪里需要贪心，一开始贪心的思路也错了，一道卡了一个半小时+的c题QAQ
因为需要满足单调性的同时减少操作次数，因此保证其中一个数为0，至于哪一位为0就遍历一次
遍历到一位为0的时候，模拟一边更新的过程，因为模拟时每个元素值只会被访问一次，因此时间复杂度为O(n^2)
值得注意的是，没有过的很重要的原因是long long的初始值开小了，学到了应该开1e18
但是改了这一点使用新构建数组的模拟还是没有过，迷惑+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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 5010;;
int n;
LL a[N];

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    LL res = 1e18; // long long 的最大初始值
    for(int i=1; i<=n; i++)
    {
        LL num = 0, pre = 0;
        for(int j=i+1; j<=n; j++)
        {
            // 对于每次循环，需要保证pre刚刚满足由a[j]的倍数并且超过之前的per
            // 因此原先的per对a[j]取模，这个时候再加上一个a[j]就刚刚好超过per了
            // 于是per需要更新的大小就是单位量a[j]和相差量的差
            pre += a[j] - pre%a[j];
            num += pre / a[j]; // 计算达到这个结果需要多少单位个a[j]
        }
        pre = 0;
        for(int j=i-1; j>=1; j--)
        {
            pre += a[j] - pre%a[j]; // 反方向来一遍，思路一样
            num += pre / a[j];
        }
        res = min(res, num);
    }
    cout << res << endl;
    return 0;
}