C. Bear and String Distance
简单题，直接从距离范围最宽广的字母开始选，每次贪心选最大的。
const int MAXN = 1e5 + 10;
int n, k;
char ss[MAXN];
struct E { char s, t; int id; } es[MAXN];
int dist(char x, char y) { return std::abs(x - y); }
bool cmp1(E x, E y) { return x.s > y.s; }
bool cmp2(E x, E y) { return x.id < y.id; }
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
cin >> (ss + 1);
rep (i, 1, n) { es[i].s = ss[i]; es[i].id = i; }
std::sort(es + 1, es + 1 + n, cmp1);
int _validator = 0;
rep (i, 1, n) {
int d = std::min(k, std::max(dist('a', es[i].s), dist('z', es[i].s)));
if (es[i].s + d > 'z') es[i].t = es[i].s - d;
else es[i].t = es[i].s + d;
k -= d;
_validator += dist(es[i].s, es[i].t);
}
if (k) {
cout << -1 << endl; return 0;
}
std::sort(es + 1, es + 1 + n, cmp2);
rep (i, 1, n) cout << es[i].t;
cout << endl;
return 0;
}
D. Magic Numbers
数位 DP 基础题，状态是考虑从高到第 (mathrm{pos}) 位，该前缀 (mod 13) 的值，是否触碰上限。
因为保证上下界数字长度相同所以就不需要考虑前导零了，问题简化了很多。
别忘了开 long long。
const int MAXN = 2000 + 10;
const int HA = 1e9 + 7;
int m, d;
char ss[MAXN];
int divnum[MAXN], cnt;
lli dp[MAXN][MAXN];
lli dfs(int pos, int rmd, bool limit, int len) {
if (pos == 0) return rmd == 0;
if (!limit && dp[pos][rmd] != -1) return dp[pos][rmd];
lli ans = 0;
int top = limit ? divnum[pos] : 9;
for (int i = 0; i <= top; ++i) {
if (((len - pos + 1) % 2 == 0) ^ (i == d)) continue;
ans += dfs(pos - 1, (rmd * 10 + i) % m, limit && (i == divnum[pos]), len);
ans %= HA;
}
if (!limit) dp[pos][rmd] = ans;
return ans;
}
void divide() {
int len = (int) strlen(ss + 1);
cnt = 0;
for (int i = len; i >= 1; --i) divnum[++cnt] = ss[i] - '0';
}
lli Solve() {
divide();
memset(dp, -1, sizeof dp);
return dfs(cnt, 0, true, cnt);
}
bool check() {
int bmod = 0;
for (int i = 1; i <= cnt; ++i) {
if ((i % 2 == 0) ^ ((ss[i] - '0') == d)) return false;
bmod = bmod * 10 + ss[i] - '0';
bmod %= m;
}
return bmod == 0;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> m >> d;
cin >> (ss + 1);
lli ans1 = Solve() - check();
(ans1 += HA) %= HA;
// DEBUG(ans1);
cin >> (ss + 1);
lli ans2 = Solve();
// DEBUG(ans2);
cout << (ans2 - ans1 + HA) % HA << endl;
return 0;
}
E. Zbazi in Zeydabad
挺有意思一题。
定义 z 线：指一条连续的全部由字符 z 组成的线段，可能是斜的也可能是横的。
首先我们可以预处理出所有点往左 tl[i][j]、往右 tr[i][j]，往左下 tld[i][j] 的最长横 z 线长度，这对于我们判断 Z 字形有很大的用处。
注意到 Z 字形的结构是正方形，所以确定了一个角和长度就可以确定整个图形的位置；而且对角线角（左下、右上）是和图形的对角线部分直接相关的，所以考虑枚举图形的右上角 ((i, j))。
可以发现，这个图形可能的最大长度即是往左和往左下 z 线长度的较小值 l = min(tl[i][j], tld[i][j])，于是接下来我们的任务就是判断这条长为 (l) 的斜 z 线上有多少满足，经过它的横 z 线向右伸展达到（或超过）这个右上角所在列 (j)，的点，以这些点作为左下角即可确定一个 Z 字形。直接枚举是 (O(n^3)) 级别的，考虑能不能优化。
注意到以我们枚举的点为右上角的所有 Z 字形有两个性质：
它们下面那一条横 z 线都至少向右伸展达到（或超过）了右上角所在列 (j)。
它们所有的左下角一定分布在这条长为 (l) 的斜 z 线上，也就是在对角线上的一个区间查询。
因此我们可以考虑去寻找所有右端点在 (j) 上（或右边）的横 z 线，它们的左端点如果在这条对角线斜 z 线上，就说明这个左端点是满足要求的一个左下角。
这个所有线是 (O(n^3)) 级别的，但是发现相同左端点的横 z 线只会产生一个贡献，而且右端点肯定尽量靠右最好，所以我们就只保留每一个点往右伸展最长长度的横 z 线，也就是对于点 ((x, y))，我们要存的线段是 ((x, y) ightarrow (x, y + mathrm{tr}_{x, y} - 1))（如果存在的话）。
接下来的任务就是，对于这个右上角 ((i, j))，枚举所有右端点也在列 (j) 上（或超过）的线段，判断它的左端点是不是在这条对角线上，而且属于这个长为 (l) 的区间。
类似树状数组求逆序对，这里我们也可以使用类似于边插入边查询的思想，考虑对每一条对角线维护一个树状数组，(b_{x + y, y}) 表示当前第 (x + y) 条对角线上是否存在以第 (y) 列的点为左端点的线段（0 或 1），通过以合适的顺序枚举线段并修改树状数组，我们可以实现在对角线上的区间查询。
为了满足线段所有右端点都在当前枚举的列右边，我们修改枚举右上角 ((i, j)) 的顺序，先从右往左枚举列 (j)，找到所有右端点在列 (j) 上的线段，将左端点插入对应对角线的树状数组；再从上到下枚举行 (i)，确定右上角 ((i, j))，在对应对角线的树状数组上进行区间查询，累计答案即可。
const int MAXN = 3000 + 10;
int n, m;
char mat[MAXN][MAXN];
int tl[MAXN][MAXN], tr[MAXN][MAXN], tld[MAXN][MAXN];
std::vector<std::pair<int, int> > segs[MAXN]; // segs[r][x] -> LeftNode(i, j)
void pre() {
rep (i, 1, n) {
rep (j, 1, m) if (mat[i][j] == 'z') tl[i][j] = tl[i][j - 1] + 1;
for (int j = m; j >= 1; --j) if (mat[i][j] == 'z') tr[i][j] = tr[i][j + 1] + 1;
}
for (int i = n; i >= 1; --i) {
rep (j, 1, m) if (mat[i][j] == 'z') tld[i][j] = tld[i + 1][j - 1] + 1;
}
rep (i, 1, n) {
rep (j, 1, m) {
int r = j + tr[i][j] - 1;
if (j <= r) segs[r].push_back({i, j});
}
}
}
struct BIT {
lli seq[MAXN];
#define lb(x) ((x) & (-(x)))
void mo(int x) {
for (; x <= m; x += lb(x)) ++seq[x];
}
lli qr(int x) {
int r = 0; for (; x; x -= lb(x)) r += seq[x]; return r;
}
} diagonals[MAXN << 1];
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
rep (i, 1, n) cin >> (mat[i] + 1);
pre();
lli ans = 0;
for (int j = m; j >= 1; --j) {
for (auto seg : segs[j]) {
int x = seg.fi, y = seg.se;
diagonals[x + y].mo(y);
}
for (int i = 1; i <= n; ++i) {
// (i, j) as the upperright corner
if (mat[i][j] != 'z') continue;
int maxlen = std::min(tl[i][j], tld[i][j]);
int ql = j - maxlen + 1, qr = j;
ans += diagonals[i + j].qr(qr) - diagonals[i + j].qr(ql - 1);
}
}
printf("%lld
", ans);
return 0;
}
F
需要网络流相关知识