A（期望通过人数 100，实际通过人数 92）

注意到除了 $1$ 以外，其他数都满足越大越强。

所以可以把 $1$ 视作 $14$ 。

当然，也可以这么写：

a,b=map(int,input().split())
a=(a+11)%13
b=(b+11)%13
if a>b:
    print("Alice")
elif a==b:
    print("Draw")
else:
    print("Bob")

B（期望通过人数 80，实际通过人数 76）

考虑到每一年后账户里的钱大约是计算利息前的 $\dfrac {101}{100}$ ，其增长是指数级的。

因此，虽然 $X$ 最大可以达到 $10^{18}$ ，但是仍然可以通过模拟每一年银行支付利息的规则求出答案。

当然，第二个样例也已经充分说明了这一点。

注意以下两点：

由于 int 变量只能存储 $[-2^{31},2^{31})$ 里的整数，部分数据需要使用 long long 进行存储，其范围是 $[-2^{63},2^{63})$ 。
请不要使用 C++ 中的 pow(a,b) 函数，因为这个函数的返回值是 double，强制转换为整型有可能产生误差，特别是结果非常大的情况下。

参考代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll x;
    cin >> x;
    ll total = 0;
    ll cnt = 100;
    while (cnt < x) {
        ++total;
        cnt += cnt / 100;
    }
    cout << total << "\n";
    return 0;
}

C（期望通过人数 80，实际通过人数 88）

我们需要输入四个字符串，判断这四个字符串中 $\texttt{H}$ 、 $\texttt{2B}$ 、 $\texttt{3B}$ 、 $\texttt{HR}$ 是否各出现至少一次。

这件事实际上就是 $\texttt{H}$ 、 $\texttt{2B}$ 、 $\texttt{3B}$ 、 $\texttt{HR}$ 是否各出现恰好一次。

因此只需要判断四个字符串中是否出现重复的。

请注意输出的 Yes 与 No 的大小写。本次比赛中所有题的输出都是大小写敏感的，这一点在 A 题题面已经提醒得相当明确。

参考代码：

#include <bits/stdc++.h>
using namespace std;
string s[4];
int main() {
    for (int i = 0; i < 4; i++) cin >> s[i];
    for (int i = 0; i < 4; i++)
        for (int l = 0; l < i; l++)
            if (s[i] == s[l]) {
                puts("No");
                return 0;
            }
    puts("Yes");
    return 0;
}

D（20，35）

若 $a=0$ ，有 $c=N$ ， $b$ 可以取任意非负整数。因此有无限组 $(a,b,c)$ ，但是为了让 $a+b+c$ 尽可能小， $b=0$ 最优。

若 $a\in \N^+$ ， $N=a\times 2^b+c\ge2^b$ ， $b$ 的取值范围是 $[0,\lfloor\log_2 N\rfloor]$ ，最多只有 $60$ 种不同的取值。

因此枚举 $b$ ，先考虑 $b=0$ 时， $a+b+c$ 的最小值；再考虑 $b=1$ 时， $a+b+c$ 的最小值...；最终把所有情况合并起来求最小值。

对于一个固定的 $b$ ，有 $N=a\times 2^b+c\Rightarrow a+c=N-a(2^b-1)$ ，因此 $a$ 越大， $a+c$ 越小，那么就应该取 $a=\lfloor \frac N{2^b}\rfloor,c=N\bmod 2^b$ 。

本题同样需要用 long long 存储数据。

选手中常见的错误思路包括但不限于认为 $c=N\bmod 2$ ，显然当 $N=998244355$ 时这个思路得到的 $(a,b,c)$ 并非最优。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    ll a, b, c;
    ll ans = n + 1;
    for (b = 0; b <= 60; ++b) {
        a = n >> b;
        c = n - ((n >> b) << b);
        ans = min(a + b + c, ans);
    }
    cout << ans << "\n";
    return 0;
}

备注：n>>b 相当于将 $n$ 的二进制位的最后 $b$ 位删掉，并把前面的位补上来；n<<b 相当于在 $n$ 的二进制位后面加上 $b$ 个 $0$ 。

E（10，27）

接下来的题目默认大家有一定编程基础（掌握赛前培训的内容），因此可能会略去一些对基本知识的解释。

先把 $n$ 个数存入桶。再枚举哪个数（ $x$ ）在三元组中出现两次，其贡献为 $\displaystyle\binom{val[x]}{2}\times(n-val[x])$

