A – 矩阵游戏
这道题看了题解之后发现就是一道 sb 题。
考虑将每一列看成一个数，发现如果忽略掉列的操作，这些数仍然满足等差的条件，所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作，那么我们就大力暴力就行了，时间复杂度是\(O(n + m)\)。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200, mod = 1e9 + 7;
int row[MAX_N], col[MAX_N], n, m, k;
long long ans = 0;
char opt[20];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= max(n, m); i++)
row[i] = col[i] = 1;
while (k--)
{
int x, y;
scanf("%s%d%d", opt + 1, &x, &y);
if (opt[1] == 'R')
row[x] = 1LL * row[x] * y % mod;
else
col[x] = 1LL * col[x] * y % mod;
}
int colBatch = 0, batch = 0;
for (int i = 1; i <= n; i++)
colBatch = (1LL * colBatch + 1LL * (1LL * (i - 1) * m % mod + 1) % mod * row[i] % mod) % mod, batch = (1LL * batch + 1LL * row[i]) % mod;
int current = colBatch;
for (int j = 1; j <= m; j++)
ans = (ans + 1LL * current * col[j] % mod) % mod, current = (1LL * current + 1LL * batch) % mod;
printf("%lld", ans);
return 0;
}
B – 跳房子
这道题听毒瘤的，很长。
我们考虑设置数组\(jump[i]\)表示从第\(i\)行第一列跳到下一次第一列的行号。这样的话，我们在找循环节的时候可以快很多，只需要除掉就好，剩余的地方进行暴力就行。
修改就用到了比较玄秘的方法，考虑一个点被修改对第一列的影响，发现被影响的点必然在一个区间内，且连续，所以我们可以从被修改点往左跳，找到区间并且全部修改为新的答案，这样就可以不用被计算多次了。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2020;
int jump[MAX_N], ptx, pty;
int mp[MAX_N][MAX_N], n, m, q;
char opt[20];
int fix(int pa, int pb) { return (pa % pb + pb) % pb; }
int next_row(int x, int y)
{
int next_row = -1;
int max_value = -1;
for (int rr = x - 1; rr <= x + 1; ++rr)
{
const int value = mp[fix(rr, n)][fix(y + 1, m)];
if (value > max_value)
{
max_value = value;
next_row = rr;
}
}
return next_row;
}
int rush(int x, int y)
{
do
{
x = fix(next_row(x, y++), n);
} while (y < m);
return x;
}
struct interval
{
int l = std::numeric_limits<int>::max();
int r = std::numeric_limits<int>::min();
bool isCotain(int x) { return l <= x && x <= r; }
bool isEmpty() { return l > r; }
int size() { return r - l + 1; }
};
void update(int x, int y)
{
const int target_row = rush(x, y);
interval rows;
rows.l = rows.r = x;
int cc = y;
while (cc > 0)
{
--cc;
interval new_rows;
for (int rr = rows.l - 1; rr <= rows.l + 1; ++rr)
{
if (rows.isCotain(next_row(rr, cc)))
{
new_rows.l = rr;
break;
}
}
for (int rr = rows.r + 1; rr >= rows.r - 1; --rr)
{
if (rows.isCotain(next_row(rr, cc)))
{
new_rows.r = rr;
break;
}
}
if (new_rows.isEmpty())
return;
rows = new_rows;
}
if (rows.size() >= n)
for (int rr = 0; rr < n; ++rr)
jump[rr] = target_row;
else
for (int rr = rows.l; rr <= rows.r; ++rr)
jump[fix(rr, n)] = target_row;
return;
}
void move(int steps)
{
static int walk_id = 0;
static int last_walk_id[MAX_N];
static int last_k[MAX_N];
walk_id++;
if (steps >= m - pty)
{
steps -= (m - pty);
ptx = rush(ptx, pty), pty = 0;
}
while (steps >= m)
{
steps -= m;
ptx = jump[ptx];
if (last_walk_id[ptx] == walk_id)
{
const int cycle_len = last_k[ptx] - steps;
if (steps >= cycle_len)
{
const int n_cycles = steps / cycle_len;
steps -= n_cycles * cycle_len;
}
}
last_walk_id[ptx] = walk_id;
last_k[ptx] = steps;
}
while (steps--)
ptx = fix(next_row(ptx, pty++), n);
}
int main()
{
/*
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
*/
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &mp[i][j]);
scanf("%d", &q);
for (int i = 0; i < n; i++)
jump[i] = rush(i, 0);
while (q--)
{
int a, b, c;
scanf("%s%d", opt + 1, &a);
if (opt[1] == 'm')
move(a), printf("%d %d\n", ptx + 1, pty + 1);
else
{
scanf("%d%d", &b, &c);
a--, b--;
mp[a][b] = c;
for (int i = a - 1; i <= a + 1; i++)
update(fix(i, n), fix(b - 1, m));
}
}
return 0;
}
C – 优美序列
这道题暴力跳，然后 AC 看天命。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, arr[MAX_N], pos[MAX_N], q, log2_[MAX_N];
int stmax[18][MAX_N], stmin[18][MAX_N], posmax[18][MAX_N], posmin[18][MAX_N];
inline int query_pos_max(int l, int r)
{
int len = r - l + 1, k = log2_[len];
return max(posmax[k][l], posmax[k][l + len - (1 << k)]);
}
inline int query_pos_min(int l, int r)
{
int len = r - l + 1, k = log2_[len];
return min(posmin[k][l], posmin[k][l + len - (1 << k)]);
}
inline int query_max(int l, int r)
{
int len = r - l + 1, k = log2_[len];
return max(stmax[k][l], stmax[k][l + len - (1 << k)]);
}
inline int query_min(int l, int r)
{
int len = r - l + 1, k = log2_[len];
return min(stmin[k][l], stmin[k][l + len - (1 << k)]);
}
int main()
{
freopen("sequence23.in", "r", stdin);
freopen("sequence.out", "w", stdout);
scanf("%d", &n);
for (int i = 2; i <= n; i++)
log2_[i] = log2_[i >> 1] + 1;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &arr[i]), pos[arr[i]] = i;
stmax[0][i] = arr[i], stmin[0][i] = arr[i];
posmin[0][arr[i]] = i, posmax[0][arr[i]] = i;
}
for (int i = 1; (1 << i) <= n; ++i)
for (int j = 1; j <= n; ++j)
{
stmax[i][j] = max(stmax[i - 1][j], stmax[i - 1][j + (1 << (i - 1))]);
stmin[i][j] = min(stmin[i - 1][j], stmin[i - 1][j + (1 << (i - 1))]);
posmax[i][j] = max(posmax[i - 1][j], posmax[i - 1][j + (1 << (i - 1))]);
posmin[i][j] = min(posmin[i - 1][j], posmin[i - 1][j + (1 << (i - 1))]);
}
scanf("%d", &q);
while (q--)
{
int l, r;
scanf("%d%d", &l, &r);
int mx, mi;
while (r - l + 1 != (mx = query_max(l, r)) - (mi = query_min(l, r)) + 1)
{
l = min(l, query_pos_min(mi, mx));
r = max(l, query_pos_max(mi, mx));
}
printf("%d %d\n", l, r);
}
return 0;
}