2026 CCPC 河北省赛

点击查看题面

A. 求求你不要再摔馍片了

题目大意

有 $n$ 包排成一排的馍片，第 $i$ 包的味道记为 $a_i\in \{1,2,3,4,5\}$。每吃一包馍片可获得 $1$ 点基础开心度。若连续吃两包味道分别为 $x$ 与 $y$ 的馍片，还会额外获得 $(y-x+5)mod5$ 点开心度。

现在按初始顺序依次处理每包馍片，对每包馍片可选择是否将其扔到序列末尾（每包馍片至多被扔一次）。处理完毕后，按最终得到的顺序依次吃掉馍片。求能够获得的最大开心度。

数据范围：$1\le n\le {10}^5$，$1\le a_i\le 5$。

---

思路

1. 问题本质拆解

每个元素至多被扔到末尾一次，且同一操作类别内的元素相对顺序保持不变。因此，原数组实际上被划分成了两个保持相对顺序的子序列：

• 保留在原地的子序列 $A$；
• 被移动至末尾的子序列 $B$。

最终的食用顺序即为序列 $A$ 与序列 $B$ 的拼接（$A+B$）。

基础开心度为每包 $1$ 点，总共恒为 $n$ 点。因此问题等价于求相邻馍片间产生的额外开心度的最大值。

2. 状态设计

额外开心度的产生仅与前后相邻的味道相关，分为三部分：

1. 序列 $A$ 内部相邻元素的贡献；
2. 序列 $B$ 内部相邻元素的贡献；
3. 序列 $A$ 的末尾元素与序列 $B$ 的首个元素连接时的跨段贡献。

由于味道数值极小（$1\sim 5$），考虑使用动态规划。在从左至右线性扫描每个元素时，只需记录：

• $x$：序列 $A$ 当前末尾元素的味道（$0$ 表示 $A$ 目前为空）；
• $y$：序列 $B$ 的首个元素的味道（$0$ 表示 $B$ 目前为空）；
• $z$：序列 $B$ 当前末尾元素的味道（$0$ 表示 $B$ 目前为空）。

定义 $\mathrm{dp}[x][y][z]$ 表示当前状态下累积的最大额外开心度（无法达到的状态初始化为 $-1$）。

3. 状态转移

遍历输入序列中的每个 $a_i$，对于所有可达状态 $(x,y,z)$，有两种决策：

• 放入序列 $A$： 新元素 $a_i$ 接在 $x$ 之后。若 $x=0$，增量为 $0$；若 $x>0$，增量为 $(a_i-x+5)mod5$。 状态转移至 $\mathrm{ndp}[a_i][y][z]$。
• 放入序列 $B$：
• 若 $y=0$（序列 $B$ 为空），则 $a_i$ 作为序列 $B$ 的起始元素与当前末尾元素，此时 $y=z=a_i$；
• 若 $y>0$（序列 $B$ 非空），新元素 $a_i$ 接在 $z$ 之后，增量为 $(a_i-z+5)mod5$。 状态转移至 $\mathrm{ndp}[x][y][a_i]$。

4. 边界与答案合并

• 初始状态：$\mathrm{dp}[0][0][0]=0$。
• 统计最终答案时，若序列 $A$ 和序列 $B$ 均非空（即 $x>0$ 且 $y>0$），还需加上两段拼接时的贡献 $(y-x+5)mod5$。
• 遍历所有可能的状态取最大值，最终答案加上固定的基础开心度 $n$。

---

复杂度分析

时间复杂度： 状态空间大小仅为 $6\times 6\times 6=216$。处理序列中的每个元素时，常数级别遍历所有状态，总时间复杂度为 $\mathcal{O}(216\cdot n)=\mathcal{O}(n)$。在 $n={10}^5$ 的规模下可以在几十毫秒内完成。

