9.8 noip模拟试题

LazyChild黑OJ(blackoj.pas/c/cpp)

LazyChild开了一家“善良OJ”。但大多数人都不知道，这其实是家黑OJ。亲爱的同学，请不要惊讶，古时候有黑店，现代为什么不能有黑OJ呢？每AC一道题，网站便会自动在电脑上安装一种木马。LazyChild通过窃取信息获取收益（如网游帐号、OI资料、YuanY和TT的照片等等）。

作为一名资深黑客，老Z某日突然发现，“善良OJ”上的木马，自己电脑上都没有。这可十分让他过意不去。老Z决定通过多A题，来丰富自己电脑的病毒库。

经过调查，老Z发现，很多木马是不能共存的。比如“和谐”木马与“团结”木马，两者只能任选其一。然而，老Z是个完美主义者，他想要自己的病毒库尽可能充实。

老Z不懈的追求最终感动了上天。天上的神仙（半仙？）“牛人雨”给这个问题稍稍降低了一点难度。神仙规定，对于n种木马，有且仅有(n-1)对不能共存，并且对于每种木马，都存在至少一个木马与之不能共存。

老Z不在乎自己AC多少题。请告诉他，他最多能从“善良OJ”上获取木马的个数。

【输入】

第一行，一个正整数n，表示木马个数。

剩余(n-1)行，每行一对木马，表示他们不能共存。（保证相同的木马可以共存，任意不同两行的描述不等价）

木马编号从0至(n-1)

【输入】

一行，老Z最多获得木马的个数。你可以认为开始时没有任何木马。

【输入样例】

0 1

1 2

【输出样例】

【数据规模】

对于100％的数据，1<=n<=200

树上最大独立集：

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 510

using namespace std;

int n,head[maxn],num,son[maxn][maxn],f[maxn][],vis[maxn];

struct node{

    int v,pre;

}e[maxn*];

void Add(int from,int to){

    num++;e[num].v=to;

    e[num].pre=head[from];

    head[from]=num;

}

void Dfs(int now,int from){

    if(from!=-)

        son[from][++son[from][]]=now;

    for(int i=head[now];i;i=e[i].pre){

        int v=e[i].v;

        if(v!=from)Dfs(v,now);

    }

}

int dp(int now,int p){

    if(f[now][p]!=-)return f[now][p];

    int sum=;

    if(p)sum=;

    for(int i=;i<=son[now][];i++)

        if(p)sum+=dp(son[now][i],);

        else sum+=max(dp(son[now][i],),dp(son[now][i],));

    return f[now][p]=sum;

}

int main()

{

    freopen("blackoj.in","r",stdin);

    freopen("blackoj.out","w",stdout);

    scanf("%d",&n);

    int u,v;

    for(int i=;i<n;i++){

        scanf("%d%d",&u,&v);

        Add(u,v);Add(v,u);

    }

    Dfs(,-);

    memset(f,-,sizeof(f));

    printf("%d\n",max(dp(,),dp(,)));

    return ;

}

世界人民大团结(greatunion.pas/c/cpp)

现在，世界的主题是和平与发展。社会学博士老Z认为，要实现和平发展，首先要实现世界人民大团结。

世界上有n个人。他们胸前和背后各有一个自然数，大于或等于0且小于或等于6。两个身上带有某个相同数字的人把身上相同的数字合在一起，就实现了团结。比如，(0,1)(1,2)就实现了团结，而(0,1)(2,1)和(0,0)(1,2)都不是团结。把数合在一起的方法，是胸靠胸、背靠背、背靠胸或胸靠背。

请判断世界人民能否实现大团结。如果能，请输出大团结的实现方案。

【输入】

第一行，一个正整数n，表示世界上有n个人。

剩余n行，每行是用空格隔开的两个自然数，大于等于0且小于等于6，第(1+i)行表示第i个人胸前和背后的数字。

【输出】

如大团结可以实现，输出n行，每行两个空格隔开的数字。第一个是人的编号（同输入）；第二个是“-”或“+”，“+”表示这个人胸在前，背在后，“-”反之。人们按照你输出的顺序和面对的方向从前到后站立。具体参见样例。

如大团结不能实现，输出一行“No Solution”（不含引号）。

【样例输入】

1 2

2 4

6 4

2 1

【样例输出】

2 -

5 +

1 +

3 +

4 -

【数据规模】

对于100%的数据，1<=n<=100

暴力：

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 110

using namespace std;

