2012年浙大9月月赛总结 (ZOJ Monthly, September 2012)
本次比赛由我、DTen和ssslpk完成，一台机子进行。
因为迟到了两个小时，最终只出四题，最终排名81。其中我出了2题，Dten出了一题二分匹配，sssplk出了一道组合数学。Dten的那道二分匹配是我和他一起做的，卡了好久，正是因为这题卡太久没时间敲A题，不然A题是绝对可以AC的，赛时想的思路赛后十几分钟就AC了。
正是这场比赛，让我明白：自己最熟悉的题应该放在第一位，大家都过的题应该在第二位。
到现在我们共A了6道题，余下的题比较神奇，慢慢补。现在说下这场比赛的题目（前面数字是题目在Zoj上的题号）：
Zoj 3644 Kitty's Game DP。第一步先把k的因子找出来，用map进行映射。第二步设Dp[i][j]为到达i节点第j个因子的方案数。 本题给的有向图，不一定无环，这就有可能陷入死循环，这个要怎么处理呢？出题者很厚道，规定如果当前分数和下一个点的分数的最小公倍数为当前分数那就不往下走，一个数进入一个环，然后又回到进入环的那个点，这时候的公倍数相当于整个环内的公倍数和进入环时的公倍数的最小公倍数，然后再在环里走最小公倍数将不会改变，这样就保证不会再环里一直死循环下去。 然后用拓扑排序或者记忆化搜素都很好写。
Zoj 3645 BiliBili 题目给出的方程组是x^2 - 2 * x * x0 + x0 * x0 + .... = dit ^2，我们很难处理又有x^2又有-2*x*x0的，所以用前一行减去后一行，得到新的不带x^2的方程组。得到这样的方程组后套个double型的高斯消元模版，最后再处理下-0.00的情况就可以了。
Zoj 3646 Matrix Transformer 二分匹配。这题很难往图论这边想，一开始我们是yy，然后往高斯消元方面想，然后又开始yy。最后开窍用二分匹配过掉了。
Zoj 3647 Gao the Grid ssslpk AC的题。在一个n*m个方格中（顶点有（n+1）*(m+1)个），求所有三角形数，即三点不共线的所有情况。令所有点的个数为t,用c[t,3]来枚举所有情况，用总数扣去所有三点共线数就是所求的三角形数。那么在求三点共线的情况时，水平和垂直的情况读者自己考虑。对于倾斜的情况，先枚举两端的端点，如图，在一个6*10的方格中选4*4的两个端点，其中可构成三点花线的另一点的个数为最大公约数gcd(4,4) -1.如图中的三个点，然后用乘于剩下的倍数（6-4+1）*（10-4+1），再乘于2（倾斜时有右上，右下两种情况）.然后依次枚举所有的矩形，求出所有三点共线的情况。于是所有情况减三点共线情况就是答案了。
Zoj 3649 Social Net 学校的胖神牛用Q-tree过掉了此题。赛后becauseofyou说dp也可以做。那就是多解吧。
Zoj 3652 Maze 学校的一队就叫Maze，然后出了一题也叫Maze，当时是被他们AC了。赛后我也AC了。带状态压缩的搜索，得用优先队列来优化，不然会超时。然后有几个trick，1、起点终点有可能不可达 2、起点可能是终点，这时候输出0 3、第k只野兽可能不出现在矩阵中数字为k的地方，处理状态的时候要和其他分开。
Zoj 3653 Letty's Math Class 简单模拟题。第一个可能是负号也可能不是符号，为了不特判我在0这个位置插入一个+号，然后从前往后遍历处理一遍。中间的计算可能爆64位，用double来做，稳妥点。
解题报告写得很粗糙题目也很少，大牛神牛勿喷..
因为这场月赛ac的题目，zoj上的ac数目终于破百了，yuo xi。
本文ZeroClock原创，但可以转载，因为我们是兄弟。
附D题代码:
#include <cstdlib>#include<math.h>#include<stdio.h>#define int64 long long intusing namespace std;#define N 1002int64 f[N][N];int gcd(int a,int b){return b? gcd(b,a%b): a;}void init(){ for(int i=1;i<=1000;i++) { for(int j=i;j<=1000;j++) { int d=gcd(i,j); f[i][j]=f[j][i]=(int64)(d-1); } }}int main() { int64 n,m; init(); while(scanf("%lld%lld",&n,&m)!=EOF) { int64 sum=0; for(int64 i=1;i<=n;i++) { for(int64 j=1;j<=m;j++) { sum+=f[j][i]*2*(n-i+1)*(m-j+1); } } if(n>=2)sum+=(n+1)*(n)*(n-1)/6*(m+1); if(m>=2)sum+=(m+1)*(m)*(m-1)/6*(n+1); int64 t=(n+1)*(m+1); int64 num; if(t%3==0) { if((t-1)%2==0)num=t/3*(t-1)/2*(t-2); else num=t/3*(t-2)/2*(t-1); } else if((t-1)%3==0) { if(t%2==0) num=t/2*(t-1)/3*(t-2); else num=(t-1)/6*(t-2)*t; } else { if((t-1)%2==0) num=(t-1)/2*(t-2)/3*t; else num=(t)/2*(t-2)/3*(t-1); } // printf("sum: %lld\n",sum); printf("%lld\n",num-sum); } return 0;}