Codeforces Round #178 (Div. 二)（完全）

Codeforces Round #178 (Div. 2)（完全）

比赛地址：http://codeforces.com/contest/294

C题：

蛮有意思的，给你m个位置，现在要从这m个位置往位置的两边扩展，问你把所有的数都扩展到总共有多少种方法。

在两个位置中间的那些数的可能的排列数应该是2^（k-1），因为每次都有两种选择，要么左端点，要么右端点。

然后从所有的间隔中各取出一种排列，a1 a2 a3 b1 b2 b3 c1 c2 c3，现在就是求这个序列的总排列数，要求同类的先后顺序不能变，很容易发现这个其实就是类似于多重集合的排列，ans=n!/(p1!*p2!*p3!)   ，然后分子再乘上一个2^(k-1)就好了

#include<cstdio>#include<vector>#include<cstring>#include<algorithm>usingnamespace;typedeflonglong;constint=~0u>>2;constint=1000000007;constint=1010;int[];Pow(,){=1;while(){if(&1)=*%;=*%;>>=1;}return;}[],[];<int>;void(int){[0]=1;[0]=1;for(int=1;<=1000;++)[]=[-1]*%;for(int=1;<=1000;++)[]=[-1]*2%;int=0;for(int=0;<.();++)+=[];// printf("sum=%d\n",sum);=[];for(int=0;<.();++){=*Pow([[]],-2)%;}for(int=1;<.()-1;++){if([]>0)=*[[]-1]%;//   printf("ans=%d\n",rec[i]);}("%I64d\n",);}int(){int,;("%d%d",&,&);for(int=0;<;++){("%d",&[]);}(,+);.([0]-1);for(int=1;<;++){.([]-[-1]-1);}.(-[-1]);();return0;}

D题：

上次做过一个网格反弹的题，，，，被陷进去了。。。。

网格中的反弹有个性质就是45度反射的时候经过的格子的奇偶性都是一样的，所以无论怎么反弹，都不会经过两个相邻的方格。

给你一个n*m的矩形网格，问你从某个位置，某个方向出发经过多少个格子才能将网格染成棋盘的样子，也就是每两个相邻的格子的颜色都不同。

每个矩形有两种棋盘，不管哪种，如果成功染成某一种，肯定会经过边界的网格n+m-2次，也就是说，如果反弹过程中经过了n+m-2个不同的边界网格，肯定就对应着一种棋盘的方案，如果两次到达同一个位置同一个方向，肯定已经进入循环了。

学了一下java中的HashMap以及一些重载方面的东西。

http://codeforces.com/contest/294/submission/3493073

E题：
给你一棵树，5000个点，每条边有边权，可以删掉一条边再将这条边换个位置，要保证改变后仍然是树的形状，现在问你所有点对的距离之和最小是多少。
5000个点，马上想到n^2..然后就是暴力枚举去掉每条边 ，剩下的就是两棵树，然后重新连接一条边，稍微想一下，这条边肯定就是将两棵树的重心连起来，所以，接下来的事情就简单了。。。
比赛的时候看错了题，以为边可以修改很多次。。。然后各种YY，不够仔细啊。。。


#include<cstdio>#include<vector>#include<cstring>#include<algorithm>usingnamespace;constint=~0u>>2;constint=1000000007;constint=5010;int[];longlong[];int;int[][];<int>[];int;structEdge{int,,;Edge(){}Edge(int,int,int){=;=;=;}}in[];int[];void(int,int){[]=1;[]=[]+1;int=[].();for(int=0;<;++){int=[][];if(==)continue;(,);[]+=[];}}int;int[];void(int,int){[]=1;int=[].();for(int=0;<;++){int=[][];if(==||==)continue;(,);[]+=[];}}longlong;void(int,int,int){[]=0;int=[].();for(int=0;<;++){int=[][];if(==||==)continue;(,,);+=(longlong)[]*([]-[])*[][];[]+=[]+(longlong)[]*[][];}}longlongMi;void(int,int,int){if(==){Mi=([],Mi);}else{longlong=[]-[]-(longlong)[]*[][];[]+=(longlong)[][]*([]-[])+;Mi=([],Mi);}int=[].();for(int=0;<;++){int=[][];if(==||==)continue;(,,);}}int(){("%d",&);int,,;int=0;for(int=1;<;++){("%d%d%d",&,&,&);[].();[].();[][]=[][]=;in[++]=Edge(,,);}(1,0);longlong=(longlong)1000000000*(longlong)1000000000;longlong=;for(int=0;<;++){int=in[].,=in[].;if([]>[])(,);=;Mi=;=0;(1,0);(1,0,1);(1,0,1);longlong=(longlong)([1]-[])*([])*in[].;+=Mi*([]);+=;Mi=;=0;(,);(,,);(,,);+=Mi*([1]-[]);+=;if(<)=;}("%I64d\n",);return0;}