分类目录归档:算法

十月(扫描线,分块,点分治)

  • 最近没什么时间更新了,今后打算一个月更一次。

  • 这个月的kickstart好可惜啊。。。痛失35分。。其实就是太菜了。。。

  • 开始在AcWing上打卡,逐步完成《算法竞赛进阶指南》的内容。

1. 重温扫描线写法

窗内的星星

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

int n,W,H;
struct  Line
{
  int x,y1,y2,c;
  bool operator<(const Line &b){
    return x==b.x? x>b.c : x<b.x; //减掉c是在下一个x查询时起作用,因为假设矩形顶点都是整数,虽不影响答案,但实际上离真正的右边界还有些余量

  } 
}L[20005];
unordered_map<int,int> val;
int raw[40005];
struct SegmentTree{
  int l,r;
  int dat;
  int add;

}t[20005*4];

void build(int l,int r,int p){
  t[p].l=l,t[p].r=r;
  t[p].dat=0;
  if(l==r){
    return ;
  }
  int mid= (l+r)>>1;  
  build(l,mid,p<<1);
  build(mid+1,r,p<<1|1);
}

void spread(int x ){
  if (t[x].add){
    t[x*2].add+=t[x].add ;
    t[2*x+1].add+=t[x].add; 
    t[x*2].dat+=t[x].add;
    t[x*2+1].dat+=t[x].add;
    t[x].add=0;
  }

}

void change(int l,int r, int p,int x){
  if (l<=t[p].l && t[p].r <=r) {
    t[p].add +=x;
    t[p].dat +=x;
    return ;
  }
  spread(p);
  int mid = (t[p].l+t[p].r)>>1;
  if (l<=mid) change(l,r,p<<1,x) ;
  if(mid<r) change(l,r,p<<1|1,x);
  t[p].dat = max(t[p*2].dat,t[p*2+1].dat);
}

int main(){
  while(~scanf("%d%d%d",&n,&W,&H)){
    int tot=0,tot2=0;
    memset(L,0,sizeof(L));
    val.clear();
    memset(raw,0,sizeof(raw));
    for(int i=0;i<n;++i){
      int x,y,c;
      scanf("%d%d%d",&x,&y,&c);
      L[tot].x=x,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c+=c;
      L[tot].x=x+W-1,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c-=c;
      raw[tot2++]=y;
      raw[tot2++]=y+H-1;
    }
    sort(L,L+tot);
    sort(raw,raw+tot2);
    int tot3 = unique(raw,raw+tot2)-raw;
    for(int i=1;i<=tot3;++i){
       val[raw[i-1]] = i;
    }
    build(1,tot3-1,1);
    int ans =0;
    for(int i =0;i<tot;++i){
      change(val[L[i].y1],val[L[i].y2]-1,1,L[i].c);
      ans = max(t[1].dat,ans);
    }
    printf("%d\n",ans);
  }

  return 0;
}

2. 学习了分块,“大段维护,局部朴素”思想。好像还混入了莫队算法这种奇妙的东西。。

(设分块数为T ,会发现要算法复杂度达到最优 ,可根据均值不等式得到T的值。)

蒲公英

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

int a[40010];
int b[40010];
int cnt[40][40][40010], cnt_temp[40010];
int maxx[40][40];
int res[40][40];
int L[40], R[40];
int pos[40010];
int n, m, t;

