https://codeforces.com/contest/1734

#822

A：

题目：

现在有 n 个棍子，都有各自的长度，现在可以执行以下任意操作。

选择一个棍子，使它的长度 - 1，保证每次操作后棍子的长度都为 1.

问你最小操作次数使得，从 n 中取得三个棍子，让他们构成等边三角形。

思路：

肯定是长度差距最小的放一起，然后进行操作。所以我们先排个序，然后遍历取连续的 3 个来找答案

代码

void solved()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    sort(nums, nums + n);

    int sum = 1e9;

    for(int i = 0; i < n; i++)
    {
        if(i + 2 < n)
        {
            int a = nums[i], b = nums[i + 1], c =  nums[i + 2];

            sum =  min(sum, b - a + c - b);
        }
    }

    cout << sum << endl;
}

B：

题目：

略。

思路：

构造几组就会发现，中间的都可以由上面的继承下来，所以只需要两边加一个火把即可

代码

void solved()
{
    cin >> n;

    if(n == 1)
    {
        cout << 1 << endl;
        return ;
    }

    if(n == 2)
    {
        cout << 1 << endl;
        cout << "1 1" <<endl;
        return;
    }

    cout << 1 << endl;
    cout << "1 1" <<endl;

    for(int i = 3; i <= n; i++)
    {
        cout << 1 << " ";
        for(int j = 0; j <= i - 3; j++)
        {
            cout << 0 << " ";
        }
        cout << 1 << " ";
        cout << endl;
    }

}

C

题目:

现在存在一个整数集合 S ， 1 , 2 ,3 ~ n;

现在存在以下操作：

​ 选择一个数字 k ，且 S 中存在 k 的倍数，那么我们就从 S 中删除 K 的最小倍数。 代价为 k。

​ 现在给出一个 S 的 子集 T， 字符串的每一位，如果是1，表示 i 没被删，否则 被删。

​ 现在问你最小的代价使得 S 转化为 T

思路：

贪心地来说，最好使用最小的 k， 来除去每个数，但是 k 是除去集合中最小的倍数，所以如果，当前要除的数，在它前一个的 k 的倍数，如果没有背除，那么就不能使用当前 k。

所以我们枚举 k 来每次删去 k 的倍数，从小到大枚举，这样如果遇到不能删除的数字，那么后面的也不用考虑了。

复杂度 O（n * log(n)）

代码

void solved()
{

     memset(st, 0, sizeof st);

    cin >> n;
    char s[N];
    cin >> s + 1;

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j += i)
        {
            if(s[j] == '1') break;
            else if(s[j] == '0')
            {
                ans += i;
                s[j] = '#';
            }
        }
    }

    cout << ans << endl;

}

D：

题目：

现在存在 n 个史莱姆在数轴上，现在第 i 个史莱姆在 第 i 个位置，血量为 i，i 可以为 负数。

现在给出一个 k， 你可以控制第 k 个史莱姆，每次可以向左向右，如果说下一个位置存在一个史莱姆，那么把他们的血量相加。成为一个新的史莱姆。

如果说你在任意时刻，血量变成负数，那么游戏输掉。

如果说你可以移动到 0 或者 n + 1 个位置时候，你就赢得了比赛。

现在问你能否赢得比赛：

思路：

因为我们要保证我们的血量始终为正数，所以每次都尽量向左向右取得血量相加。

假设我们一开始只向右走，走到第 i 个位置，如果 第 i + 1 个位置，我们血量为负数，这时候我们不能走了。

我们想加点血量来走，那么就考虑走左边能不能加点血量。因为样例 4 ，所以我们最优解是在血量最多的时候，向左走是最优的。

所以维护一个向右走最大值，这样假设在最大值时向左走即可。

这样向左一直走，直到走到下一个位置血量相加后为负数，那么我们只需要维护一个走左边血量的最大值即可。

假设左一直走到头，那么游戏胜利，如果没有，判断一下右边的算上左边加的血量还够不够向右走，如果不够那么说明游戏结束。

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >>a[i];

    int l = m - 1;
    int r = m + 1;
    int sumr  = a[m];
    int suml = 0;

    int mxxr = a[m];
    int mxxl = 0;

    if(a[m] < 0)
    {
        cout << "NO" << endl;
        return;
    }

    while(l >= 1 && r <= n)
    {

        // 向右一直走，走到不能走为止。
        while(r <= n && sumr + a[r] + mxxl >= 0) sumr += a[r], mxxr = max(mxxr, sumr), r++;

        //如果一直走，那么赢了
        if(r > n) break;

        //如果停下来了，那么向左走加点血。
        while(l >= 1)
        {

            //向左走走到不能走为止。
            if(suml + mxxr + a[l] < 0) break;

            //维护一下左边走的最大值
            suml += a[l];
            mxxl =  max(mxxl, suml);
            l--;

            //走到头那么赢了
            if(l == 0)
            {
                cout << "YES" << endl;
                return ;
            }
        }


        //判断一下左边走完了右边还能不能走，不能走那么输了，否则进入下个循环，右边继续走。
        if(mxxl + sumr + a[r] < 0)
        {
            cout << "NO" <<endl;
            return;
        }

    }


    cout << "YES" << endl;



}