CCF 2016-12/4 & POJ 1738

类型: 石子合并问题
算法: GarsiaWachs算法。时间复杂度为O(n^2),平衡树来优化,使得最终复杂度为O(nlogn),也可以用动态规划,等等学一下再补充.

GarsiaWachs算法(摘自别人的blog):

具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W,Lemma X,Lemma Y,Lemma Z。
只能说一个概要吧:
设一个序列是A[0..n-1],每次寻找最小的一个满足A[k-1]<=A[k+1]的k,(方便起见设A[-1]和A[n]等于正无穷大)
那么我们就把A[k]与A[k-1]合并,之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。
有定理保证,如此操作后问题的答案不会改变。
举个例子:
186 64 35 32 103
因为35<103,所以最小的k是3,我们先把35和32删除,得到他们的和67,并向前寻找一个第一个超过67的数,把67插入到他后面
186 64(k=3,A[3]与A[2]都被删除了) 103
186 67(遇到了从右向左第一个比67大的数,我们把67插入到他后面) 64 103
186 67 64 103 (有定理保证这个序列的答案加上67就等于原序列的答案)
现在由5个数变为4个数了,继续!
186 (k=2,67和64被删除了)103
186 131(就插入在这里) 103
186 131 103
现在k=2(别忘了,设A[-1]和A[n]等于正无穷大)
234 186
420
最后的答案呢?就是各次合并的重量之和呗。420+234+131+67=852,哈哈,算对了。

证明嘛,基本思想是通过树的最优性得到一个节点间深度的约束,之后
证明操作一次之后的解可以和原来的解一一对应,并保证节点移动之后他所在的
深度不会改变。详见TAOCP。

具体实现这个算法需要一点技巧,精髓在于不停快速寻找最小的k,即维护一个“2-递减序列”
朴素的实现的时间复杂度是O(n*n),但可以用一个平衡树来优化(好熟悉的优化方法),使得最终复杂度为O(nlogn)


解题思路:(这是我找到的一个关于GarsiaWachs算法的解释)

      1. 这类题目一开始想到是DP, 设dp[i][j]表示第i堆石子到第j堆石子合并最小得分.

         状态方程: dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

         sum[i]表示第1到第i堆石子总和. 递归记忆化搜索即可.

      2. 不过此题有些不一样, 1<=n<=50000范围特大, dp[50000][50000]开不到这么大数组.

         问题分析:

         (1). 假设我们只对3堆石子a,b,c进行比较, 先合并哪2堆, 使得得分最小.

              score1 = (a+b) + ( (a+b)+c )

              score2 = (b+c) + ( (b+c)+a )

              再次加上score1 <= score2, 化简得: a <= c, 可以得出只要a和c的关系确定,

              合并的顺序也确定.

         (2). GarsiaWachs算法, 就是基于(1)的结论实现.找出序列中满足stone[i-1] <=

              stone[i+1]最小的i, 合并temp = stone[i]+stone[i-1], 接着往前面找是否

              有满足stone[j] > temp, 把temp值插入stone[j]的后面(数组的右边). 循环

              这个过程一直到只剩下一堆石子结束.

        (3). 为什么要将temp插入stone[j]的后面, 可以理解为(1)的情况

             从stone[j+1]到stone[i-2]看成一个整体 stone[mid],现在stone[j],

             stone[mid], temp(stone[i-1]+stone[i-1]), 情况因为temp < stone[j],

             因此不管怎样都是stone[mid]和temp先合并, 所以讲temp值插入stone[j]

             的后面是不影响结果.

代码实现:

