【Codeforces】Codeforces Round #53

Problem A (div 2)

照着它说的做就行了。
时间复杂度为

#include <iostream>
#include <algorithm>

using namespace std;

int w[4], h[4];

void Roll(int &w, int h0, int h1)
{
    while(h0 >= h1)
    {
        w += h0;
        h0--;
    }
}

int main()
{
    for(int i = 0; i < 3; i++)
    {
        cin >> w[i] >> h[i];
    }
    if(h[1] < h[2])
    {
        swap(w[1], w[2]);
        swap(h[1], h[2]);
    }
    if(h[0] >= h[1])
    {
        Roll(w[0], h[0], h[1]);
        w[0] -= w[1];
        w[0] = max(0, w[0]);
        h[0] = h[1] - 1;
    }
    if(h[0] >= h[2])
    {
        Roll(w[0], h[0], h[2]);
        w[0] -= w[2];
        w[0] = max(0, w[0]);
        h[0] = h[2] - 1;
    }
    Roll(w[0], h[0], 0);
    cout << w[0] << endl;
    return 0;
}

Problem B (div 2)

事实上只需要搭出一个a*b的网格的左上角的边（也就是a+b条边），那么便可以构建出a*b个以内的任意个数的正方形格子。
于是问题便变为，给定n，求出最小的a+b使得a*b>=n
那么，假设len=a+b，二分答案即可。
时间复杂度为

#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

bool check(LL len, LL n)
{
    LL maxn = (len / 2) * (len - len / 2);
    return maxn >= n;
}

int main()
{
    LL n;
    cin >> n;

    LL l = 2, r =  2*n;
    while(l < r)
    {
        LL mid = (l + r) >> 1;
        if(check(mid, n))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}

Problem C (div 2)

首先需要需要判断是否是impossible。当最小长度大于k，或者最大长度小于k，那么认为其为Impossible的。
接着就是如何构造出符合要求的串。这个只需要贪心地尽可能用掉前面的*和?就行了。
时间复杂度为

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define INF 200000

string s;
vector<int> stat;

int Caclu_min()
{
    int ret = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if(stat[i] == 0)
        {
            ret++;
        }
    }
    return ret;
}

int Caclu_max()
{
    int ret = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if(stat[i] == 2)
        {
            return INF;
        }
        ret++;
    }
    return ret;
}

string Solve(int k)
{
    string ret;
    if((k < Caclu_min()) || (k > Caclu_max()))
    {
        ret = "Impossible";
        return ret;
    }

    int min_len = Caclu_min();
    for(int i = 0; i < s.length(); i++)
    {
        if(stat[i] == 0)
        {
            ret += s[i];
        }
        else if(stat[i] == 1)
        {
            if(k > min_len)
            {
                ret += s[i];
                k--;
            }
        }
        else
        {
            while(k > min_len)
            {
                ret += s[i];
                k--;
            }
        }
    }
    return ret;
}

int main()
{
    string input_s;
    cin >> input_s;
    for(int i = 0; i < input_s.length(); i++)
    {
        if(input_s[i] == '?')
        {
            stat[s.length() - 1] = 1;
        }
        else if(input_s[i] == '*')
        {
            stat[s.length() - 1] = 2;
        }
        else
        {
            s += input_s[i];
            stat.push_back(0);
        }
    }

    int k;
    cin >> k;

    cout << Solve(k) << endl;
    return 0;
}

Problem A (div 1)

这个事实上可以贪心地将每个点的权值安排在【不跟已知的冲突的情况下，点的权值分布尽可能往根部走】

于是就需要两遍遍历操作：

• 第一次遍历从末尾往根部遍历，将所有未知的全部换成其儿子们的所有已知的的最小值
• 第二次遍历从根部往末尾遍历并计算。如果此时仍为-1的话，那么默认来计算

注意判断impossible的情况。
时间复杂度为

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

int p[100005];
int s[100005];
int a[100005];

vector<int> e[100005];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 2; i <= n; i++)
    {
        scanf("%d", &p[i]);
        e[p[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
    }

    bool flag = true;

    for(int i = n; i >= 1; i--)
    {
        if(s[i] != -1)
        {
            for(int j = 0; j < e[i].size(); j++)
            {
                if(s[e[i][j]] == -1)
                {
                    continue;
                }
                if(s[i] > s[e[i][j]])
                {
                    flag = false;
                    break;
                }
            }
        }
        else
        {
            for(int j = 0; j < e[i].size(); j++)
            {
                if(s[i] == -1)
                {
                    s[i] = s[e[i][j]];
                }
                else if(s[e[i][j]] != -1)
                {
                    s[i] = min(s[i], s[e[i][j]]);
                }
            }
        }
    }
    
    if(flag)
    {
        for(int i = 1; i <= n; i++)
        {
            if(s[i] == -1)
            {
                a[i] = 0;
                s[i] = s[p[i]];
            }
            else
            {
                if(s[i] < s[p[i]])
                {
                    flag = false;
                    break;
                }
                a[i] = s[i] - s[p[i]];
            }
        }
    }

    if(flag)
    {
        LL ans = 0;
        for(int i = 1; i <= n; i++)
        {
            ans += a[i];
        }
        printf("%lld\n", ans);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}

后续待补充