2025“钉耙编程”中国大学生算法设计春季联赛（8）10031007

题目的意思很好理解找从最左边到最右边最短路（BFS）

#include <bits/stdc++.h>
using namespace std;
int a[510][510];  // 存储网格中每个位置是否有障碍（1表示有障碍，0表示无障碍）
int v[510][510];   // 记录每个位置是否被访问过（1表示已访问，0表示未访问）
int ans, n, m;     // ans: 最短路径长度，n: 网格行数，m: 网格列数
queue<pair<int, int>> q;  // 使用pair存储坐标的队列，用于BFS
int T;             // 测试用例数量inline void solve(){// 初始化数组memset(a, 0, sizeof(a));  // 清空障碍物数组memset(v, 0, sizeof(v));   // 清空访问标记数组cin >> n >> m;            // 读取网格行数和列数ans = n * m;              // 初始化为最大可能值（网格总格子数）// 读取每个行的障碍物信息for (int i = 1; i <= n; ++i) {int r, t;cin>>r; // 读取第i行的障碍物数量for (int j = 1; j <= r; ++j) {cin>>t;    // 读取障碍物所在列a[i][t] = 1;        // 标记该位置有障碍}}// 初始化BFS队列：将所有第一列无障碍的位置加入队列for (int i = 1; i <= n; ++i) {if (!a[i][1]) {         // 如果该位置无障碍q.push({i, 1});     // 加入队列v[i][1] = 1;        // 标记为已访问}}int t = 0;          // 当前步数bool found = false; // 是否找到解的标志while (!q.empty() && !found) {t++;            // 步数增加int s = q.size(); // 遍历队列里面的所有for (int j = 0; j < s; ++j) {auto [x, y] = q.front();  // 取出队首坐标q.pop();// 如果到达最后一列，更新答案并结束搜索if (y == m) {ans = min(ans, t);found = true;break;}// 剪枝：如果当前步数加上剩余列数已经不可能更优，跳过,其实这里不用剪也行if (t + (m - y) >= ans) continue;// 尝试向右移动if (y + 1 <= m && !v[x][y + 1] && !a[x][y + 1]) {v[x][y + 1] = 1;q.push({x, y + 1});}// 尝试向下移动if (x + 1 <= n && !v[x + 1][y] && !a[x + 1][y]) {v[x + 1][y] = 1;q.push({x + 1, y});}// 尝试向上移动if (x - 1 >= 1 && !v[x - 1][y] && !a[x - 1][y]) {v[x - 1][y] = 1;q.push({x - 1, y});}// 尝试向左移动if (y - 1 >= 1 && !v[x][y - 1] && !a[x][y - 1]) {v[x][y - 1] = 1;q.push({x, y - 1});}}}cout << ans << endl;  // 输出当前测试用例的答案// 清空队列，准备下一个测试用例while (!q.empty()) q.pop();
}
int main() {cin >> T;  // 读取测试用例数量while (T--) {solve();}return 0;
}

1007
其实这个题目不是很难，化简后找相同的就可以，但是主要就是题目的判断，一开始题目我读错了，导致看成是n1个开始节点，每次在前者的基础上敲击往后走，导致对题目的判断出了差错。。。。

本题稍微注意一点的就是要用双指针来降复杂度，其他的没啥（题目真的要先读懂，不然都白费了） 

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline void solve(){int n1,n2;cin>>n1>>n2;vector<pair<int,int>>ni(n1),ca(n2);for(int i=0;i<n1;i++){cin>>ni[i].first>>ni[i].second;}for(int i=0;i<n2;i++){cin>>ca[i].first>>ca[i].second;}vector<int>a;vector<int>b;int sum=0;for(auto it:ni){int zong=(48*it.first)/it.second;//这里根据题目可以知道48是最大的公倍数，所以我们直接对它乘上a.push_back(sum);//sum就是在前者的基础上加上现在的时刻sum+=zong;}sum=0;for(auto it:ca){int zong=(48*it.first)/it.second;b.push_back(sum);sum+=zong;}int count=0;/*for(int i=0;i<a.size();i++){cout<<a[i]<<" ";}cout<<endl;for(int j=0;j<b.size();j++){cout<<b[j]<<" ";}cout<<endl;*/int i=0,j=0;while(i<a.size()&&j<b.size()){//双指针来进行判断，因为a，b都是有序上升的if(a[i]==b[j]){count++;i++,j++;}else if(a[i]<b[j]){i++;}else{j++;}}cout<<count<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;while(n--)solve();
}