不是签到

拼凑出一个ACM需要裁剪出个的纸，模拟即可。

int main(){
    int n, m;
    cin >> n >> m;
    cout << (n / 5) * (m / 5) / 3;
    return 0;
}

在ACM里打ACM

模拟

注意到时间是有序的，所以可以直接使用 按照队伍名进行分类放置。

对每个队伍名，按照题目所给的 赛制进行模拟，注意反复提交通过的题和提交多次但最终未通过的情况。

注意大数据量读入时对程序效率的影响，建议关同步流。

struct node {
    string s;
    char   ch;
    int    flag, t;
};

void solve() {
    int n;
    cin >> n;
    std::vector<node>   temp(n + 1);
    vector<vector<int>> edge(n + 1);
    int                 ans = 0;
    map<string, int>    wz;
    string              xst;
    int                 ed_tm, ed_time;

    for (int i = 1; i <= n; i++) {
        cin >> temp[i].s >> temp[i].ch >> temp[i].flag >> temp[i].t; // 采用结构体输入
        if (!wz[temp[i].s]) wz[temp[i].s] = ++ans; // 先将队伍名转换成一个特定的数字方便后续存储
        edge[wz[temp[i].s]].push_back(i);          // 按队伍名存储
    }
    for (int i = 1; i <= ans; i++) // 遍历每个队伍
    {
        vector<int>  vec(14);
        vector<bool> pd(14); // 判断是否过题
        pd.clear();
        vec.clear();
        int cnt = 0, js = 0, sum = 0;
        for (int j : edge[i]) // 遍历该队的评测队列
        {
            if (temp[j].flag == 1) // 过题
            {
                if (pd[int(temp[j].ch) - 64] == false) // 是第一次过
                {
                    cnt += vec[int(temp[j].ch) - 64]; // 计算总的错误尝试次数
                    sum += temp[j].t;                 // 加上解题用时
                    js++;                             // 通过题目数
                    pd[int(temp[j].ch) - 64] = true;  // 标记这道题已过
                }
            } else vec[int(temp[j].ch) - 64]++; // 未过题则加一次该题错误尝试次数
        }
        if (ed_tm < js || (ed_tm == js && ed_time >= sum + cnt * 20))       // 判断是否超过当前冠军
            xst = temp[edge[i][0]].s, ed_tm = js, ed_time = sum + cnt * 20; // 更新冠军答案
    }
    cout << xst << " " << ed_tm << " " << ed_time << endl;
}

民以食为天

知道 两点的坐标则很容易求出 点。

知道 点， 点的坐标则很容易求出 的横纵坐标。

通过 即可很容易求出

由于保证 点坐标为整数，观察数据范围可知使用整型即可。

void solve() {
    int ax, ay, cx, cy, dx, dy;
    cin >> ax >> ay >> cx >> cy >> dx >> dy;
    int bx = cx - ax, by = cy - ay; // 两个端点作差，相当于将AC平移到原点
    bx /= 3, by /= 3;               // 求出B点相对于AC线段的坐标
    bx += ax, by += ay;             // 加上A点的坐标即为B点实际坐标
    cout << (dx - bx) * (dx - bx) + (dy - by) * (dy - by) << endl;
}

生电难题

贪心，枚举，二分

显然想要让花费时间最少，先建好农场再进行献祭是最优的，关键就是建多少农场可以达到最优。 我们可以枚举建造农场的个数，可以发现最坏情况下农场的个数不会超过 个，因此可以直接枚举建造农场的数量，然后再解出之后需要多少时间。

void solve() {
    ll s, k, t1, t2, ans = 2e9;
    cin >> s >> k >> t1 >> t2;
    ll v = k, res = 0, t = t1;
    while (res < s) {
        ll cost  = (t2 * (s - res) + v * t2) / (v * t2 + 1);
        ans      = min(ans, t + cost);
        res     += t1 * v;
        t       += t1;
        v       += k;
    }
    cout << ans;
}

答案显然具有单调性，我们还可以直接进行二分答案。 二分时算出建造的农场数量，设二分答案为，显然数量为 和 时最优，分别计算取最大即可。 二分时注意上界，防止爆long long。

ll s, k, t1, t2;
ll calc(ll c, ll t) {
    ll res  = c * t - t1 * c * (c + 1) / 2;
    res    *= k;
    res    += (t - c * t1) / t2;
    return res;
}

bool chk(ll t) {
    ll c   = max(t / t1, 1LL);
    ll res = calc(c, t);
    if (c > 1) {
        res = max(res, calc(c - 1, t));
    }
    return res >= s;
}

