B. Corner Twist
以一个 2 × 2 2\times 2 2×2矩阵为例,其他矩阵的操作都可以通过 2 × 2 2 \times 2 2×2矩阵的操作得到
[ 1 2 2 1 ] \begin{bmatrix} {1 \quad2}\\ {2 \quad1}\\ \end{bmatrix} [1221]
或者
[ 2 1 1 2 ] \begin{bmatrix} {2 \quad1}\\ {1 \quad2}\\ \end{bmatrix} [2112]
可以发现,矩阵中每一行加起来模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 s s保存三个人的前缀和,因为三个人一共有6种情况,用 n e x t _ p e r m u t a t i o n next\_permutation 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;
}