Codeforces Round #956 (Div. 2) and ByteRace 2024

B. Corner Twist

题目地址

以一个$2\times 2$矩阵为例，其他矩阵的操作都可以通过$2\times 2$矩阵的操作得到
$$\left[\begin{array}{c}12\\ 21\end{array}\right]$$
或者
$$\left[\begin{array}{c}21\\ 12\end{array}\right]$$
可以发现，矩阵中每一行加起来模3等于0，每一列加起来模3也等于0，所以无论经过多少次变换，变换后的矩阵每一行之和模3和变换前每一行之和模3是一样的，每一列之和模3也是一样的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
int n, m;
int s1_row[505], s1_col[505], s2_row[505], s2_col[505];
void solve()
{memset(s1_row, 0, sizeof(s1_row));memset(s1_col, 0, sizeof(s1_col));memset(s2_row, 0, sizeof(s2_row));memset(s2_col, 0, sizeof(s2_col));cin >> n >> m;vector<string> s1, s2;for (int i = 0; i < n;i++){string s;cin >> s;s1.push_back(s);}for (int i = 0; i < n;i++){string s;cin >> s;s2.push_back(s);}for (int i = 0; i < n; i++){for (int j = 0; j<m;j++){s1_row[i] = (s1_row[i]+s1[i][j] - '0') % 3;s1_col[j] = (s1_col[j]+s1[i][j] - '0') % 3;s2_row[i] = (s2_row[i]+s2[i][j] - '0') % 3;s2_col[j] = (s2_col[j]+s2[i][j] - '0') % 3;}}bool flag = true;for (int i = 0; i < n;i++){if(s1_row[i]!=s2_row[i]){flag = false;break;}}for (int i = 0; i < m;i++){if(s1_col[i]!=s2_col[i]){flag = false;break;}}if(flag){cout << "YES\n";}else{cout << "NO\n";}
}int main()
{int t;t=1;cin>>t;while(t--){solve();}return 0;
}

问题C：Have Your Cake and Eat It Too

题目地址

首先用前缀和数组$s$保存三个人的前缀和，因为三个人一共有6种情况，用$next\_permutation$生成全排列，然后遍历每一个排列顺序，看有没有满足题意的索引

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, V = 3;
int n, l[V], r[V], p[V];
ll s[V][N], lim; // s是前缀和数组
bool flag = 0;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--){cin >> n;for (int i = 0; i < V; i++){for (int j = 1; j <= n; j++){int x;cin >> x;s[i][j] = s[i][j - 1] + x;}}lim = (s[0][n] + V - 1) / V; // 每个人分到的蛋糕数flag = 0;iota(p, p + V, 0);do{int lst = 0, nxt;for (int i = 0; i < V; i++){ll *t = s[p[i]];nxt = lower_bound(t, t + n + 1, lim + t[lst]) - t;if (nxt > n)break;l[p[i]] = lst + 1, r[p[i]] = nxt; //序列开始位置 序列结束位置lst = nxt; // lst是上个子序列结束位置 nxt是当前子序列结束位置}if (nxt <= n){flag = 1;break;}} while (next_permutation(p, p + V));if (flag)for (int i = 0; i < V; i++){cout << l[i] << " " << r[i] << " ";}else{cout << -1;}cout << '\n';}return 0;
}