void solve() {
    cin >> s >> k >> t1 >> t2;
    ll l = t1, r = t1 + 1 + s / k;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (chk(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << l;
}

完全弹性碰撞

模拟，数学，思维。

数据范围比较小，可以直接模拟球的运动，先把运动距离求出来后直接进行模拟。 球的碰撞可以直接看成穿过，位置顺序不会改变，把两个球独立来算后再把小的放在前面即可。 可以利用取模来算出答案。

int L, v, k, xa, ta, xb, tb;
int calc(int x, int t) {
    x = ((x + t * v * k) % L + L) % L;
    x = min(x, L - x);
    return x;
}

void solve() {
    cin >> L >> v >> k >> xa >> ta >> xb >> tb;
    L  *= 2;
    xa  = calc(xa, ta);
    xb  = calc(xb, tb);
    if (xa > xb) swap(xa, xb);
    cout << xa << ' ' << xb;
}

逆

数学

由于题目问的是 是否满足不小于 个不同的正整数 能够使得 所以我们只需找出 的解的个数就可以了。

观察 这条式子，可以得出两个结论：

①考虑除数和余数的关系，我们得出

②对原式稍加变形得出

结合上述两个结论，则该问题可以转化为找 中大于 的因子。

int  n, q, k, r;
void solve() {
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        cin >> k >> r;
        int ans = 0;
        for (int j = 1; j * j <= n - r; j++) {
            if ((n - r) % j == 0) {               // j是(n-r)的因子
                if (j > r) ans++;                 // 如果j>r,那么记录个数
                if ((n - r) / j != j)             // 判断(n-r)是否为平方数
                    if (((n - r) / j) > r) ans++; // 若不是且另一个因子也大于r，那么记录个数
            }
        }
        if (ans >= k) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
}

老树也有几颗新芽

模拟，

首先很容易想到，最坏情况下，亡语会尽可能叠加到已有亡语层数较少的怪身上，我们也应优先解决亡语层数较少的怪；在这个思路下，对于只普通的怪，若干操作后总是会得到只怪身上有层亡语的情况，然后消灭这只怪，将问题转化为消灭只普通的怪；

我们用表示将只怪全部消灭的操作次数，特别地，定义；用 表示某只怪身上有层亡语；那么需要研究的是到的推导关系；

接下来可以尝试简单的操作以寻找规律；例如当时，根据先前分析的规律，枚举\textbf{亡语层数尽量平均时最小的亡语层数}，一定会经过以下几种状态：、、、，将其标号为状态至；注意到，从状态到达状态的过程实质上是先消灭只""然后操作了次，从状态到达状态的过程实质上是先消灭然后操作了次，从状态到达状态的过程实质上是先消灭""然后操作了次；那么找出所有这样的状态，就可以在已知至的情况下算出；

考虑枚举至作为每个状态最小的亡语层数，然后枚举至作为每个状态场上怪的数量，就可以以的复杂度完成的计算，全局时间复杂度，参考代码略；

接下来进行优化，设；普遍情况下，若为的因数，将不是的因数；因此，在计算的分步中，会出现状态""，在计算的分步中会出现状态""，两种状态相比较，差值为；即当为的因数时，将对有一次贡献；对于特殊情况与，在我们先前的定义下，它们并不需要特殊处理；

枚举的每个因数较为复杂，可以对于每个，枚举所有的倍数，为其加上，总复杂度；

constexpr int N = 1e6 + 5, M = 1e9 + 7;
ll        a[N];

void solve() {
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        a[i]++;
        for (int j = i; j <= n; j += i) (a[j] += a[i - 1]) %= M;
        (ans += a[i]) %= M;
    }
    cout << ans << endl;
}

刷材料

dp

考虑 设 表示当前拥有 个原材料时的方案数，设初始状态种数为 分类讨论它能往更高数量的原材料转移的结果：

设掉落的原材料数量为 需要大于等于 个原材料，最终答案数为

若 那么

若 那么

注意对 和 进行取模操作，即它们执行完一次累加时都取模一次。

注意数据范围，由于 之前是没有用的，所以可以先用 减去 再进行操作。

constexpr ll MOD = 1e9 + 7;
int          n, m, k;
ll           x[105], dp[200005];

void solve() {
    cin >> n >> m >> k;
    m -= n;
    for (int i = 1; i <= k; i++) cin >> x[i];
    ll ans = 0;
    dp[0]  = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= k; j++)
            if (i + x[j] < m) dp[i + x[j]] += dp[i], dp[i + x[j]] %= MOD;
            else ans += dp[i], ans %= MOD;
    }
    cout << ans << endl;
}

I. 取石子

