=_____=拖了好久啊，我是渣渣。
ZOJ 3644 Kitty’s Game
有一只喵身上有个记分牌，她每沿着边走一步，记分牌上的数字就会变为$$lcm(x, x_i)$$，其中$$x_i$$表示这一步的终点的一个给定值。问从起点S走到终点T，最后记分牌上写着k的方案有多少种。
因为最后记分牌到达到k，而记分牌上数字唯一的变化操作是lcm，所以中间过程必须是k的约数，注意到这点就可以只对有效状态dp了。复杂度$$O(\sqrt{k} * (V + E))$$
#include
#include
#include
#include
#include
#include
#include
ZOJ 3645 BiliBili
定义11维空间中点与点的距离为$$\sqrt{\sum (a_i – b_i)^2}$$。先给出一个未知点与另外12个点的距离，问这个未知点的坐标。
把$$(a_i – b_i)^2$$展开，得$$a_i^2 + b_i^2 + 2a_ib_i$$，然后对12个方程两两作差，得出11个11元线性方程。用gauss解之即可。
需要注意的是，答案不要输出-0.00，否则会WA的。
#include
#include
#include
#include
#include
using namespace std;
int n=11;
double a[15][15];
double x[15];
void guass(){
int i,j,k; double sum,rate;
for (k=1;kfabs(a[j][k])?i:j;
for (i=k;i<=n+1;i++) swap(a[j][i],a[k][i]);
for (i=k+1;i<=n;i++)
for (rate=a[i][k]/a[k][k],j=k;j<=n+1;j++)
a[i][j]-=a[k][j]*rate;
}
for (i=n;i>=1;i--){
for (sum=0,j=i+1;j<=n;sum+=a[i][j]*x[j],j++);
x[i]=(a[i][n+1]-sum)/a[i][i];
}
}
double mat[15][15];
double result[15];
double Fix(double y){
if (fabs(y)<5e-3) return 0;
return y;
}
int main(){
int Tc;
scanf("%d",&Tc);
while (Tc--){
for (int i=1;i<=12;i++){
for (int j=1;j<=11;j++)
scanf("%lf",&mat[i][j]);
scanf("%lf",&result[i]);
result[i]=result[i]*result[i];
for (int j=1;j<=11;j++){
result[i]-=mat[i][j]*mat[i][j];
mat[i][j]*=-2;
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++)
a[i][j]=mat[i][j]-mat[i+1][j];
a[i][n+1]=result[i]-result[i+1];
}
guass();
for (int i=1;i<=n;i++){
if (i!=1) printf(" ");
printf("%.2lf",Fix(x[i]));
}
printf("\n");
}
}
ZOJ 3646 Matrix Transformer
给定一个矩阵，里面包含了U和D，你可以随意交换任意列以及任何行，问最后能否使得矩阵主对角线上的元素都是U。
把这个矩阵看成邻接矩阵，U为1，然后做最大匹配即可。最后第i对匹配占领第i行第i列，就成了一个对角线全是U的矩阵。
#include
#include
#include
#include
#include
#include
#include
ZOJ 3647 Gao the Grid
问一个网络内点在整点上的非退化三角形的数目。
就是求C((n + 1)*(m + 1), 3) - 共线三角形的数目。共线的话，不妨先假设斜率 > 0。然后线段的右上角的端点减左下角的端点就会得到一个向量，这个向量一样的线段，都是本质相同的。枚举这个向量，再用gcd求中间整点的个数，就可以得解。根据对称性不难得出斜率 < 0的情况。 = 0的再特判一下就好了。
#include
#include
#include
#include
#include
#include
#include
ZOJ 3648 Gao the Grid II
问一个网络内点在整点上的非退化锐角三角形的数目。
对三角形占领的最小矩形范围分类，然后分别算出来输出即可。(相当于打表，累加一下即可) 分别算的时候注意非锐角三角形满足$$a^2 + b^2 \leq c^2$$ 就很简单了。
#include
#include
#include
#include
using namespace std;
const int maxn = 101;
const double EPS = 1e-10;
long long f[maxn][maxn];
int n, m;
int x, y;
long long gao(int m, int n, int & a, int & b) {
// x*x - m*x + n > 0
// 0 < x < m, x, m, n: integer
// return: number of solution(x)
long long d = (long long) m * m - 4LL * n;
if (d < 0) return (m-1 > 0) ? m-1 : 0;
if (d == 0) {
if (m & 0x1) return (m-1 > 0) ? m-1 : 0;
a = b = m / 2;
return (m-2 > 0) ? m-2 : 0;
}
a = (int)floor((m + sqrt(d)) / 2.0);
b = (int)ceil((m - sqrt(d)) / 2.0);
return b-1 + m-1-a;
}
void init() {
memset(f, 0, sizeof(f));
// a*a - m*a + n*b > 0
// b*b - n*b + m*a > 0
for (int i = 2; i < maxn; i++) { // n
for (int j = i; j < maxn; j++) { // m
for (int k = 1; k < j; k++) { // a
// k*k - m*k + n*b > 0 --> n*b > k*(m-k)
// b*b - n*b + m*k > 0
x = y = 0;
long long ret = gao(i, j*k, y, x); // b in (0, x) + (y, i)
int c = k*(j-k) / i; // b > c
if (x == 0 && y == 0) {
f[i][j] += max(i-1-c, 0);
continue;
}
if (c < x) f[i][j] += max(x-1-c, 0) + max(i-1-y, 0); // b in (c, x) + (y, i)
else {
if (c < i && c > y) f[i][j] += max(i-1-c, 0);
if (c < i && c <= y) f[i][j] += max(i-1-y, 0);
}
}
f[j][i] = f[i][j];
}
}
}
long long count(int n, int m) {
long long ret = 0;
ret = 2 * (gao(n, m*m, x, y) + gao(m, n*n, x, y)) + 4 * f[n][m];
return ret;
}
int main() {
init();
while (scanf("%d%d", &n, &m) == 2) {
long long ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
long long ret = count(i, j);
ans += ret * (n-i+1) * (m-j+1);
}
}
printf("%lld\n", ans);
}
return 0;
}
ZOJ 3649 Social Net
每次问一棵最大生成树上，把x->y的边拿出来按顺序放在一个list里面，求$$\max(a_j - a_i) j \geq i, 0 \leq i, j \leq n$$
先最大生成树然后使用倍增算法。算出向根走$$2^k$$步这一段区间的max, min, 正向ans, 反向ans。询问的时候把路径上的若干段取出来然后先取里面的ans，再考虑段与段间的max, min即可。
#include
#include
#include
#include
#include
#include
#include
ZOJ 3650 Toy Blocks
在数轴上给定若干多米诺骨牌，然后每次你可以选择一个未推倒的骨牌把他向左或者向右推倒，推倒条件为$$| X_i - X_j | \leq H_i $$，问你最少要推几次。
先用线段树预处理出这个牌向左倒能推到哪里，向右能推到哪里。最后再用线段树优化dp的转移即可。dp的状态是f[i]表示前i个牌全倒了的方案数，转移就是像左推以及向右推。
#include
#include
#include
#include
#include
#include
#include
ZOJ 3651 Cipher Lock
n个拥有a, b属性的物品放成一圈，相邻物品要求$$a_i = a_{i + 1}$$或者$$b_i = b_{i + 1}$$。再限定8个位置的物品属性，问可能的不同属性分布的方案数。
mask dp + 矩阵乘法。mask的意思是前一个值等不等于接下来的u，以及后一个值等不等于接下来的v。这两个2进制位压成一个<4的数字dp即可。 注意那8个是可能重复的= =b，注意判断。
#include
#include
#include
#include
#include
#include
#include
ZOJ 3652 Maze
蘑菇题。。。略过吧-.-，就记录那几维，mask+bfs就好了。
#include
#include
#include
#include
#include
#include
#include