KickStart 2018 Round D

第一题滑动窗口+multiset的运用
第二题将两个不等式条件转化为两个点的位置关系(一个点在另一个点的右上方),这个转化像整体换元,感觉很巧妙...然后贪心。
第三题四维dp+前缀和处理,参考了【Kickstart】2018 Round D - Funniest Word Search
以下是第三题的代码,值得保存下来复习。

——————————
好难……
——————————

Funniest Word Search

#include<bits/stdc++.h>

using namespace std;

const int SIZE = 105;
int R,C,W;
char in [SIZE][SIZE];
int sumr[SIZE][SIZE][SIZE];
int sumc[SIZE][SIZE][SIZE];
int f[SIZE][SIZE][SIZE][SIZE];
int vr[SIZE][SIZE][SIZE];
int vc[SIZE][SIZE][SIZE];

typedef unordered_multiset<string> DICT;
unordered_map<int,DICT> word;

int  value,_size,cnt;
void check(int i1,int j1,int i2,int j2){
    int  s=i2-i1+j2-j1+2;
    int  v=f[i1][j1][i2][j2];
    if((long long)v*_size>=(long long) value*s){
      if((long long) v*_size==(long long)value*s) cnt++;
      else{
        cnt=1;
        value=v;
        _size=s;
        int divisor=__gcd(value,_size);
        value/=divisor,_size/=divisor;
      }
    }

}

void solve (){

    for(int i=1;i<=R;++i){
      for(int j=1;j<=C;++j){
        string val="";
        for(int k=1;k<=j;++k){
            vr[i][j][k]=vr[i][j][k-1];
            val+=in[i][j-k+1-1];
            vr[i][j][k]+=word[k].count(val)*k;

        }

        string val2="";
        for(int k=1;k<=i;++k){
          vc[i][j][k]=vc[i][j][k-1];
          val2+=in[i-k+1][j-1];
          vc[i][j][k]+=word[k].count(val2)*k;
        }
      }
    }

    for(int i=1;i<=R;++i){
      for(int j=1;j<=C;++j){
        for(int k=1;k<=j;++k){
          sumr[i][j][k]=sumr[i-1][j][k]+vr[i][j][k];
        }

        for(int k=1;k<=i;++k){
          sumc[i][j][k]=sumc[i-1][j][k-1]+vc[i][j][k];
        }

      }
    }

    for(int i1=1;i1<=R;++i1){
      for(int j1=1;j1<=C;++j1){
        for(int i2=i1;i2<=R;++i2){
          for(int j2=j1;j2<=C;++j2){
              if(j2==j1){
                f[i1][j1][i2][j2]=f[i1][j1][i2-1][j2]+vr[i2][j2][1]+vc[i2][j2][i2-i1+1];
                check(i1,j1,i2,j2);
              }
              else{
                f[i1][j1][i2][j2]=f[i1][j1][i2][j2-1]+sumr[i2][j2][j2-j1+1]-sumr[i1-1][j2][j2-j1+1]+sumc[i2][j2][i2-i1+1];
                check(i1,j1,i2,j2);
              }
          }
        }
      }
    }
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    while(T--){
      _size=1,value=0,cnt=0;
      word.clear();
      scanf("%d%d%d",&R,&C,&W);
      for(int i=1;i<=R;++i){
        scanf("%s",in[i]);

      }
      for(int i=1;i<=W;++i){
        string tmp;
        cin>>tmp;
        int len = tmp.length();
        word[len].insert(tmp);
        reverse(tmp.begin(),tmp.end());
        word[len].insert(tmp);
      }

      solve();
      printf("Case #%d: %d/%d %d\n",++kase, value, _size , cnt );
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注