int ask(int l, int r) {
  int p = pos[l], q = pos[r];
  int ans = 0;
  int ret;
  if (p == q) {
    for (int i = l; i <= r; ++i) cnt_temp[a[i]] = 0;
    for (int i = l; i <= r; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]];
      }
      if (ans == cnt_temp[a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }
    return b[ret];
  } else {
    ans = maxx[p + 1][q - 1];
    ret = res[p + 1][q - 1];
    for (int i = l; i <= R[p]; ++i) {
      cnt_temp[a[i]] = 0;
    }
    for (int i = L[q]; i <= r; ++i) {
      cnt_temp[a[i]] = 0;
    }
    for (int i = l; i <= R[p]; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
      }
      if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }

    for (int i = L[q]; i <= r; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
      }
      if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }
    return b[ret];
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  t = pow(1.0 * n, 1.0 / 3.0);

  for (int i = 1; i <= t; ++i) {
    L[i] = (i - 1) * (n / t) + 1;
    R[i] = n / t * i;
  }
  if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;

  sort(b + 1, b + n + 1);
  int M = unique(b + 1, b + 1 + n) - b - 1;
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + M, a[i]) - b;

  int T = 1;
  for (int i = 1; i <= n; ++i) {
    pos[i] = T;
    if (i >= R[T]) T++;
  }
  for (int i = 1; i <= t; ++i) {
    for (int j = i; j <= t; ++j) {
      for (int k = L[i]; k <= R[j]; ++k) {
        cnt[i][j][a[k]]++;
        if (maxx[i][j] < cnt[i][j][a[k]]) {
          maxx[i][j] = cnt[i][j][a[k]];
          res[i][j] = a[k];
        }
        if (maxx[i][j] == cnt[i][j][a[k]] && a[k] < res[i][j]) {
          res[i][j] = a[k];
        }
      }
    }
  }
  int x = 0;
  int l0, r0, l, r;
  while (m--) {
    scanf("%d%d", &l0, &r0);
    l = (l0 + x - 1) % n + 1;
    r = (r0 + x - 1) % n + 1;
    if (l > r) swap(l, r);

    printf("%d\n", x = ask(l, r));
  }

  return 0;
}

还有做法是保存段边界为端点的区间众数。这个做法涉及到一个技巧,就是顺序保存数a在序列里的出现位置,然后对要求范围的L,R进行二分查找,下标相减可得到a在[L,R]中的出现次数。

磁力块

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

