作者存档：edward_mj

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

【题目大意】有这样一个序列，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

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

【题目大意】给定一种操作：交换两个相邻的数。问最少操作多少次，可以使得给定的序列不降序。

【算法分析】其实就是逆序对。为什么呢？因为每次有效操作，必然把两个位置不对的数交换，这样就相当于搞定了其中一个逆序对，所以最后答案就是逆序对的个数。

【其它】1A

6429266 edward2 2299 Accepted 4100K 391MS G++ 603B 2010-02-09 18:16:14

【CODE】

#include

【题目大意】给出分给给N个球涂色的代价，让你给某些球涂色，使得满足任意连续M个球中至少有2个是已经涂色的。

【算法分析】易得方程F[I,J]=min(F[J,K])+A[I]   (K

【其它】2WA，一次是瞎扯，根本理解错题意，一次是某个地方i1打成i了。

997585 09.02.10 12:51 edward 183 .CPP Accepted 143 ms 95 kb

【CODE】

#include #include #define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
const int N=11111;
const int M=111;
const int inf=(0x7FFFFFFF-5)/4;
int n,m,a[N],f[M][M],g[M][M],mod;
void init(){
    mod=M;
    memset(f,50,sizeof(f));
    memset(g,50,sizeof(g));
    for (int i=2;i<=m;i++)
      for (int j=1;j        f[i][j]=a[i]+a[j];
    for (int i=2;i<=m;i++){
        g[i][i-1]=f[i][i-1];
        for (int j=i-2;j>=1;j–)
          g[i][j]=min(f[i][j],g[i][j+1]);
    }   
}   

void work(){
    for (int i1=m+1;i1<=n;i1++){
      int i=i1%mod;
      memset(f[i],50,sizeof(f[i]));
      memset(g[i],50,sizeof(g[i]));
      for (int j1=i1-m+1;j1          int j=j1%mod;
          f[i][j]=g[j][(i1-m)%mod]+a[i1];
      }
      g[i][(i1-1)%mod]=f[i][(i1-1)%mod];
      for (int j1=i1-2;j1>=i1-m+1;j1–){
          int j=j1%mod;
          g[i][j]=min(g[i][(j+1)%mod],f[i][j]);
      }   
    }   
}   

void print(){
    int ans=0x7FFFFFFF;
    for (int i=n-m+2;i<=n;i++)
      for (int j=n-m+1;j        if (f[i%mod][j%mod]    printf("%dn",ans);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n<=m){
        int min1=0x7FFFFFFF,min2=0x7FFFFFFF;
        for (int i=1;i<=n;i++)
          if (a[i]              min2=min1;
              min1=a[i];
          }
          else
          if (a[i]        printf("%dn",min1+min2);
        return 0;
    }
    init();
    work();
    print();
    return 0;
}