26-05-15思维周赛题解

周赛链接：https://hydro.ac/d/codingSunday/contest

原题连接：
T1:
https://www.luogu.com.cn/problem/P7060
T2:
https://www.luogu.com.cn/problem/P6444
T3:
https://www.luogu.com.cn/problem/AT_abc456_d
T4:
https://atcoder.jp/contests/abc456/tasks/abc456_e

T1:

题意简述

Alice 梦见了她的闹钟，醒来只记得数码管上总共亮了多少段。闹钟显示四位时间hh:mm，每个数字0~9在数码管上亮的段数是固定的。给定一个总段数n，让你找出最小的一个合法时间。如果没有合法时间能凑出这个段数，输出Impossible。

思路分析

这题看着唬人，其实范围极小。

小时只有0~23，分钟只有0~59，总共就24 × 60 = 1440种可能。对于这么小的一个集合，直接暴力枚举完全够用，不需要任何高级算法。

关键问题：怎么算一个时间的段数？

把hh:mm拆成四个独立的数字：

• 小时的十位：h / 10
• 小时的个位：h % 10
• 分钟的十位：m / 10
• 分钟的个位：m % 10

每个数字亮几段是固定的，提前打表存好就行。比如0亮 6 段，1亮 2 段，8亮 7 段。

为什么从小到大枚举，第一个找到的就是答案？

因为你是从00:00开始，按时间顺序往后扫的。时间本身天然有序，第一个满足条件的时间，就是所有解里最小的那个。不需要额外排序，也不需要记录最小值。

如果全部1440个时间都扫完了，没有一个段数等于n，那就说明n不可能由任何合法时间凑出来，输出Impossible。

C++ 标程

#include<<bits/stdc++.h> using namespace std; // 每个数字 0~9 在数码管上点亮的段数 // 顺序：0, 1, 2, 3, 4, 5, 6, 7, 8, 9 // 例如：数字 0 亮 6 段，数字 1 亮 2 段，数字 8 亮 7 段 int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int main() { int n; cin >> n; // 从小到大枚举所有合法时间 // h 从 0 到 23（小时），m 从 0 到 59（分钟） for (int h = 0; h < 24; h++) { for (int m = 0; m < 60; m++) { // 拆位：把 hh:mm 拆成四个单独的数字 int a = h / 10; // 小时的十位 int b = h % 10; // 小时的个位 int c = m / 10; // 分钟的十位 int d = m % 10; // 分钟的个位 // 查表求和，得到这个时间的总段数 int sum = seg[a] + seg[b] + seg[c] + seg[d]; // 如果总段数正好等于 n，这就是最小答案 if (sum == n) { // %02d 表示输出两位整数，不足两位自动补前导零 // 例如 h=9, m=3 会输出成 09:03 printf("%02d:%02d\n", h, m); return 0; // 直接结束程序 } } } // 全部 1440 种可能都枚举完了，没有一个匹配 cout << "Impossible\n"; return 0; }

代码要点：

• seg数组打表，查表复杂度 O(1)。
• 双重循环枚举，总次数固定 1440，远低于时限。
• %02d自动处理前导零，不用自己写if判断。
• 找到第一个解立刻return 0，保证输出的是最小时间。

T2

题意简述

nnn间宿舍排成一排，第iii间住了两名学生，分别来自省份aia_iai​和bib_ibi​。

阿姨要选一段连续的宿舍（比如第LLL间到第RRR间），每间宿舍只能查一人，而且查到的所有人必须来自同一个省份。

问最多能查多少人？如果多种方案人数相同，输出省份编号最小的那个。

思路分析

不管值域多大，核心问题都是一样的：找一段连续区间，使得区间内每间宿舍都包含某个特定省份xxx，求这个区间的最大长度。

不同数据范围，用的工具不一样，但思路是递进的。

1. 测试点 1~10：值域≤10\le 10≤10（小值域）

省份编号最多只有1∼101\sim 101∼10这十种可能。那最直接的办法就是枚举每个省份x=1∼10x = 1\sim 10x=1∼10，看看xxx能连续撑多少间宿舍。

对每个xxx，从头到尾扫一遍：

• 第iii间宿舍有xxx（ai=xa_i=xai​=x或bi=xb_i=xbi​=x）：当前连续长度+1+1+1
• 没有xxx：连续长度清零

扫完 10 遍，取最大值。长度相同时，因为xxx从小到大枚举，天然保留了省份编号最小的。

复杂度：O(10×n)O(10 \times n)O(10×n)，也就是O(n)O(n)O(n)。

大概代码：