int x0,Y0,pl;
long long rl;
int N;
struct stone{
  int m,cp;
  long long r; 
  long long cr;
  bool operator<(stone a){
     return  m<a.m;
  }
}A[250050];
bool cmp(stone a,stone b){
  return a.r<b.r;
}
int L[505];
int R[505];
int maxx[505];
int v[250050];
int main(){
  scanf("%d%d%d%lld%d",&x0,&Y0,&pl,&rl,&N);
  A[0].r=0;
  A[0].cr=rl*rl;
  A[0].cp=pl;
  A[0].m=-1;
  for(int i=1;i<=N;++i){
    int x,y,m,p;
    long long r;
    scanf("%d%d%d%d%lld",&x,&y,&m,&p,&r);
    A[i].r=(long long)(x-x0)*(x-x0)+(long long)(y-Y0)*(y-Y0);
    A[i].m=m;
    A[i].cr=r*r;
    A[i].cp=p;
  }
  sort(A+1,A+1+N);
  int t =sqrt(N);
  for(int i=1;i<=t;++i){
    L[i]=(i-1)*(N/t)+1;
    R[i]=i*(N/t);
    maxx[i]=A[R[i]].m;
  }
  if(R[t]<N) t++,L[t]=R[t-1]+1,R[t]=N,maxx[t]=A[N].m;

  for(int i=1;i<=t;++i){
    sort(A+L[i],A+R[i]+1,cmp);
  }

  int ans=0;
  queue<stone> q;
  q.push(A[0]);
  v[0]=1;
  while(q.size()){
    stone S = q.front();
    q.pop();
    for(int i=1;i<=t;++i){
      if(maxx[i]<=S.cp){
        while(L[i]<=R[i] && A[L[i]].r<=S.cr){
          if (!v[L[i]]){
            q.push(A[L[i]]);
            v[L[i]]=1;
            ans++;
          }
         L[i]++;
        }
      }
      else {
        for(int j = L[i];j<=R[i];++j){
          if(!v[j] && A[j].m<=S.cp && A[j].r<=S.cr){
            q.push(A[j]);
            v[j]=1;
            ans++;
          }
        }
        break;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

小Z的袜子

莫队离线处理,将询问区间排序、分块,由已经求出的区间推至相邻的区间。

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

struct query {
  int l, r, id, pos;
  long long ans, base;
  bool operator<(const query& a) { return l < a.l; }
} Q[50005];
int L[50005];
int R[50005];
int num[50005];

int N, M;
int C[50005];
bool cmp(query a, query b) {
  if (a.pos == b.pos) {
    return a.r < b.r;
  } else
    return a.pos < b.pos;
}
bool cmp2(query a, query b) { return a.id < b.id; }

int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &C[i]);
  }
  int t = sqrt(N);
  int T = 0;
  for (int i = 1; i <= M; ++i) {
    int il, ir;
    scanf("%d%d", &il, &ir);
    Q[i].l = il, Q[i].r = ir;
    Q[i].id = i;
    Q[i].pos = il / t + 1;
    T = max(T, Q[i].pos);
  }
  sort(Q + 1, Q + 1 + M, cmp);

  int p = 0;
  for (int i = 1; i <= M; ++i) {
    if (Q[i].pos != p) {
      L[++p] = i;
      if (p > 0) R[p - 1] = i - 1;
    }
  }
  R[p] = M;

  long long temp, bans;
  for (int i = 1; i <= T; ++i) {
    memset(num, 0, sizeof(num));

    int first = L[i];

    int l = Q[first].l, r = Q[first].r;

    for (int j = l; j <= r; ++j) {
      Q[first].ans -= (long long)num[C[j]] * (num[C[j]] - 1) / 2;
      num[C[j]]++;
      Q[first].ans += (long long)num[C[j]] * (num[C[j]] - 1) / 2;
    }

    temp = (long long)(r - l + 1) * (r - l) / 2;
    bans = Q[first].ans;

    if (Q[first].ans == 0) {
      Q[first].base = 1;
    } else if (bans > temp) {
      Q[first].base = 1, Q[first].ans = 1;
    } else {
      Q[first].ans = bans / __gcd(bans, temp);
      Q[first].base = temp / __gcd(bans, temp);
    }

    for (int j = L[i] + 1; j <= R[i]; ++j) {
      int l = Q[j].l, r = Q[j].r;

      Q[j].ans = bans;
      if (Q[j - 1].l > l) {
        for (int k = l; k < Q[j - 1].l; ++k) {
          Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
          num[C[k]]++;
          Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        }
      } else if (Q[j - 1].l < l) {
        for (int k = Q[j - 1].l; k < l; ++k) {
          Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
          num[C[k]]--;
          Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        }
      }
      for (int k = Q[j - 1].r + 1; k <= r; ++k) {
        Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        num[C[k]]++;
        Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
      }

      temp = (long long)(r - l + 1) * (r - l) / 2;
      bans = Q[j].ans;
      if (Q[j].ans == 0) {
        Q[j].base = 1;
      } else if (bans > temp) {
        Q[j].ans = Q[j].base = 1;
      } else {
        Q[j].ans = bans / __gcd(bans, temp);
        Q[j].base = temp / __gcd(bans, temp);
      }
    }
  }
  sort(Q + 1, Q + 1 + M, cmp2);
  for (int i = 1; i <= M; ++i) {
    printf("%lld/%lld\n", Q[i].ans, Q[i].base);
  }
  return 0;
}

3.学习了点分治,也就是树上的分治,相比于线性数组里的序列[L,R],树对应的是两点之间的路径,线性序列二分对应于找树的重心。此题在递归求解时,当前层的需求是得到两点路径经过树根p的情况,考虑到会遍历整棵树,两点在同一棵p的子树(不经过p)的情况也会被包括,但是路径长度却算上了子树树根到父结点p的距离,要减掉这种情况(容斥)

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

const int maxn  = 40000+100;
struct edge{
  int to,w;
};

int N,K;
int vis[maxn];
int max_part[maxn];
int _size[maxn];
int d[maxn];
int b[maxn];
int len[maxn];
int root;
int tot_node;
int ans;
vector<edge> E[maxn*2];

void addEdge(int x,int y,int z){
  E[x].push_back(edge{y,z});
}

void getRoot(int u,int fa){
  max_part[u] = 0;
  _size[u]=1;

  for(int i = 0;i<E[u].size();++i){
    int v =E[u][i].to;
    if(vis[v]|| v ==fa) continue;
    getRoot(v,u);
    _size[u] += _size[v];
    max_part[u]=max(max_part[u],_size[v]); 
  }
  max_part[u] = max(max_part[u],tot_node - _size[u]);
  if (max_part[u] < max_part[root]){
      root =u;
  }
}

void getDis(int u,int fa){
  len[++len[0]] = d[u];
  for(int i=0;i<E[u].size();++i){
    int v = E[u][i].to;
    if(vis[v] || v == fa ) continue;
    d[v] = d[u]+E[u][i].w;
    getDis(v,u);
  }
}

int cal(int u,int now){
  d[u] = now , len[0]=0;
  getDis(u,0);
  sort(len+1,len+len[0]+1);
  int all = 0;
  for(int l=1,r=len[0];l<r;){
    if(len[l]+len[r]<=K){
      all+=r-l;
      ++l;
    }
    else r--;
  }
  return all;
}

void solve(int u){
  vis[u] = true;
  ans +=cal(u,0);
  for(int i=0;i<E[u].size();++i){
    int v = E[u][i].to;
    if(vis[v] ) continue;
    ans -= cal(v, E[u][i].w);
    tot_node = _size[v];
    root =0;
    getRoot(v,u);
    solve(root);
  }
}

int main(){
  while(~scanf("%d%d",&N,&K) && N && K){
    for(int i=1;i<=N;++i){
      E[i].clear();
    }
    ans = 0;
    memset(vis,0,sizeof(vis));

    for(int i=1;i<N;++i){
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      addEdge(x+1,y+1,z);
      addEdge(y+1,x+1,z);
    }
    tot_node = N;
    max_part[0]=N;
    root = 0;
    getRoot(1,0);
    solve(root);
    printf("%d\n",ans);
  }
  return 0;
}

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

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小的,开头字典序比i大时的方案里第P-f[1][i]大的,就是原来所有方案里第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;
}

