第三周的题开始出现“同一套窗口代码换一种问法”的情况:定长窗口问含 C/G 最多的子串(DNA 序列),也问快乐值最大、羞耻度最小的子串(比那名居的桃子);变长窗口问最长无重复区间。窗口的骨架相同,差别只在维护几个量、并列时怎么选、初值写成多少。

题目模型时间复杂度
牛牛冲钻五规则模拟O(n)
最长无重复子数组变长窗口O(n)
重排字符串频次 + 构造O(n)
乒乓球筐计数哈希O(n)
组队竞赛排序 + 贪心O(n log n)
删除相邻数字的最大分数值域 DPO(n + V)
平方数整数开方O(1)
分组二分答案O(k log max)
拓扑排序入度 + BFSO(n+m)
字符串替换逐字符模拟O(n+m)
神奇数枚举 + 试除O((b−a+1)·d²·√100)
DNA 序列定长窗口O(n)
小乐乐改数字逐位替换O(n)
十字爆破行列和预处理O(nm)
比那名居的桃子定长窗口 + 双关键字O(n)
压缩字符串双指针游程O(n)
chika 和蜜柑排序 + 取前 kO(n log n)
01 背包一维背包O(nV)

定长窗口:DNA 序列与桃子

DNA 序列。在长度为 n 的串里找长度为 x 的子串,要求其中 C 和 G 的个数最多;并列时输出第一个。窗口长度固定,右端进一个、左端出一个。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    int x;
    cin >> s >> x;
    int n = s.size();
    if (x > n) x = n;
 
    int begin = 0;
    int best = -1, cnt = 0, left = 0;
 
    for (int right = 0; right < n; right++)
    {
        if (s[right] == 'C' || s[right] == 'G') cnt++;
 
        while (right - left + 1 > x)
        {
            if (s[left] == 'C' || s[left] == 'G') cnt--;
            left++;
        }
 
        if (right - left + 1 == x && cnt > best)
        {
            best = cnt;
            begin = left;
        }
    }
    cout << s.substr(begin, x) << endl;
    return 0;
}

begin 的初值是 0,不是 -1。课件用 -1 当“还没找到”的哨兵,如果整条串里一个 C 或 G 都没有,best 从 0 开始,cnt > best 永远不成立,begin 原样送进 substr。substr 的参数是无符号的 size_type,-1 先变成 2^64−1,必定大于 size(),标准规定这种情况抛 std::out_of_range,程序直接终止。

best 用 -1 作初值,第一个长度正好为 x 的窗口一定会写入,begin 从此有效。并列时保留更早的窗口,靠严格大于 cnt > best。如果 x 比串长还大,窗口长度永远到不了 x,所以先把 x 截到 n;不截的话输出会是空串或抛异常。

时间 O(n)、空间 O(1)。

比那名居的桃子。长度为 k 的区间里,先让快乐值之和最大,再让羞耻度之和最小,还并列就取更早的。两个和都要随窗口滑动维护。

#include <iostream>
using namespace std;
 
const int N = 100010;
long long h[N], s[N];
 
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> s[i];
 
    long long hSum = 0, sSum = 0;
    long long hMax = -1, sMin = 0;
    int begin = 0, left = 1;
 
    for (int right = 1; right <= n; right++)
    {
        hSum += h[right];
        sSum += s[right];
 
        while (right - left + 1 > k)
        {
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
 
        if (right - left + 1 == k)
        {
            if (hSum > hMax || (hSum == hMax && sSum < sMin))
            {
                hMax = hSum;
                sMin = sSum;
                begin = left;
            }
        }
    }
    cout << begin << endl;
    return 0;
}

三个比较关键字可以压成一行,是因为“并列取更早”由 sSum < sMin 的严格小于保证:快乐值和羞耻度都相同时不更新,第一个窗口自然保留。写成 <= 就会选到更靠后的窗口。

hMax 的初值取 -1 而不是 0。快乐值非负时 0 也能工作,但只要某个窗口的快乐值和是 0,hSum > 0 不成立,sMin 不会被写入,后面的“并列比较羞耻度”全部失效,begin 会一直停在 0。取 -1 让第一个窗口必然写入。课件写的是 hMax = 0, sMin = 0,在快乐值全为 0 的数据上会选错窗口。

复杂度 O(n),hSum、sSum 到 1e14 量级,必须 64 位。

变长窗口:最长无重复子数组