intcur[11]={0},best[11]={0};for(inti=1;i<=n;i++){inta,b;cin>>a>>b;for(intx=1;x<=10;x++){if(a==x||b==x){cur[x]++;best[x]=max(best[x],cur[x]);}else{cur[x]=0;// 断了}}}

2. 测试点 11~18：值域≤106\le 10^6≤106（中值域）

值域变大了，不能再枚举1∼1061\sim 10^61∼106，那样会超时。

关键观察：每间宿舍只跟ai,bia_i, b_iai​,bi​两个省份有关。走到第iii间时，只有这两个省份的连续段可能变长，其他所有省份在这一步一定断掉。

既然值域是10610^6106，我们可以直接开两个大小为106+510^6+5106+5的数组：

• len[x]：省份xxx当前的连续长度
• last[x]：省份xxx上一次出现在哪间宿舍（版本号）

处理第iii间宿舍的省份xxx时：

• 如果last[x] == i - 1，说明xxx是连续出现的，len[x]++
• 否则说明中间断了，len[x] = 1（从当前这间重新开始）
• 更新last[x] = i

数组查改都是O(1)O(1)O(1)，每间宿舍最多处理两个值，总复杂度O(n)O(n)O(n)。两个 int 数组约 8MB，内存够用。

大概代码：

constintMAX=1e6+5;intlen[MAX]={0},last[MAX]={0};// last 默认 0，表示还没出现过for(inti=1;i<=n;i++){inta,b;cin>>a>>b;// 处理 aif(last[a]==i-1)len[a]++;elselen[a]=1;last[a]=i;// 同理处理 b（注意 a==b 时别重复处理）// ...}

3. 测试点 19~20：值域≤109\le 10^9≤109（大值域）

值域太大，数组开不下。但思路还是一样：每步只处理当前宿舍的两个省份，其他省份不管。

用map（或者unordered_map）动态存每个省份的len和last。逻辑和数组版完全一样，只是查改从O(1)O(1)O(1)变成O(log⁡n)O(\log n)O(logn)。

总复杂度O(nlog⁡n)O(n \log n)O(nlogn)，n=105n = 10^5n=105时约1.7×1061.7 \times 10^61.7×106次操作，完全够用。

C++ 标程

#include<<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // len[x]：省份 x 当前的连续段长度 // last[x]：省份 x 上一次被处理到的宿舍编号（版本号） map<long long, int> len; map<long long, int> last; int ansLen = 0; // 最多查到的人数 long long ansVal = 0; // 对应的省份编号 bool first = true; // 标记是不是第一次更新答案 for(int i = 1; i <= n; i++){ long long a, b; cin >> a >> b; // 当前宿舍需要处理的省份（去重，防止 a==b 时重复处理两次） long long cur[2]; int cnt = 0; if(a == b){ cur[cnt++] = a; }else{ cur[cnt++] = a; cur[cnt++] = b; } for(int k = 0; k < cnt; k++){ long long x = cur[k]; // 检查 x 是否刚好在上一个宿舍出现过 auto it = last.find(x); if(it != last.end() && it->second == i - 1){ len[x]++; // 连续段延续 }else{ len[x] = 1; // 中断了，从当前宿舍重新开始算 } last[x] = i; // 更新版本号 // 更新全局最优：更长，或长度相同但省份编号更小 if(first || len[x] > ansLen || (len[x] == ansLen && x < ansVal)){ ansLen = len[x]; ansVal = x; first = false; } } } cout << ansLen << " " << ansVal << "\n"; return 0; }

• a == b时只处理一次，避免同一间宿舍给同一个省份连续段加两次。
• 用first标记处理第一次更新，避免初始值干扰。
• 比较答案时显式判断x < ansVal，因为我们是按宿舍顺序处理，不是按省份大小顺序。

T3：

题意简述

你得到一个字符串SSS，由a，b，c组成。

对998244353998244353998244353取模，求SSS中没有两个相邻字符相同的非空子序列的个数。

如果两个子序列取自不同的位置，则认为它们是不同的，即使它们是相同的字符串。

什么是子序列？SSS的子序列是从SSS中删除零个或多个字符并将其余字符按原始顺序连接起来获得的字符串。例如，ab，ac是abc的子序列，但ca，bb不是abc的子序列。

思路分析

这道题要求统计字符串中所有满足"相邻字符不同"的非空子序列数量。与子串问题不同，子序列允许跳过某些字符，但必须保持原有顺序。

我们可以用动态规划来解决这个问题。核心思想是维护以每个字符结尾的合法子序列数量。设 dp[i][x] 表示前 i 个字符中，以字符 x （ x 为 0、1、2 分别代表a、b、c）结尾的满足条件的子序列数量。

对于每个字符，我们有两种选择：选或不选。如果不选当前字符，那么状态直接继承前一个位置的结果。如果选择当前字符，那么它可以接在所有不以相同字符结尾的子序列后面，同时它本身也构成一个新的子序列。

具体来说，假设当前字符是 x ，那么以 x 结尾的子序列数量等于：之前以 x 结尾的子序列数量（不选当前字符）加上之前以其他字符结尾的子序列数量之和（选当前字符并接在后面），再加上 1（仅包含当前字符本身）。

最终答案就是以a、b、c结尾的子序列数量之和。

C++ 标程

#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 5, MOD = 998244353; string s; int dp[maxn][3]; // dp[i][x]:前i个字符中以字符x结尾的合法子序列数 int main() { cin >> s; int n = s.size(); for (int i = 0; i < n; i++) { int x = s[i] - 'a'; // 将字符转换为0-2的索引 dp[i][x] = 1; // 当前字符本身构成一个子序列 if (i) // 不是第一个字符时 { // 不选当前字符，继承前一个位置的状态 dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD; dp[i][1] = (dp[i][1] + dp[i - 1][1]) % MOD; dp[i][2] = (dp[i][2] + dp[i - 1][2]) % MOD; // 选当前字符，可以接在所有不以相同字符结尾的子序列后面 for (int j = 0; j < 3; j++) if (j != x) // 只能接在不同字符结尾的子序列后 dp[i][x] = (dp[i][x] + dp[i - 1][j]) % MOD; } } // 答案是所有以a、b、c结尾的子序列数量之和 cout << ((dp[n - 1][0] + dp[n - 1][1]) % MOD + dp[n - 1][2]) % MOD; return 0; }

T4：

题意简述

AtCoder王国有几个城市，称为city。有连接成对城市的MMM条双向道路，其中iii条道路连接城市UiU _ iUi​和ViV _ iVi​。任何一对城市都可以通过穿越一些道路到达对方。

在AtCoder王国，一个星期由WWW天组成。一个星期是由天1,2,…,W1,2,\dots,W1,2,…,W组成的，日复一日WWW就是天111。

每个城市每周都有特定的假日。城市iii的假日信息以长度为WWW的字符串SiS _ iSi​给出：如果SiS _ iSi​的jjj第一个字符为 ‘ o ’，则日期jjj为假日；如果为 ‘ x ’，则日jjj为工作日。

高桥选了一个他喜欢的城市，在一天的中午去参观。此后的每个晚上，他都反复选择要么留在现在的城市，要么搬到有公路直接连接的城市。如果他有可能继续移动，使他每天中午所在的城市是假日，则输出 “Yes”，否则输出 “No”。

给出了TTT测试用例；每个都解出来。

思路分析

这道题要求判断是否存在一种旅行方案，使得 Takahashi 每天中午所在的城市都是假期。核心思路是将问题转化为在状态图中寻找环的问题。

我们可以将每个状态表示为 (城市, 天数) 的组合，其中天数在 0 到 W-1 之间循环。从第 1 天开始，Takahashi 可以选择任何一个当天是假期的城市作为起点。每天晚上，他有两种选择：留在当前城市，或者移动到相邻城市。这两种选择对应着状态之间的转移。

关键观察是，如果状态图中存在环，那么Takahashi就可以无限循环下去。因此问题转化为：在状态图中是否存在从任何合法起点出发的环。

具体实现时，我们构建一个扩展图，其中每个节点代表 (城市, 天数) 的状态。如果某天在城市 u ，第二天可以选择留在 u 或者移动到相邻城市 v 。我们使用DFS来检测这个图中是否存在环，如果存在环就输出 “Yes”，否则输出 “No”。

C++ 标程

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n, m, w, vis[maxn * 10]; // vis记录节点访问状态：0-未访问，1-访问中，2-已访问 string s[maxn]; vector<int> e[maxn * 10]; // 扩展图的邻接表 vector<pair<int, int>> edge; // 存储原始边 // 将(城市x, 天数d)转换为唯一的节点编号 int num(int x, int d) { return x + d * n; } // DFS检测环，返回true表示找到环 bool dfs(int x) { if (vis[x] == 1) // 发现回边，存在环 return true; if (vis[x] == 2) // 该节点已处理完毕，无环 return false; vis[x] = 1; // 标记为访问中 for (int i : e[x]) { int _x = i % n; // 获取城市编号 int _d = i / n; // 获取天数 if (s[_x][_d] == 'o') // 目标状态必须是假期 { if (dfs(i)) return true; } } vis[x] = 2; // 标记为已处理完毕 return false; } void solve() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; edge.push_back({u - 1, v - 1}); // 转换为0-based索引 } cin >> w; for (int i = 0; i < n; i++) cin >> s[i]; // 添加"留在原地"的边：从(城市i, 天数j)到(城市i, 天数(j+1)%w) for (int i = 0; i < n; i++) for (int j = 0; j < w; j++) { e[num(i, j)].push_back(num(i, (j + 1) % w)); } // 添加"移动到相邻城市"的边 for (auto [u, v] : edge) { // 从u到v：第i天在u，第i+1天在v for (int i = 0; i < w; i++) e[num(u, i)].push_back(num(v, (i + 1) % w)); // 从v到u：第i天在v，第i+1天在u for (int i = 0; i < w; i++) e[num(v, i)].push_back(num(u, (i + 1) % w)); } int ans = 0; // 检查所有第1天是假期的城市作为起点 for (int i = 0; i < n; i++) if (s[i][0] == 'o' && !vis[num(i, 0)]) { ans |= dfs(num(i, 0)); // 只要有一个起点能找到环就可以 } cout << (ans ? "Yes" : "No") << '\n'; // 清空数据，准备下一组测试用例 edge.clear(); for (int i = 0; i <= n * w; i++) e[i].clear(), vis[i] = 0; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) { solve(); } return 0; }