作者存档：edward_mj

【题目大意】

给定一个M*N的矩阵，让你求其中非障碍格的哈密顿回路有多少种。

【算法分析】

按照CDQ的论文所写。

我用两个二进制位来表示插头：

00表示无插头

01表示“(”插头

10表示“)”插头

然后就分类讨论即可。

实现上，我用一个hash表来达到定位的目的。

因为这样表示状态很多，但是实际上状态是非常稀疏的，所以我开一个线性表来保存扩展到的状态，然后更新的时候，就从hash表里指向过去，然后维护一下就好了。

【其它】1A，跑了109MS

【CODE】

#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=10003;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[1000000];
int m,n,ng,pg,e,mx,my;
char c[13][13];
LL fl[2][20000],ans;
int sl[2][20000];
int tot[2],ls[key];

inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
    if (!t1 && !t2) return 0;
    if (t1) return 1;
    return 2;
}   

void add(int s,LL f){
    int st=s%key;
    for (int t=ls[st];t;t=g[t].next)
      if (sl[ng][g[t].y]==s){
          fl[ng][g[t].y]+=f;
          return;
      }
    sl[ng][++tot[ng]]=s;
    fl[ng][tot[ng]]=f;
    addedge(st,tot[ng]);
}   

void input(){
    ng=1; pg=0; ans=0;
    scanf("%d%d",&m,&n);
    int i,j;
    for (i=0;i      for (j=0;j        for (c[i][j]=getchar();c[i][j]!=’*’&&c[i][j]!=’.’;c[i][j]=getchar());
    if (c[0][0]==’*’) add(0,1);
                 else add(1+cf(n*2+1),1);
    mx=0; my=0;
    for (i=0;i      for (j=0;j        if (c[i][j]==’.’){
            mx=i;
            my=j;
        }   
}   

void No(int j){
    int k,t1,t2;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        if ((s&cf(j*2))||(s&cf(j*2+1))||(cf(n*2)&s)||(cf(n*2+1)&s)) continue;
        add(s,fl[pg][k]);
    }   
}

void Yes(int I,int j){
    int k,lct,uct,ts,i,top,ct;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        LL &f=fl[pg][k];
        uct=ChaTou(s&cf(j*2),s&cf(j*2+1));
        lct=ChaTou(s&cf(n*2),s&cf(n*2+1));
        if (!j && lct) continue;
        ts=(INF-cf(j*2)-cf(j*2+1)-cf(n*2)-cf(n*2+1))&s;
        switch (lct){
            case 0:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2)|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 2:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                }   
                break;
            case 1:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 1:
                        top=0;
                        for (i=j;;i++){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }
                        add((ts^cf(i*2+1))|cf(i*2),f);
                        break;
                    case 2:
                        if (I==mx && j==my && ts==0) ans+=f;
                        break;
                }   
                break;
            case 2:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts,f);
                        break;
                    case 2:
                        top=0;
                        for (i=j;;i–){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }   
                        add((ts^cf(i*2))|cf(i*2+1),f);
                        break;
                }   
                break;
        }   
    }   
}            

void dp(){
    for (int i=0;i      for (int j=0;j          if (!i && !j) continue;
          ng=1-ng;
          pg=1-pg;
          tot[ng]=0;
          init();
          if (c[i][j]==’*’) No(j);
                       else Yes(i,j);
      }
}   

int main(){
    input();
    dp();
    cout << ans << endl;
    return 0;   
}   

【题目大意】

NOIP的传纸条。不过点权只能为1.

【算法分析】

f[k][i][j]表示走k-2步第一个人走到第i行，第二个人走到第j行，所能达到的最大分数。

之所以搞k-2是因为对于一个人的坐标(i,j)有i+j=k

【其它】1A

= =又在刷水题了。。。。

【CODE】

#include #include #include const int N=1001111;
int m,n;
char a[111][111];
int f[222][111][111];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%s",a[i]+1);
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        switch (a[i][j]){
            case ‘.’:a[i][j]=0; break;
            case ‘*’:a[i][j]=1; break;
            case ‘#’:a[i][j]=2; break;
        }   
    memset(f,200,sizeof(f));
}   

inline void max(int &x,int y){
    if (y>x) x=y;
}   

void work(){
    f[2][1][1]=a[1][1];
    for (int k=3;k<=m+n;k++)
      for (int i=1;i<=m;i++) if (k-i<1 || k-i>n) continue; else
        for (int j=1;j<=m;j++) if (k-j<1 || k-j>n) continue; else{
            if (a[i][k-i]==2 || a[j][k-j]==2) continue;
            int &t=f[k][i][j];
            max(t,f[k-1][i-1][j-1]);
            max(t,f[k-1][i-1][j]);
            max(t,f[k-1][i][j-1]);
            max(t,f[k-1][i][j]);
            t+=a[i][k-i];
            if (i!=j) t+=a[j][k-j];
        }   
    max(f[m+n][m][m],0);
    printf("%dn",f[m+n][m][m]);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
      init();
      work();
    }   
}   

题目地址：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1563

【算法分析】