空间复杂度： 采用两组 $6\times 6\times 6$ 数组实现滚动更新，动态规划部分空间复杂度为 $\mathcal{O}(1)$；存储输入的序列需要 $\mathcal{O}(n)$ 空间，因此整体空间复杂度为 $\mathcal{O}(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

void fc() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int& i : a) std::cin >> i;

    int dp[6][6][6];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0]=0;

    for (int i = 0; i < n; i++) {
        int ndp[6][6][6];
        memset(ndp, -1, sizeof(ndp));
        for (int x = 0; x <= 5; x++) {
            for (int y = 0; y <= 5; y++) {
                for (int z = 0; z <= 5; z++) {
                    if (dp[x][y][z] == -1) continue;
                    if(y==0){
                        ndp[x][a[i]][a[i]]=std::max(ndp[x][a[i]][a[i]],dp[x][0][0]);
                    }
                    int u = (x == 0 ? 0 : a[i] - x + 5) % 5 + dp[x][y][z];
                    int v = (z == 0 ? 0 : a[i] - z + 5) % 5 + dp[x][y][z];
                    ndp[a[i]][y][z] = std::max(ndp[a[i]][y][z], u);
                    if(y)ndp[x][y][a[i]] = std::max(ndp[x][y][a[i]], v);
                }
            }
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    int ans = 0;
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            for (int k = 0; k <= 5; k++) {
                if (dp[i][j][k] == -1) continue;
                // std::cout << i << " " << j << " " << k << " " << dp[i][j][k] + (j - i + 5) % 5 << "\n";
                ans = std::max(ans, dp[i][j][k] + (i == 0 || j == 0 ? 0 : j - i + 5) % 5);
            }
        }
    }
    std::cout << ans + n << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin>>t;
    while (t--) fc();
    return 0;
}

---

E. 电梯

题目大意

大楼共有 $n$ 层，自底向上依次编号为 $1,2,\dots ,n$。现需规划 $m$ 个电梯，每个电梯必须停靠在第 $1$ 层和第 $n$ 层，且可在某些中间楼层停靠。

要求对于大楼中任意两层 $x,y$（$1\le x<y\le n$），存在至少一个电梯可以直达两层（即该电梯在 $x$ 与 $y$ 均停靠，且在 $x$ 和 $y$ 之间不停靠任何其他楼层）。

求出电梯数量 $m$ 的最小值并构造具体的停靠序列。

数据范围：

• $2\le n\le 1000$
• 所有电梯停靠的总层数满足 $\sum _{i=1}^m{k}_i\le 2\times {10}^6$

---

思路

1. 图论模型转化

本题可以抽象为完全有向无环图的路径覆盖问题：

• 将每一层看作图中的顶点 $V=\{1,2,\dots ,n\}$。
• 若电梯在 $x$ 层与 $y$ 层（$x<y$）连续停靠，则等价于在图中包含一条有向边 $(x,y)$。
• 题目要求任意两层均可直达，即图中的每条有向边 $(x,y)$（共 $\frac{n(n-1)}{2}$ 条）都必须作为某个电梯停靠序列中的相邻点对出现至少一次。
• 每个电梯从第 $1$ 层出发，单调递增停靠，最终到达第 $n$ 层，对应一条从源点 $1$ 到汇点 $n$ 的有向路径。

2. 电梯数量 $m$ 的理论下界

考虑对顶点集进行割划分。选取割 $S=\{1,2,\dots ,k\}$ 与 $T=\{k+1,\dots ,n\}$（其中 $1\le k<n$）：

• 从集合 $S$ 指向集合 $T$ 的直达边总数为 $k(n-k)$。
• 由于电梯停靠楼层严格单调递增，任意一条从 $1$ 到 $n$ 的路径一旦从 $S$ 进入 $T$，便无法再次回到 $S$。
• 因此，任意一条路径至多只能覆盖一条跨越割集 $(S,T)$ 的边。

由此可得电梯数量 $m$ 的理论下界：

$$m\ge \underset{1\le k<n}{max}k(n-k)=\lfloor \frac{n}{2}\rfloor \cdot \lceil \frac{n}{2}\rceil =\lfloor \frac{n^2}{4}\rfloor$$

3. 贪心路径拼接与构造