窗口合法的条件是“元素互不相同”。右端加入新元素后,不合法的唯一原因是这个新值和窗口里某个旧值相同,所以左端一直收缩到它的计数回到 1。

#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    int maxLength(vector<int>& arr)
    {
        unordered_map<int, int> cnt;
        int left = 0, best = 0;
 
        for (int right = 0; right < (int)arr.size(); right++)
        {
            cnt[arr[right]]++;
            while (cnt[arr[right]] > 1)
            {
                cnt[arr[left]]--;
                left++;
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

while 里判断的是“右端这个值的计数”,不需要知道重复的是谁:只要它仍然大于 1,就说明窗口里还有另一个相同的值,必须继续缩。收缩完成后窗口一定合法。

两种常见写法的区别:

  • 记录每个值上次出现的位置,然后 left = max(left, last[x] + 1)。max 不能省,否则 left 可能往回退,窗口变成不连续区间,长度计算全错。
  • 每次遇到重复就 left = last[x] + 1,遇到 1 2 1 2 这种会得到超过 n 的长度。

left 单调不减是窗口类题目的不变式,比任何公式都值得记。值域小的时候(比如元素都在 1e5 以内),把 unordered_map 换成 int cnt[100010] 更快;值域不可控就用哈希表。平均 O(n)、空间 O(不同元素个数)。

规则直译:四道模拟题

牛牛冲钻五。输一局扣一颗星;赢一局时,如果前两局也都是赢,加 k 颗星,否则加一颗星。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        string s;
        cin >> n >> k >> s;
 
        long long ret = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'L') ret--;
            else if (i >= 2 && s[i - 1] == 'W' && s[i - 2] == 'W') ret += k;
            else ret += 1;
        }
        cout << ret << endl;
    }
    return 0;
}

i >= 2 一个条件同时挡住 i-1 和 i-2 的越界。写成 i - 1 >= 0 && i - 2 >= 0 逻辑等价,但 i 一旦改成无符号类型,i - 1 >= 0 恒真,两个判断都失效。ret 用 long long:n 到 1e5、k 可能很大时,连胜累加能超过 32 位。

字符串替换。把模板串里的每个 %s 依次换成参数,剩下没用的参数直接追加到末尾。

#include <string>
#include <vector>
using namespace std;
 
class StringFormat
{
public:
    string formatString(string A, int n, vector<char> arg, int m)
    {
        string ret;
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (A[i] == '%' && i + 1 < n && A[i + 1] == 's')
            {
                if (j < m) ret += arg[j++];
                i++;
            }
            else
            {
                ret += A[i];
            }
        }
        while (j < m) ret += arg[j++];
        return ret;
    }
};

两个细节:i + 1 < n 防止末尾孤立的 % 越界;i++ 跳过已经消费掉的 s。% 后面不是 s 时按普通字符输出,% 和后面的字符都会进入结果。if (j < m) 是防御性判断,题面通常保证参数个数够用。

小乐乐改数字。把一个十进制数的偶数位变成 0、奇数位变成 1,去掉前导零后输出。直接把数当字符串读,比反复取模省事。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    for (char& c : s)
        c = ((c - '0') % 2 == 0) ? '0' : '1';
 
    int i = 0;
    while (i < (int)s.size() - 1 && s[i] == '0') i++;
    cout << s.substr(i) << endl;
    return 0;
}

课件写的是 s[i] % 2 == 0,直接对字符编码取奇偶。它能工作是因为 ASCII 里 '0' 是 48(偶数),数字字符的奇偶和数值的奇偶一致。C++ 标准只保证 '0' 到 '9' 连续且递增,并没有保证 '0' 是偶数;换一种字符集,这个技巧就不成立。写成 (c - '0') % 2 只是多减一次,意图也明确。

前导零的处理用下标找第一个非零位,保留至少一位(i < size - 1)。课件 C++ 版用 stoi 把结果转回整数,省掉了前导零,但依赖结果能装进 int;本题结果最多十位 1,数值不超过 1111111111,能装下。直接按字符串输出不依赖这个范围,更稳。

压缩字符串。连续的相同字符压成“字符 + 次数”,次数为 1 时省略数字。

#include <string>
using namespace std;
 
class Solution
{
public:
    string compressString(string param)
    {
        string ret;
        int n = param.size();
        int i = 0;
        while (i < n)
        {
            int j = i;
            while (j + 1 < n && param[j] == param[j + 1]) j++;
            int len = j - i + 1;
 
            ret += param[i];
            if (len > 1) ret += to_string(len);
            i = j + 1;
        }
        return ret;
    }
};

