月度归档:2019年09月

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

Transformation HDU – 4578 (延迟标记)

对延迟标记要有深入的理解。。。多个标记同时存在时要考虑顺序

参考:http://www.cfzhao.com/2019/04/03/hdu-4578-transformation/

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int SIZE = 100005;
const int MOD = 10007;
int n, q;

struct SegmentTree {
  int l, r;
  int sum,sum2,sum3;
  int lazy_add,lazy_mul,lazy_assign;
 #define l(x) tree[x].l
 #define r(x) tree[x].r
 #define sum(x) tree[x].sum
 #define sum2(x) tree[x].sum2
 #define sum3(x) tree[x].sum3
 #define lazy_add(x) tree[x].lazy_add
 #define lazy_mul(x) tree[x].lazy_mul
 #define lazy_assign(x) tree[x].lazy_assign
} tree[SIZE * 4];

void pushup(int p){
  sum(p)=(sum(p<<1|1)+sum(p<<1))%MOD;
  sum2(p)=(sum2(p<<1|1)+sum2(p<<1))%MOD;
  sum3(p)=(sum3(p<<1|1)+sum3(p<<1))%MOD;
}

void spread(int p){
  if(lazy_assign(p)){
    int s1=lazy_assign(p)%MOD,s2=s1*lazy_assign(p)%MOD,s3=s2*lazy_assign(p)%MOD;
    sum(p<<1|1)=s1*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=s1*(r(p<<1)-l(p<<1)+1)%MOD;
    sum2(p<<1|1)=s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum2(p<<1)=s2*(r(p<<1)-l(p<<1)+1)%MOD;
    sum3(p<<1|1)=s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum3(p<<1)=s3*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_assign(p<<1|1)=lazy_assign(p<<1)=lazy_assign(p);
    lazy_add(p<<1|1)=lazy_add(p<<1)=0;
    lazy_mul(p<<1|1)=lazy_mul(p<<1)=1;
    lazy_assign(p)=0; 
  }
  if(lazy_mul(p)!=1){
    int s1=lazy_mul(p)%MOD,s2=s1*lazy_mul(p)%MOD,s3=s2*lazy_mul(p)%MOD;
    sum(p<<1|1)=sum(p<<1|1)*s1%MOD;
    sum(p<<1)=sum(p<<1)*s1%MOD;
    sum2(p<<1|1)=sum2(p<<1|1)*s2%MOD;
    sum2(p<<1)=sum2(p<<1)*s2%MOD;
    sum3(p<<1|1)=sum3(p<<1|1)*s3%MOD;
    sum3(p<<1)=sum3(p<<1)*s3%MOD;
    lazy_mul(p<<1|1)=lazy_mul(p<<1|1)*lazy_mul(p)%MOD;
    lazy_mul(p<<1)=lazy_mul(p<<1)*lazy_mul(p)%MOD;
    lazy_add(p<<1|1)=lazy_add(p<<1|1)*lazy_mul(p)%MOD;
    lazy_add(p<<1)=lazy_add(p<<1)*lazy_mul(p)%MOD;
    lazy_mul(p)=1;
  }
  if(lazy_add(p)!=0){
    int s1=lazy_add(p)%MOD,s2=s1*lazy_add(p)%MOD,s3=s2*lazy_add(p)%MOD;
    sum3(p<<1|1)=(sum3(p<<1|1)+3*s1%MOD*sum2(p<<1|1)%MOD+3*s2%MOD*sum(p<<1|1)%MOD+s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum3(p<<1)=(sum3(p<<1)+3*s1%MOD*sum2(p<<1)%MOD+3*s2%MOD*sum(p<<1)%MOD+s3*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum2(p<<1|1)=(sum2(p<<1|1)+2*s1%MOD*sum(p<<1|1)%MOD+s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum2(p<<1)=(sum2(p<<1)+2*s1%MOD*sum(p<<1)%MOD+s2*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum(p<<1|1)=sum(p<<1|1)+lazy_add(p)*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=sum(p<<1)+lazy_add(p)*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_add(p<<1|1)=(lazy_add(p<<1|1)+lazy_add(p))%MOD;
    lazy_add(p<<1)=(lazy_add(p<<1)+lazy_add(p))%MOD;
    lazy_add(p)=0;
  }

}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  lazy_add(p)=0,lazy_assign(p)=0,lazy_mul(p)=1;
  if (l == r) {
    sum(p)=sum2(p)=sum3(p)=0;
    return ;
  }
  int mid = (l + r) >>1;
  build(p<<1, l, mid);
  build(p <<1 | 1, mid + 1, r);
  pushup(p);
}

void change(int p, int L,int R, int c,int d) {
  if(L<=l(p) && r(p)<=R){
    ll s1=d%MOD,s2=s1*d%MOD,s3=s2*d%MOD;
    if(c==1){
     sum3(p)=(sum3(p)+3*s1%MOD*sum2(p)%MOD+3*s2%MOD*sum(p)%MOD+s3*(r(p)-l(p)+1)%MOD)%MOD;
     sum2(p)=(sum2(p)+2*s1%MOD*sum(p)%MOD+s2*(r(p)-l(p)+1)%MOD)%MOD;
     sum(p)=(sum(p)+s1*(r(p)-l(p)+1)%MOD)%MOD;
     lazy_add(p)=(lazy_add(p)+d)%MOD;
    }
    if(c==2){
      sum(p)=s1*sum(p)%MOD;
      sum2(p)=s2*sum2(p)%MOD;
      sum3(p)=s3*sum3(p)%MOD;
      lazy_mul(p)=lazy_mul(p)*d%MOD;
      lazy_add(p)=lazy_add(p)*d%MOD;
    }
    if(c==3){
      sum(p)=s1*(r(p)-l(p)+1)%MOD;
      sum2(p)=s2*(r(p)-l(p)+1)%MOD;
      sum3(p)=s3*(r(p)-l(p)+1)%MOD;
      lazy_assign(p)=d;
      lazy_add(p)=0;
      lazy_mul(p)=1;
    }
    return;
  } 
  spread(p);
  int mid=(l(p)+r(p))>>1;
  if(L<=mid) change(p<<1,L,R,c,d);
  if(R>mid) change(p<<1|1,L,R,c,d);
  pushup(p);
} 

int ask(int p,int l,int r,int c){
    if(l<=l(p) && r(p)<=r){
      if(c==1) return sum(p);
      if(c==2) return sum2(p);
      if(c==3) return sum3(p);
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    int val=0;
    if(l<=mid)  val+=ask(p<<1,l,r,c);
    if(r>mid)  val+=ask(p<<1|1,l,r,c);
    return val%MOD;
} 

int main() {
  int T,kase=0;
  while(~scanf("%d%d",&n,&q)&&n&&q){
    build(1,1,n);
    while(q--){
      int a,x,y,c;
      scanf("%d%d%d%d",&a,&x,&y,&c);
      if(a!=4) change(1,x,y,a,c);
      else{
        printf("%d\n",ask(1,x,y,c));
      }
    }

  }
  return 0;
}