容易得到方程f[i]=min(f[j]+|sum[j]-sum[i]+j-i-1-L|^P)

令w(j,i)=|sum[j]-sum[i]+j-i-1-L|^P

则f[i]=min(f[j]+w[j,i])

这是经典的1D/1D模式的DP方程。

首先我们来证明一个性质：

命题1：对于i

证明：

令g(x)=|x|^P

1、P为偶数，对其求导得g(x)’=P*x^(P-1)，是单调递增的。

2、P为奇数，对其求导得g(x)’=P*x^(P-1)*(x/|x|)，容易发现，同样是单调递增的。

由于导函数单调递增，而导函数的定积分又对应于g(x)的变化量。

若a

而对于我们的w函数，随着i的增加，w[j,i]的增量是相同的，

所以相当于把g(x)不断向左平移。

由于f[i]又是固定的常数，所以命题1得证。

下面再证明另外一个性质：

命题2：方程满足决策单调性。

方程满足凸四边形不等式<=>方程满足决策单调性

w[i,j]满足凸四边形不等式当且仅当：

固定j以后，将w[i,j+1]-w[i,j]表示为i的函数，该函数的导数恒<=0。

（这个结论位于《算法艺术与信息学竞赛》的152页，定理3下面）

令g(i)=w[i,j+1]-w[i,j]，即g(i)=sum[j+1]-sum[i]+1-(sum[j]-sum[i])=a[j+1]+1。

所以g(i)为常数函数，g'(i)=0。

满足条件。

所以，综上所述，命题2得证。

于是我们就可以开一个双端队列维护决策序列了。

这个序列每一个域包含3个元素，两个是表示该点造成最优决策的区间，第3个是表示这个点是哪个。

然后我们维护这个队列即可得到最优解。

维护方法：

头部：顺次下去，如果i超过区间尾就到下一个决策区间。

尾部：每次把新弄好的i试图插进去，从后面开始，如果它负责的区域都没有i好，那么就把它删掉。由于命题1，我们只需要判断开头的结点就可以了。

当然，如果它负责的区域包含的<=i的点，那么就不可能删掉它了，因为i这个点不能完全替代它。

所以最后不可能把队列的元素都删掉，然后对队尾元素进行二分，看什么时候i这个点能够超越它。（这依赖于命题1的性质）

然后修改区间就可以了。

【其它】1A

【CODE】

#include #include #include #include using namespace std;
const int N=101111;
const long long INF=(long long)(1000000000)*(long long)(1000000000);
char S[N][33];
struct Queue_Type{int l,r,p;}Q[N];
int n,P,L,head,tail;
int a[N],sum[N],fa[N],v[N];
long long f[N];

double w(int j,int i){
    int x=sum[i]-sum[j]-1-L;
    if (x<0) x=-x;
    double ans=1;
    for (int i=1;i<=P;i++) ans*=x;
    ans+=f[j];
    return ans;
}   

long long lw(int j,int i){
    int x=sum[i]-sum[j]-1-L;
    if (x<0) x=-x;
    long long ans=1;
    for (int i=1;i<=P;i++) ans*=x;
    ans+=f[j];
    return ans;
}

void input(){
    cin >> n >> L >> P;
    sum[0]=0;
    for (int i=1;i<=n;i++){
        scanf("%s",S[i]+1);
        a[i]=strlen(S[i]+1);
        sum[i]=sum[i-1]+a[i]+1;
    }   
    sum[n+1]=sum[n]+1;
}   

void insert(int i){
    if (i==n) return;
    while (Q[tail].l>i && w(Q[tail].p,Q[tail].l)>=w(i,Q[tail].l)){
        tail–;
        Q[tail].r=n;
    }   
    int l=i+1,r=n,mid;
    if (Q[tail].l>i+1) l=Q[tail].l;
    while (l        mid=(l+r)/2;
        if (w(Q[tail].p,mid)>=w(i,mid)) r=mid;
                                   else l=mid+1;
    }
    if (w(Q[tail].p,l)    Q[++tail].p=i;
    Q[tail].l=l;
    Q[tail].r=n;
    Q[tail-1].r=l-1;
}   

void work(){
    memset(Q,0,sizeof(Q));
    head=0; tail=0; Q[0].l=1; Q[0].r=n; Q[0].p=0; f[0]=0;
    for (int i=1;i<=n;i++){
        while (i>Q[head].r) head++;
        if (w(Q[head].p,i)>INF+10 || lw(Q[head].p,i)>INF) f[i]=-1;
        else{   
          f[i]=lw(Q[head].p,i);
          fa[i]=Q[head].p;
          insert(i);
        }   
    }   
}   

void output(){
    if (f[n]==-1){
        printf("Too hard to arrangen");
        return;
    }   
    cout << f[n] << endl;
/*    memset(v,0,sizeof(v));
    for (int i=n;i;i=fa[i]) v[i]=1;
    for (int i=1;i<=n;i++){
        printf("%s",S[i]+1);
        if (v[i]) printf("n");
             else printf(" ");
    }    */
}   

int main(){
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
        input();
        work();
        output();
        printf("——————–n");
    }   
}