[SPOJ 744]连续最长1..M排列

【题目大意】给定一个1..N的序列，然后让你求一段连续的子串包含1..M中所有的数字，且不重复。最后输出max(M)

【算法分析】

定义S[I]=前I个数的和。

NEXT[I]为下一个和当前这个数相同的数的位置

LAST[I]为前一个和当前这个数相同的数的位置

如果输满足条件的一个连续串的话，必然是没有重复的数字的，并且和为(M+1)*M/2。（等差数列求和）

已知结果串必然包含1，所以我们以1为标志，进行左右扫描。

情况1

假设这个1所能达到的最大M在左边，i为这个1的位置，则j向左扫描

q=max(a[j],q)

p=min(next[j],q)

显然p不能<=i，另外j+q-1

情况2和情况1对称，不再赘述。

【其它】1A

3251945 2010-02-09 16:03:34 cwj Longest Permutation accepted 0.96 4.7M

C++

4.3.2

【CODE】

#include #include #define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
const int N=111111;
int n,a[N],last[N],next[N],lpos[N],s[N];

void init(){
    s[0]=0;
    for (int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
        next[lpos[a[i]]]=i;
        last[i]=lpos[a[i]];
        lpos[a[i]]=i;
    }   
    for (int i=1;i<=n;i++)
      if (lpos[i]!=0) next[lpos[i]]=n+1;
}   

void work(){
    int ans=0;
    for (int i=1;i<=n;i++)
      if (a[i]==1){
          ans=max(1,ans);
          int q=1,p=next[i];
          for (int j=i;j>last[i];j–){
              q=max(a[j],q);
              p=min(next[j],p);
              if (p<=i) break;
              if (j+q-1<=n && j+q-1

                ans=max(ans,q);
          }   
          q=1,p=last[i];
          for (int j=i;j              q=max(a[j],q);
              p=max(last[j],p);
              if (p>=i) break;
              if (j-q+1>=1 && j-q+1>p && s[j]-s[j-q]==q*(q+1)/2)
                ans=max(ans,q);
          }   
      }
    printf("%dn",ans);   
}   

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    init();
    work();
}   

[SGU 177]利用并差集处理矩形覆盖问题**

【题目大意】给定一个N*N的矩阵和M次染色，问最后是白色的格子还有多少个？

【算法分析】这题一看是线段树or矩形切割，但是仔细一想，可以发现一种新的算法，这中间利用了并差集。定义next[i,j]表示如果要染i，j这一个格子的话，应当去染哪一个格子。考虑我们写矩形切割的“浮冰法”，从后面开始进行insert，这样的话，后insert的必须避开先insert得。所以可以利用这个next进行跳跃。我这个next只针对当前行，就是next[i,j]的跳跃位置是对于第i行而言的。

初始时next[i,j]=j，表示要染这一格，那么就应该染这一格，比较拗口

然后如果对这一格被染色的话，那么next[i,j]=j+1，这样下一次就会越过我跳到下一格了，然后用并差集进行路径压缩，这样就能在平摊O(1)的复杂度调到下一个能染得格了！

这个算法中，对每个格子最多碰一次，所以染色的复杂度为O(N^2)，但是由于对于每一次染色，都必须枚举行，所以总复杂度是O(N^2+NM)。

【其它】1A,时限7S

997757 09.02.10 16:53 edward 177 .CPP Accepted 796 ms 9739 kb

【CODE】

#include #include const int N=1111;
const int M=5555;
int n,m,next[N][N],x1[M],x2[M],y1[M],y2[M],color[N][N],dc[M];

void swap(int &x,int &y){
    int tmp=x; x=y; y=tmp;
}   

void init(){
    for (int i=0;i<=n+1;i++)
      for (int j=0;j<=n+1;j++)
        next[i][j]=j;
}   

int findnext(int i,int j){
    if (next[i][j]==j) return j;
    next[i][j]=findnext(i,next[i][j]);
    return next[i][j];
}   

void work(){
    memset(color,200,sizeof(200));
    for (int tmp=m;tmp>=0;tmp–)
      for (int i=x1[tmp];i<=x2[tmp];i++){
          for (int j=y1[tmp];j<=y2[tmp];)
            if (next[i][j]==j){
                color[i][j]=dc[tmp];
                next[i][j]=j+1;
                j++;
            }
            else j=findnext(i,j);
      }
}   

void print(){
    int ans=0;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (color[i][j]==0) ans++;
    printf("%dn",ans);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    x1[0]=1; y1[0]=1; x2[0]=n; y2[0]=n;
    for (int i=1;i<=m;i++){
        int lx,ly,rx,ry;
        char co;
        scanf("%d%d%d%d %c",&lx,&ly,&rx,&ry,&co);
        if (lx>rx) swap(lx,rx);
        if (ly>ry) swap(ly,ry);
        x1[i]=lx; x2[i]=rx; y1[i]=ly; y2[i]=ry;
        if (co==’b’) dc[i]=1;
    }   
    init();
    work();
    print();
    return 0;
}   

[POJ 2029]矩阵处理

【题目大意】给定N*M的矩形和T个点，让你求A*B的子矩形最多能覆盖几个点。

【算法分析】压缩列，再扫描行。这个方法是O(N^3)的，最快的算法请参见这道题的加强版：http://hi.baidu.com/edwardmj/blog/item/b2ffc2f83570dd9d59ee900a.html

【其它】1A

6429770 edward2 2029 Accepted 508K 16MS G++ 924B 2010-02-09 20:40:21

【CODE】

#include

[POJ 1019]数字处理

【题目大意】有这样一个序列，1，112，112123，1121231234，112123123412345…，求它的第X位是多少。

【算法分析】

构造，分步骤来求，逐步逼近答案。

先对序列进行分组，即按1，12，123，1234，12345这样分组，利用递推求出前I组数的位数，即Sum[I]:=Sum[I-1]+F[I]，F[I]:=F[I-1]+Trunc(ln(I)/ln(10))+1。

这样，我们可以很容易确定第X位的所在组（当组大于40000时，位数已经超过Maxlongint）

然后在用While循环求出第X位是这个组中的第几个数，再求出是这个数的第几位即可。

【其它】复杂度约为O(sqrt(n))

6429639 edward2 1019 Accepted 884K 16MS G++ 1094B 2010-02-09 20:10:37

【CODE】

#include

[POJ 2019]矩阵处理

【题目大意】给定一个N*N的矩阵和K个询问，对于每个询问输出以该坐标为左上角的B*B的子矩阵中，最大值-最小值是多少？

【算法分析】先预处理把列压缩，然后再利用枚举打表，最后直接输出。

【其它】1A。时间复杂度O(N^3)

6429453 edward2 2019 Accepted 1036K 219MS G++ 1117B 2010-02-09 19:08:19

【CODE】

#include