TC SRM 573

结果：过了250，challenge环节-1。 最后rate -9。
第一次TC连续跌两次了，只能呵呵了
主要还是250把题目看错一次，然后某SIR来个电话有事。。。
然后赛后好久才知道把450看错，我以为是能到达每一个点。。
不过结束之后很快把DIV2的做了。。。。
 
 
DIV2 A：直接和前一个比较
 
 
DIV2 B：贪心，将剩下的数排序之后。先取一个最大的，然后找到一个尽可能小的数，刚好和之前选的数相加能超过自己的得分。剩下一个数选尽可能小的。
 
 
DIV2C：大致写得很随意 。枚举坐标区间大致是[-50,100]，然后就是150*150枚举目标坐标。
遍历所有点，每个点到目标点的步数是知道的，大概就是坐标差。然后判断是否可达一下。
剩下的步数，当然是n左n右，m上m下的结构。然后统计一下每个方向有多少步，组合数搞一下就行了。
要是这次做的是div2那应该爽了。。。
[cpp] 
class WolfPackDivTwo  
{  
        public:  
        LL c[55][55];  
        void Init(){  
            for(int i=0;i<=50;i++){  
                c[i][0]=c[i][i]=1;  
                for(int j=1;j<i;j++)  
                    c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;  
            }  
        }  
        LL check(vi x,vi y,int cx,int cy,int m){  
            LL ans=1;  
            for(int i=0;i<x.size();i++){  
                int a=abs(x[i]-cx)+abs(y[i]-cy);  
                if(a>m || (m-a)&1)  
                    return 0;  
                int up=0,down=0,left=0,right=0;  
                int k=m-a;  
                if(x[i]>cx) left=x[i]-cx;  
                else right=cx-x[i];  
                if(y[i]>cy) up=y[i]-cy;  
                else up=cy-y[i];  
                LL t=0;  
                for(int j=0;j*2<=k;j++){  
                    int l=left+j;  
                    int r=right+j;  
                    int u=up+(k-2*j)/2;  
                    int d=down+(k-2*j)/2;  
                    t=((((c[m][l]*c[m-l][r])%MOD)*c[m-l-r][u]%MOD)+t)%MOD;  
                }  
                ans=((LL)ans*t)%MOD;  
            }  
            return ans;  
        }  
        int calc(vector <int> x, vector <int> y, int m)  
        {  
            LL ans=0;  
            Init();  
            for(int i=-51;i<=151;i++){  
                for(int j=-51;j<=151;j++){  
                    ans=(ans+check(x,y,i,j,m))%MOD;  
                }  
            }  
            return ans;  
        }  
}  
 
class WolfPackDivTwo
{
        public:
        LL c[55][55];
        void Init(){
         for(int i=0;i<=50;i++){
         c[i][0]=c[i][i]=1;
         for(int j=1;j<i;j++)
         c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
         }
        }
        LL check(vi x,vi y,int cx,int cy,int m){
         LL ans=1;
         for(int i=0;i<x.size();i++){
         int a=abs(x[i]-cx)+abs(y[i]-cy);
         if(a>m || (m-a)&1)
         return 0;
         int up=0,down=0,left=0,right=0;
         int k=m-a;
         if(x[i]>cx) left=x[i]-cx;
         else right=cx-x[i];
         if(y[i]>cy) up=y[i]-cy;
         else up=cy-y[i];
         LL t=0;
         for(int j=0;j*2<=k;j++){
         int l=left+j;
         int r=right+j;
         int u=up+(k-2*j)/2;
         int d=down+(k-2*j)/2;
             t=((((c[m][l]*c[m-l][r])%MOD)*c[m-l-r][u]%MOD)+t)%MOD;
         }
         ans=((LL)ans*t)%MOD;
         }
         return ans;
        }
        int calc(vector <int> x, vector <int> y, int m)
        {
         LL ans=0;
         Init();
         for(int i=-51;i<=151;i++){
         for(int j=-51;j<=151;j++){
         ans=(ans+check(x,y,i,j,m))%MOD;
         }
         }
         return ans;
        }
}
 
 
DIV1 A：大概和DIV2的B是差不多的。
也是贪心，先排序之后，找一个最大的。然后再找一个尽可能小的，和之前选的相加超过自己的得分的。
最后一个是在二者之前去找，如果没有说明已经找不到这样的组合了。
 
 
 
 
DIV1 B：题目看错了，囧。。。。
我以为是从0出发，能到达剩下N-1个点，只能呵呵了。
是说怎么大家都是用从0到N-1的最短路去做。。。
将高度离散化一下，dp[i][j]表示在i这个点，高度为w

补充：软件开发 , C++ ,