SGU385 Highlander

题目来源:SGU 385
图片来自国家集训队论文《浅析竞赛中一类数学期望问题的解决方法》

其中min(j,i-j+1) 更改为min(j-1,i-j)貌似更合适。

#include<bits/stdc++.h>

using namespace std;

double d[105];
double fac[105];
double f[105][105][105];
double g[105][105];

double A(int i,int j){
    return fac[i]/fac[i-j];
}

int main(){
    int n;
    scanf("%d",&n);

    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=i*fac[i-1];
    }

    d[1]=0,d[2]=1;
    for(int i=3;i<=n;++i){
        d[i]=(i-1)*(d[i-1]+d[i-2]);
    }

    for(int i=2;i<=n;++i){
        for(int j=2;j<i;++j){
            for(int l=2;l<=min(j-1,i-j);l++){
                f[i][j][1]+=g[i-j][l];
            }
            f[i][j][1]*=A(n-i+j,j)/j;
            g[i][j]+=f[i][j][1];
            for(int k=2;k<=i/j;k++){
                f[i][j][k]=f[i-j][j][k-1]*A(n-i+j,j)/j/k;
                g[i][j]+=f[i][j][k];
            }
        }
        f[i][i][1]=A(n,i)/i;
        g[i][i]+=f[i][i][1];
    }

    double res=0;
    for(int j=2;j<=n;++j){
        for(int k=1;k<=n;++k){
            res+=f[n][j][k]*j*k;
        }
    }
    printf("%.10f\n",res/d[n]);

    return 0;
}

[NOI2005]聪聪与可可

聪聪与可可

在一个单位时间内,聪聪根据可可的位置,会先走出最短路中的下一步,然后被抓者可等概率随意走一步,也可原地不动。
在距离一步或者两步的时候,只要一个单位时间就可以抓到了,这是递归基。然后记忆化搜索解决之。

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

