标签归档:Kick Start

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;
}

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s,满足K个限制(s[A,B]中含有C个1),且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]:假设前i个字符已固定,且这前i个中最后16个字符为j时的合法方案数(注意j前面的到底是什么我们不用管,反正看作前缀是固定的,而这个结果统计的是前缀之后的部分可以有多少种变化)。我们从后往前转移,最终得到每个位置的情况。如何转移看代码就很清楚了,再次感到熟练位操作对做状压方面的题目很重要。

官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系,一开始没理解...就是如果串是i开头的话(我们以字典序的顺序来尝试i),f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了,否则从P中减掉f[1][i](f[1][i]的方案里都是些比P小的啊,减掉f[1][i]之后的P(用P'表示吧)就是开头字典序比i大时的方案里第p'大的,也是原来那个第P大的),i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。

#include<bits/stdc++.h>
using namespace std;

long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];

bool check(int i,int last){
    for(int j=0;j<limits[i].size();++j){
        if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
            return false;
        }
    }
    return true;
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    for(int i=1;i<(1<<16);++i){
        cnt[i]=cnt[i>>1]+(i&1);
        shl[i]=(i<<1)&((1<<16)-1);
    }
    while(T--){
        int n,k;
        long long p;
        scanf("%d%d%lld",&n,&k,&p);
        for(int i=1;i<=n;++i) limits[i].clear();
        for(int i=1;i<=k;++i){
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            limits[B].push_back(make_pair(B-A+1,C));
        }
        for(int i=0;i<(1<<16);++i){
            if(check(n,i)){
                f[n][i]=1;
            }
            else f[n][i]=0;
        }
        for(int i=n-1;i>0;--i){
            for(int j=0;j<(1<<16);++j){
                if(check(i,j)){
                    f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
                    if(f[i][j]>1e18) f[i][j]=1e18+1;
                }
                else f[i][j]=0;
            }
        }

        printf("Case #%d: ",++kase);
        for(int i=1,j=0;i<=n;++i,j=shl[j]){
            if(f[i][j]>=p){
                printf("0");
            }
            else{
                p-=f[i][j];
                j^=1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}