要达到理论下界，需要让尽可能多的边被复用进同一条路径中。利用队列数组 a[i] 维护当前末尾停靠在第 $i$ 层的路径集合：

1. 初始路径生成： 对于所有 $i\in [2,n]$，构建基础二元路径 $\{1,i\}$ 放入 a[i]，覆盖所有从第 $1$ 层出发的边 $(1,i)$。
2. 中间节点延伸（贪心匹配）： 按顺序遍历中间楼层 $i=2,3,\dots ,n-1$。对于所有待覆盖的出边 $(i,j)$（$j>i$）：

• 若 a[i] 非空，说明已有以 $i$ 结尾的路径，直接取出一条路径在其末尾追加 $j$，并将其转移到 a[j]；
• 若 a[i] 为空，说明当前到达 $i$ 的路径已被耗尽，必须新开辟一条路径 $\{1,i,j\}$ 压入 a[j]。

3. 汇点收拢： 处理完所有出边后，遍历 $i=1,\dots ,n-1$，将所有未到达顶层的路径追加终点 $n$，合并至 a[n]。

该策略在前一半节点充分分裂路径以应对瓶颈宽度，在后一半节点高度复用并合并路径，最终生成的总路径数恰好达到下界 $\lfloor n^2/4\rfloor$。

4. 资源限制验证

每条生成的路径长度至多为 $n$。总停靠层数上界为 $\mathcal{O}(n^2)$。当 $n=1000$ 时，总停靠层数约在 $5\times {10}^5$ 左右，远低于题目限制的 $2\times {10}^6$。

---

复杂度分析

时间复杂度： 外层双重循环枚举每对 $(i,j)$，总迭代次数为 $\mathcal{O}(n^2)$。借助 std::move 实现路径的所有权转移，单次转移为 $\mathcal{O}(1)$。最终输出所有停靠层，输出规模与总层数呈线性关系，因此整体时间复杂度为 $\mathcal{O}(n^2)$。

空间复杂度： 队列容器中维护的所有向量元素总数即为电梯停靠的总层数，空间规模为 $\mathcal{O}(n^2)$，满足内存限制。

---

参考代码

参考代码

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

int n;