j + 1 < n 让 param[j + 1] 始终合法;内层循环结束后 j 是这一段最后一个字符,下一段从 j + 1 开始。长度用 to_string 转成十进制,两位以上的次数(如 12)也能正确拼接。时间 O(n)、空间 O(n)。

计数、排序与构造

乒乓球筐。判断第二个串的字符是否都能由第一个串提供,每个字符只能用一次。统计第一个串的频次,再逐个扣减第二个串,扣成负数就说明不够。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s1, s2;
    while (cin >> s1 >> s2)
    {
        int cnt[26] = {0};
        for (char c : s1) cnt[c - 'A']++;
        for (char c : s2) cnt[c - 'A']--;
 
        bool ok = true;
        for (int i = 0; i < 26; i++)
            if (cnt[i] < 0) ok = false;
 
        cout << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}

题面不给组数,while (cin >> s1 >> s2) 读到 EOF 为止,每组重新开一个计数数组。先全部扣完再判断,和边扣边 break 等价,但不会漏掉后面字符的越界(c - 'A' 对非大写字母会得到负下标,输入只含大写)。时间 O(总字符数)。

组队竞赛。3n 个人分成 n 队,每队 3 人,队伍水平是队内第二高的水平值,求所有队伍水平值之和最大。排序后,从第 3n−2 个元素开始,每隔一个取一个。

#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 300010;
long long a[N];
 
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < 3 * n; i++) cin >> a[i];
    sort(a, a + 3 * n);
 
    long long ans = 0;
    int pos = 3 * n - 2;
    for (int i = 0; i < n; i++)
    {
        ans += a[pos];
        pos -= 2;
    }
    cout << ans << endl;
    return 0;
}

每一队贡献的是“队内第二”,它上面必须有一个比它大的数陪跑。把最大的那些数当陪跑,次大的才有机会成为中位数。排序后,下标 3n−1 的最大值一定当陪跑,下标 3n−2 的次大值可以作为某一队的中位数;再往前,每取一个中位数就要跳过它右边的一个更大的数,所以下标每次减 2。交换论证可以把这个策略固定下来:任何方案里,最大值都不可能成为中位数,最优解至少能换成这个取法而不变差。

n 到 1e5、每人水平到 1e9,总和能到 1e14,ans 必须是 long long。课件把数组也写成 long long,读入时避免中间转换。

chika 和蜜柑。每个橘子有酸度和甜度,选 k 个使甜度总和最大;甜度相同时酸度总和尽量小。按“甜度降序、酸度升序”排序,取前 k 个。

#include <iostream>
#include <algorithm>
using namespace std;
 
struct Orange
{
    long long sour;
    long long sweet;
};
 
const int N = 200010;
Orange a[N];
 
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i].sour;
    for (int i = 0; i < n; i++) cin >> a[i].sweet;
 
    sort(a, a + n, [](const Orange& x, const Orange& y) {
        if (x.sweet != y.sweet) return x.sweet > y.sweet;
        return x.sour < y.sour;
    });
 
    long long s = 0, t = 0;
    for (int i = 0; i < k; i++)
    {
        s += a[i].sour;
        t += a[i].sweet;
    }
    cout << s << " " << t << endl;
    return 0;
}

第二个排序关键字不能省。甜度相同的那一批橘子,选哪几个会影响酸度总和;按酸度升序让“同样甜”的橘子先取更酸的便宜货,才能让酸度和最小。sort 的比较器必须满足严格弱序:两个字段都相等时返回 false,上面的写法满足。

复杂度 O(n log n),两个总和都能到 1e5×1e9 = 1e14,必须 64 位。

重排字符串。重排后不能有相邻相同字符。先数出出现次数最多的字符,若它的次数超过 (n+1)/2 则无解;否则把它放在偶数下标,其余字符从后续位置继续填,越过末尾就回到 1。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin >> n >> s;
 
    int cnt[26] = {0};
    int maxCount = 0, maxIdx = 0;
    for (char c : s)
    {
        int idx = c - 'a';
        if (++cnt[idx] > maxCount)
        {
            maxCount = cnt[idx];
            maxIdx = idx;
        }
    }
 
    if (maxCount > (n + 1) / 2)
    {
        cout << "no" << endl;
        return 0;
    }
 
    string ret(n, ' ');
    int pos = 0;
    for (int i = 0; i < maxCount; i++)
    {
        ret[pos] = char('a' + maxIdx);
        pos += 2;
    }
 
    for (int i = 0; i < 26; i++)
    {
        if (i == maxIdx) continue;
        for (int j = 0; j < cnt[i]; j++)
        {
            if (pos >= n) pos = 1;
            ret[pos] = char('a' + i);
            pos += 2;
        }
    }
 
    cout << "yes" << endl;
    cout << ret << endl;
    return 0;
}

