Codeforces Round #822 (Div. 2)

A.Select Three Sticks

题目大意

给定$n$根木棍，长度分别为正整数$a_1,a_2,\cdots ,a_n$，可做任意次操作，每次操作可将一根木棍的长度加一或减一，问最少进行多少次操作后可以从这$n$根木棍中选出三根构成等边三角形

解题思路

签到题
先排序，然后试试每组连续的三根木棍，对于每一组内部的最优解肯定是都变成中间的那个木棍的长度，那么操作次数即$(a_{i+1}-a_i)+(a_i-a_{i-1})$

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::map<int, int> S;
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
            std::cin >> a[i];
        std::sort(a + 1, a + n + 1);
        LL ans = INF;
        for (int i = 2; i <= n - 1; ++i)
            ans = std::min(ans, a[i + 1] - a[i - 1]);
        std::cout << ans << '\n';
    }
    return 0;
}

B.Bright, Nice, Brilliant

题目大意

有$n$层的金字塔，第$i$层有$i$个房间
位于$(i,j)$的房间可以走到位于$(i+1,j)$和$(i+1,j+1)$的房间
对于每个房间，可以选择放一个火把或者不妨火把
定义房间$(i,j)$的亮度：从$(1,1)$出发到达$(i,j)$的所有可能路径中，有火把的房间数量
定义金字塔的亮度:每一层第一个房间的亮度之和
给出一种放置火把的方案，使得每一层层内的房间的亮度相同，并且让金字塔亮度最大

解题思路

构造题
说下我构造的思路：
因为每一层层内的房间的亮度相同
所以第$i$层的亮度一定小于等于$i$，因为到达$(i,1)$的路径上只有$i$个房间
要让金字塔亮度最大，先假设第$i$层的亮度就是$i$试试
那么就是说每层的第一个房间里面都要放置火把
同理，每层的最后一个房间也都要放置火把
然后就可以惊奇地发现这道题已经做完了，其他房间都不放火把就可以了

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                if (j != 1 && j != i)
                    std::cout << 0 << ' ';
                else
                    std::cout << 1 << ' ';
            }
            std::cout << '\n';
        }
        // std::cout << '\n';
    }
    return 0;
}

C.Removing Smallest Multiples

题目大意

给定一个$n$，定义一个正整数集$S=\lbrace 1,2,3\cdots n\rbrace$
再给定一个集合$T$，这个$T$是$S$的子集
你可以在$S$上做任意次操作：
选择一个$k$，删去集合中最小的且是$k$的整数倍的数，代价为$k$
请问最少需要多少代价，能把$S$变为$T$

解题思路

很显然的贪心，作为$C$题有些简单了
每个需要被删掉的元素都肯定以尽量小的代价删掉
那么枚举代价$k$，让每个代价尽量删多一点元素

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 1e6 + 10; //经典因为数组开小了WA了第一发
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
std::string str;
bool st[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        memset(st, false, sizeof st);
        std::cin >> n >> str;
        LL cost = 0;
        str = "?" + str;
        for (int i = 1; i <= n; ++i) //枚举代价k
        {
            for (int j = i; j <= n; j += i) //枚举k的整数倍的元素
                if (str[j] == '0') //如果这个元素需要删掉
                {
                    if (!st[j]) //之前是否已经被更小的因子删掉
                        cost += i;
                    st[j] = true; //标记这个元素已经被删掉
                }
                else 
                    break;
        }
        std::cout << cost << '\n';
    }
    return 0;
}

D.Slime Escape

题目大意

有$n$个史莱姆排成一排，在数轴上的位置依次为$1,2\cdots ,n$，生命值依次为$a_1,a_2\cdots ,a_n$，注意生命值可能是负数
你是第$k$个史莱姆(保证$a_k\geq 0$)
数轴上$0$和$n+1$位置是出口，你要想办法走到其中一个出口
你每一步可以向左移动一位或者向右移动一位，如果移动到达的位置上有另一个史莱姆，你必须吃掉它。吃掉这个史莱姆，你的生命值就会加上它的生命值(再强调一下被吃掉的这个史莱姆的生命值可能是负数，也就是吃掉它以后你的生命值会减少)
但在移动过程中如果你的生命值变成负数，你就会立即死掉
问你是否有可能活着走到其中一个出口

解题思路

赛时的数据可能有点弱，乱糊了一百多行，可惜还是没逃过$fst$
不过思路还是比较简单的：
就是先往左边走，如果不能一直走到出口，就掉头往右边走
但是这个掉头走要贪心地掉头走，要在向左走的过程中生命值最高的地方就掉头走(注意掉头走的前提是原本那边走不通)
然后循环往复
想优美地实现还蛮难的，双指针容易写成假的双指针，我大概就是，所以$fst$了

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q, k;
LL a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n >> k;
        for (int i = 1; i <= n; ++i)
            std::cin >> a[i];
        LL initial = a[k]; // 初始生命值
        LL l = k - 1, r = k + 1;
        LL lnow, rnow, lmax, rmax;
        lnow = rnow = lmax = rmax = 0;
        // lnow表示向左走的过程中生命值的变化值
        // lmax表示向左走的过程中生命值的变化值的最大值
        // rnow,rmax同理
        while (l >= 1 && r <= n)
        {
            bool can_move = false; //如果下面两个while都执行不了，说明没有可能走出去了
            while (l >= 1 && initial + lnow + rmax + a[l] >= 0)
            {
                can_move = true;
                lnow += a[l];
                lmax = std::max(lmax, lnow);
                --l;
            }
            while (r <= n && initial + rnow + lmax + a[r] >= 0)
            {
                can_move = true;
                rnow += a[r];
                rmax = std::max(rmax, rnow);
                ++r;
            }
            if (!can_move)
                break;
        }
        if (l == 0 || r == n + 1)
            std::cout << "YES" << '\n';
        else
            std::cout << "NO" << '\n';
    }
    return 0;
}