注意到，从初始状态到某一堆石子被取完的过程中，取石子的位置序列构成一个循环，且最小周期不大于,所以只需要按照题意模拟，并记录当前取过的堆中石子数量的最小值与最小值的位置（注意只有在当前取的堆的石子数量严格小于之前取的堆的石子数量的最小值时，才更新最小值与最小值的位置），直到下一堆被取的石子已经被取过，此时最小值的位置就是答案。

constexpr int N = 1e9 + 7;

void solve() {
    int n, k, s;
    cin >> n >> k;
    vector<int> vt(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> vt[i];
    }
    cin >> s;
    s--;
    int pos = 0;
    int now = (s + k) % n;
    int mn  = N;
    do {
        if (vt[now] < mn) {
            mn  = vt[now];
            pos = now;
        }
        now = (now + k) % n;
    } while (now != (s + k) % n);
    cout << pos + 1 << "\n";
}

J. 纸牌游戏

随着游戏的进行，双方手中的牌的点数之和有以下规律：

1.双方手中的牌的点数之和的差不变，因为每次出牌过后双方的点数和都减去一个相同的数字

2.每一方的点数和都小于上次出牌时的点数和，因为每张牌的点数至少为

3.不会有任意一方的点数和小于

综合这3个规律，假设 的点数和为 ， 为 ，且 ，那么游戏结束时的状态一定是Alice的点数和为 , Bob 的点数和为 ，所以只需要求出双方各自的点数和并比较大小即可。

void solve() {
    int n, m;
    cin >> n >> m;
    ll suma = 0, sumb = 0;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        suma += temp;
    }
    for (int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        sumb += temp;
    }
    if (suma > sumb) cout << "Alice\n";
    else if (suma < sumb) cout << "Bob\n";
    else cout << "draw\n";
}

登塔

用变量维护以下几个信息，模拟即可

：闪电球的数量；

：闪电球的基本伤害；

：强化结束回合。

：最终伤害可能会超过 的范围，因此伤害使用 类型。

void solve() {
    int n;
    cin >> n;

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

    int sign   = -1;
    int damage = 3;
    int count  = 0;

    ll res = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            res += 6;
            if (i <= sign) res += 3;
        } else if (a[i] == 2) {
            sign = i + 2;
        } else if (a[i] == 3) {
            count++;
        } else damage += 2;

        res += 1LL * damage * count;
    }

    cout << res;
}

这道题，或许开启了四的时代

暴力，最短路，

本题的数据范围相对较小，多种恰当的暴力和搜索都能通过，这里给出其中一种解法；

若使用及以下数量个能组成的数已经全部枚举完毕，那么在枚举个能组成的数时，考虑对于的所有无序正整数对，枚举个能组成的所有数分别与个能组成的所有数进行一次运算，即可暴力得到个能组成的所有数

map<ll, ll> ans;
vector<ll>  num[50];

void solve() {
    int n;
    cin >> n;
    if (n == 4) {
        cout << 1 << endl;
        return;
    }

    num[1].push_back(4);
    ans[4] = 1;


    for (int i = 2; i < 50; i++) {
        for (int j = 1; j <= i / 2; j++) {
            for (int p = 0; p < num[j].size(); p++) {
                for (int q = 0; q < num[i - j].size(); q++) {
                    ll k;
                    k = num[j][p] + num[i - j][q];
                    if (k < 1e9 && !ans[k]) {
                        num[i].push_back(k);
                        ans[k] = i;
                        if (n == k) {
                            cout << i << endl;
                            return;
                        }
                    }
                    k = num[j][p] * num[i - j][q];
                    if (k < 1e9 && !ans[k]) {
                        num[i].push_back(k);
                        ans[k] = i;
                        if (n == k) {
                            cout << i << endl;
                            return;
                        }
                    }
                    k = abs(num[j][p] - num[i - j][q]);
                    if (k && k < 1e9 && !ans[k]) {
                        num[i].push_back(k);
                        ans[k] = i;
                        if (n == k) {
                            cout << i << endl;
                            return;
                        }
                    }
                    if (num[j][p] >= num[i - j][q]) {
                        if (!(num[j][p] % num[i - j][q])) {
                            k = num[j][p] / num[i - j][q];
                            if (k && k < 1e9 && !ans[k]) {
                                num[i].push_back(k);
                                ans[k] = i;
                                if (n == k) {
                                    cout << i << endl;
                                    return;
                                }
                            }
                        }
                    } else {
                        if (!(num[i - j][q] % num[j][p])) {
                            k = num[i - j][q] / num[j][p];
                            if (k && k < 1e9 && !ans[k]) {
                                num[i].push_back(k);
                                ans[k] = i;
                                if (n == k) {
                                    cout << i << endl;
                                    return;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}