TopCoder SRM 496

本次Rating降至空心黄

500搞了半天j打成i看不出来。。。交的时候都只剩200+分了。

最后500还是挂掉了，后来发现if里有个东西又打错了。。。一改Y了。

5555555555555555，现在神马都不行了。

在TC里那个字体太疼了= =。下次在外面打算了。

250

题目给定一个矩阵，每一笔你可以横向涂一笔连续的红的，或者竖向涂一笔连续的蓝的。如果一个格子被涂了红和蓝的，那么会变绿的。最后给出矩阵每个格子的颜色，问最少涂多少笔涂成这个样。

矩阵最大是50*50的。

……就是枚举。

class ColoredStrokes {
    vector    int m,n,ans;
    int v[55][55];
public:
    void solvex(){
      memset(v,0,sizeof(v));
      for (int i=0;i        for (int j=0;j          if ( (S[i][j]==’G’ || S[i][j]==’R’) && (!v[i][j]) ){
            for (int k=j;k              v[i][k]=1;
            ans++;
          }       
        }
    }
    
    void solvey(){
      memset(v,0,sizeof(v));
      for (int i=0;i        for (int j=0;j          if ( (S[i][j]==’B’ || S[i][j]==’G’) && (!v[i][j]) ){
            for (int k=i;k              v[k][j]=1;
            ans++;
          }
        }
    }
    
    int getLeast(vector       S=picture.begin();
      m=picture.size();
      n=picture[0].size();
      ans=0;
      solvex();
      solvey();
      return ans;
    }
};

 

500

有一些球在数轴上跑，然后他们都有一个相同的正的速度。(并且球不会发生碰撞)

然后他给出的第一个数组给定了一开始每个球的位置。

他又给了第二个数组，表示的是之后某个时刻每个球的位置。（但是有一些无关的球会被加进去）

假设way[i]表示第一个数组中第i个球是第二个数组中第way[i]个球，那么问way这个数组有多少种可能的不同的取值。

两个数组中的元素个数都<=50，题目保证了两个数组中，都不会有重复的数值。

样例：

具体做法就是先枚举他们的速度，设为dis。(显然速度只能是 abs(a[i]-b[j]) )

接下来我们来建边：

a[i] ->  (a[i]-dis) in b[j]

a[i] ->  (a[i]+dis) in b[j]

对于a[i]，如果不存在其它的a[j]和它争b数组中的结点，那么显然他连出去多少条边，就有多少种方案，然后利用乘法原理乘起来就行。

然后我们关注发生冲突的。因为a,b数组中都不包含重复元素，那么发生冲突只能是这样情况：

a[i]+dis=a[j]-dis

然后继续发生冲突：a[j]+dis=a[k]-dis…

如此下去就会变成一条链。

然后……就判一个每个结点-dis和+dis的是否在b数组中存在。然后匹配时对于这条链，要么全-dis，要么全+dis，要么从中间部分开始，前一半-dis,后一半+dis……于是就这样每条链分开讨论，乘法原理将方案数乘起来。

然后再根据加法原理把不同速度的方案加起来。得到解。

class OneDimensionalBalls {
public:
    int up[55];
    int down[55];
    int m,n;
    int a[55];
    int b[55];
    int v[55];
    int tail;
    int dis;
    int List[55*55];
    
    void make_up_down(){
      int i,j;
      memset(up,0,sizeof(up));
      memset(down,0,sizeof(down));
      for (i=0;i        for (j=0;j          if (a[i]-dis==b[j]) up[i]=1;
          if (a[i]+dis==b[j]) down[i]=1;
        }
    }
    
    int Q[55];
    int Qt;
    int Link(int st){
      int i;
      Qt=1; Q[1]=st;
      v[st]=1;
      for (i=st+1;i        if (a[i]-a[Q[Qt]]==2*dis && down[Q[Qt]]){
          v[i]=1;
          Q[++Qt]=i;
        }
      int ed=Q[Qt];
      if (!up[st] && !down[ed]) return 0;
      if (!up[st]) return 1;
      if (!down[ed]) return 1;
      return Qt+1;
    }
    
    long long countValidGuesses(vector       m=firstPicture.size();
      n=secondPicture.size();
      for (int i=0;i      for (int i=0;i      sort(a,a+m);
      sort(b,b+n);
      tail=0;
      for (int i=0;i        for (int j=0;j          if (a[i]!=b[j])
            List[++tail]=abs(a[i]-b[j]);
      long long ans=0;
      long long now;
      sort(List+1,List+tail+1);
      for (int i=1;i<=tail;i++)
        if (i==1 || List[i]!=List[i-1]){
          dis=List[i];
          make_up_down();
          memset(v,0,sizeof(v));
          now=1;
          for (int j=0;j            if (!v[j])
              now*=Link(j);
          ans+=now;
        }
      return ans;
    }
};

 

950

推荐hhanger大神的解题报告