延迟罐罐

显然直接枚举找个答案就好。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    for (int x = 1;; x++)
    {
        if (n + x == min(756, m + x / 4))
        {
            cout << n + x;
            return 0;
        }
    }
    return 0;
}

圈个矩形

很多后期选手一看就二分，但是没有注意到 $mid\times (n-mid)$ 会超 long long 直接就没了。

实际上因为最终乘积的小于 $10^{16}$，所以较短的那条边必然小于 $10^8$，所以直接枚举就好了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, L, R;
signed main()
{
    cin >> n >> L >> R;
    for (int i = 1; i <= n / 2; i++)
    {
        int j = n - i;
        if (i * j > R)
            break;
        if (L <= i * j && i * j <= R)
        {
            cout << i << " " << j << "\n";
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}

因式分解

有三个小考点，怎么输入，怎么输出第一行，怎么输出第二行。

输入可以用 char 吃掉多余单个字符，然后读整数的方法读每个整数。也可以直接不停读字符然后处理。

第一行的内容就是要细致，按题目要求一点点处理。

第二行很多同学会用一元二次方程求根公式。但实际先排除无解和都是解之后，可以看最初给的形式 $(ix+n)(jx+m)$，就确定了根就两个 $-\frac{n}{i},-\frac{m}{j}$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
char t;
int i, n, j, m;
signed main()
{
    cin >> t >> i >> t >> t >> n >> t; // (ix+n)
    cin >> t >> j >> t >> t >> m >> t; // (jx+m)
    int a = i * j;
    int b = i * m + j * n;
    int c = n * m;
    if (a != 0)
    {
        if (a != 1)
            cout << a;
        cout << "x^2";
    }
    if (b != 0)
    {
        if (a != 0)
            cout << "+";
        if (b != 1)
            cout << b;
        cout << "x";
    }
    if (c != 0)
    {
        if (a != 0 || b != 0)
            cout << "+";
        cout << c;
    }
    cout << "\n";
    bool flag = false;
    int ans;
    if (a == 0 && b == 0)
    {
        if (c == 0)
            flag = true, ans = 33;
    }
    else if (a == 0)
    {
        if (c % b == 0)
            flag = true, ans = -c / b;
    }
    else
    {
        // (ix+n)(jx+m)
        if (n % i == 0)
            flag = true, ans = -n / i;
        if (m % j == 0)
            flag = true, ans = -m / j;
    }
    if (flag)
        cout << ans << "\n";
    else
        cout << "No\n";
    return 0;
}

无敌闯关

这题的原题是我收藏已久的 P7167 [eJOI2020 Day1] Fountain

30 分

直接暴力枚举就好。

#include <bits/stdc++.h>
using namespace std;
int n, m, T, k;
// 敌人战斗力，敌人胆量
int a[100000 + 5], b[100000 + 5];
// 返回从 pos 开始的游戏结局
int f(int pos)
{
    //cout << "====" << pos << "====\n";
    int health = n;
    int power = 0;
    while (pos <= m)
    {
        // 吓跑直接不战斗
        if (b[pos] <= power)
        {
            pos++;
            continue;
        }
        // 战斗结算
        health -= a[pos];
        power = b[pos];
        //cout << pos << ":" << health << "," << power << "\n";
        if (health <= 0)
            return pos;
        pos++;
    }
    return 0;
}
int main()
{
    cin >> n >> m >> T;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= T; i++)
    {
        int k;
        cin >> k;
        cout << f(k) << "\n";
    }
    return 0;
}

60 分

因为此时肯定是一个个打过去，所以可以直接处理个前缀和，然后二分就能找到结束位置了。

100 分

都在注释里了。也可以去原题看看题解。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, T, k;
const int MAXN = 100000;
// 敌人战斗力，敌人胆量
int a[MAXN + 5], b[MAXN + 5];
// f[i][j] 记录 i 后面第 2^j 个是谁
// g[i][j] 记录 i 开始后面的 2^j 个敌人的战斗力之和
int f[MAXN + 5][25];
int g[MAXN + 5][25];
// 单调栈计算每个敌人下一个胆量大于他的在哪儿
stack<int> s;
void init()
{
    // 预处理 2^0 层
    for (int i = m; i >= 1; i--)
    {
        // 去掉栈顶小于等于 b[i] 的
        while (!s.empty() && b[s.top()] <= b[i])
            s.pop();
        // 现在的栈顶就是下一个大于 b[i] 的位置
        g[i][0] = a[i];
        if (s.empty())
            f[i][0] = 0;
        else
            f[i][0] = s.top();
        // 当前编号放入单调栈
        s.push(i);
    }
    // 处理 2^k 层
    for (int k = 1; k <= 20; k++)
        for (int i = 1; i <= m; i++)
        {
            int ii = f[i][k - 1]; // 往后 2^{k-1} 层的位置
            f[i][k] = f[ii][k - 1];
            g[i][k] = g[i][k - 1] + g[ii][k - 1];
        }
}
// 计算从 pos 位置开始，初始血量为 n，最终打败的是谁
int cal(int pos)
{
    int health = n;
    for (int k = 20; k >= 0; k--)
    {
        if (g[pos][k] < health)
        {
            health -= g[pos][k];
            pos = f[pos][k];
        }
    }
    return pos;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> m >> T;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    init(); // 预处理 f,g
    for (int i = 1; i <= T; i++)
    {
        int k;
        cin >> k;
        cout << cal(k) << "\n";
    }
    return 0;
}