需要开 long long，题面中有相应的提示。

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, num[200010];
int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x ;
        cin>>x;
        num[x]++;
    }
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += 1ll * num[i] * (num[i] - 1) / 2 * (n - num[i]);
    cout << sum;
    return 0;
}

F（5，6）

可以猜测一下题目背景是哪只猪在扫货。

考虑 $m=1$ 时的做法？

因为优先买便宜的东西，把商品按照 $a_i$ 从小到大排序，这样就肯定是按顺序买，直到超出限购再选择下一件商品。

单次回答询问的时间复杂度为 $\mathcal O(n)$

如何回答多次询问？

重要观察： 对于 $c_i$ 的预算，最多只能购买 $c_i$ 件商品。

由于 $c_i\le 2\times 10^5$ ，只有可能购买 最便宜的 $2\times 10^5$ 件商品。

把从小到大排序后的商品分别拆成 $b_i$ 件商品，只取前 $2\times 10^5$ 件。

每次购买的时候一定取的是一个前缀。

预处理前缀和+二分即可。

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, top;
ll b[200010];
array<int, 2> a[200010];
int main() {
    cin>>n>>m;
    for (int i = 1; i <= n; i++) cin>>a[i][0];
    for (int i = 1; i <= n; i++) cin>>a[i][1];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n && top <= 200000; i++)
        while (a[i][1]--) {
            b[++top] = a[i][0];
            if (top == 200000)
                break;
        }
    for (int i = 1; i <= top; i++) b[i] += b[i - 1];
    while (m--) {
        int x = read();
        cout << (upper_bound(b + 1, b + 1 + top, x) - b - 1) << '\n';
    }
    return 0;
}

G（期望通过人数 5，实际通过人数 34）

一开始可能会有一个想法：先给一些人分相同颜色的三朵花，剩下的零碎可以用来给一些人分不同颜色的三朵花。

这个做法似乎可以通过全部的样例，但是显然是错误的。当三朵花的数量分别是 $3,5,5$ 时，这样的策略只能分三个人，然而其实存在一种方案使得能分给四个人。

3 5 5
-----
3 0 0
0 3 0
0 0 3
-----
0 2 2(give up)


3 5 5
-----
1 1 1
1 1 1
-----
1 3 3(two more people)

可以注意到当确定了给 $k$ 人分三朵不同颜色的花时，分别剩下了 $r-k,g-k,b-k$ 朵花，可以再送 $\lfloor\frac{r-k}3\rfloor+\lfloor\frac{g-k}3\rfloor+\lfloor\frac{b-k}3\rfloor$ 个人。

因此只需要枚举 $k$ ，然后取所有情况的最大值即可。

又因为 $k=3$ 和 $k=0$ 的情况等价； $k=4$ 和 $k=1$ 的情况等价 ...

只需要枚举 $k=\{0,1,2\}$ 即可。

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll read() {
    ll x = 0;
    bool flag = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            flag = 0;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return (flag ? x : ~(x - 1));
}
int a, b, c;
int calc(int x) {
    if (x > min({ a, b, c }))
        return 0;
    return x + (a - x) / 3 + (b - x) / 3 + (c - x) / 3;
}
int main() {
    a = read();
    b = read();
    c = read();
    cout << max({ calc(0), calc(1), calc(2) });
    return 0;
}

本题还可以在一开始错误想法的基础上，通过一些神秘的观察和分类讨论解决，在此不展开。绝大多数 AC 本题的同学都没有写出本人预想中的做法。

不过还是感叹大家做这种题的能力大大超出了想象。

H（5，0）

枚举那个出现了至少 $k$ 遍的数码 $x$ ，那么对于第 $i$ 位数码 $s_i$ ，变成 $x$ 需要操作 $|s_i-x|$ 次。

我们关心最少的总操作次数，所以可以把 $n$ 个数码的操作次数排序，取前 $k$ 小的操作次数加起来。对于 $x=[0,9]$ 均进行相同地操作，最终求出最小值即为最少操作次数。

那如果有多种方案，如何求出字典序最小的方案？

可以注意到若 $x$ 是固定的，如果存在 $i,j$ 满足 $|s_i-x|=|s_j-x|$ ，若 $s_i<x<s_j$ ，应该优先把 $s_j$ 变成 $x$ ，反之同理；若 $s_i,s_j<x$ ，那么应该优先把更靠后的下标变成 $x$ ，若 $s_i,s_j>x$ ，那么应该优先把更靠前的下标变成 $x$ 。

