Codeforces Round #619 (Div. 2)
A：只要每个位置都满足a[i] = c[i]或b[i] = c[i]即可。
int main() {
int t; scanf("%d", &t);
while(t --) {
char a[110], b[110], c[110];
scanf("%s%s%s", a, b, c);
int n = strlen(a), tag = 1;
for(int i = 0; i < n; i ++) {
if(a[i] == c[i] || b[i] == c[i]) {
} else {
tag = 0; break ;
}
}
puts(tag ? "YES" : "NO");
}
return 0;
}
B：写了无脑二分，实际上可以线性：k取(max - min) / 2。max和min是与-1相邻的数中最大值和最小值。
const int N = 4e5 + 10;
const int mo = 1e9 + 7;
int n, a[N], k;
bool ck(int mid) {
ll l = 0, r = 1e9;
for(int i = 1; i <= n; i ++) if(~ a[i]) {
if(a[i + 1] == -1 || a[i - 1] == -1) {
ll nl = a[i] - mid, nr = a[i] + mid;
l = max(l, nl); r = min(r, nr);
}
}
if(l <= r) k = l;
return l <= r;
}
int main() {
int t; scanf("%d", &t);
while(t --) {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
a[0] = a[n + 1] = 0;
int l = 0, r = 1e9, mid, ans;
for(int i = 1; i < n; i ++) if(~ a[i] && ~ a[i + 1])
l = max(l, a[i] > a[i + 1] ? a[i] - a[i + 1] : a[i + 1] - a[i]);
while(l <= r) {
mid = (l + r) >> 1;
if(ck(mid)) r = (ans = mid) - 1;
else l = mid + 1;
}
ck(ans);
printf("%d %d
", ans, k);
}
return 0;
}
C：利用容斥思想化简式子，最后发现问题转换为：
给定(x)和(k)，你需要安排(x_i)使得(sum_{i = 1}^k x_i = x)，最小化(sum_{i = 1}^k x_i^2)
结论是尽可能平均分。即令(y = lfloor frac{x}{k} floor)，(x mod k)个元素为(y + 1)，剩下为(y)
简单的证明：假设最优方案中存在(x_i > x_j, x_i - x_j > 1)，此时((x_i - 1)^2 + (x_j + 1)^2 = x_i^2 + x_j^2 + 2 (x_j - x_i + 1) < x_i^2 + x_j^2)，说明有更优方案。
int n, m;
ll calc(ll n) {
return n * (n + 1) / 2;
}
ll __div(ll z, ll d) {
ll c = z / d, r = z % d;
return (c + 1) * (c + 1) * r + c * c * (d - r);
}
int main() {
int t; scanf("%d", &t);
while(t --) {
scanf("%d%d", &n, &m);
ll z = n - m, d = m + 1;
printf("%lld
", calc(n) - (z + __div(z, d)) / 2);
}
return 0;
}
D：构造题，有方法把所有边都走一遍，构造方法见代码
int n, m, k;
vector< pair<string, int> > ans;
void push(string s, int t) {
if(t == 0) return ;
static int x;
int sz = (int) s.size();
if(x + (ll) sz * t >= k) {
int d = k - x; string tmp;
if(d / sz > 0) ans.pb(mp(s, d / sz));
for(int i = 0; i < d % sz; i ++) tmp.pb(s[i]);
if(d % sz > 0) ans.pb(mp(tmp, 1));
printf("YES
%d
", (int) ans.size());
for(auto y : ans) {
printf("%d %s
", y.sc, y.fs.c_str());
}
exit(0);
}
ans.pb(mp(s, t)); x += sz * t;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i < n; i ++) {
push("RDU", m - 1);
push("L", m - 1);
push("D", 1);
}
push("R", m - 1);
push("L", m - 1);
push("U", n - 1);
puts("NO");
return 0;
}
E：标算是二维ST表，实际上冷静分析可以只需二维前缀和。首先我们发现了一个简单的结论，以某个点为左上角，最多有一个满足条件的正方形。
那就直接f[len][i][j]表示(i, j)这个前缀矩形里有多少个点，以该点为左上角边长为len的正方形是合法的，询问就枚举长度用前缀和判断。
复杂度(O(n^3 + qn)).
const int N = 500 + 10;
int n, m, q, sum[4][N][N], Map[N], f[N][N][N];
char s[N][N];
int query(int a[N][N], int x1, int y1, int x2, int y2) {
return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}
bool judge(int x, int y, int l) {
int mx = x + (l / 2), my = y + (l / 2);
int sz = l * l / 4, ex = x + l - 1, ey = y + l - 1;
if(query(sum[0], x, y, mx - 1, my - 1) != sz) return 0;
if(query(sum[2], mx, y, ex, my - 1) != sz) return 0;
if(query(sum[1], x, my, mx - 1, ey) != sz) return 0;
if(query(sum[3], mx, my, ex, ey) != sz) return 0;
return 1;
}
int main() {
Map['R'] = 0; Map['G'] = 1; Map['Y'] = 2; Map['B'] = 3;
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++) {
scanf("%s", s[i] + 1);
for(int j = 1; j <= m; j ++) {
sum[Map[s[i][j]]][i][j] = 1;
}
}
for(int k = 0; k < 4; k ++) {
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
sum[k][i][j] += sum[k][i - 1][j] + sum[k][i][j - 1] - sum[k][i - 1][j - 1];
}
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) if(s[i][j] == 'R') {
int lim = min(n - i + 1, m - j + 1);
for(int k = 2; k <= lim; k += 2) {
if(judge(i, j, k)) {
f[k][i][j] = 1; break ;
}
}
}
}
for(int k = 2; k <= max(n, m); k += 2) {
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
f[k][i][j] += f[k][i - 1][j] + f[k][i][j - 1] - f[k][i - 1][j - 1];
}
}
}
for(int i = 0; i < q; i ++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = 0, lim = min(x2 - x1 + 1, y2 - y1 + 1);
for(int k = 2; k <= lim; k += 2) {
int ex = x2 - k + 1, ey = y2 - k + 1;
if(query(f[k], x1, y1, ex, ey)) {
ans = k * k;
}
}
printf("%d
", ans);
}
return 0;
}
F：做法又不同于标算，但其实大同小异。
首先容易预处理d[x][y][col]表示((x, y))到最近的col颜色的点需要多少步。
然后想象把颜色建成了一个图，图中每个颜色有一个出点和入点。图里c1的出点连到c2的入点，代价是最近的c1和c2格子的曼哈顿距离。
在这张无向图上，c1出点到c2入点的最短路，表示的是起点你可以选定c1任意一点，终点你可以选c2任意一点，这两点的最短路。
Floyd预处理(G[c1][c2])表示c1出点到c2入点的最短路。
然后考虑询问，你移动的方式是行走->传送1->行走...->传送n->行走。首先不传送就是曼哈顿距离。然后你可以枚举传送1和传送n的颜色，假设是c1和c2，答案就是d[x1][y1][c1] + G[c1][c2] + d[x2][y2][c2] + 1 + [c1 != c2]。即你从(x1, y1)先走到c1的入点，然后走到c1出点，然后转移到c2的入点，然后转移到c2出点，最后转移到(x2, y2)。
这说明了：你从(x1, y1)走到颜色c1下一步就是传送。会不会下一步是移动？若是移动到同颜色的位置再传送，显然不优。若是移动到其他颜色ci，那会在c1 = ci的时候被统计的。
复杂度就是(O(k^3 + knm + q k^2))
const int N = 40 + 4;
const int M = 1004;
const int INF = 1e8 + 10;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, k, q, a[M][M], G[N][N], d[M][M][N];
vector<pii> vec[N];
void bfs(int col) {
queue<pii> q;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
d[i][j][col] = -1;
for(pii u : vec[col]) {
q.push(u); d[u.fs][u.sc][col] = 0;
}
while(q.size()) {
pii u = q.front(); q.pop();
int t = a[u.fs][u.sc];
G[t][col] = G[col][t] = min(G[col][t], d[u.fs][u.sc][col]);
for(int i = 0; i < 4; i ++) {
pii v = mp(u.fs + dx[i], u.sc + dy[i]);
if(v.fs < 1 || v.fs > n || v.sc < 1 || v.sc > m) continue ;
if(-1 == d[v.fs][v.sc][col]) {
d[v.fs][v.sc][col] = d[u.fs][u.sc][col] + 1;
q.push(v);
}
}
}
}
int myabs(int x) {
return x > 0 ? x : -x;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= k; i ++)
fill(G[i] + 1, G[i] + k + 1, INF), G[i][i] = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
scanf("%d", &a[i][j]);
vec[a[i][j]].pb(mp(i, j));
if(i != 1 && a[i - 1][j] != a[i][j]) {
int u = a[i - 1][j], v = a[i][j];
G[u][v] = G[v][u] = 1;
}
if(j != 1 && a[i][j - 1] != a[i][j]) {
int u = a[i][j - 1], v = a[i][j];
G[u][v] = G[v][u] = 1;
}
}
}
for(int i = 1; i <= k; i ++) bfs(i);
for(int w = 1; w <= k; w ++)
for(int u = 1; u <= k; u ++)
for(int v = 1; v <= k; v ++)
G[u][v] = min(G[u][v], G[u][w] + G[w][v] + 1);
scanf("%d", &q);
for(int i = 1; i <= q; i ++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = myabs(x1 - x2) + myabs(y1 - y2);
for(int x = 1; x <= k; x ++) {
for(int y = 1; y <= k; y ++) {
ans = min(ans, d[x1][y1][x] + d[x2][y2][y] + G[x][y] + 1 + (x != y));
}
}
printf("%d
", ans);
}
return 0;
}
ps：本比赛模板代码
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <ctime>
#include <set>
using namespace std;
#define fs first
#define sc second
#define pb push_back
typedef pair<int, int> pii;
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;