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;
}

POJ 3723

【类型】

并查集优化kruskal

【Tip】

并查集使得可以判断任意两点是否可归溯于同一点,藉此来判断若链接两点是否会形成一个环.

这道题的输入是两个人以及两个人之间的亲密关系,征募某个人的花费为10000-(已征募人中亲密关系和自己的最大值).

这里我们在每征募某个人a时,若使用了a,b的关系,就连一条a,b的边。

如果这个图中存在圈,则一定会出现矛盾(谁是第一个被征募的?).

所以这个图一定是森林.

把人看做顶点.关系看做边,则这个问题就可以转化为求解无向图中的最大权森林问题(即亲密度之和最大),最大权森林问题可以通过把所有边权取反来求最小生成树.

【Code】

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int MAX_N=60000;
struct edge{
    int u,v,cost;
};

bool comp(const edge& e1,const edge& e2){
    return e1.cost<e2.cost;
}

edge es[MAX_N];
int V,E;//顶点数和边数

//并查集
int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

void init_union_find(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}

//查询树的根
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

//合并x和y所属集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

int kruskal(){
    sort(es,es+E,comp);
    int res=0;
    init_union_find(V);
    for(int i=0;i<E;++i){
        edge e=es[i];
        if(!same(e.u,e.v)){
            unite(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main(){
    int N;
    scanf(“%d”,&N);
    while(N–){
        int B,G,R;
        scanf(“%d%d%d”,&G,&B,&R);
        V=G+B;
        E=R;
        for(int i=0;i<R;++i){
            int a,b,c;
            scanf(“%d%d%d”,&a,&b,&c);
            es[i]=(edge){a,G+b,-c};
        }
        printf(“%d\n”,10000*(V)+kruskal());
    }

    return 0;
}