因此可以制定一个新的排序方案，还是按照操作次数 $|s_i-x|$ 从小到大排序，只不过当 $|s_i-x|$ 相同的时候，又会按照如上所说的更细规则继续排序。

可以把每一个 $x$ 的最少操作次数和字典序最小的方案求出来，对于若干最小操作次数相同的 $x$ ，直接 $\mathcal O(n)$ 暴力比较方案之间的字典序。

时间复杂度： $\mathcal O(nB\log n)$ ，其中 $B=10$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;
struct PossibleChange {
    int cost, dalta_negative, pos;
    friend bool operator<(const PossibleChange &c1, const PossibleChange &c2) {
        if (c1.cost != c2.cost)
            return c1.cost < c2.cost;
        if (c1.dalta_negative != c2.dalta_negative)
            return c1.dalta_negative;
        if (c1.dalta_negative)
            return c1.pos < c2.pos;
        else
            return c1.pos > c2.pos;
    }
};
pair<int, string> calc(string str, int k, int target) {
    vector<PossibleChange> changes;
    for (int i = 0; i < str.size(); i++) {
        PossibleChange p;
        p.cost = abs(target - str[i]);
        p.dalta_negative = (target < str[i]);
        p.pos = i;
        changes.push_back(p);
    }
    sort(changes.begin(), changes.end());
    int cost = 0;
    for (int i = 0; i < k; i++) {
        cost += changes[i].cost;
        str[changes[i].pos] = target;
    }
    return make_pair(cost, str);
}
int main() {
    int n, k;
    cin>>n>>k;
    string str;
    cin >> str;
    int best = INT_MAX / 2;
    string beststr;
    for (int target = '0'; target <= '9'; target++) {
        pair<int, string> now = calc(str, k, target);
        if (now.first < best || now.first == best && now.second < beststr) {
            best = now.first;
            beststr = now.second;
        }
    }
    cout << best << endl << beststr;
    return 0;
}

本题题目背景中的图片由 Gemini Nano Banana Pro 模型直接生成，只返工了一次。这张平平无奇的图片实际上对于 AI 来说是一个挑战，下面给出提示词，可以自己体会一下各个绘图 AI 的表现。

生成一张密码箱的图片，上面有密码滚轮，显示的密码是 8 9 8 1 9 6
需要注意到滚轮一圈分别是0~9，所以相邻的数码也要正确的显示

I（0，0）

唯一预测误差率严格小于 $5\%$ 的题吗.....

在第 $n$ 秒之后就不存在其他猪会经过 $x=n-1$ 处了，所以对于时间的限制其实是假的。

考虑用数列记录这个过程：令 $a_i$ 表示在足够长的时间后，会有多少个分身曾经经过 $x=i$ 的位置。

其中 $a_0=1,a_1=1,a_2=3$ ，并且 $\forall i\ge 3,a_i=a_{i-1}+2a_{i-2}+3a_{i-3}$

这个递推式并没有很好的办法通过数学推导得到递推式，所以我们又需要利用计算机的长处了：

首先，构造一个向量 $\begin{pmatrix}a_{i-1}\\a_{i-2}\\a_{i-3}\end{pmatrix}$ ，那么注意到：

\begin{pmatrix}1&2&3\\1&0&0\\0&1&0\end{pmatrix}\begin{pmatrix}a_{i-1}\\a_{i-2}\\a_{i-3}\end{pmatrix}=\begin{pmatrix}a_i\\a_{i-1}\\a_{i-2}\end{pmatrix}

进一步地， $\forall k\ge 3$ ，有：

\begin{pmatrix}a_i\\a_{i-1}\\a_{i-2}\end{pmatrix}=\begin{pmatrix}1&2&3\\1&0&0\\0&1&0\end{pmatrix}^{i-2}\begin{pmatrix}3\\1\\1\end{pmatrix}

使用快速幂优化矩阵乘法即可，快速幂的原理详见题目下方的提示区域。

参考代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
struct node {
    int a[3][3];
} ans, val;
node operator*(const node x, const node y) {
    node z = {};
    for (int i = 0; i < 3; i++)
        for (int l = 0; l < 3; l++)
            for (int j = 0; j < 3; j++) (z.a[i][l] += 1ll * x.a[i][j] * y.a[j][l] % mod) %= mod;
    return z;
}
int main() {
    ans = { 1, 0, 0, 0, 0, 0, 0, 0, 0 };
    val = { 1, 2, 3, 1, 0, 0, 0, 1, 0 };
    ll n;
    cin>>n;
    n--;
    while (n) {
        if (n & 1)
            ans = val * ans;
        val = val * val;
        n >>= 1;
    }
    cout << ans.a[0][0];
    return 0;
}

