2021.7.16模拟赛
比赛概括：
\(\mathrm{sum}=10+30+0+100\)
唉，我果然只是暴力选手。
T1 【BZOJ 4131】并行博弈：
题目大意：
在一个 \(n\times m\) 的棋盘上，选择一个黑点可使得矩阵 \((1,1,x,y)\) 翻转。无法操作的人败。问 \(k\) 组棋盘一起下，是否先手必胜。
思路：
先手最优一定是选一直选棋盘的左上角，所以统计左上角是 \(1\) 的个数，询问是否是奇数。证明不会，看来得增加博弈论的知识储备。
代码：
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int k, n, m;
int main()
{
for (int T = Read(); T--; )
{
k = Read();
int ans = 0;
for (int t = 1; t <= k; t++)
{
n = Read(), m = Read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int x = Read();
if (i == 1 && j == 1)
ans ^= x;
}
}
puts(!ans? "ld win": "lyp win");
}
return 0;
}
T2 图书馆：
题目大意：
在一个 DAG 找到一条长度不到 \(20\) 的 \(s\rightarrow t\) 的路径，使得路径方差最小。
思路：
先化方差：
\[\begin{aligned} \sigma^2&=\frac{1}{n}\sum_{i=1}^n(a_i-\bar{a})^2\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a}+\bar{a}^2)\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a})+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\frac{1}{n}\sum_{i=1}^n2a_i\bar{a}+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-2\bar{a}^2+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\bar{a}^2\\ \end{aligned} \]然后设 \(f_{i,j,k}\) 表示当前在 \(i\) 楼梯，已经走了 \(j\) 个楼梯，且消耗了 \(k\) 体力的最小体力平方和。则有：
\[f_{u,j,k}=\min_{v\to u,\mathrm{val}}\{f_{v,j-1,k-\mathrm{val}}+\mathrm{val}^2\} \]统计答案时把 \(f_{i,j,k}\) 代回去就行了。
代码：
const int N = 60, M = 310, V = 1010;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n, m;
int f[N][M][V];
struct edge
{
int to, val, nxt;
}e[M];
int head[N], tot;
void add(int u, int v, int w)
{
e[++tot] = (edge) {v, w, head[u]}, head[u] = tot;
}
int main()
{
freopen("library.in", "r", stdin);
freopen("library.out", "w", stdout);
memset (f, 127 / 3, sizeof f);
n = Read(), m = Read();
for (int i = 1; i <= m; i++)
{
int u = Read(), v = Read(), w = Read();
add(u, v, w);
}
f[1][0][0] = 0;
for (int len = 0; len < 19; len++)
for (int u = 1; u < n; u++)
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
for (int sum = 0; sum <= 1000; sum++)
f[v][len + 1][sum + e[i].val] =
min(f[v][len + 1][sum + e[i].val], f[u][len][sum] + e[i].val * e[i].val);
}
double ans = 1e9;
for (int j = 1; j <= 20; j++)
for (int k = 0; k <= 1000; k++)
if (f[n][j][k] < f[0][0][0])
ans = min(ans, f[n][j][k] * 1.0 / j - (k * k * 1.0 / j / j));
printf ("%.4f", ans);
return 0;
}
T3 [GDOI2017]小学生语文题：
题目大意：
将字符串 \(t\) 中的一些字符往前移动若干位得到 \(s\)，求次数及方案。
正文：
设 \(f_{i,j}\) 表示 \(s\) 串中 \([i,n]\) 与 \(t\) 串 \([j,n]\) 匹配（有可能有剩余的）的最小次数。
则分三部分：
- \(s_i=t_j\)，直接往前跳，\(f_{i,j}=f_{i+1,j+1}\)。
- \(s_i\ne t_j\) 但是 \(t\) 串 \([j,n]\) 中的字符 \(s_i\) 的数量大于 \(s\) 串 \([i,n]\)，则说明 \(t\) 中可以移动一个字符 \(s_i\)，\(f_{i,j}=f_{i+1,j}\)。
- \(t\) 串中不够，\(f_{i,j}=f_{i+1,j+1}+1\)。
顺便维护 \(g_{i,j,[0,1]}\) 表示 \(f_{i,j}\) 从哪两个点转移过来的。
然后从 \(1,1\) 往后跳，把不定点排除，枚举剩下的点即可。
代码：
const int N = 2010;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int T, n;
char s[N], t[N];
int a[30][N], b[30][N];
int f[N][N], g[N][N][2];
bool NoMoveA[N], NoMoveB[N];
int main()
{
freopen("chinese.in", "r", stdin);
freopen("chinese.out", "w", stdout);
for (T = Read(); T--;)
{
scanf ("%s%s", s + 1, t + 1);
memset (a, 0, sizeof a);
memset (b, 0, sizeof b);
memset (NoMoveA, 0, sizeof NoMoveA);
memset (NoMoveB, 0, sizeof NoMoveB);
n = strlen(s + 1);
for (int i = n; i; i--)
{
a[s[i] - 'a'][i] = 1, b[t[i] - 'a'][i] = 1;
for (int j = 0; j < 26; j++) a[j][i] += a[j][i + 1], b[j][i] += b[j][i + 1];
}
memset (f, 127 / 3, sizeof f);
f[n + 1][n + 1] = 0;
for (int j = n; j; j--) f[n + 1][j] = f[n + 1][j + 1] + 1;
for (int i = n; i; i--)
{
for (int j = n; j; j--)
{
if (f[i][j] > f[i + 1][j] && a[s[i] - 'a'][i + 1] < b[s[i] - 'a'][j])
f[i][j] = f[i + 1][j], g[i][j][0] = i + 1, g[i][j][1] = j;
if (f[i][j] > f[i + 1][j + 1] && s[i] == t[j])
f[i][j] = f[i + 1][j + 1], g[i][j][0] = i + 1, g[i][j][1] = j + 1;
if (f[i][j] > f[i][j + 1] + 1)
f[i][j] = f[i][j + 1] + 1, g[i][j][0] = i, g[i][j][1] = j + 1;
}
}
printf ("%d\n", f[1][1]);
int x = 1, y = 1;
while (x <= n && y <= n)
{
int nxtx = g[x][y][0], nxty = g[x][y][1];
if (nxtx == x + 1 && nxty == y + 1)
NoMoveA[x] = 1, NoMoveB[y] = 1;
x = nxtx, y = nxty;
}
for (int i = 1; i <= n; i++)
{
if (NoMoveA[i]) continue;
for (int j = i; j <= n; j++)
{
if (NoMoveB[j] || s[i] != t[j]) continue;
bool tmp = NoMoveB[j];
for (int k = j; k >= i + 1; k--)
t[k] = t[k - 1], NoMoveB[k] = NoMoveB[k - 1];
NoMoveB[i] = tmp;
t[i] = s[i];
printf ("%d %d\n", j, i);
break;
}
}
}
return 0;
}
T4 矩形：
题目大意：
给你 \(n\) 条线段（他们要么平行要么垂直），求那些线段可以围成矩阵。
正文：
每行用 bitset 存一个与每列是否有交点的状态，然后枚举两行求同时拥有两列的数量。时间复杂度 \(\mathcal{O}(n^3\omega^{-1})\)，其中 \(\omega=32\)，勉强卡过。
代码：
const int N = 2010;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
int cnt1, cnt2;
struct Segment
{
int x1, y1, x2, y2;
}a[N], b[N];
bool isInt (int u, int v)
{
return b[v].y1 <= a[u].y1 && a[u].y1 <= b[v].y2 && a[u].x1 <= b[v].x1 && b[v].x1 <= a[u].x2;
}
bitset<N> con[N], tmp;
ll ans;
int main()
{
n = Read();
for (int i = 1; i <= n; i++)
{
int x1 = Read(), y1 = Read(), x2 = Read(), y2 = Read();
if (x1 != x2)
{
if (x1 > x2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2;
a[++cnt1] = (Segment){x1, y1, x2, y2};
}
else
{
if (y1 > y2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2;
b[++cnt2] = (Segment){x1, y1, x2, y2};
}
}
for (int i = 1; i <= cnt1; i++)
for (int j = 1; j <= cnt2; j++)
if (isInt(i, j))
con[i].set(j, 1);
for (int i = 2; i <= cnt1; i++)
for (int j = 1; j < i; j++)
{
tmp = con[i] & con[j];
ll cnt = tmp.count();
ans += cnt * (cnt - 1) / 2;
}
printf ("%lld\n", ans);
return 0;
}