模拟套题 12.9-526互联

不敢想象这是曾经初二的人做的

T1 非皇后

大意：给定 $R$ 行 $C$ 列的棋盘你可以随便在一个格子放一个非皇后要求不能走直线和对角线走 $M$ 步
将走过的格子按顺序记起来求最终有多少种不同排列

Solution

dp 裸题

定义 $f_{i,j,k}$ 为走了 $i$ 次 ,到格子 $(j,k)$ 的方案
容易有转移 $f_{i,j,k}=\sum\limits f_{i-1,x,y} \space $
其中 $x,y$ 不是同行同列不是对角线

用四个前缀和优化一下就好了

时间复杂度 $O(RCM)$

T2 染色

给出 $n$ 个结点 $m$ 条边的无向图。有k种不同的颜色，编号 $1$ 至 $k$ 。现在你要对这n个结点染色，每个结点只能染一种颜色。还有一个特殊要求：凡是有边相连的两个结点，它们的颜色编号的和不能等于 $z$ 。问有多少种不同的染色方案

$n,m\leq 18\space k\leq 10^9$

Solution

正面思考非常麻烦看到 $n,m\le 18$ 那肯定和 $2^n$ 脱不了关系

颜色很大不能装压还有 $2^n$ 次方的算法还有枚举和容斥

显然可以容斥

直接枚举不满足的边然后分类讨论即可

用并查集维护时间复杂度是 $O((n+m)2^m\log n)$ 并查集常数很小可以接受

最大是 993ms

T3 子序列整数

给定字符串 $S$ 和整数 $n$
求出有多少个不同的 $S$ 的子序列 $P$ 使得 $n|P$
$|S|\le 5000\space n\le1000$

Solution

难度还行

考虑难度在于 不同的 子序列
要是没有这个条件一个 dp 划过去即可时间复杂度 $O(n^2|S|)$
怎样才能保证每次产生的都是不同的呢？

我们要保证每个数只记最开始出现的一次

根据这个,每个数的开头都是固定的了注意 $0$ 不能开头

这个时候手玩样例是最佳选择

$Instance:$
$12412412$
$1$
$2,12$
$4,14,24,124$
$11,21,121,41,141,241,1241$
$22,12,42,142,242,1242,112,212,121,412,1412,2412,12412$
$...$
一手玩玩规律马上就出来了
能往下接的必须从上一个相同的数开始

记一下 $last_{num}$ 即可
分析时间复杂度
$O(n^2|S|) \to O(n|S|)$ 有常数 $10$

因为每个点的转移都是一部分所以时间复杂度大大降低
均摊一下就有了

T4 三角形

前置芝士：This

想了三天才做出来用了挺多数学课是时间推
很毒瘤的一道题

第一步肯定是手玩样例
手玩一下不难发现合理的只有两种情况

1.在目前已经围成的三角形内部此时随便连都是三个
2.在目前围成的三角形延长线的里面这样会扩大三角形的面积

最后成的三角形的外围是固定的
我们可以这样拆分一个排列：
$[P_1,P_2,P_3],P_4,[P_5],P_6,P_7,[P_8],···,[P_n]$
其中有括号的表示三角形的坐标发生改变
这样每种排列都有一个唯一的跳跃
我们用一个状态来记录这些排列：$f_{i,j,k}$ 表示第 $i,j,k$ 个点构成了三角形
这样似乎就可 dp 转移了
但这是错的我们的想法是转移维护三角形的扩大(情况1) 可是这样无法维护情况 $2$
往三角形内部一放可能就不是排列了
怎么办？
为此我们再加一维 $t$ 表示三角形内部的点

这样每个排列就被我们表示出来了因为三角形内部的是任意的可以计做一维
这样我们的 dp 就出来了

对于情况 $1$ 有 $f(i,j,k,t)+=f(i,j,k+1,t)\times k$
对于情况 $2$ 判断 $(i,j,k)$ 外面的点 $x$ 能把这个图连成三角 $(i,j,x)$ 有$f_{i,j,k,t}+=f_{i,j,x,P}$
$P$ 的处理后面会讲

最终的答案就是 $f_{p1,p2,p3,0}$ 其中 $p1,p2,p3$ 是最终的顶点

现在主要问题处理完了下面就是细节

怎么判断一个点在不在三角形内部？

$Solution$
用最简单的方法面积法
对于三角形内任意一点 $P$ 有 $S_{\Delta ABC}=S_{\Delta ABP}+S_{\Delta APC}+S_{\Delta PBC}$
其中对于 $S_{\Delta ABC}=\frac{1}{2}\times |A_x\times B_y+B_x\times C_y+C_x\times A_y-A_y\times B_x-B_y\times C_x-C_y\times A_x|$