int n,a[maxn][],falg,c[maxn],f[maxn],vis[maxn];

void Printf(){

    for(int i=;i<=n;i++){

        printf("%d ",c[i]);

        if(f[i])printf("-\n");

        else printf("+\n");

    }

}

void Dfs(int x,int y,int s){

    if(s==n){

        Printf();

        falg=;

        return;

    }

    for(int i=;i<=n;i++){

        if(i==x||vis[i])continue;

        if(a[x][y]==a[i][]){

            vis[i]=;c[s+]=i;f[s+]=;

            Dfs(i,,s+);if(falg)return;

            vis[i]=;c[s+]=;f[s+]=;

        }

    }

    for(int i=;i<=n;i++){

        if(i==x||vis[i])continue;

        if(a[x][y]==a[i][]){

            vis[i]=;c[s+]=i;f[s+]=;

            Dfs(i,,s+);if(falg)return;

            vis[i]=;c[s+]=;f[s+]=;

        }

    }

}

int main()

{

    freopen("greatunion.in","r",stdin);

    freopen("greatunion.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d%d",&a[i][],&a[i][]);

    for(int i=;i<=n;i++){

        c[]=i;f[]=;vis[i]=;Dfs(i,,);

        if(falg)break;

        c[]=i;f[]=;vis[i]=;Dfs(i,,);

        if(falg)break;

    }

    return ;

}

机房人民大团结（smallunion.c/cpp/pas）

最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。

同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。

每个“教授糖豆”的性质都有所不同。同志们已经研究出每个糖豆对人的影响。具体地，每个糖豆都有一个破坏值，吃掉这颗糖豆后，身先士卒的和谐家会对机房造成一定的破坏，破坏程度为先前累积的破坏值加上本次食用糖豆的破坏值，而且这颗“教授糖豆”的破坏值会加入累积。为了减小实验造成的破坏，同学们准备了几颗“治疗糖豆“，功能是无条件将累积的“破坏值”清零。

由于实验要求，和谐家只能按照给定的顺序吃掉“教授糖豆”，但可以随时吃掉一颗或多颗“治疗糖豆”。

你能帮助和谐家同志尽量减小实验所造成的破坏吗？

【输入】

第一行，两个数，用空格，分隔开，一个n，一个m。（n，m均为正整数。）n表示“教授糖豆”的数目，m表示“治疗糖豆”的数目。

剩余n行，每行1个正整数，表示“教授糖豆”的破坏值。和谐家必须按照给定的顺序，一次一个，吃掉所有“教授糖豆”。

【输出】

一行，一个数，表示实验造成的最小破坏。

【输入样例】

3 1

1 2 3

【输出样例】

【数据规模】

对于100%的数据，1<=n<=100，m<=n

所有破坏值的加和小于10^9。

暴力30：

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 110

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll n,m,a[maxn],ans=inf;

ll min(ll a,ll b){

    return a<b?a:b;

}

void Dfs(ll now,ll sum,ll c,ll s){

    if(sum>m||s>=ans)return ;

    if(now==n){

        ans=min(ans,s);

        return;

    }

    Dfs(now+,sum+,a[now+],s+a[now+]);

    Dfs(now+,sum,c+a[now+],s+c+a[now+]);

}

int main()

{

    freopen("smallunion.in","r",stdin);

    freopen("smallunion.out","w",stdout);

    cin>>n>>m;

    for(int i=;i<=n;i++)

        cin>>a[i];

    Dfs(,,,);

    cout<<ans<<endl;

    return ;

}

正解线性dp：

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 110

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll n,m,a[maxn],s[maxn],f[maxn][maxn][maxn],ans;

ll min(ll a,ll b){

    return a<b?a:b;

}

int main()

{

    freopen("smallunion.in","r",stdin);

    freopen("smallunion.out","w",stdout);

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>a[i];

        s[i]=s[i-]+a[i];

    }

    memset(f,/,sizeof(f));

    ans=f[][][];

    f[][][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=i;j++)

            for(int k=;k<=i;k++){

                f[i][j][k]=min(f[i][j][k],f[i-][j][k]+s[i]-s[k-(k!=)]);

                if(k<i&&j)f[i][j][i]=min(f[i][j][i],f[i-][j-][k]+a[i]);

            }

    for(int i=;i<=n;i++)

        ans=min(ans,f[n][m][i]);

    cout<<ans;

    return ;

}

巴特西

9.8 noip模拟试题

最新文章

热门文章