精华内容
下载资源
问答
  • 1120日小

    2019-11-21 12:02:44
    这几天主要是开始数学知识的学习,前面的质数,约数和矩阵乘法还是比较容易理解的,接下来的高斯消元和线性空间的知识就有点难搞了,之前的老师发的高斯消元模板还没有理解透,对于图论这部分还是要及时的复习。...

    这几天主要是开始数学知识的学习,前面的质数,约数和矩阵乘法还是比较容易理解的,接下来的高斯消元和线性空间的知识就有点难搞了,之前的老师发的高斯消元模板还没有理解透,对于图论这部分还是要及时的复习。另外接下来几周有好几次考试要好好的复习一下了,毕竟有的课没怎么听。。。

    今天晚上的题目还可以,e题比赛期间没有看懂不明白那个k是干嘛的,比赛结束问了一下是说k是个不确定的数,最小的时间使得都可以整除k,感觉贪心应该可以。c是大模拟的题目。赛后补上了。加油吧!!!

    展开全文
  • 84日小

    2017-08-04 21:27:17
    集训进行了好几天了,感觉剩下的题目理解起来都挺麻烦,要想好一会,看好几遍题目才能知道个大概,题目的要求也有点复杂。今天勉强写了3个题,最后一个正在调试,还不知道问题出在哪,怎么看都没问题,思路感觉也...

    集训进行了好几天了,感觉剩下的题目理解起来都挺麻烦,要想好一会,看好几遍题目才能知道个大概,题目的要求也有点复杂。今天勉强写了3个题,最后一个正在调试,还不知道问题出在哪,怎么看都没问题,思路感觉也正确,但连样例都没输出,有点心急,脑子有点混乱,放着明天再调试一下。

    其他两道题目也测试了好久,后来看了一下大神们的方法,那么简便,关键还是再技巧还有规律的寻找上,我在寻找规律上还很欠缺,有些地方还是总用暴力解决,有简便的处理方式但想不到,还需要多多锻炼。其次寻找规律很多地方用到数学思维,以后处理题目要多用一下数学思维去思考,找一些规律。

    3个代码调试了一整天,感觉好郁闷,脖子也有点疼,今晚真理好心情,明天继续努力。

    展开全文
  • 跟踪学习小

    2020-04-12 19:20:30
    复习现代控制这本书的时候,对于状态空间就几乎不理解,比如其中的预测方程和观测方程,为什么长这样,这些矩阵是怎么回事呢?等到实际学习Kalman滤波器的时候,对这些就有的初步的理解,比如卡尔曼是用观测方程来...

    断断续续学习了一个月,一边准备复试的科目一边做毕业设计,结果,复试的东西快忘光了,但还好毕设基本完成了。
    复习现代控制这本书的时候,对于状态空间就几乎不理解,比如其中的预测方程和观测方程,为什么长这样,这些矩阵是怎么回事呢?等到实际学习Kalman滤波器的时候,对这些就有的初步的理解,比如卡尔曼是用观测方程来修正预测方程,像是自动控制原理中的反馈,只不过是在时域下进行的。
    主要收获呢如下:

    • 学会了调试程序
    • 先画流程图后写程序

    对于三种算法,自己看了网上的一些程序,在看懂的情况下,并且进行了相应的修改

    Meanshift在这里插入图片描述

    Meanshift+Kalman

    在这里插入图片描述

    CAMshift

    在这里插入图片描述

    • 由于是跟踪前期,此时效果都还不错

    在这里插入图片描述

    • 此时就可以看出来Kalman的修正作用了。

    在这里插入图片描述

    • 这个时候最明显,没有反馈的meanshift已经跑偏了。

    在这里插入图片描述

    总的来说,meanshift比较相邻帧的相似度,而Kalman对其结果进行反馈优化,Camshift可以更新搜索窗口(由于是在H色调分量来处理,更准确),但由于Camshift的窗口变化的值是固定的,所以前期跟踪的好,后期由于距离近了就窗口变化就不够了。

    但也有一些提高的空间,比如跟踪的框可以有角度的调整,大小上更适应一些,有遮挡的情况下怎么处理,这些难度有点高,等以后有机会接触再进行学习。
    做毕设主要是通过matlab来进行的,以后可能还要学python,python的话以前接触过,有时间继续研究一下,近期的话试一试把跟踪小车调整一下,毕竟跟踪小车的应用背景比较好。

    展开全文
  • 后缀数组小

    2018-02-11 21:18:00
    刚开始因为板子不理解非常费力气,后来慢慢写着写着就会背了,背着背着也有一种理解了一点的错觉……可能并不是十分理解原理,只不过学会了怎么用而已。按自己原来的题解和日记整理一下。 入门时看的资料:五分钟...

           后缀数组是从去成都之前开始学的,但是当时只是写了遍板子既不会背也不会用。从成都回来之后依然不想做这个专题,到一月中旬才填坑。刚开始因为板子不理解非常费力气,后来慢慢写着写着就会背了,背着背着也有一种理解了一点的错觉……可能并不是十分理解原理,只不过学会了怎么用而已。按自己原来的题解和日记整理一下。

           入门时看的资料:五分钟并不能学会后缀数组用法总结罗穗骞的论文。板子是从Narcissus那学的,他的总结也十分详细,给了我很大帮助。

     

           1.板子与套路

     1 void rsort()
     2 {
     3     memset(tx,0,sizeof(int)*(m+1));
     4     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
     5     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
     6     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
     7 }
     8 void suffix()
     9 {
    10     int i,j,k,l,p;
    11     for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
    12     m=inf,rsort();
    13     for(l=1,p=1;p<n;m=p,l<<=1)
    14     {
    15         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
    16         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
    17         rsort(),swap(rk,ty),rk[sa[1]]=p=1;
    18         for(i=2;i<=n;i++)  rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
    19     }
    20     for(i=1,k=0;i<=n;h[rk[i++]]=k)
    21         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
    22 }

            $rsort$部分是一个基数排序。这是一个倍增的过程,先求出$sa$和$rk$,再根据性质快速求出$h$(即上列讲解中的$height$)。$sa[i]$的含义是排名为$i$的后缀开头的位置,$rk[i]$的含义是以$i$位置开头的后缀的排名,$h[i]$的含义是排名为$i$和$i-1$的后缀的$lcp$(最长公共前缀);$tx$和$ty$是用于实现基数排序的桶,$n$是字符串长度而$m$是字符集大小。最常见的问题是快速求两个后缀的$lcp$,答案是它们$rk$之间$h$的最小值。如果需要解决多串问题,常把多个串拼成一个并用分隔符隔断。比较裸的题有BZOJ1717BZOJ4698

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<algorithm>
     5 using namespace std;
     6 const int sj=20010;
     7 int n,k,le,ri,mid,mx,pos,a[sj],rk[sj],sa[sj],m,cnt,tx[sj],ty[sj],h[sj];
     8 struct ls
     9 {
    10     int num,vl;
    11 }s[sj];
    12 int comp(const ls&x,const ls&y)
    13 {
    14     return x.vl<y.vl;
    15 }
    16 bool check(int x)
    17 {
    18     for(int i=1;i<=n;i=pos+1)
    19     {
    20         pos=i;
    21         while(h[pos]>=x)  pos++;
    22         if(pos-i>=k-1)  return 1;
    23         if(pos!=i)  pos--;
    24     }
    25     return 0;
    26 }
    27 void rsort()
    28 {
    29     memset(tx,0,sizeof(int)*(m+1));
    30     for(int i=1;i<=n;++i)  tx[rk[ty[i]]]++;
    31     for(int i=1;i<=m;++i)  tx[i]+=tx[i-1];
    32     for(int i=n;i>=1;--i)  sa[tx[rk[ty[i]]]--]=ty[i];
    33 }
    34 void suffix()
    35 {
    36     int i,j,k,p,l;
    37     for(int i=1;i<=n;++i)  rk[i]=a[i],ty[i]=i;
    38     m=sj-10;rsort();
    39     for(p=1,l=1;p<n;m=p,l<<=1)
    40     {
    41         for(p=0,i=n-l+1;i<=n;++i)  ty[++p]=i;
    42         for(i=1;i<=n;++i)  if(sa[i]>l)  ty[++p]=sa[i]-l;
    43         rsort(),swap(rk,ty),rk[sa[1]]=p=1;
    44         for(i=2;i<=n;++i)  rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
    45     }
    46     for(i=1,k=0;i<=n;h[rk[i++]]=k)  
    47         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
    48 }
    49 int main()
    50 {
    51     scanf("%d%d",&n,&k);
    52     for(int i=1;i<=n;i++)  scanf("%d",&a[i]),s[i].vl=a[i],s[i].num=i;
    53     sort(s+1,s+n+1,comp);
    54     a[s[1].num]=1,mx=1;
    55     for(int i=2;i<=n;i++)
    56     {
    57         if(s[i-1].vl!=s[i].vl)  mx++;
    58         a[s[i].num]=mx;
    59     }
    60     le=1,ri=n;
    61     suffix();
    62     while(le<ri)
    63     {
    64         mid=(le+ri+1)>>1;
    65         if(check(mid))  le=mid;
    66         else  ri=mid-1;
    67     }
    68     printf("%d",le);
    69     return 0;
    70 }
    1717
     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 using namespace std;
     5 const int sj=1000010;
     6 const int bd=2000;
     7 int n,m,h[sj],tx[sj],ty[sj],rk[sj],sa[sj],a[sj];
     8 int le,ri,mid,num,bl[sj],pos,la,nt,cnt;
     9 bool r[sj];
    10 void rsort()
    11 {
    12     memset(tx,0,sizeof(int)*(m+1));
    13     for(int i=1;i<=cnt;++i)  tx[rk[ty[i]]]++;
    14     for(int i=1;i<=m;++i)    tx[i]+=tx[i-1];
    15     for(int i=cnt;i>=1;--i)  sa[tx[rk[ty[i]]]--]=ty[i];
    16 }
    17 void getsa()
    18 {
    19     int i,j,p,l,k;
    20     for(i=1;i<=cnt;++i)  rk[i]=a[i],ty[i]=i;
    21     m=4000,rsort();
    22     for(p=1,l=1;p<cnt;m=p,l<<=1)
    23     {
    24         for(p=0,i=cnt-l+1;i<=cnt;++i)  ty[++p]=i;
    25         for(i=0;i<=cnt;++i)  if(sa[i]>l)  ty[++p]=sa[i]-l;
    26         rsort(),swap(rk,ty),rk[sa[1]]=p=1;
    27         for(i=2;i<=cnt;++i)  
    28             rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
    29     }
    30     for(i=1,k=0;i<=cnt;h[rk[i++]]=k)
    31         for(k=k?k-1:0,j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
    32 }
    33 bool check(int x)
    34 {
    35     for(int i=1;i<=cnt;i=pos+1)
    36     {
    37         pos=i,num=0;
    38         while(h[pos]>=x) 
    39         {
    40            if(bl[sa[pos]]&&!r[bl[sa[pos]]])  num++;
    41            r[bl[sa[pos]]]=1;
    42            pos++;
    43         }
    44         if(h[i]>=x)  
    45             if(bl[sa[i-1]]&&!r[bl[sa[i-1]]])  num++;
    46         for(int j=i;j<pos;++j)  r[bl[sa[j]]]=0;
    47         if(num==n)  return 1;
    48     }
    49     return 0;
    50 }
    51 int main()
    52 {
    53     scanf("%d",&n);
    54     ri=0x7fffffff;
    55     for(int i=1;i<=n;++i)
    56     {
    57         scanf("%d",&m);
    58         if(m<ri)  ri=m;
    59         for(int j=1;j<=m;++j)
    60         {
    61             scanf("%d",&nt);
    62             a[++cnt]=nt-la+bd,la=nt;
    63             bl[cnt]=i;
    64         }
    65         ++cnt,la=0;
    66     }
    67     ri--;
    68     getsa();
    69     while(le<ri)
    70     {
    71         mid=(le+ri+1)>>1;
    72         if(check(mid))  le=mid;
    73         else  ri=mid-1;
    74     }
    75     if(n==1)  printf("0");
    76     else      printf("%d",le+1);
    77     return 0;
    78 }
    4698

     

           2.BZOJ3238 差异

          观察题目中给的式子,每个后缀的长度都会被加$n-1$次,后缀的长度又是一个公差为$1$的等差数列,可以直接用求和公式$n*(n+1)/2*(n-1)$完成统计。剩下的就是后缀之间两两$lcp$的长度和,可以转化为每个长度*$lcp$等于该长度的后缀数。$lcp$是$rk$区间$h$的最小值,可以用单调栈求出每个$h$控制的范围,就变成暑假集训常做的那种NOIP模拟题了。

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<stack>
     5 #define ll long long
     6 using namespace std;
     7 const int sj=500010;
     8 stack<int> q;
     9 int tx[sj],ty[sj],rk[sj],sa[sj],m,h[sj],a[sj],lm[sj],rm[sj];
    10 char s[sj];
    11 ll ans,n;
    12 void rsort()
    13 {
    14     memset(tx,0,sizeof(int)*(m+1));
    15     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
    16     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
    17     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
    18 }
    19 void suffix()
    20 {
    21     int i,j,k,l,p;
    22     for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
    23     m=26;rsort();
    24     for(l=1,p=1;p<n;m=p,l<<=1)
    25     {
    26         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
    27         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
    28         rsort(),swap(ty,rk),rk[sa[1]]=p=1;
    29         for(i=2;i<=n;i++)
    30             rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
    31     }
    32     for(i=1,k=0;i<=n;h[rk[i++]]=k)
    33         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
    34 }
    35 int main()
    36 {
    37     scanf("%s",s);
    38     n=strlen(s);
    39     ans=n*(n+1)/2*(n-1);
    40     for(int i=1;i<=n;i++)  a[i]=s[i-1]-'a'+1;
    41     suffix();
    42     q.push(0),h[0]=-1;
    43     for(int i=1;i<=n;i++)
    44     {
    45         while(h[q.top()]>=h[i])  q.pop();
    46         lm[i]=q.top()+1;
    47         q.push(i);
    48     }
    49     while(!q.empty())  q.pop();
    50     q.push(n+1),h[n+1]=-1;
    51     for(int i=n;i>=1;i--)
    52     {
    53         while(h[q.top()]>h[i])  q.pop();
    54         rm[i]=q.top()-1;
    55         q.push(i);
    56     }
    57     for(ll i=1;i<=n;i++)  
    58         ans-=(i-lm[i]+1)*(rm[i]-i+1)*2*h[i];
    59     printf("%lld",ans);
    60     return 0;
    61 }
    3238

     

     

           3.BZOJ4556 字符串

            求一个字符串内一个子串和另一个子串的子串们的$lcp$。$lcp$的长度受到h和两个子串长度的双重限制,于是考虑二分答案来确定可行区间的端点。例如我们要求$[a,b]$的子串和$[c,d]$的$lcp$,二分$lcp$长度为$mid$,那么只能是开头在$[a,b-mid+1]$的后缀和$[c,d]$的$lcp$。维护一个下标为字符串中对应位置、权值为$rk$的线段树,每次$check$利用$h$数组二分两次求出$rk$在$[l,r]$的区间满足要求,再在主席树上查询$[a,b-mid+1]$中是否有rk落在$[l,r]$中。总复杂度$mlog^2n$。

      1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 using namespace std;
      5 const int sj=100010;
      6 int rk[sj],tx[sj],ty[sj],sa[sj],h[sj],a[sj],p[sj][20];
      7 int rt[sj],n,q,a1,a2,a3,a4,l,r,mid,lm,rm,cnt,m;
      8 char s[sj];
      9 struct tree
     10 {
     11     int sum,lc,rc;
     12 }t[sj*50];
     13 inline int read()
     14 {
     15     int jg=0,jk=getchar()-'0';
     16     while(jk<0||jk>9)    jk=getchar()-'0';
     17     while(jk>=0&&jk<=9)  jg*=10,jg+=jk,jk=getchar()-'0';
     18     return jg;
     19 }
     20 inline int bj(int x,int y)
     21 {
     22     return x<y?x:y;
     23 }
     24 void pre()
     25 {
     26     for(int i=1;i<=n;i++)  p[i][0]=h[i];
     27     for(int j=1;(1<<j)<=n;j++)
     28         for(int i=1;i+(1<<j)-1<=n;i++)
     29             p[i][j]=bj(p[i][j-1],p[i+(1<<(j-1))][j-1]);
     30 }
     31 void rsort()
     32 {
     33     memset(tx,0,sizeof(int)*(m+1));
     34     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
     35     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
     36     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
     37 }
     38 void suffix()
     39 {
     40     int i,j,k,p,l;
     41     for(int i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
     42     m=26;rsort(); 
     43     for(p=1,l=1;p<n;m=p,l<<=1)
     44     {
     45         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
     46         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
     47         rsort(),swap(rk,ty),rk[sa[1]]=p=1;
     48         for(i=2;i<=n;i++)  rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
     49     } 
     50     for(i=1,k=0;i<=n;h[rk[i++]]=k)
     51         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
     52 }
     53 void insert(int nt,int la,int z,int y,int vl)
     54 {
     55     t[nt].sum=t[la].sum+1,t[nt].lc=t[la].lc,t[nt].rc=t[la].rc;
     56     if(z==y)  return;
     57     int mi=z+y>>1;
     58     if(vl<=mi)  t[nt].lc=++cnt,insert(t[nt].lc,t[la].lc,z,mi,vl);
     59     else        t[nt].rc=++cnt,insert(t[nt].rc,t[la].rc,mi+1,y,vl);   
     60 }
     61 bool query(int nt,int la,int z,int y,int le,int ri)
     62 {
     63     if(t[la].sum-t[nt].sum==0)  return 0;
     64     if(z==le&&y==ri)            return 1;
     65     int mi=z+y>>1;
     66     if(ri<=mi)  return query(t[nt].lc,t[la].lc,z,mi,le,ri);
     67     if(le>mi)   return query(t[nt].rc,t[la].rc,mi+1,y,le,ri);
     68     bool p1=query(t[nt].lc,t[la].lc,z,mi,le,mi);
     69     bool p2=query(t[nt].rc,t[la].rc,mi+1,y,mi+1,ri);
     70     return (p1|p2);
     71 }
     72 int main()
     73 {
     74     n=read(),q=read();
     75     scanf("%s",s);
     76     for(int i=1;i<=n;i++)  a[i]=s[i-1]-'a'+1;
     77     suffix();pre();
     78     for(int i=1;i<=n;i++)
     79     {
     80         rt[i]=++cnt;
     81         insert(rt[i],rt[i-1],1,n,rk[i]);
     82     }
     83     for(int i=1;i<=q;i++)
     84     {
     85         a1=read(),a2=read(),a3=read(),a4=read();   
     86         l=0,r=bj(a4-a3+1,a2-a1+1);
     87         while(l<r)
     88         {
     89             mid=(l+r+1)>>1,lm=rm=rk[a3];
     90             for(int j=16;j>=0;j--) 
     91                 if(lm>(1<<j)&&p[lm-(1<<j)+1][j]>=mid)
     92                     lm-=(1<<j);
     93             for(int j=16;j>=0;j--)
     94                 if(rm+(1<<j)<=n&&p[rm+1][j]>=mid)
     95                     rm+=(1<<j);
     96             if(query(rt[a1-1],rt[a2-mid+1],1,n,lm,rm))  l=mid;
     97             else  r=mid-1;
     98         }
     99         printf("%d\n",l);
    100     }
    101     return 0;
    102 }
    4556

     

           4.BZOJ2754 喵星球上的点名

            暴力水过去的,并不知道正解应该怎么写。把所有姓名和询问都接成一个串,对每一个询问RMQ求出可行区间,然后就暴力扫可行区间统计答案。实际上复杂度非常没保障。 COGS上数据是学长强化过的,貌似只有cooook过了。

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 using namespace std;
     5 inline int read()
     6 {
     7     int jg=0,jk=getchar()-'0';
     8     while(jk<0||jk>9)    jk=getchar()-'0';
     9     while(jk>=0&&jk<=9)  jg*=10,jg+=jk,jk=getchar()-'0';
    10     return jg;
    11 }
    12 const int sj=300010;
    13 const int inf=10001;
    14 int h[sj],rk[sj],sa[sj],tx[sj],ty[sj],cnt,q,m,a[sj],n,len,a1,bl[sj],p[sj][20];
    15 int st[50010],ln[50010],num[20010],ans,lm,rm;
    16 bool r[20010];
    17 inline int bj(int x,int y)
    18 {
    19     return x<y?x:y;
    20 }
    21 void pre()
    22 {
    23     for(int i=1;i<=n;i++)  p[i][0]=h[i];
    24     for(int j=1;(1<<j)<=n;j++)
    25         for(int i=1;i+(1<<j)-1<=n;i++)
    26             p[i][j]=bj(p[i][j-1],p[i+(1<<(j-1))][j-1]);
    27 }
    28 void rsort()
    29 {
    30     memset(tx,0,sizeof(int)*(m+1));
    31     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
    32     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
    33     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
    34 }
    35 void suffix()
    36 {
    37     int i,j,k,l,p;
    38     for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
    39     m=inf,rsort();
    40     for(l=1,p=1;p<n;m=p,l<<=1)
    41     {
    42         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
    43         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
    44         rsort(),swap(rk,ty),rk[sa[1]]=p=1;
    45         for(i=2;i<=n;i++)  rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
    46     }
    47     for(i=1,k=0;i<=n;h[rk[i++]]=k)
    48         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
    49 }
    50 int main()
    51 {
    52     cnt=read(),q=read();
    53     for(int i=1;i<=cnt;i++)
    54     {
    55         len=read();
    56         for(int j=1;j<=len;j++)
    57             a1=read(),a[++n]=a1,bl[n]=i;
    58         a[++n]=inf;
    59         len=read();
    60         for(int j=1;j<=len;j++)
    61             a1=read(),a[++n]=a1,bl[n]=i;
    62         a[++n]=inf;
    63     }
    64     for(int i=1;i<=q;i++)
    65     {
    66         ln[i]=read(),st[i]=n+1;
    67         for(int j=1;j<=ln[i];j++)
    68             a1=read(),a[++n]=a1;
    69         a[++n]=inf; 
    70     }
    71     suffix();pre();
    72     for(int i=1;i<=q;i++)
    73     {
    74         lm=rm=rk[st[i]],ans=0;
    75         for(int j=19;j>=0;j--)
    76             if(lm>(1<<j)&&p[lm-(1<<j)+1][j]>=ln[i])
    77                 lm-=(1<<j);
    78         for(int j=19;j>=0;j--)
    79             if(rm+(1<<j)<=n&&p[rm+1][j]>=ln[i])
    80                 rm+=(1<<j);
    81         for(int j=lm;j<=rm;j++)
    82             if(bl[sa[j]]&&!r[bl[sa[j]]])
    83                 r[bl[sa[j]]]=1,num[bl[sa[j]]]++,ans++;
    84         for(int j=lm;j<=rm;j++)
    85             if(bl[sa[j]])
    86                 r[bl[sa[j]]]=0;
    87         printf("%d\n",ans);
    88     }
    89     for(int i=1;i<cnt;i++)
    90         printf("%d ",num[i]);
    91     printf("%d",num[cnt]);
    92     return 0;
    93 }
    2754

     

           5.BZOJ3230 相似子串

             最重要的还是按照题目里的那个奇怪定义和排序方式求出询问字符串的开始和结尾位置……剩下的倒都是SA+RMQ的套路。开头与结尾不可得兼,取开头而求结尾者也。以下是当初写的注释。

    如何根据题意求结尾位置:
    题意中越短的子串字典序越靠前,同一个位置开头的子串字典序一定相连
    求结尾位置本质上也就是求它在i位置为开头的子串中是第几个
    a1-sum[i-1]     是以i开头的子串中排第几
    +h[i]                是去掉重复,以i开头的子串原本就没有算这h[i]个
    sa[i]                是起始的基准位置
    -1                    手调拍出来的QAQ

      1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 #define ll long long
      5 using namespace std;
      6 const int sj=100010;
      7 int tx[sj],ty[sj],sa[sj],rk[sj],a[sj],n,q,p[2][sj][25],rr[sj],m,h[sj];
      8 int l,r,mid,pos1,pos2,pos3,pos4,he[sj],ss[sj];
      9 ll a1,a2,sum[sj],ans,len1,len2;
     10 char s[sj];
     11 void rsort()
     12 {
     13     memset(tx,0,sizeof(int)*(m+1));
     14     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
     15     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
     16     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
     17 }
     18 inline ll read()
     19 {
     20     ll jg=0,jk=getchar()-'0';
     21     while(jk<0||jk>9)    jk=getchar()-'0';
     22     while(jk>=0&&jk<=9)  jg*=10,jg+=jk,jk=getchar()-'0';
     23     return jg;
     24 }
     25 inline int bj(int x,int y)
     26 {
     27     return x<y?x:y;
     28 }
     29 void pre(int op)
     30 {
     31     for(int i=1;i<=n;i++)  p[op][i][0]=h[i];
     32     for(int j=1;(1<<j)<=n;j++)
     33         for(int i=1;i+(1<<j)-1<=n;i++)
     34             p[op][i][j]=bj(p[op][i][j-1],p[op][i+(1<<(j-1))][j-1]);
     35 }
     36 int RMQ(int op,int l,int r)
     37 {
     38     if(l==r) return n;
     39     if(l>r)  swap(l,r);
     40     l++;int k;
     41     for(k=0;(1<<(k+1))<=r-l+1;k++);
     42     return bj(p[op][l][k],p[op][r-(1<<k)+1][k]);
     43 }
     44 void suffix()
     45 {
     46     int i,j,k,l,p;
     47     for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
     48     m=26;rsort();
     49     if(n==1)  rk[sa[1]]=1;
     50     for(p=1,l=1;p<n;m=p,l<<=1)
     51     {
     52         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
     53         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
     54         rsort(),swap(ty,rk),rk[sa[1]]=p=1;
     55         for(i=2;i<=n;i++) 
     56             rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
     57     }
     58     for(i=1,k=0;i<=n;h[rk[i++]]=k)
     59         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
     60 }
     61 void work()
     62 {
     63     pre(0);
     64     memcpy(rr,rk,sizeof(rk));
     65     memcpy(he,h,sizeof(he));
     66     memcpy(ss,sa,sizeof(ss));
     67     for(int i=1;i<=n;i++)  a[i]=s[n-i]-'a'+1;
     68     for(int i=1;i<=n;i++)  sum[i]=sum[i-1]+n-sa[i]+1-h[i];
     69 }
     70 int getpos(ll x)
     71 {
     72     l=1,r=n;
     73     while(l<r)
     74     {
     75         mid=l+r>>1;
     76         if(sum[mid]<x)  l=mid+1;
     77         else            r=mid;
     78     }
     79     return r;
     80 }
     81 int main()
     82 {
     83     n=read(),q=read();
     84     scanf("%s",s);
     85     for(int i=1;i<=n;i++)  a[i]=s[i-1]-'a'+1;
     86     a[n+1]=-1;
     87     suffix(),work();
     88     suffix(),pre(1);
     89     for(int i=1;i<=(n-1)/2+1;i++)  swap(rk[i],rk[n-i+1]);
     90     for(int i=1;i<=q;i++)
     91     {
     92         a1=read(),a2=read();
     93         if(a1>sum[n]||a2>sum[n])  printf("-1\n");
     94         else
     95         {
     96             pos1=getpos(a1),pos2=getpos(a2);
     97             pos3=ss[pos1]+a1+he[pos1]-sum[pos1-1]-1,pos1=ss[pos1];
     98             pos4=ss[pos2]+a2+he[pos2]-sum[pos2-1]-1,pos2=ss[pos2];
     99             len2=bj(pos3-pos1+1,pos4-pos2+1);
    100             len1=bj(RMQ(1,rk[pos3],rk[pos4]),len2);
    101             ans=len1*len1;
    102             len1=bj(RMQ(0,rr[pos1],rr[pos2]),len2);
    103             ans+=len1*len1;
    104             printf("%lld\n",ans);
    105         }
    106     }
    107     return 0;
    108 }
    similar

     

     

           6.BZOJ4199 品酒大会

            充分利用height数组的性质。在n相似的时候没有任何两杯酒满足要求,而0相似的时候任意两杯酒都满足要求;满足要求的总是$rk$在一个区间里的所有酒,两问的答案都可以通过区间计算得到。如果我们从大到小处理,相当于一个区间合并、更新答案的过程。注意有负权存在。刚开始犯蠢写了个主席树,T了之后才发现这完全是并查集就能解决的问题……

      1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 #include<algorithm>
      5 #define ll long long
      6 using namespace std;
      7 const int sj=300010;
      8 int n,m,a[sj],tx[sj],ty[sj],rk[sj],sa[sj],h[sj],a1,a2,fa[sj];
      9 ll vl[sj],ans1[sj],ans2[sj],sum,ans,tp1,tp2,tp,tp3,tp4,qwq,mx[sj],mi[sj],num[sj];
     10 char s[sj];
     11 struct ls
     12 {
     13     int num,val;
     14 }ss[sj];
     15 struct tree
     16 {
     17     int lc,rc,sum;
     18 }t[sj*30];
     19 int comp(const ls&x,const ls&y)
     20 {
     21     return x.val<y.val;
     22 }
     23 void rsort()
     24 {
     25     memset(tx,0,sizeof(int)*(m+1));
     26     for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
     27     for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
     28     for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
     29 }
     30 void suffix()
     31 {
     32     int i,j,k,l,p;
     33     for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
     34     m=26;rsort();
     35     for(p=1,l=1;p<n;m=p,l<<=1)
     36     {
     37         for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
     38         for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
     39         rsort(),swap(ty,rk),rk[sa[1]]=p=1;
     40         for(i=2;i<=n;i++) 
     41             rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
     42     }
     43     for(i=1,k=0;i<=n;h[rk[i++]]=k)
     44         for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
     45 } 
     46 void init()
     47 {
     48     scanf("%d%s",&n,s);
     49     memset(fa,-1,sizeof(fa));
     50     tp1=-1ll<<62,tp2=-1ll<<62,tp3=1ll<<62,tp4=1ll<<62;
     51     for(int i=1;i<=n;i++)  
     52     {    
     53         scanf("%lld",&vl[i]);
     54         a[i]=s[i-1]-'a'+1;
     55         if(vl[i]>=tp1)  tp2=tp1,tp1=vl[i];  
     56         else if(vl[i]>tp2)  tp2=vl[i];
     57         if(vl[i]<=tp3)  tp4=tp3,tp3=vl[i];
     58         else if(vl[i]<tp4)  tp4=vl[i];  
     59     }
     60 }
     61 int find(int x)
     62 {
     63     if(fa[x]==-1)  return x;
     64     return fa[x]=find(fa[x]);
     65 }
     66 inline ll maxx(ll x,ll y)
     67 {
     68     return x>y?x:y;
     69 }
     70 inline ll minn(ll x,ll y)
     71 {
     72     return x<y?x:y;
     73 }
     74 int main()
     75 {
     76     init();
     77     suffix();
     78     for(int i=1;i<=n;i++)
     79     {
     80         ss[i].num=i,ss[i].val=h[i];
     81         num[i]=1,mx[i]=mi[i]=vl[sa[i]];
     82     }
     83     sort(ss+1,ss+n+1,comp);
     84     ans=-1ll<<62;
     85     for(int i=n;i>=1;i--)
     86     {
     87         if(ss[i].val!=ss[i+1].val)  
     88             ans1[ss[i+1].val]=sum/2,ans2[ss[i+1].val]=ans;
     89         a1=ss[i].num,a2=a1-1;
     90         if(!h[a1])  break;
     91         a1=find(a1),a2=find(a2);
     92         sum-=(ll)num[a1]*(num[a1]-1);
     93         sum-=(ll)num[a2]*(num[a2]-1);
     94         tp=mx[a1]*mx[a2],qwq=mi[a1]*mi[a2];
     95         if(tp>ans)   ans=tp;
     96         if(qwq>ans)  ans=qwq;
     97         if(num[a1]<num[a2])  swap(a1,a2);
     98         mx[a1]=maxx(mx[a1],mx[a2]);
     99         mi[a1]=minn(mi[a1],mi[a2]);
    100         num[a1]+=num[a2];
    101         fa[a2]=a1;
    102         sum+=(ll)num[a1]*(num[a1]-1);
    103     }
    104     ans1[0]=(ll)n*(n-1)/2,ans2[0]=maxx(tp1*tp2,tp3*tp4);
    105     for(int i=0;i<n;i++)
    106         printf("%lld %lld\n",ans1[i],ans2[i]);
    107     return 0;
    108 }
    4199

     

    转载于:https://www.cnblogs.com/moyiii-/p/8443099.html

    展开全文
  • 面向对象学习小

    2020-08-07 11:37:51
    而简单的系统软件,像之前那个销售管理系统,我可以做到,但老实说,我并没有感受到面向对象的魅力在哪里,我并没有怎么分离对象,也没有经历需求的改变,一切都在静态条件下完成的,我花了半天时间理解题意,半天...
  • (多图预警)

    2016-10-12 21:02:55
    怎么说呢。今年停课也是顶着很大的压力,毕竟高三了,到了最紧张的时候,一个多不学文化课,肯定一轮复习会爆炸。。。但是我并不后悔我做的这个决定。 记得黄学长博客有一句话说的很有道理:自己选的路,跪着也要...
  • '代码中长单词怎么记住的? '比如copyfromrecordset可以拆开记忆,copy、from、recordset 这三个单词意思知道吧,就是“复制、从、记录集” '----------------- 'Sql = "select sum(分数) from [sheet1$]"这里加...
  • 这一部分怎么理解呢?我觉得应该找个主线把它串起来。 估计很多人都思考我们写的程序是怎么驱动电脑运行的,今天我们就以Java为例来说道说道。 打开IDEA,写了.java程序,一运行,生成.class文件,然后再运行这个...
  • 海思 芯片开发 面经

    2020-09-18 15:33:50
    917日连续一二面,18日主管面 面试结束可以秒出结果,目前已进池子 技术一面 40分钟,视频 实习情况 成绩情况,笔试情况 有没有发过论文 项目介绍,相关问题 数字电路功耗的组成与影响因素 如何解决EM 解释PN...
  • 出版日期:2011 年1 开本:16开 页码:706 版次:2-1 编辑推荐  久负盛名的Oracle经典  世界顶级专家Thomas Kyte力作  Ask Tom!解决你所有的Oracle疑难杂症 内容简介  本书是一本关于oracle database 9i、...
  • 7.11 小:多方位理解Java方法 191 7.12 习题 192 第8章 Java中的包(Package)命名习惯和注释 193 教学视频:43分钟 8.1 Java中的包(Package) 193 8.1.1 Java中的包 193 8.1.2 在Eclipse中使用包 194 ...
  • 7.11 小:多方位理解Java方法 191 7.12 习题 192 第8章 Java中的包(Package)命名习惯和注释 193 教学视频:43分钟 8.1 Java中的包(Package) 193 8.1.1 Java中的包 193 8.1.2 在Eclipse中使用包 194 ...
  • 7.11 小:多方位理解Java方法 191 7.12 习题 192 第8章 Java中的包(Package)命名习惯和注释 193 教学视频:43分钟 8.1 Java中的包(Package) 193 8.1.1 Java中的包 193 8.1.2 在Eclipse中使用包 194 ...
  • 出版日期:2006 年10 开本:16开 页码:737 版次:1-1 内容简介  本书是一本关于Oracle 9i & 10g数据库体系结构的权威图书,涵盖了所有最重要的Oracle体系结构特性,包括文件、内存结构和进程,锁和闩,事务、...
  • 发行时间: 2011年0601日 语言: 简体中文 简介: 抵御恶意软件和Rootkit不断掀起的攻击浪潮!《黑客大曝光:恶意软件和Rootkit安全》用现实世界的案例研究和实例揭示了当前的黑客们是如何使用很容易得到的工具...
  • 本书注重对实际动手能力的指导,在遵循技术研发知识体系的严密性同时,在容易产生错误、不易理解的环节配以了翔实的开发情景截图,并将重要的知识点和开发技巧以“小实验”、“小提醒”、“小知识”、“注意”等的...
  • 出版日期:2011 年4 开本:16开 页码:612 版次:1-1 内容简介  最大程度地利用oracle恢复管理器的功能  《oracle database 11g rman备份与恢复》提供了在硬件、软件、操作发生故障时保护数据库的详细信息。...
  • 4.2.5 进一步理解 106 4.3 RAC下的并发控制 109 4.3.1 DLM中资源和锁 110 4.3.2 Non-Cache Fusion资源 111 4.3.3 Cache Fusion资源 112 4.3.4 GRD(Global Resource Directory) 114 4.3.5 PCM Lock 114...
  • 什么是控制

    2014-09-22 21:42:48
    这就是我们前三章所学习的内容:“结构”、“流程”、“系统”,你怎么理解这三者之间的关系?(提问) 总结:系统是普遍存在的,大到天体星系,小到基本粒子无不是一个系统。不同的系统有不同的功能,而系统有何种...
  • 应届毕业生工作7个 教你在服务器搭建个人面试项目 记一次害敖丙差点丢工作的线上P0事故 阿里五年老员工有什么话想对大家说? 从毕业到技术专家我做了啥 50天全网2W粉,感谢坚持! MacBook Pro 入手一年了,...
  • 望大家理解! 请翻译以下全部内容 <pre><code> 标题(翻译主要意思即可,不要超过 100 个字符) 老家的梨树了非常多果子,决定上棚用纸袋包起来防止鸟儿来偷吃 简介 大家如果之前...
  • 【最近项目小】使用 Vue 实现一个简单的鼠标拖拽滚动效果插件 我开源了第一个基于Vue的组织架构树组件 五一看别人去玩,而我守在这里! 福利 100本最棒前端开发图书 求职招聘季奉上多套精美收费简历模板--总有...
  • 软件工程教程

    热门讨论 2012-07-06 23:10:29
    用例只描述参与者和系统在交互过程中做些什么,并不描述怎么做。 用例图 关联关系 用例图 泛化关系 用例图 泛化关系 用例图 用例图 用例图 用例用于什么情况? 不知道什么情况不用用例 如果没有用到用例,...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    C#--微软.NET的第一语言 本书着重介绍语言本身,比较少涉及应用,不错的入门书,从头讲起,不怕不明白。 <<page 1>> page begin==================== 目 ... 1.4 小 .11 ... 2.4 小 .19 ... 2000 年 6 ...
  • C#微软培训资料

    2014-01-22 14:10:17
    <<page 1>> page begin==================== 目 目目 目 录 录录 ... 2000 年 6 22 日 不论对 Microsoft 还是对整个 IT 业界都将成为值得纪念的一天 这一天 微软公司正式推出了其下一代...
  • 望大家理解! 请翻译以下全部内容 <pre><code> 标题(翻译主要意思即可,不要超过 100 个字符) 把老家梨树的果子包起来防止鸟儿来偷吃!偶遇停电怎么办?居然还能继续剪视频...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

月结怎么理解