J

我们给出一份带注释的面向过程的参考代码：

#include <bits/stdc++.h>
constexpr long double pi = acosl(-1);
int n, num, m;
std::vector<std::string> stud; // 学生编号
std::string sysBegin, sysEnd; // 系统开始日期、系统结束日期
std::vector<long double> latL, latR, lngL, lngR; // 场地的纬度和经度的区间
std::map<std::string, std::set<std::string>> rec; // 映射表<学生编号, 集合<日期>>
int timeInt(std::string timeStr) {
  #define timeStr(x) (timeStr[x] - '0')
  return 36000 * timeStr(0) + 3600 * timeStr(1) + 600 * timeStr(3)
         + 60 * timeStr(4) + 10 * timeStr(6) + timeStr(7);
} // 把时间转化为它是当天的第几秒
long double sqr(long double x) { return x * x; } // 求平方
int main() {
  std::cin >> n; stud.resize(n);
  for (int i = 0; i < n; ++i) std::cin >> stud[i]; // 输入学生编号
  std::cin >> sysBegin >> sysEnd >> num; // 输入系统开始日期、系统结束日期
  latL.resize(num), latR.resize(num), lngL.resize(num), lngR.resize(num);
  for (int i = 0; i < num; ++i) // 输入场地的纬度和经度的区间
    std::cin >> latL[i] >> latR[i] >> lngL[i] >> lngR[i];
  std::cin >> m; // 输入跑步记录条数
  while (m--) { // 输入每条记录并检查
    std::string sid; std::cin >> sid; // 输入跑步的学生编号
    std::string begin, beginTime, end, endTime;
    std::cin >> begin >> beginTime >> end >> endTime;
    // 输入跑步的开始日期、开始时间、结束日期、结束时间
    int id, cnt; std::cin >> id >> cnt; --id;
    std::vector<long double> lat, lng;
    lat.resize(cnt), lng.resize(cnt); // 输入经纬度坐标序列
    for (int i = 0; i < cnt; ++i) std::cin >> lat[i] >> lng[i];
    if (begin != end || end < sysBegin || sysEnd < end) continue;
    // 若不在同一天，或日期不在系统允许的日期区间内，直接跳过这条记录
    if (beginTime < "06:00:00" || "22:00:00" < endTime) continue;
    // 若不在 6~22 时内，直接跳过这条记录
    int dur = timeInt(endTime) - timeInt(beginTime);
    if (dur < 240 || 720 < dur) continue; // 若用时不在 4~12 分钟内，直接跳过
    int inside = 0; long double dis = 0;
    for (int i = 0; i < cnt; ++i) {
      if (latL[id] <= lat[i] && lat[i] <= latR[id] &&
          lngL[id] <= lng[i] && lng[i] <= lngR[id]) ++inside; 
      // inside 统计场地内的坐标个数
      if (i) {
        long double t = sqr(sin((lat[i] - lat[i - 1]) * pi / 360)) +
                        sqr(sin((lng[i] - lng[i - 1]) * pi / 360)) *
                        cos(lat[i] * pi / 180) *
                        cos(lat[i - 1] * pi / 180);
        dis += 2 * asin(sqrt(t));
        // 用公式计算距离
      }
    }
    if (inside * 20 < cnt * 17 || 6371 * dis < 1.2) continue;
    // 若场地内点数不到总点数的 85%，或距离不到 1.2 千米，跳过
    rec[sid].insert(end);
    // 合法（除了当天是否已有合法记录还没判），插入对应学生的日期集合中
  }
  for (int i = 0; i < n; ++i)
    std::cout << stud[i] << ' ' << rec[stud[i]].size() << '\n';
  // 按顺序输出学生编号、日期集合的大小
  return 0;
}

第七届「帆软杯」东南大学大学生程序设计竞赛（冬季）新手组 题解

A（期望通过人数 100，实际通过人数 92）

B（期望通过人数 80，实际通过人数 76）

C（期望通过人数 80，实际通过人数 88）

D（20，35）

E（10，27）

F（5，6）

G（期望通过人数 5，实际通过人数 34）

H（5，0）

I（0，0）

J

第七届「帆软杯」东南大学大学生程序设计竞赛（冬季）新手组题解