void fc() {
    std::cin>>n;

    std::vector<std::queue<std::vector<int>>>a(n+1);
    for(int i=2;i<=n;i++){
        std::vector<int>x={1,i};
        a[i].push(std::move(x));
    }

    for(int i=2;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i].empty()){
                std::vector<int>x={1,i,j};
                a[j].push(std::move(x));
            }else{
                a[i].front().push_back(j);
                a[j].push(std::move(a[i].front()));
                a[i].pop();
            }
        }
    }

    for(int i=1;i<n;i++){
        while(a[i].size()){
            a[i].front().push_back(n);
            a[n].push(std::move(a[i].front()));
            a[i].pop();
        }
    }

    std::cout<<a[n].size()<<"\n";
    while(a[n].size()){
        for(auto x:a[n].front())std::cout<<x<<" ";
        std::cout<<"\n";
        a[n].pop();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

H. 可能是字符串签到题

题目大意

给定一个长度为 $n$ 且仅由小写英文字母组成的字符串 $s$（下标从 $1$ 开始）。给出 $q$ 次询问，每次询问给出区间 $[l,r]$，求子串 $s[l,r]$ 中出现次数最多的子串的出现次数。

数据范围：

• $1\le n,q\le {10}^6$
• $1\le l\le r\le n$
• 字符串 $s$ 仅包含小写字母

---

思路

1. 问题性质转化（单字符支配性）

题目询问的是子串 $s[l,r]$ 中出现次数最多的任意子串的频次。

假设某个长度为 $m$（$m\ge 1$）的非空子串 $T=t_1{t}_2\dots t_m$ 在区间 $[l,r]$ 中出现了 $k$ 次。由于 $T$ 的每次出现都必定伴随着其首字符 $t_1$ 在相同起始位置的出现，因此单字符 $t_1$ 在 $[l,r]$ 内的出现次数必然不小于 $k$。

由此可得：

$$\underset{T\subseteq s[l,r]}{max}\mathrm{count}(T)=\underset{c\in \mathrm{\Sigma }}{max}\mathrm{count}(c)$$

即出现频次最高的子串必可退化为单个字符。原问题直接等价于：在子串 $s[l,r]$ 中，统计出现频次最高的单个字符的出现次数。

2. 前缀和优化

由于字符集大小 $|\mathrm{\Sigma }|=26$ 极小，针对区间频次查询，最直接有效的数据结构为二维前缀和：

• 定义 $b[c][i]$ 表示前缀 $s[1\dots i]$ 中字符 $c$ 的出现次数。
• 状态转移方程为：

$$b[c][i]=b[c][i-1]+[s[i]=c]$$

• 对于每次给定的询问 $[l,r]$，字符 $c$ 在该区间内的频次可利用前缀和在 $\mathcal{O}(1)$ 复杂度内计算：

$$\mathrm{count}(c,[l,r])=b[c][r]-b[c][l-1]$$

• 遍历 $26$ 个字符取最大值，即可在 $\mathcal{O}(|\mathrm{\Sigma }|)$ 的时间内回答单次询问。

---

复杂度分析

时间复杂度：

• 预处理阶段：构建前缀和数组需要扫描整个字符串并更新各字符的前缀和，耗时 $\mathcal{O}(|\mathrm{\Sigma }|\cdot n)$。
• 查询阶段：单次查询枚举 $26$ 个字母计算区间和，耗时 $\mathcal{O}(|\mathrm{\Sigma }|)$；处理 $q$ 次询问的总耗时为 $\mathcal{O}(|\mathrm{\Sigma }|\cdot q)$。
• 总时间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|\cdot (n+q))$，其中 $|\mathrm{\Sigma }|=26$。代入 $n,q\le {10}^6$，整体运算量约为 $5\times {10}^7$，在 $1.0\text{ s}$ 内可轻松通过。

空间复杂度：

• 维护大小为 $26\times (n+1)$ 的前缀和数组。当 $n={10}^6$ 时，该数组约占用 $26\times {10}^6\times 4\text{ B}\approx 104\text{ MB}$ 内存。
• 总空间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|\cdot n)$，处于常规限制（$256\text{ MB}$ 或 $512\text{ MB}$）的安全阈值内。

---

参考代码

参考代码

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