可行性条件是“最多频次不超过 ceil(n/2)”。构造分两段:最多字符占 0、2、4…,任意两个之间至少隔一个位置;其余字符先接着偶数位往后填,填到末尾就回到 1 继续填奇数位。因为最多字符只占前 2*maxCount 个偶数位,后面的偶数位和所有奇数位都是空的,不会覆盖。pos >= n 回绕到 1 而不是 0,就是为了避开已经被占用的偶数位。

复杂度 O(n + 26),空间 O(n)。

二分答案:分组

分组。把 n 个人分成 m 组,同一声部的人可以在不同组,要求每组人数不超过 x,问 x 最小是多少。check(x) 统计“每种声部需要多少组”:ceil(cnt/x) 相加,看是否不超过 m。

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
int n, m;
unordered_map<int, int> cnt;
 
bool check(int x)
{
    int groups = 0;
    for (auto& p : cnt)
        groups += p.second / x + (p.second % x == 0 ? 0 : 1);
    return groups <= m;
}
 
int main()
{
    cin >> n >> m;
    int hmax = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        hmax = max(hmax, ++cnt[x]);
    }
 
    if ((int)cnt.size() > m)
    {
        cout << -1 << endl;
        return 0;
    }
 
    int l = 1, r = hmax;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

check 关于 x 单调:x 越大,每种声部需要的组数越少,groups <= m 从假变真。二分取“最小的可行 x”,所以可行时收缩右边界 r = mid,不可行时 l = mid + 1。

cnt.size() > m 是先决条件:连“每种声部至少一组(每组只能放一个声部)”都做不到,再大的 x 也没用,直接 -1。groups < m 说明上限还有富余,把某些组再拆小只会让人数更少,所以二分时判断“不超过 m 组”就够。

复杂度 O(k log hmax),k 是声部种类数。

拓扑排序

【模板】拓扑排序。有向无环图给出任意一个合法拓扑序;有环输出 -1。统计入度,入度为 0 的点入队,出队时把它的所有出边终点的入度减一,减到 0 再入队。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    vector<vector<int>> edges(n + 1);
    vector<int> in(n + 1, 0);
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        in[b]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);
 
    vector<int> ret;
    while (!q.empty())
    {
        int a = q.front();
        q.pop();
        ret.push_back(a);
 
        for (int b : edges[a])
            if (--in[b] == 0) q.push(b);
    }
 
    if ((int)ret.size() != n)
    {
        cout << -1 << endl;
        return 0;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (i) cout << ' ';
        cout << ret[i];
    }
    cout << endl;
    return 0;
}

判断有环不需要额外 DFS:如果图里有环,环上的点入度永远减不到 0,队列耗尽时结果不足 n 个。n、m 到 2e5,邻接表比邻接矩阵省内存。输出任意合法顺序即可,多个入度 0 的点同时进队时,出队顺序不影响合法性。行末不能多空格,按“第一个元素前不加空格”的写法输出。

时间 O(n+m),空间 O(n+m)。

值域与容量上的 DP

删除相邻数字的最大分数。选一个数 x 得 x 分,同时所有 x−1 和 x+1 被删掉。同一个数值出现几次不重要,因为选 x 时所有 x 会一起被拿走,所以先把值域压成一维:sum[v] 是数值 v 出现次数的总和。

#include <iostream>
#include <algorithm>
using namespace std;
 
