T1分糖果（candy）
题目
【题目背景】
红太阳幼儿园的小朋友们开始分糖果啦！
【题目描述】
红太阳幼儿园有 n 个小朋友，你是其中之一。保证 n ≥ 2。
有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。
由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 R 块糖回去。但是拿的太少不够分的，所以你至少要拿 L 块糖回去。保证 n ≤ L ≤ R。
如果你拿了 k 块糖，你将把这 k 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 n 块糖果，幼儿园的所有 n 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。
作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 n, L, R，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量。
【输入格式】
从文件 candy.in 中读入数据。输入一行，包含三个正整数 n, L, R，分别表示小朋友的个数、糖果数量的下界和上界。
【输出格式】
输出到文件 candy.out 中。输出一行一个整数，表示你最多能获得的作为你搬糖果的奖励的糖果数量。
【样例 1】
输入：
71623输出：
6【样例 1 解释】
拿 k = 20 块糖放入篮子里。篮子里现在糖果数 20 ≥ n = 7，因此所有小朋友获得一块糖；篮子里现在糖果数变成 13 ≥ n = 7，因此所有小朋友获得一块糖；篮子里现在糖果数变成 6 < n = 7，因此这 6 块糖是作为你搬糖果的奖励。容易发现，你获得的作为你搬糖果的奖励的糖果数量不可能超过 6 块，因此答案是 6。
【样例 2】
输入：
101418输出：
8【数据范围】
对于所有数据，保证 2 ≤ n ≤ L ≤ R ≤ 10^9。
参考代码（数组写法）
#include <bits/stdc++.h>usingnamespace std;intmain(){ ios::sync_with_stdio(false);cin.tie(0);longlong n, L, R;cin >> n >> L >> R;if (L / n == R / n) {cout << R % n << '\n'; // 区间没跨过整轮，最右边的余数最大 } else {cout << n - 1 << '\n'; // 跨过整轮了，一定能凑出 n-1 }return0;}代码解析
① 篮子里的奖励数量就是 k 除以 n 的余数（k % n）。因为每轮 n 个小朋友各拿一块，拿走的都是"整轮"，剩下的就是余数。
② 题目变成：在 [L, R] 里挑一个 k，让 k % n 最大。
③ 关键判断：看区间 [L, R] 有没有"跨过整轮"。
如果 L / n == R / n（整数除法），说明 L 和 R 在同一个"轮"里，比如 n = 10 时 14 和 18 都在第二轮。这一轮里余数随着 k 增大而增大，所以取 k = R，答案是R % n。如果 L / n != R / n，说明区间跨过了一轮的边界，比如 n = 7 时 16 在第二轮、23 在第三轮。那么在 21 × 7 之前一定存在一个形如 7 × a - 1 的数（余数等于 6 = n-1），取它就行，答案是n - 1。
④ 余数最大只能到 n-1，所以答案不可能超过 n-1，else 分支直接输出 n - 1 就对了。
⑤ n, L, R 都能到 10^9，用 int（最大约 2.1×10^9）勉强够，但养成习惯用 long long 更保险。
思路总结
算法：数学（整除分块）。
核心思路：奖励 = k % n。区间内余数最大能到多少，取决于区间是否跨过 n 的整数倍边界。没跨过就取右端点，跨过了就一定能凑出 n-1。
时间复杂度：O(1)。
易错点
别把题意理解成"最后获得的总糖果数"，题目特意强调是奖励部分，也就是余数。 判断用整数除法 L / n和R / n，不要转成小数再比较。不要试图枚举 k，R 最大 10^9，会超时。
一句话记忆：奖励就是 k%n，区间跨没跨过整轮决定了答案是 R%n 还是 n-1。
T2插入排序（sort）
题目
【题目描述】
插入排序是一种非常常见且简单的排序算法。假设比较两个元素的时间为 O(1)，则插入排序可以以 O(n^2) 的时间复杂度完成长度为 n 的数组的排序。
不妨假设这 n 个数字分别存储在 a1, a2, ..., an 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
for (int i = 1; i <= n; i++)for (int j = i; j >= 2; j--)if (a[j] < a[j-1]) {int t = a[j-1]; a[j-1] = a[j]; a[j] = t; }为了帮助小 Z 更好的理解插入排序，H 老师留下了这么一道家庭作业：
H 老师给了一个长度为 n 的数组 a，数组下标从 1 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a 上的 Q 次操作，操作共两种：
1 x v：将 a 的第 x 个元素 ax 的值修改为 v。这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。 2 x：假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 x 个元素 ax 在排序后的新数组所处的位置。这种操作不会改变数组的元素。
H 老师不喜欢过多的修改，所以他保证类型 1 的操作次数不超过 5000。
【输入格式】
从文件 sort.in 中读入数据。
输入的第一行包含两个正整数 n, Q，表示数组长度和操作次数。
输入的第二行包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 ai。
接下来 Q 行，每行 2～3 个正整数，表示一次操作，操作格式见题目描述。
【输出格式】
输出到文件 sort.out 中。对于每一次类型为 2 的询问，输出一行一个正整数表示答案。
【样例 1】
输入：
34321231322223输出：
112【样例 1 解释】
在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3, 2, 1。
【数据范围】
对于所有测试数据，满足 1 ≤ n ≤ 8000，1 ≤ Q ≤ 2×10^5，1 ≤ x ≤ n，1 ≤ v, ai ≤ 10^9。对于所有测试数据，保证在所有 Q 次操作中，至多有 5000 次操作属于类型一。
参考代码（数组写法）
#include <bits/stdc++.h>usingnamespace std;constint MAXN = 8005;int n, Q;int a[MAXN]; // 原数组（其实只用于读入）int sv[MAXN], si[MAXN]; // 排序后的两个平行数组：值 和 原下标int pos[MAXN]; // pos[i]：原下标 i 排序后落在第几位// 插入排序 + 重新计算 pos。数组基本有序，只有一处需要移动void rebuild(){for (int i = 1; i <= n; i++) {int v = sv[i];int id = si[i];int j = i - 1;while (j >= 1 && (sv[j] > v || (sv[j] == v && si[j] > id))) { sv[j + 1] = sv[j]; si[j + 1] = si[j]; j = j - 1; } sv[j + 1] = v; si[j + 1] = id; }for (int i = 1; i <= n; i++) { pos[si[i]] = i; }}intmain(){ ios::sync_with_stdio(false);cin.tie(0);cin >> n >> Q;for (int i = 1; i <= n; i++) {cin >> a[i]; sv[i] = a[i]; si[i] = i; } rebuild(); // 先排一次初始数组for (int k = 1; k <= Q; k++) {int op;cin >> op;if (op == 1) {int x, v;cin >> x >> v; sv[pos[x]] = v; // 直接改掉它在有序数组中的值 rebuild(); // 只有一个元素位置不对，插入排序很快 } else {int x;cin >> x;cout << pos[x] << '\n'; // O(1) 回答 } }return0;}代码解析
① 题目的排序规则是稳定的：伪代码里只有 a[j] < a[j-1] 才交换，相等时不交换。所以值相同的两个元素，原来在前的排完序后仍然在前。代码里的比较条件写成 sv[j] > v || (sv[j] == v && si[j] > id)，后半句就是为了保持这个稳定性。
② 用 sv[] 和 si[] 两个平行数组存排好序的结果：一个存值，一个存它原来的下标。下标相同的两个数组元素属于同一条记录，这是不用结构体时用数组存"一组数据"的常用办法。
③ 类型 2 的询问为什么能 O(1)？因为 pos[x] 直接记录了"原下标 x 排完序在第几位"。修改发生时我们才重算 pos，而修改最多 5000 次。
④ 修改操作 sv[pos[x]] = v 之后调用 rebuild()。此时整个有序数组只有被改的那个元素位置不对，插入排序的内层 while 几乎不会执行，外层扫一遍 n 个元素就够了，所以 rebuild 的代价约 O(n)，5000 次修改总共 4×10^7，可以接受。
⑤ 注意：不能每次询问都去数"有几个元素排在它前面"，那样复杂度是 O(n) × 2×10^5 = 1.6×10^9，直接超时。本题的突破口就是"修改少、询问多"，把代价压在修改上、让询问 O(1)。
思路总结
算法：插入排序（利用"基本有序"）+ 维护排名。
核心思路：题目明说修改次数 ≤ 5000 而询问可达 2×10^5，所以要把准备工作做在修改时。维护一个始终有序的数组，每次修改后重新排一次（几乎不用移动），并把每个原下标的排名记下来，询问时直接查表。
时间复杂度：O(n log n) 级别的初始排序 + O(5000 × n) + O(Q)。
空间复杂度：O(n)。
易错点
排序必须稳定，值相等时按原下标从小到大排，否则样例 1 的最后一问会答错。 修改操作要真的保留（影响后续），询问操作不能改变数组。 修改时先改 sv[pos[x]]，再 rebuild；如果直接在原数组改了却不 rebuild，询问答案会过时。n 只有 8000，但 Q 有 2×10^5，凡是 O(n) 回答询问的写法都会超时。
一句话记忆：修改少 → 每次修改重排一遍；询问多 → 维护 pos 数组 O(1) 回答；排序要稳定。
T3网络连接（network）
题目
【题目描述】
TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。
在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。
需要进行网络连接的计算机共有 n 台，编号为 1～n，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。
每台机器在尝试建立或加入连接时需要提供一个地址串。
一个符合规范的地址串应当具有以下特征：
1. 必须形如 a.b.c.d:e 的格式，其中 a, b, c, d, e 均为非负整数； 2. 0 ≤ a, b, c, d ≤ 255，0 ≤ e ≤ 65535； 3. a, b, c, d, e 均不能含有多余的前导 0。
如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。
在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接。
由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的地址串的服务机均可成功建立连接。
如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。
【输入格式】
从文件 network.in 中读入数据。
第 1 行，一个正整数 n。
接下来 n 行，每行 2 个字符串 op, ad，按照编号从小到大给出每台计算机的类型及地址串。
其中 op 保证为字符串 Server 或 Client 之一，ad 为一个长度不超过 25 的，仅由数字、字符 . 和字符 : 组成的非空字符串。
【输出格式】
输出到文件 network.out 中。输出共 n 行，每行一个正整数或字符串表示第 i 台计算机的连接状态。
如果第 i 台计算机为服务机，则：
1. 如果其提供符合规范的地址串且成功建立连接，输出字符串 OK； 2. 如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功建立连接，输出字符串 FAIL； 3. 如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。
如果第 i 台计算机为客户机，则：
1. 如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号； 2. 如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 FAIL； 3. 如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。
【样例 1】
输入：
5Server 192.168.1.1:8080Server 192.168.1.1:8080Client 192.168.1.1:8080Client 192.168.1.1:80Client 192.168.1.1:99999输出：
OKFAIL1FAILERR【样例 2】
输入：
10Server 192.168.1.1:80Client 192.168.1.1:80Client 192.168.1.1:8080Server 192.168.1.1:80Server 192.168.1.1:8080Server 192.168.1.999:0Client 192.168.1.1.8080Client 192.168.1.1:8080Client 192.168.1.1:80Client 192.168.1.999:0输出：
OK1FAILFAILOKERRERR51ERR【数据范围】
对于 100% 的数据，保证 1 ≤ n ≤ 1000。
参考代码（数组写法）
#include <bits/stdc++.h>usingnamespace std;constint MAXN = 1005;char op[20], ad[30];char svr[MAXN][30]; // 已成功建立连接的服务机地址int sid[MAXN]; // 对应的服务机编号int scnt;// 判断地址串是否规范，规范返回 1，否则返回 0int check(char s[]){int len = strlen(s);int seg = 0; // 当前在处理第几段（0,1,2,3,4）int i = 0;while (i < len) {int v = 0, d = 0; // v 是这一段的数值，d 是位数while (i < len && s[i] >= '0' && s[i] <= '9') { v = v * 10 + s[i] - '0'; d = d + 1; i = i + 1; }if (d == 0) return0; // 这一位是空的，比如 "192..0.1:1"if (d > 1 && s[i - d] == '0') return0; // 有前导 0，比如 "192.168.00.1:10"if (seg <= 3 && v > 255) return0;if (seg == 4 && v > 65535) return0; seg = seg + 1;if (i < len) { // 后面还有内容，说明该出现分隔符了if (seg <= 3 && s[i] != '.') return0;if (seg == 4 && s[i] != ':') return0; i = i + 1; } }if (seg != 5) return0; // 必须是 5 段return1;}intmain(){ ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> op >> ad;if (check(ad) == 0) {cout << "ERR" << '\n'; } elseif (op[0] == 'S') { // 服务机int same = 0;for (int j = 1; j <= scnt; j++) {if (strcmp(svr[j], ad) == 0) { same = 1;break; } }if (same == 1) {cout << "FAIL" << '\n'; } else { scnt = scnt + 1; strcpy(svr[scnt], ad); sid[scnt] = i; // 记下这台服务机的编号cout << "OK" << '\n'; } } else { // 客户机int find = 0;for (int j = 1; j <= scnt; j++) {if (strcmp(svr[j], ad) == 0) {cout << sid[j] << '\n'; // 输出服务机的编号 find = 1;break; } }if (find == 0) cout << "FAIL" << '\n'; } }return0;}代码解析
① check 函数用"一段一段扫"的方式验证地址，一次扫出一段连续的数字：
d == 0说明这一位根本不是数字（可能是连续的分隔符），直接判非法； d > 1 && s[i-d] == '0'判断前导 0，比如 00、088都不行，单独的0可以；前四段（seg 0～3）不能超过 255，最后一段（seg 4）是端口，不能超过 65535； 分隔符也很讲究：前三段后面必须是 .，第四段后面必须是:，所以192:168:0:1.233会在第一段就被判非法。
② 扫完后 if (seg != 5) return 0; 兜底：像 1.2.3.4: 或 1.2.3 这种段数不对的都会被挡掉。
③ 服务机处理：先查重（题目不允许两台服务机用同一地址），重复就 FAIL，否则存进 svr 数组并输出 OK。
④ 客户机处理：在 svr 里找有没有一模一样的地址，找到就输出那台服务机的编号。注意输出的是机器编号 i，不是我存数组的下标，所以额外开了一个 sid[] 数组记录编号。
⑤ 因为 n ≤ 1000，直接顺序查找就完全够了，不需要哈希或者二分。
思路总结
算法：字符串模拟 + 顺序查找。
核心思路：写一个严谨的地址合法性判断函数；然后按题目给出的三条规则分别处理服务机和客户机。这题几乎没有算法难度，考的是细心。
时间复杂度：O(n × 25 + n × scnt)，n ≤ 1000，完全没问题。
空间复杂度：O(n)。
易错点
前导 0 的判断：单独的 0是合法的，00才非法，别一刀切。端口 e 的上限是 65535，不是 255，两段的上限不一样。 分隔符的位置要对：前三段后是 .，第四段后是:，写成四个点一个冒号就错。客户机输出的是服务机在输入中的编号，不是数组下标。如果只是顺序遍历服务机列表，中间可能有非法的服务机没被记进去，两者会不一致。 用 op[0] == 'S'区分 Server 和 Client，简洁又好记。
一句话记忆：细心写地址判断，服务机去重、客户机查表，输出编号别输出下标。
T4小熊的果篮（fruit）
题目
【题目描述】
小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1、2、3、……、n 编号。连续排在一起的同一种水果称为一个"块"。
小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个"块"中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。
注意，每次挑完一个果篮后，"块"可能会发生变化。比如两个苹果"块"之间的唯一桔子被挑走后，两个苹果"块"就变成了一个"块"。
请帮小熊计算每个果篮里包含的水果。
【输入格式】
从文件 fruit.in 中读入数据。
输入的第一行包含一个正整数 n，表示水果的数量。输入的第二行包含 n 个空格分隔的整数，其中第 i 个数表示编号为 i 的水果的种类，1 代表苹果，0 代表桔子。
【输出格式】
输出到文件 fruit.out 中。输出若干行。第 i 行表示第 i 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。
【样例 1】
输入：
12110011101100输出：
135891124612710【样例 1 解释】
所有水果一开始的情况是 1 1 0 0 1 1 1 0 1 1 0 0，一共有 6 个块。在第一次挑水果组成果篮的过程中，编号为 1、3、5、8、9、11 的水果被挑了出来。之后剩下的水果是 1 0 1 1 1 0，一共 4 个块。在第二次挑水果组成果篮的过程中，编号为 2、4、6、12 的水果被挑了出来。之后剩下的水果是 1 1，只有 1 个块。在第三次挑水果组成果篮的过程中，编号为 7 的水果被挑了出来。最后剩下的水果是 1，只有 1 个块。在第四次挑水果组成果篮的过程中，编号为 10 的水果被挑了出来。
【样例 2】
输入：
2011110001110010110000输出：
1581113141517269121618371019420【数据范围】
对于 10% 的数据，n ≤ 5。对于 30% 的数据，n ≤ 1000。对于 70% 的数据，n ≤ 50000。对于 100% 的数据，n ≤ 2×10^5。
参考代码（数组写法）
#include <bits/stdc++.h>usingnamespace std;constint MAXN = 200005;int n;int a[MAXN]; // 每个位置是苹果(1)还是桔子(0)int pre[MAXN], nxt[MAXN]; // 双向链表：数组模拟int cur[MAXN], ncur; // 本轮要挑的块首编号int nxtL[MAXN], nnxt; // 下一轮要挑的块首编号intmain(){ ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i]; pre[i] = i - 1; nxt[i] = i + 1; } nxt[n] = 0; pre[1] = 0;// 一开始的块首：第 1 个，以及每种水果第一次出现的位置 ncur = 0;for (int i = 1; i <= n; i++) {if (i == 1 || a[i] != a[i - 1]) { ncur = ncur + 1; cur[ncur] = i; } }while (ncur > 0) { nnxt = 0;int first = 1;for (int i = 1; i <= ncur; i++) {int x = cur[i];if (first == 1) {cout << x; first = 0; } else {cout << ' ' << x; }int l = pre[x];int r = nxt[x];// 把 x 从链表里删掉if (l != 0) nxt[l] = r;if (r != 0) pre[r] = l;// r 会成为本块新的块首……if (r != 0 && a[r] == a[x]) {// ……除非它跟前面那个块合并了if (!(l != 0 && a[l] == a[r])) { nnxt = nnxt + 1; nxtL[nnxt] = r; } } }cout << '\n'; ncur = nnxt;for (int i = 1; i <= ncur; i++) { cur[i] = nxtL[i]; } }return0;}代码解析
① 每挑走一个水果就要把它"删掉"，用数组模拟的双向链表最合适：pre[i] 是 i 前面是谁，nxt[i] 是 i 后面是谁，删除只改两个指针，O(1) 完成。删除操作是：
nxt[pre[x]] = nxt[x];pre[nxt[x]] = pre[x];（代码里加了 l != 0、r != 0 的判断，因为最左边和最右边没有前驱/后继。）
② 直接遍历链表去数"块"会超时：如果 20 万个全是苹果（只有 1 个块），每轮都要从头扫到尾，总复杂度就是 O(n^2)。所以要用 cur[] 数组直接记录本轮的块首，一轮只遍历块首，不遍历水果。
③ 每轮处理块首 x 时，x 被删掉，它后面那个位置 r 有可能成为新的块首，但有个条件：
如果 a[r] == a[x]，说明 r 和 x 是同一种水果，r 就是本块剩下的部分的块首 → 加入下一轮列表。如果还满足 a[l] == a[r]，说明删掉 x 之后，前面那个块和 r 所在的部分连到一起了，它们合并成一个块 → r 就不算块首了，不能加入。
④ 如果 a[r] != a[x]，说明 x 是它所在块的最后一个，r 属于下一个块，而下一个块的块首本来就在本轮的 cur[] 里等着被处理，不需要额外加入。
⑤ 每一轮结束把 nxtL[] 拷回 cur[]，继续下一轮。每个位置最多被加入一次块首列表，所以总复杂度是 O(n)。
⑥ 输出时用 first 变量控制空格：第一个数字前面不加空格，后面每个数字前面加一个空格。这是输出列表的标准写法。
思路总结
算法：数组模拟双向链表 + 维护"块首队列"。
核心思路：不要每轮重新扫描整条链去找块，而是维护一个"本轮块首列表"，每轮只处理这些块首，并顺手推算出下一轮的块首。难点在于处理"删掉一个块首后，左右两块可能合并"的情况。
时间复杂度：O(n)。每个位置最多当一次块首，最多被加入一次列表。
空间复杂度：O(n)。
易错点
直接遍历链表找块会退化到 O(n^2)，在全是同一种水果的数据上必炸。 合并的判断是本题最核心的细节：删掉 x 后要看 a[l]和a[r]是否相等，相等就合并，此时 r 不能当块首。块首列表必须保持从小到大的顺序，由于我们按 cur的顺序处理、r = nxt[x]天然递增，顺序自动满足。删除最左边的元素时 l == 0，删除最右边的元素时r == 0，都要判断，不能越界。
一句话记忆：双向链表删水果，每轮只处理块首，删完记得判断左右两块有没有合并。
本年份小结
2021 年四道题分别是：数学（整除分块）、插入排序维护排名、字符串模拟、双向链表模拟。
这一年的特点：T1 考思维、T2 考复杂度权衡、T3 考细心、T4 考数据结构基本功。四道题都不是靠背模板能解决的，需要真的理解题目。
给选手的启示：
T2 是典型的"谁少谁承担代价"题型 —— 修改少就把重活放在修改时做，让频繁的询问变成 O(1)。 T3 提醒我们，模拟题的分水岭在于边界条件：前导 0、端口上限、分隔符位置，漏一个就是大面积丢分。 T4 说明链表不只能存数据，还能用来"加速模拟"，关键是找到避免重复扫描的方法。