const int INF=0x3f3f3f3f;
int ver[2010],edge[2010],Next[2010],head[2010];
int t[1005],v[1005];
int dis[1005][1005]; //i到j的最短路长度
int p[1005][1005]; //p[i][j]从i到j的最短路中,i第一步到达的地方
double f[1005][1005]; //f[i][j] 初始地点i和j,抓到时的期望步数
int N,tot;

void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}

void shortest_path(int *d,int len,int s){
     memset(d,0x3f,len);
     memset(v,0,sizeof(v));
     d[s]=0;
     v[s]=1;
     queue<int> q;
     q.push(s);
     while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!v[y]){
                v[y]=1;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
     }
}

double solve(int i,int j){
    if(f[i][j]||i==j) return f[i][j];
    int fir=p[i][j],sec=p[fir][j];
    if(fir==j||sec==j) return f[i][j]=1;
    for(int k=head[j];k;k=Next[k]){
        f[i][j]+=solve(sec,ver[k]);
    }
    f[i][j]+=solve(sec,j);
    return f[i][j]=f[i][j]/(t[j]+1)+1;
}

int main(){
    //freopen("testdata.in","r",stdin);
    int E,C,M;
    scanf("%d%d%d%d",&N,&E,&C,&M);
    for(int i=0;i<E;++i){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        add(t1,t2,1);
        add(t2,t1,1);

    }

    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            dis[i][j]=INF;
        }
    }

    for(int i=1;i<=N;++i){
        shortest_path(dis[i],sizeof(dis[i]),i);
    }

    memset(p,0x3f,sizeof(p));
    for(int i=1;i<=N;++i){
        p[i][i]=i;
        for(int j=head[i];j;j=Next[j]){
            int y=ver[j];
            for(int k=1;k<=N;++k){
                if(dis[y][k]==dis[i][k]-1){
                    p[i][k]=min(p[i][k],y);
                }
            }
            t[i]++;
        }
    }

    printf("%.3lf\n",solve(C,M));

    return 0;
}

扫描线(POJ 1151)

在平面坐标系里给出一些矩形,求面积并.
Atlantis

#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=106;
int n,m,num=0;

struct P{
    double x,y,z;
    int k;
    bool operator<(const P w) const{
        return x<w.x;
    }
}a[N<<1];

double raw[N<<1];
map<double ,int > val ;

struct Tree{
    int l,r,cnt;
    double len;
}t[N<<3];

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].cnt=0;
    t[p].len=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void change(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r) t[p].len=((t[p].cnt+=k)>0?raw[t[p].r+1]-raw[t[p].l]:0);
    if(t[p].l==t[p].r) return;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(p<<1,l,r,k);
    if(r>mid) change(p<<1|1,l,r,k);
    t[p].len=(t[p].cnt>0?raw[t[p].r+1]-raw[t[p].l]:t[p<<1].len+t[p<<1|1].len);
}

void  Atlantis(){
    for(int i=1;i<=n;++i){
        int k=i<<1;
        double y,z; //竖直方向坐标
        scanf("%lf %lf %lf %lf",&a[k-1].x,&y,&a[k].x,&z);
        raw[k-1]=a[k-1].y=a[k].y=y;//矩形左边界
        raw[k]=a[k-1].z=a[k].z=z; //矩形右边界
        a[k-1].k=1;
        a[k].k=-1;
    }
    n<<=1;
    //离散化
    sort(raw+1,raw+n+1);
    int m=unique(raw+1,raw+n+1)-(raw+1);
    for(int i=1;i<=m;++i) val[raw[i]]=i;
    sort(a+1,a+n+1);
    build(1,1,m-1);
    double ans=0;
    for(int i=1;i<n;++i){
        int y=val[a[i].y],z=val[a[i].z]-1;  // y:[val[a[i].y], val[a[i].y]+1]  z: [val[a[i].z]-1, val[a[i].z]]
        change(1,y,z,a[i].k); //y~z: [val[a[i].y], val[a[i].z]
        ans+=t[1].len*(a[i+1].x-a[i].x); //t[1].len 整个扫描线覆盖的长度
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);
}