const int V = 10010;
long long sum[V], f[V], g[V];
 
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        sum[x] += x;
    }
 
    for (int i = 1; i < V; i++)
    {
        f[i] = g[i - 1] + sum[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(f[V - 1], g[V - 1]) << endl;
    return 0;
}

f[i] 表示选 i 时的最大分数,g[i] 表示不选 i 时的最大分数。选了 i 就不能选 i−1(它被删掉了),所以 f[i] = g[i-1] + sum[i];不选 i 时,i−1 选不选都可以,g[i] 取两者较大。这就是打家劫舍的递推,只是“相邻”从下标换成了数值。

值域只有 1e4,状态数与 n 无关,时间 O(n + V)。总和最坏到 1e9(n = 1e5、每个数 1e4),int 刚好够,long long 不用算这个边界。

01 背包。n 个物品,每个有体积和价值,容量 V,每个物品最多选一次,求最大价值。二维状态是“前 i 个物品、容量 j”,一维滚动时容量必须从大到小遍历。

#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    int knapsack(int V, int n, vector<vector<int>>& vw)
    {
        vector<int> dp(V + 1, 0);
        for (int i = 0; i < n; i++)
        {
            int v = vw[i][0], w = vw[i][1];
            for (int j = V; j >= v; j--)
                dp[j] = max(dp[j], dp[j - v] + w);
        }
        return dp[V];
    }
};

dp[j] 表示容量不超过 j 时的最大价值。从大到小遍历,dp[j - v] 读到的还是“没有考虑第 i 个物品”的旧值,所以第 i 个物品最多被用一次;从小到大遍历会读到已经更新过的 dp[j - v],同一物品被重复使用,那是完全背包。

时间 O(nV)、空间 O(V)。dp[j] 在 j < v 时保持原值,不需要单独处理。

数学与预处理

平方数。给 x(不超过 1e12),找离它最近的完全平方数。题面说明答案唯一,所以不用处理“距离相同取较小”的情况。

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    long long x;
    cin >> x;
 
    long long a = (long long)sqrt((long double)x);
    while ((a + 1) * (a + 1) <= x) a++;
    while (a * a > x) a--;
 
    long long lo = a * a, hi = (a + 1) * (a + 1);
    cout << (x - lo < hi - x ? lo : hi) << endl;
    return 0;
}

sqrt 返回浮点数,理论上可能差一个边界;两个 while 把 a 调整到“a² ≤ x < (a+1)²”,就不依赖浮点舍入。x ≤ 1e12 时 (a+1)² 最大约 1e12,long long 不会溢出。比较 x - lo < hi - x 取更近的那个;两边相等的情况题面保证不出现,真出现时这里会取较大的 hi。

时间 O(1),只做常数次乘法和一次开方。

神奇数。区间 [a,b] 内,若一个数的某两个不同数位能组成一个不含前导零的两位数且是质数,它就算神奇数。范围到 1e5,直接逐个枚举,拆出所有数位,枚举十位和个位的组合,试除判质数。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
bool isPrime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
 
bool isMagic(int x)
{
    int d[10], k = 0;
    while (x)
    {
        d[k++] = x % 10;
        x /= 10;
    }
 
    for (int i = 0; i < k; i++)
    {
        if (d[i] == 0) continue;
        for (int j = 0; j < k; j++)
        {
            if (i == j) continue;
            if (isPrime(d[i] * 10 + d[j])) return true;
        }
    }
    return false;
}
 
int main()
{
    int a, b;
    cin >> a >> b;
 
    int ans = 0;
    for (int x = max(a, 10); x <= b; x++)
        if (isMagic(x)) ans++;
 
    cout << ans << endl;
    return 0;
}

从 max(a, 10) 开始:一位数没有两个不同数位,不可能成为神奇数。i == j 排除了同一个数位被用两次;d[i] == 0 排除了前导零。判断质数只需要试到 sqrt,两位数最多 97,试除几乎不花时间。区间长度 1e5、每个数最多几十次判断,总量很小。

十字爆破。每个格子输出“所在行之和 + 所在列之和 − 自己”,因为自己那一格被行、列各算了一次。预先扫描一遍存下每行和与每列和,之后每个答案是 O(1)。

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
 
    vector<vector<long long>> a(n, vector<long long>(m));
    vector<long long> row(n, 0), col(m, 0);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << row[i] + col[j] - a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

课件 C++ 版有两处要改:

  • scanf("%ld", &arr[i][j]) 读的是 long long。%ld 对应 long,在 Windows 上 long 是 4 字节而 long long 是 8 字节,scanf 只会写进去一半,另一半是未初始化的垃圾;在 Linux 上 long 是 8 字节,碰巧正确。这种“换平台就坏”的写法要用 %lld,或者干脆用 cin。printf("%ld ") 同理。
  • long long arr[n][m] 是变长数组,属于 GCC 扩展,不是标准 C++;它分配在栈上,元素总数到 1e6 量级时就是 8 MB,远超 Windows 默认 1 MB 的栈。用 vector 放堆上,或者按数据上限开静态数组。

时间 O(nm)、空间 O(nm + n + m)。