void fc() {
    int n,q;std::cin>>n>>q;
    std::string s;std::cin>>s;

    std::vector<std::vector<int>>b(26,std::vector<int>(n+1));
    for(int i=0;i<n;i++){
        int c=s[i]-'a';
        b[c][i+1]=1;
    }

    for(int i=0;i<26;i++){
        for(int j=1;j<=n;j++)b[i][j]+=b[i][j-1];
    }

    while(q--){
        int l,r;std::cin>>l>>r;
        int mx=0;
        for(int i=0;i<26;i++)mx=std::max(mx,b[i][r]-b[i][l-1]);
        std::cout<<mx<<"\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

I. 山海关老冰棍

题目大意

工厂中有 $N$ 台生产线同时并行工作，第 $i$ 台生产线生产一份老冰棍需要耗时 $t_i$ 分钟。现需生产至少 $M$ 份老冰棍，求完成订单所需的最少分钟数。

数据范围：

• $1\le N\le {10}^5$
• $1\le M\le {10}^{12}$
• $1\le t_i\le {10}^6$

---

思路

1. 问题性质与单调性分析

设总耗时为 $T$（$T\ge 0$）。由于各生产线独立并行工作，且每台生产线生产一份冰棍所需时间固定为 $t_i$，则在时间 $T$ 内，第 $i$ 台生产线所能独立完成的冰棍数量为：

$$c_i(T)=\lfloor \frac{T}{t_i}\rfloor$$

在时间 $T$ 内，工厂所有生产线产出的冰棍总数即为：

$$f(T)=\sum _{i=1}^N\lfloor \frac{T}{t_i}\rfloor$$

易知函数 $f(T)$ 关于时间 $T$ 具有单调不减性（Monotonicity）：

• 当 $T$ 增大时，各生产线能生产的冰棍数量 $c_i(T)$ 必然单调不减，因此总产出 $f(T)$ 随之单调不减；
• 当 $T\to \mathrm{\infty }$ 时，$f(T)\to \mathrm{\infty }$。

原问题要求求解满足 $f(T)\ge M$ 的最小非负整数 $T$。最优化问题具备单调判定性，故可直接使用二分答案（Binary Search on Answer）进行求解。

2. 二分上界估计与设计

• 下界（$l$）：若 $T=0$，显然产出为 $0<M$，故可行解的开区间下界可设为 $l=0$。
• 上界（$r$）：考虑最劣情况，即使仅由生产耗时最短的生产线单独完成全部 $M$ 份订单，耗时至多为 $min(t_i)\times M\le {10}^6\times {10}^{12}={10}^{18}$。在 64 位有符号整型（long long，最大值约 $9.22\times {10}^{18}$）表示范围内不会超出，直接取上界为足够大值（如 LLONG_MAX）亦可。

3. 判定函数（Check）实现

对于二分出的时间点 $\text{mid}$：

• 累加各生产线的产出 $s=\sum _{i=1}^N\lfloor \text{mid}/t_i\rfloor$。
• 一旦累加和 $s\ge M$，即可提前返回 true。这一步不仅实现了常数级剪枝，而且有效规避了多项累加可能导致的 64 位整型溢出风险。
• 遍历结束后若 $s<M$，返回 false。

采用开区间 $(l,r)$ 二分范式维护不变量（$l$ 始终不满足条件，$r$ 始终满足条件），当 $l+1=r$ 时二分收敛，$r$ 即为所求的最小合法时间。

---

复杂度分析

时间复杂度：

• 判定函数 check 需要遍历 $N$ 条生产线，单次复杂度为 $\mathcal{O}(N)$。
• 二分搜索的值域跨度为 $R\approx {10}^{18}$（或 $2^{63}-1$），二分迭代次数为 $\mathcal{O}(\log R)\approx 60$ 次。
• 总时间复杂度为 $\mathcal{O}(N\log R)$。代入 $N={10}^5$，总运算量约为 $6\times {10}^6$，在时限内耗时极低。

空间复杂度：

• 仅需线性数组存储 $N$ 条生产线的耗时参数 $t_i$。
• 总空间复杂度为 $\mathcal{O}(N)$。

---

参考代码

参考代码

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

void fc() {
    int n,m;
    std::cin>>n>>m;

    std::vector<ll>a(n);
    for(auto &i:a)std::cin>>i;

    auto check=[&](ll k){
        ll s=0;
        for(auto& x:a){
            s+=k/x;
            if(s>=m)return true;
        }
        return s>=m;
    };

    ll l=0,r=1e18;
    while(l+1<r){
        ll mid=l+((r-l)>>1);
        if(check(mid))r=mid;
        else l=mid;
    }
    std::cout<<r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

J. 海鲜大排档点生蚝

题目大意

秦皇岛的海鲜大排档中共有 $N$ 家售卖生蚝的摊位，你的总预算为 $M$ 元，且只能选择其中一家摊位进行消费。

对于第 $i$ 家摊位，提供两种购买模式（可混合购买）：

1. 单买：价格为 $A_i$ 元/个；
2. 整打购买：价格为 $B_i$ 元/打（$1$ 打包含 $12$ 个）。

求在最优购买策略下最多可以购买的生蚝总数。若有多家摊位均可达到该最大数量，输出其中编号最小的摊位编号。

数据范围：

• $1\le N\le {10}^5$
• $1\le M\le {10}^9$
• $1\le A_i,B_i\le {10}^5$

---

思路

1. 单个摊位的贪心策略分析

对于固定的摊位 $i$（单价 $A_i$，整打价 $B_i$），购买生蚝的问题等价于带约束的性价比贪心问题。购买 $12$ 个单买生蚝的成本为 $12\times A_i$。

根据性价比对比，可以分为两种情况：

• 情况一：$12\times A_i\le B_i$ 此时单买 $12$ 个的成本不高于整打购买的价格，整打购买没有任何价格优势。因此完全无需整打购买，全部预算用于单买即可取得最优解：

$$\text{count}=\lfloor \frac{M}{A_i}\rfloor$$

• 情况二：$12\times A_i>B_i$ 此时整打购买具有更低的均价，即 $B_i/12<A_i$。最优策略应尽可能优先整打购买：

1. 最大化购买整打数量：$k=\lfloor M/B_i\rfloor$，获得 $12\times k$ 个生蚝；
2. 剩余资金为 $M^{\prime }=Mmod{B}_i$。由于 $M^{\prime }<B_i$，已无法再买整打，剩余资金全部用于单买，获得 $\lfloor M^{\prime }/A_i\rfloor$ 个生蚝。

贪心最优性证明： 是否存在“少买一打，腾出资金用于单买能获得更多生蚝”的情况？ 若退订 $1$ 打生蚝，释放资金 $B_i$，用该资金单买所能获得的生蚝数量为 $\lfloor B_i/A_i\rfloor$。 由于 $B_i<12\times A_i⟹B_i/A_i<12$，因此：

$$\lfloor \frac{B_i}{A_i}\rfloor \le 11<12$$

即退订 $1$ 打生蚝腾出的资金最多只能单买 $11$ 个生蚝，净收益严格减少。因此，优先买满整打的贪心选择具有最优子结构性质。

2. 全局最优维护

遍历全部 $N$ 家摊位，分别计算在预算 $M$ 下各摊位能产出的最大生蚝数。动态维护历史最大数量 ans 以及对应的最优摊位编号 as。当且仅当当前摊位获得的数量严格大于历史最大值时更新答案，天然保证了在数量并列时保留编号更小的摊位。

---

复杂度分析

时间复杂度：

• 对于每家摊位，计算最大购买量仅涉及常数次基础整数运算（乘法、除法、取模），单次复杂度为 $\mathcal{O}(1)$。
• 遍历所有 $N$ 家摊位，整体时间复杂度为 $\mathcal{O}(N)$。在 $N={10}^5$ 下耗时在数毫秒内。

空间复杂度：

• 算法采用在线扫描处理，无需持久化存储摊位数据，仅需常数级别的变量辅助，整体空间复杂度为 $\mathcal{O}(1)$。

---

参考代码

参考代码

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

ll f(ll a,ll b,ll m){
    ll aa=a*12;
    if(aa<=b)return m/a;
    else{
        ll res=m/b*12;
        m%=b;
        return res+m/a;
    }
}

void fc() {
    ll n,m;
    std::cin>>n>>m;
    ll ans=0,as=0;

    for(int i=0;i<n;i++){
        int a,b;std::cin>>a>>b;
        ll k=f(a,b,m);
        if(k>ans){
            as=i+1;
            ans=k;
        }
    }

    std::cout<<ans<<" "<<as;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

M. 拯救猫猫

题目大意

给定一个 $n\times m$ 的网格图，其中包含空地（.）、障碍物（#）、起点 $S$、出口 $E$ 以及若干只朝向固定的狗（U、D、L、R 分别表示上、下、左、右）。

每只狗的视线沿其正前方直线延伸，直到遇到障碍物或另一只狗为止。猫猫需要从起点 $S$ 走到出口 $E$，移动规则如下：

1. 只能在上下左右相邻的四个空地间移动，不能走出网格；
2. 不能进入任何狗的视线覆盖范围；
3. 不能踏入障碍物或狗所在的格子。

现在可以选择恰好一只狗让其睡着。睡着的狗会失去其视线，但该位置本身依然不可通行。问是否存在一种方案使得猫猫能成功从 $S$ 走到 $E$。若存在，输出字典序最小（即行坐标优先，其次列坐标）的狗的坐标（$1$-indexed）；若不存在，输出 -1 -1。

数据范围：

• $1\le t\le 100$
• $1\le n,m\le 2000$，且所有测试数据中 $n$ 与 $m$ 的总和均不超过 $2000$
• 起点 $S$ 和出口 $E$ 保证初始时不在任何狗的视线内，且网格中至少存在一只狗

---

思路

1. 问题建模与视线预处理

猫猫移动的限制核心在于“不能进入任何狗的视线”。设全网格中每只狗的视线路径为一个有向线段集合。

• 若一个空地被 $\ge 2$ 只狗的视线重叠覆盖，则使其中任意一只狗睡着，该格子依然处于其他狗的监视之下，依然不可通行；
• 若一个空地恰好只被 $1$ 只狗的视线覆盖，则当且仅当这只特定的狗睡着时，该格子才会重新变为可行走的空地；
• 若一个空地从未被任何狗覆盖（包括 $S$ 和 $E$），则它始终是绝对安全的通行格。

因此，可以先遍历所有的狗，沿其朝向发射射线，在遇到边界、障碍物或其他狗之前，对路径上的空地统计覆盖次数（在代码中通过在字符 '1' 上递增模拟计数）。

2. 基底图连通性与动态扩展

对于初始状态下未被任何狗监视的格子集合 $V_{\text{safe}}$，猫猫在其相邻的格子之间可以自由移动。

• 我们利用并查集（DSU）预先将所有四连通的初始安全格子合并，建立静态的连通分量基底。
• 此时若直接将某只狗置为睡眠状态，相当于将该狗视线上覆盖次数恰好为 $1$ 的格子动态加入图。这些新解锁的格子需要：

1. 与其自身射线方向上相邻的解锁格子连边；
2. 与其上下左右相邻的初始安全格子连边。

3. 可撤销并查集（Rollback DSU）

网格中可能存在多只狗，若对每只狗都重新构建完整的并查集，时间开销将达到 $\mathcal{O}(K\cdot nm)$（$K$ 为狗的数量），严重超时。

注意到每次让一只狗睡着所带来的图结构变化是暂时的、局部的：

• 采用按秩/按大小合并（Union by Size）并不使用路径压缩的可撤销并查集。
• 在测试某只狗之前，记录并查集的操作历史版本快照（Snapshot）。
• 动态连边并判定起点 $S$ 与出口 $E$ 是否连通。
• 判定结束后，通过操作栈回滚（Rollback）撤销该狗引起的所有合并操作，瞬间还原到基底图状态。

4. 贪心搜索与字典序优先

按照从上到下、从左到右的顺序依次收集每只狗。由于题目要求优先输出行坐标最小、其次列坐标最小的方案，因此按该顺序枚举测试狗。一旦某只狗能使 $S$ 与 $E$ 连通，当前狗的坐标即为全局字典序最优解，直接输出并退出即可；若所有狗测试完毕后均无法连通，则无解输出 -1 -1。

---

复杂度分析

时间复杂度：

• 视线覆盖预处理：每只狗的射线最长为 $max(n,m)$。设狗的总数为 $K$，射线遍历的总步数不超过 $\mathcal{O}(K\cdot max(n,m))$，在最坏网格分布下受限于 $\mathcal{O}(nm)$。
• 初始基底合并：遍历所有单元格并合并相邻安全格，由于采用按大小合并的并查集，单次合并耗时 $\mathcal{O}(\log (nm))$，总耗时 $\mathcal{O}(nm\log (nm))$。
• 枚举与回滚：对于每只狗，其视线上解锁的格子数不超过射线长度 $L_i$。每个解锁格至多进行 $5$ 次合并操作，单次代价 $\mathcal{O}(\log (nm))$，回滚代价为 $\mathcal{O}(1)$。因此每只狗的检验代价为 $\mathcal{O}(L_i\log (nm))$。
• 总时间复杂度：$\mathcal{O}(nm\log (nm)+\sum L_i\log (nm))$。对于 $\sum n,\sum m\le 2000$，整体运算量完全在时限（$1.0\text{ s}$）允许范围内。

空间复杂度：

• 网格地图占用 $\mathcal{O}(nm)$ 内存；
• 并查集数组 fa、siz 占用 $\mathcal{O}(nm)$ 内存；
• 操作历史栈 his 的深度在基底合并时至多为 $\mathcal{O}(nm)$，在单只狗测试阶段至多增长 $\mathcal{O}(max(n,m))$。
• 总空间复杂度：$\mathcal{O}(nm)$。

---

参考代码

参考代码

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

struct DSU {
    std::vector<int> fa, siz;
    struct op {
        int u, v;
    };
    std::vector<op> his;

    DSU(int n) : fa(n + 1), siz(n + 1, 1) { std::iota(fa.begin(), fa.end(), 0); }

    int find(int x) {
        while (x != fa[x]) x = fa[x];
        return fa[x];
    }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) std::swap(x, y);
        siz[x] += siz[y];
        fa[y] = x;
        his.push_back({x, y});
        return true;
    }

    int snapshot() const { return his.size(); }

    void rollback(int snap) {
        while ((int)his.size() > snap) {
            auto& [u, v] = his.back();
            siz[u] -= siz[v];
            fa[v] = v;
            his.pop_back();
        }
    }
};

bool isDog(char c) { return c == 'U' || c == 'D' || c == 'L' || c == 'R'; }

void Dxy(int& dx, int& dy, char c) {
    if (c == 'U')
        dx = -1, dy = 0;
    else if (c == 'D')
        dx = 1, dy = 0;
    else if (c == 'L')
        dx = 0, dy = -1;
    else
        dx = 0, dy = 1;
}

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void fc() {
    int n, m;
    std::cin >> n >> m;

    auto id = [&](int x, int y) { return x * m + y; };

    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) std::cin >> s[i];

    std::vector<std::pair<int, char>> dog;
    dog.reserve(2000);

    auto isGo = [&](int x, int y, bool is) -> bool {
        if (x < 0 || x >= n || y < 0 || y >= m) return false;
        return s[x][y] == '.' || s[x][y] == 'S' || s[x][y] == 'E' || (is && s[x][y] == '1');
    };

    int start = -1, end = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'S')
                start = id(i, j);
            else if (s[i][j] == 'E')
                end = id(i, j);
            else if (isDog(s[i][j]))
                dog.push_back({id(i, j), s[i][j]});
        }
    }

    for (auto& [idx, c] : dog) {
        int dxx, dyy;
        Dxy(dxx, dyy, c);

        int x = idx / m + dxx, y = idx % m + dyy;
        while (true) {
            if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#'||isDog(s[x][y])) break;
            if (s[x][y] == '.')
                s[x][y] = '1';
            else
                s[x][y]++;
            x += dxx;
            y += dyy;
        }
    }

    DSU dsu(n * m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!isGo(i, j, 0)) continue;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (isGo(nx, ny, 0)) {
                    dsu.merge(id(i, j), id(nx, ny));
                }
            }
        }
    }

    for (auto& [idx, c] : dog) {
        int dxx, dyy;
        Dxy(dxx, dyy, c);
        int x = idx / m + dxx, y = idx % m + dyy;

        int snap = dsu.snapshot();
        int prex = -1, prey = -1;

        int k=0;

        while (true) {
            if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#' || isDog(s[x][y])) break;
            
            if (s[x][y] != '1') {
                prex = prey = -1;
                x += dxx;
                y += dyy;
                continue;
            }
            if(prex!=-1)dsu.merge(id(x,y),id(prex,prey));
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (isGo(nx, ny, 0)) dsu.merge(id(x, y), id(nx, ny));
            }
            prex=x,prey=y;
            x += dxx;
            y += dyy;
        }

        if (dsu.same(start, end)) {
            std::cout << idx / m + 1 << " " << idx % m + 1 << "\n";
            return;
        }

        dsu.rollback(snap);
    }

    std::cout << "-1 -1" << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---