Educational Codeforces Round 125 (Rated for Div. 2) (A-D题解)

源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

更好的阅读体验: Educational Codeforces Round 125 (Rated for Div. 2) (A-D题解) - Abmcar’s 茶水间

可以知道最多只需要执行2次,一次移动横坐标,一次移动纵坐标

而当 x 2 + y 2 sqrt{x^2+y^2} x2+y2 ​为整数时 只需要一次操作即可

void solution()
{
    cin >> n >> m;
    if (n == m && m == 0)
    {
        cout << 0 << endl;
        return;
    }
    int tmp = n * n + m * m;
    int tt = int(sqrt(tmp)) * int(sqrt(tmp));
    if (tt == tmp)
        cout << 1 << endl;
    else
        cout << 2 << endl;
}

由于让求最大值,因此我们知道肯定选择最多的+操作最好

因此我们直接贪心选择+操作,当且仅当采用+操作过大时才使用-操作

void solution()
{
    cin >> n >> b >> x >> y;
    int nowNum = 0;
    int nowAns = 0;
    for (int i = 1; i <= n; i++)
    {
        if (nowNum + x <= b)
        {
            nowNum += x;
            nowAns += nowNum;
        }
        else
        {
            nowNum -= y;
            nowAns += nowNum;
        }
    }
    cout << nowAns << endl;
}

题目不难理解,很快我们就可以按照题目写出一个暴力,在写暴力的过程中用了stack判断合法,用reverse判断回文,信心满满交上去,结果

Time limit exceeded on test 5

回过头来再仔细思考题目,我们发现,当前缀为

((

))

()

时,均可以被删除

只有)(不可以

观察)(,发现只有在添加(时,才不合法,如果添加一个),则立刻合法

因此,我们可以用vector来判断,若开头为’('或者开头等于末尾即可删

void solution()
{
    string oriS;
    int cnt = 0;
    cin >> n;
    cin >> oriS;
    vector tmp;
    for (int i = 0; i < n; i++)
    {
        tmp.push_back(oriS[i]);
        if (tmp.size() > 1)
        {
            if (tmp[0] == '(' || tmp[0] == tmp.back())
            {
                tmp.clear();
                cnt++;
            }
        }
    }
    cout << cnt << " " << tmp.size() << endl;
}

值得注意的有这么几点

任何一个单位都不能被杀队伍中只能有1种类型的单位

因此,选择更多单位的收益只有攻击力

当 H i D e > H e D i frac{H_i}{D_e} > frac{H_e}{D_i} De​Hi​​>Di​He​​时,可以胜利(i为自己,e为敌人)

可以得到 H i ∗ D i > H e ∗ D e H_i*D_i > H_e*D_e Hi​∗Di​>He​∗De​

由于一个小队只能有一种类型

我们可以把所有代价对应的最大 H i ∗ D i H_i*Di Hi​∗Di表示出来,之后对于每一个敌人,二分处理即可

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, c;
    cin >> n >> c;
    vector cost(n), damage(n), health(n);
    vector maxValue(c + 1);
    for (int i = 0; i < n; i++)
    {
        cin >> cost[i] >> damage[i] >> health[i];
        maxValue[cost[i]] = max(maxValue[cost[i]], damage[i] * health[i]);
    }
    for (int i = 1; i <= c; i++)
        for (int j = 2; j * i <= c; j++)
        {
            maxValue[i * j] = max(maxValue[i * j], maxValue[i] * j);
        }
    for (int i = 1; i <= c; i++)
        maxValue[i] = max(maxValue[i - 1], maxValue[i]);
    int m;
    cin >> m;
    while (m--)
    {
        int td, th;
        cin >> td >> th;
        int nowValue = td * th;
        if (nowValue >= maxValue.back())
        {
            cout << "-1" << endl;
            continue;
        }
        cout << upper_bound(maxValue.begin(), maxValue.end(), nowValue) - maxValue.begin() << endl;
    }
    return 0;
}