分类存档：默认分类

【题目大意】给定一个长度为N的没有相同元素的序列，然后让你求一个连续子串A[I],A[I+1]….A[J]使得A[I]是这短子串中的最小值，A[J]是这段子串中的最大值，并使得它J-I的值最大。

【算法分析】我先假设确定了起点，然后考虑在O(lgN)的复杂度里找到对应的最长长度。对于这个问题，我们可以考虑先找出以I为起点的区间范围，即以A[I]为最小值的区间范围。找出这个范围以后，只需要再找出其中的最大值所在的位置，就已经找出了以I为起点对应的最长区间了。（因为这个数在可取值的范围里最大，所以不能再延伸区间了）。对于实现这个算法，我们很容易得到确定了起点的最小值单调递减，于是我们可以二分得到这个范围，复杂度O(lgN)。然后那个取最大值和最小值均可以用RMQ在O(1)的复杂度内搞出来。由于预处理RMQ复杂度也为O(NlgN)，所以整个算法的复杂度是O(NlgN)。

【其它】1A，今天的第10题，刷完睡觉

6430690 edward2 2452 Accepted 12516K 766MS G++ 1971B 2010-02-10 01:08:32

【CODE】

#include

【题目大意】给定一个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;
}