int main() {
    while (cin >> n && n) Atlantis();
    return 0;
}

线段树延迟标记 (POJ3468)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 100010;

struct SegmentTree{
    int l,r;
    long long sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
} tree[SIZE*4];

int a[SIZE],n,m;

void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r) { sum(p)=a[l];return; }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}

void spread(int p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        add(p*2)+=add(p);
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}

void change(int p,int l,int r,int d){
    if(l<=l(p) && r>=r(p)){
        sum(p)+=(long long) d*(r(p)-l(p)+1);
        add(p)+=d;
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
}

long long ask(int p,int l,int r){
    if(l<=l(p) && r>=r(p)) return sum(p);
    spread(p);
    int mid=(l(p)+r(p))/2;
    long long val=0;
    if(l<=mid) val+=ask(p*2,l,r);
    if(r>mid) val+=ask(p*2+1,l,r);
    return val;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(1,l,r,d);
        }
        else printf("%lld\n",ask(1,l,r));
    }
    return 0;
}

最大连续子段和

RT,线段树单点修改,区间查询.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

#define SIZE 500000

int a[SIZE+1];
struct SegmentTree {
    int l,r;
    int dat,sum,lmax,rmax;
    SegmentTree() {
        l = r = sum = 0;
        lmax = rmax  =dat= -INF;
    }
} t[SIZE*4];

void build(int p,int l,int r) {
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

void change(int p,int x,int v) {
    if(t[p].l==t[p].r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=v;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
    else
        change(p*2+1,x,v);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

SegmentTree ask(int p,int l,int r) {
    if(l<=t[p].l&&r>=t[p].r) {
        return t[p];
    }
    SegmentTree res,a,b;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) {
        a=ask(p*2,l,r);
        res.sum+=a.sum;
    }
    if(r>mid) {
        b=ask(p*2+1,l,r);
        res.sum+=b.sum;
    }
    res.lmax=max(a.lmax,a.sum+b.lmax);
    res.rmax=max(b.rmax,b.sum+a.rmax);
    res.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
    return res;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--) {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1) {
            if(x>y)
                swap(x,y);
            printf("%d\n",ask(1,x,y).dat);
        } else {
            change(1,x,y);
        }
    }
    return 0;
}

HDU – 6214 Smallest Minimum Cut

HDU 6214

求最小割的最小割边数量.
每边以w*(m+1)+1为边权加入图中,最小割为maxflow/(m+1),最小割的边数为maxflow%(m+1).
精髓在于将已选边数加到了流量信息里.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};

struct Dinic{
  int n,m,s,t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int d[maxn];
  int cur[maxn];

  void init(int n){
    for(int i=0;i<=n;++i) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap){
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0)); //反向弧
    m=edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
  }

  bool BFS(){
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!Q.empty()){
      int x=Q.front();Q.pop();
      for(int i=0;i<G[x].size();++i){
        Edge &e=edges[G[x][i]];
        if(!vis[e.to]&&e.cap>e.flow){
          vis[e.to]=1;
          d[e.to]=d[x]+1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x,int a){
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[x];i<G[x].size();++i){
      Edge &e=edges[G[x][i]];
      if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
        e.flow+=f;
        edges[G[x][i]^1].flow-=f;
        flow+=f;
        a-=f;
        if(a==0)  break;
      }
    }
    return flow;
  }

  int Maxflow(int s,int t){
    this->s=s;
    this->t=t;
    int flow=0;
    while(BFS()){
      memset(cur,0,sizeof(cur));
      flow+=DFS(s,INF);
    }
    return flow;
  }

} flow;

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
   int T,n,m;
   scanf("%d",&T);
   while(T--){
     scanf("%d%d",&n,&m);
     int s,t;
     scanf("%d%d",&s,&t);
     flow.init(n);
     for(int i=0;i<m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        flow.AddEdge(u,v,w*(m+1)+1);
        flow.AddEdge(v,u,0);
     }
     printf("%d\n",flow.Maxflow(s,t)%(m+1));

   }
   return 0;
}