///186 64 35 32 103
///GarsiaWachs算法。时间复杂度为O(n^2),平衡树来优化,使得最终复杂度为O(nlogn)
/*
设序列是stone[],从左往右,找一个满足
stone[k-1] <= stone[k+1]的k,找到后合
并stone[k]和stone[k-1],再从当前位置
开始向左找最大的j,使其满足
stone[j] > stone[k]+stone[k-1],
插到j的后面就行。一直重复,直到只剩下
一堆石子就可以了。在这个过程中,可以假设
stone[-1]和stone[n]是正无穷的。
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005;

int stone[maxn];
int N,ans,T;
///186 64 35 32 103
void combine(int k){
    int tmp=stone[k]+stone[k-1];
    ans+=tmp;
    for(int i=k;i<T-1;++i)
        stone[i]=stone[i+1];
    T--;
    int j=0;
    for(j=k-1;j>0&&stone[j-1]<tmp;--j)
        stone[j]=stone[j-1];
    stone[j]=tmp;
    while(j>=2&&stone[j]>=stone[j-2]){
        int d=T-j;
        combine(j-1);
        j=T-d;
    }
}

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=0;i<N;++i) scanf("%d",&stone[i]);
        T=1;
        ans=0;
        for(int i=1;i<N;++i){
            stone[T++]=stone[i];
            while(T>=3&&stone[T-3]<=stone[T-1]){
                combine(T-2);
            }
        }
        while(T>1)combine(T-1);
        printf("%d\n",ans);
    }
    return 0;
}
///186 64 35 32 103

ccf 2017前四题

第一题官网挂掉了.第五题感觉可以用最大流搞搞.
类型:
第一题:贪心
第二题:链表(我用STL里的list实现的)
第三题:中等模拟?
第四题:并查集+最小堆优化Kruskal
题目连接: **要登录和会员 ** http://118.190.20.162/home.page

github: :earth_africa:CCF 2017-3 前四题

第一题:

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int N,K;
    while(~scanf("%d%d",&N,&K)){
        int ans=0,d,n=0;
        for(int i=0;i<N;++i){
            scanf("%d",&d);
            n+=d;
            if(n>=K){
                n=0;
                ans++;
            }
        }
        if(n)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

第二题:

#include<bits/stdc++.h>
using namespace std;

int N,M;
int I,J;

list<int> li;

int main(){
    while(~scanf("%d%d",&N,&M)){
        li.clear();
        for(int i=1;i<=N;++i){
            li.push_back(i);
        }
        for(int i=1;i<=M;++i){
            scanf("%d%d",&I,&J);
            if(J==0)continue;
            list<int>::iterator it,it2;
            for(it=li.begin();*it!=I;it++){}
            it2=it;
            int flag=J>0?1:-1;
            J=abs(J)+(flag>0?1:0);
            while(J){
                J--;
                flag>0?it++:it--;
            }
            li.insert(it,I);
            li.erase(it2);
        }
        list<int>::iterator it;
        it=li.begin();
        printf("%d",*it);
        it++;
        for(;it!=li.end();it++){
            printf(" %d",*it);
        }
        printf("\n");
    }
    return 0;
}

第三题:

#include<bits/stdc++.h>

#define BUF_SS 101

using namespace std;

char buf[101];
int pre=-1;

int check_hl(int st){
    char hr[100];
    string tip;
    int ind=st+1,cs=0,hs=0;
    while(buf[ind]!=']'){
        if(buf[ind]=='_'){
            tip+="<em>";
            ind++;
            while(buf[ind]!='_'){
                tip+=buf[ind];
                ind++;
            }
            tip+="</em>";
            ind++;
        }else{
            tip+=buf[ind];
            ind++;
        }
    }
    ind+=2;
    while(buf[ind]!=')'){
        hr[hs++]=buf[ind];
        ind++;
    }
    hr[hs]='\0';
    printf("<a href=\"%s\">",hr);
    cout<<tip<<"</a>";
    return ind-st;
}

int check_em(int st){
    int ind=st+1;
    printf("<em>");
    while(buf[ind]!='_'){
        if(buf[ind]=='['){
            int ed=check_hl(ind);
            ind+=(ed+1);
        }else{
            putchar(buf[ind]);
            ind++;
        }
    }
    printf("</em>");
    return ind-st;
}

void check_h(int sz){
    int n,r=0;
    char sts[20],ste[20];
    while(buf[r]=='#'){
        r++;
    }
    int s=r,e=sz-1;
    sprintf(sts,"<h%d>",r);
    sprintf(ste,"</h%d>",r);
    for(;buf[s]==' ';s++){}
    printf("%s",sts);
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("%s\n",ste);
}

void check_u(int sz){
    if(pre!=2)printf("<ul>\n");
    int s=1,e=sz-1;
    for(;buf[s]==' ';s++){}
    printf("<li>");
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("</li>\n");
}

void check_p(int sz){
    if(pre!=3)printf("<p>");
    if(pre==3)putchar('\n');
    for(int i=0;buf[i]!='\n' && i<sz;++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    while(fgets(buf,BUF_SS,stdin)){
        if(buf[0]=='\n'){
            if(pre==3){
                printf("</p>\n");
                pre=0;continue;
            }else if(pre==2){
                printf("</ul>\n");
                pre=0;continue;
            }
            continue;
        }
        int sz=strlen(buf);
        if(buf[0]=='#') check_h(sz),pre=1;
        else if(buf[0]=='*') check_u(sz),pre=2;
        else check_p(sz),pre=3;
    }
    if(pre==3)printf("</p>\n");
    if(pre==2)printf("</ul>\n");
    return 0;
}

写题的时候写了一组测试数据:
In[1]:

# Heading

## Sub-heading

Paragraphs are separated
by a blank line.

Text attributes _italic_.

Bullet list:

*      apples
* oranges
* pears

A _[NLJ6link616lins1](http://example.com)_.

[NLJ6_link_616_lins_1](http://example.com)

out[1]:

<h1>Heading</h1>
<h2>Sub-heading</h2>
<p>Paragraphs are separated
by a blank line.</p>
<p>Text attributes <em>italic</em>.</p>
<p>Bullet list:</p>
<ul>
<li>apples</li>
<li>oranges</li>
<li>pears</li>
</ul>
<p>A <em><a href="http://example.com">NLJ6link616lins1</a></em>.</p>
<p><a href="http://example.com">NLJ6<em>link</em>616<em>lins</em>1</a></p>

第四题:

#include<bits/stdc++.h>
using namespace std;
const int MAX_M=200000+10;
const int maxn=200000+10;
int N,M;
int A,B,C;

struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,from,to;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};

struct Kruskal{
    int n,m;///点数和边数
    vector<Edge> edges;///边表
    vector<int> G[maxn];///每个节点出发的边编号
    priority_queue<HeapNode> Q;

    ///并查集
    int fa[maxn];///父亲
    int ra[maxn];///高度
    ///init:初始化(点数)
    ///find_Root:查找树的根
    ///unite:合并x和y所属集合
    ///same:判断x和y是否是同一个集合
    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i){
            fa[i]=i;
            ra[i]=0;
            G[i].clear();
        }
        edges.clear();
    }
    int find_Root(int x){
        if(fa[x]==x){
            return x;
        }else{
            return fa[x]=find_Root(fa[x]);
        }
    }
    void unite(int x,int y){
        x=find_Root(x);
        y=find_Root(y);
        if(x==y) return;

        if(ra[x]<ra[y]){
            fa[x]=y;
        }else{
            fa[y]=x;
        }
    }
    bool same(int x,int y){
        return find_Root(x)==find_Root(y);
    }

    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size()-1;
        G[from].push_back(m-1);
        Q.push((HeapNode){dist,from,to});
    }

    int kruskal(){
        HeapNode h;
        while(!Q.empty()){
            if(find_Root(N)==find_Root(1))break;
            h=Q.top();Q.pop();
            if(find_Root(h.from)==find_Root(h.to))continue;
            unite(h.from,h.to);
        }
        printf("%d\n",h. d);
    }
}K;

int main(){
    while(~scanf("%d%d",&N,&M)){
        K.init(N);
        for(int i=0;i<M;++i){
            scanf("%d%d%d",&A,&B,&C);
            K.AddEdge(A,B,C);
        }
        K.kruskal();
    }
    return 0;
}