CF1459E Latin Square
把矩形抽象为 \((x,y,z)\) 意思为
\(A_{x,y}=z\) 这样位移操作就对应 \(X\) 轴或 \(Y\) 轴的加减，求逆操作就对应 \(X\) 轴或 \(Y\) 轴与 \(Z\)
轴的交换，我们对于最初的每一维维护它们最终对应的位置和加减情况即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
typedef double f32;
using namespace std;
const int N = 1e3+5, M = 1e5+5;
int T, n, m, A[N][N], B[N][N], u[3], v[3], w[3]; char o[M]; void fix(int &x) { x<n?0:x-=n; }
int main()
{
for(scanf("%d", &T); T--; )
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", A[i]+j), --A[i][j];
scanf("%s", o); for(int i = 0; i < 3; ++i) u[i] = i, v[i] = 0;
for(int i = 0; i < m; ++i)
if(o[i] == 'R') fix(++v[1]);
else if(o[i] == 'L') fix(v[1] += n-1);
else if(o[i] == 'D') fix(++v[0]);
else if(o[i] == 'U') fix(v[0] += n-1);
else if(o[i] == 'I') swap(v[1], v[2]), swap(u[1], u[2]);
else swap(v[0], v[2]), swap(u[0], u[2]);
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
{
for(int k = 0; k < 3; ++k) fix(w[k] = (u[k] == 2?A[i][j]:u[k]?j:i)+v[k]);
B[w[0]][w[1]] = w[2];
}
for(int i = 0; i < n; puts(""), ++i) for(int j = 0; j < n; ++j) printf("%d ", B[i][j]+1);
}
return 0;
}
CF1459F Flip and Reverse
我们记 \(d_x=\sum_{i=1}^x[s_i=0]-[s_i=1]\)，作出 \(x\in[0,n]\)，\((x,d_x)\) 的图象，会发现对 \([l,r]\) 进行操作需要满足 \(d_{l-1}=d_r\)，操作的结果是 \(x\in[l,r-1]\) 的 \((x,d_x)\) 做左右翻转。
不难发现，无论如何操作 \(d_x\) 的值集合都不会发生变化，我们将 \((d_{x-1},d_x)\) 连有向边构成边集 \(E\) 也不会变化（从合法的区间如果存在 \((x,y)\) 必须存在 \((y, x)\) 可以得到），那么一个合法的折线图就是 \(E\) 与由 \(d_x\) 构成的点集 \(V\) 决定的图 \(G\)，从 \(0\) 到 \(d_n\) 的一条欧拉路，我们优先走 \((x,x+1)\) 这类边即可。
1 |
|