A.
把两个数合并成一个数，数的总和并没有变
要对应相等，那么两个数组所有数的总和一定相等，所以在最坏情况下两个数组都合并为1个数时一定满足条件
求最少合并次数的话，因为要对应下标对应相等，那么当前一定要通过合并一些数让当前对应下标相等，因为合并后面的对当前没有影响
所以直接用两个队列，取出队首元素，一直加到当前和想等
int n,m;
queue<ll>a,b;
void solve() {
cin>>n;
ll x;
ll tmp_a=0,tmp_b=0;
for(int i=0;i<n;i++){
cin>>x;a.push(x);tmp_a+=x;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>x;b.push(x);tmp_b+=x;
}
if(tmp_b!=tmp_a){
cout<<-1;return ;
}
ll sum_a=0,sum_b=0,ans=0;
while(1){
if(sum_a==sum_b&&sum_a==0){
sum_a+=a.front();a.pop();
sum_b+=b.front();b.pop();
}
else if(sum_a<sum_b){
sum_a+=a.front();a.pop();
}else if(sum_a>sum_b){
sum_b+=b.front();b.pop();
}
if(sum_a==sum_b&&sum_a!=0){
ans++;sum_a=sum_b=0;
}
if(a.size()==0&&b.size()==0)break;
}
cout<<ans;
}
B.
相当于一趟列车，起点和路径不是重点，终点才是重点，只要我们把捕鼠器设置在终点，那么老鼠一定会被捕获
证明最优：
因为一定要抓到老鼠，所以终点必然是要放捕鼠器的，那在其他位置放捕鼠器就浪费了，证毕
老鼠的逃亡路径最简单的就是一个链式结构，考虑当前老鼠能逃亡的下一个地点：
1.去往链式结构之前的节点，那么形成了环
2.不动，去往自己，那么也形成了一个自环
3.去往下一个节点（依然是链式结构）
综上，老鼠的逃亡路径一定会形成环
若几个房间在一个环上，那么在任意一个房间放捕鼠器老鼠最终都会被捕获，那我们贪心地找花费最小的房间即可
可以把老鼠逃亡路径上所有的节点放在一个并查集里，因为起点是多个的，那么可能会有多个集合
继续逃亡路径，复杂点就是分叉结构+链式结构+环
分叉相当于有的乘客在中途站上车，但无关紧要，因为列车依然要开往终点，也把它放入这个集合里即可
最后我们处理出了多个集合，在每个集合里dfs找环，记录下环的起点，遍历一遍环，找到该环的最小花费，把所有集合的环的最小花费累加即为答案
再证：每个集合里有且仅有一个环
因为这是有向的，一个节点只能指向一个节点（当然可以有多个节点都指向一个节点）
链式结构首尾相连才能形成环，当前节点要么指向之前已经经过的一个节点形成环要么指向一个未到达节点依然是链式结构，一旦现在形成了环，如果有新的节点想要加入，只能连在链或环的上面，而链上或环上的点没有多余的边来连新节点，所以新节点永远不会成环，证毕
代码：
int fa[N];
int find(int x){
if(x==fa[x])return fa[x];
return fa[x]=find(fa[x]);
}
int n;
ll cost[N];
int nxt[N];
unordered_map<int,int>mp;
bool vis[N];
int st;
ll ans,res;
void get_res(int u){
res=min(res,cost[u]);
if(u==st)return ;
get_res(nxt[u]);
}
void dfs(int u){
vis[u]=true;
if(vis[nxt[u]]==true){
st=u;
res=cost[st];
get_res(nxt[u]);
ans+=res;
//cout<<"st="<<st<<' '<<"res="<<res<<endl;
return ;
}
dfs(nxt[u]);
}
void solve() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>cost[i];
fa[i]=i;
}
for(int i=1;i<=n;i++){
cin>>nxt[i];
int fa_i=find(i);
int fa_nxt=find(nxt[i]);
fa[fa_i]=fa_nxt;
}
for(int i=1;i<=n;i++){
int father=find(i);
if(mp[father]==0)mp[father]++;
}
for(auto tmp:mp){
dfs(tmp.first);
}
cout<<ans;
}
C.
考虑实验室的四周，若这个格子最多只有两条路可以走，那么我们向机器人下达不是通往实验室的那个方向，那么它一定会走进实验室
照这个原理，把一定能走进实验室的点标记（只要走到它们，那也一定会进入实验室）
vector < vector < char > > map;
vector < vector < bool > > vis;
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = { 0, 0, -1, 1};
int inline CBC(int x, int y) { // 输出 (x, y) 周围的 . 的个数
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (map[x + dx[i]][y + dy[i]] == '.') {
cnt++;
}
}
return cnt;
}
void bfs(int x, int y) {
queue < pair < int , int > > q;
q.push(make_pair(x, y));
vis[x][y] = true; // 为了防止起点也被改成 +
while (!q.empty()) {
pair < int , int > u = q.front();
q.pop();
int x = u.first;
int y = u.second;
for (int nx, ny, i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
// 判重 能否走过去 周围的 . 个数 < 2
if (!vis[nx][ny] && map[nx][ny] != '#' && CBC(nx, ny) < 2) {
vis[nx][ny] = true;
map[nx][ny] = '+';
q.push(make_pair(nx, ny));
}
}
}
}
void inline solve() {
cin >> n >> m;
// 清空数组
map.clear();
vis.clear();
// resize(n + 2) 的含义: 往一个 vector 里填充 n + 2 个空 / 值为 0 的元素
map.resize(n + 2);
vis.resize(n + 2);
for (int i = 0; i < n + 2; i++) {
map[i].resize(m + 2);
vis[i].resize(m + 2);
}
// 我习惯在边上围一圈 # 来判断边界
for (int j = 0; j < m + 2; j++) {
map[0][j] = '#';
vis[0][j] = true;
map[n + 1][j] = '#';
vis[n + 1][j] = true;
}
for (int i = 1; i <= n; i++) {
map[i][0] = '#';
vis[i][0] = true;
map[i][m + 1] = '#';
vis[i][m + 1] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> map[i][j];
}
}
// 找到 L 的位置
int Lx, Ly;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] == 'L') {
Lx = i, Ly = j;
}
}
}
bfs(Lx, Ly); // 搜索
// 输出
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << map[i][j];
}
cout << "\n";
}
}