2014-11-2 NOIP模拟赛1

2014-11-2 NOIP模拟赛1

Noip2009 团结模拟赛
如题目明白困难,请自行阅读或参照样例。
内存限制均为 256MB,时间限制均为 1s。
出题人不会 故意 在题材中安装圈套,但请自己小心程序的不利。
IO 文件名(.in/.out)与程序名(题目名)相同。
对于具有语言均不利用优化选项。
对于 Pascal 选手,打开-Ct –Cr –Ci –Co 多少个编译开关。
祝各位答题顺利,谢谢。

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 最多收获木马的个数。你可以认为起始潮流未此外木马。
【输入样例】
3
0 1
1 2
【输出样例】
2
【数据规模】
对于 100%的数据,1<=n<=200

个人档案 1个人档案 2

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 210
int n,num,head[maxn],f[maxn][2];
struct node{
    int to,pre;
}e[maxn*2];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs(int now,int father){
    f[now][0]=0;f[now][1]=1;
    for(int i=head[now];i;i=e[i].pre){
        int to=e[i].to;
        if(to==father)continue;
        dfs(to,now);
        f[now][0]+=f[to][1];
        f[now][1]+=f[to][0];
    }
}
int main(){
    freopen("blackoj.in","r",stdin);freopen("blackoj.out","w",stdout);
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        x++;y++;
        Insert(x,y);Insert(y,x);
    }
    dfs(1,0);
    int ans=max(f[1][0],f[1][1]);
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

20分 树形dp

个人档案 3个人档案 4

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 210
int n,num,head[maxn],f[maxn][2];
bool vis[maxn];
struct node{
    int to,pre;
}e[maxn*2];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs(int now,int father){
    vis[now]=1;
    f[now][0]=0;f[now][1]=1;
    for(int i=head[now];i;i=e[i].pre){
        int to=e[i].to;
        if(to==father)continue;
        dfs(to,now);
        f[now][0]+=max(f[to][0],f[to][1]);
        f[now][1]+=f[to][0];
    }
}
int main(){
    freopen("blackoj.in","r",stdin);freopen("blackoj.out","w",stdout);
    //freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        x++;y++;
        Insert(x,y);Insert(y,x);
    }
    dfs(1,0);
    int ans=max(f[1][0],f[1][1]);
    printf("%d",ans);
    //fclose(stdin);fclose(stdout);
    return 0;
}

100分
仍然树形dp,刚才有个细节错了

 

世界国民大合力

(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” (不含引号) 。
【样例输入】
5
1 2
2 4
2 4
6 4
2 1
【样例输出】
2 –
5 +
1 +
3 +
4 –
【数据规模】
对于 100%的数据,1<=n<=100

个人档案 5个人档案 6

#include<iostream>
#include<cstdio>
#define maxn 110
using namespace std;
struct node{
    int x,y;
}a[maxn*2];
int n,ans[maxn*2],cnt;
bool vis[maxn*2],flag;
void dfs(int pos){
    if(flag==1)return;
    if(pos==n+1){
        for(int i=1;i<=n;i++){
            if(ans[i]>n)printf("%d -\n",ans[i]-n);
            else printf("%d +\n",ans[i]);
        }
        flag=1;
        return;
    }
    if(pos>1){
        node pre=a[ans[pos-1]];
        int now=pre.y;
        for(int i=1;i<=n;i++){
            if(a[i].x==now&&!vis[i]){
                vis[i]=1,vis[n+i]=1;
                ans[pos]=i;
                dfs(pos+1);if(flag)return;
                vis[i]=0,vis[n+i]=0;
            }
            int ii=i+n;
            if(a[ii].x==now&&!vis[ii]){
                vis[ii]=1;vis[ii-n]=1;
                ans[pos]=ii;
                dfs(pos+1);if(flag)return;
                vis[ii]=0;vis[ii-n]=0;
            }
        }
    }
    else{
        for(int i=1;i<=n;i++){
            vis[i]=1,vis[n+i]=1;
            ans[pos]=i;
            dfs(pos+1);
            if(flag)return;
            vis[i]=0,vis[n+i]=0;

            int ii=i+n;
            vis[ii]=1;vis[ii-n]=1;
            ans[pos]=ii;
            dfs(pos+1);
            if(flag)return;
            vis[ii]=0;vis[ii-n]=0;
        }
    }
}
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("greatunion.in","r",stdin);freopen("greatunion.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i+n].x=a[i].y,a[i+n].y=a[i].x;
    }
    dfs(1);
    if(!flag)
        printf("No Solution");
    fclose(stdin);fclose(stdout);
    return 0;
}

80分 暴力

个人档案 7个人档案 8

/*
    以自然数0至6为顶点,以每个人为边,建图。求出图上的欧拉回路或欧拉路即可。
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 110
int n,du[maxn],map[maxn][maxn],ans[maxn],tot;
bool vis[maxn];
struct node{
    int x,y;
}a[maxn];
void Eular(int now){
    for(int i=1;i<=7;i++){
        if(map[now][i]){
            du[now]--;du[i]--;
            map[now][i]--;map[i][now]--;
            Eular(i);
        }
    }
    ans[++tot]=now;
}
int main(){
    freopen("greatunion.in","r",stdin);
    freopen("greatunion.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].x++;a[i].y++;
        du[a[i].x]++;du[a[i].y]++;
        map[a[i].x][a[i].y]++;
        map[a[i].y][a[i].x]++;
    }
    int cnt=0;
    for(int i=1;i<=7;i++)
        if(du[i]&1)cnt++;
    if(cnt!=2&&cnt!=0){
        printf("No Solution");
        return 0;
    }
    int S;
    if(cnt){
        for(int i=1;i<=7;i++){
            if(du[i]&1){S=i;break;}
        }
    }
    else S=1;
    Eular(S);
    for(int i=1;i<=7;i++){
        if(du[i]){
            printf("No Solution");
            return 0;
        }
    }
    for(int i=1;i<tot;i++){
        for(int j=1;j<=n;j++){
            if(vis[j])continue;
            if(ans[i]==a[j].x&&ans[i+1]==a[j].y){
                printf("%d +\n",j);
                vis[j]=1;
                break;
            }
            else if(ans[i]==a[j].y&&ans[i+1]==a[j].x){
                printf("%d -\n",j);
                vis[j]=1;
                break;
            }
        }
    }
    return 0;
}

100分 欧拉路

 

擒贼先擒王

(king.pas/c/cpp)
公元 3941 年 10 月,宇宙中最具侵略野心的 X
星人发现了地球。他们以月球为据点,向人
类开战。同年 12 月 7 日,X
星人四次中标的突袭,使人类军队境遇挫败,以至在军事力量
上,人类不可能与 X 星人抗衡。
X 星人正沉醉在偷袭成功的洋洋得意中时,老
Z——人类社会的五星级间谍,秘密地潜入月球,盗
取了 X 星军队的一份机密军事材料。
WREAMC(World Resist Extraterrestrial Aggression Military
Committee,世界反外来侵略军事
委员会)于 12 月 8 日凌晨 4 时收取了这份机密材料,通过 3
刻钟的商量,WREAMC 有丰裕
的凭据表达该材料中蕴含 了 X 星军队所有成员的个人档案。据《宇宙法》513
条:档案是
宇宙生物的绝无仅有标识。但是,WREAMC 发现,X
星军队档案集中有些档案所描述的始末本
质上 是平等的。换句话说,某些成员的个人档案在该档案集中曾多次出现。
WREAMC 预计,某个成员的档案在该档案集出现的效能越高, 该成员在 X
星军队中的地位
就越高。而档案出现频率最高的,自然就是 X
星军队的首脑(你不用多疑该臆度的不利,
俺们相应相信 WREAMC 成员的直觉) 。
正所谓“擒贼先擒王”,在人类军事力量处于劣势的情况下,WREAMC
决定集中力量,消灭
X 星军队的主脑。你的职责就是按照那份档案集,扶助 WREAMC 找到 X
星军队领袖的档
案。
为了便利你的钻研,WREAMC 已经将档案集简化成了巴科斯-瑙尔范式(BNF):
<档案> ∷= ( <属性> | <子女档案> { , <属性> |
<子女档案> } )
<子女档案> ∷= <档案>
<属性> ∷= <数字> { <数字> }
<数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
注:其中“∷=”表示定义为,“|”表示或,“{…}”内的项可以另行任意多次或不出现。
X
星人的个人档案和人类的等同,包括了自家的各类性能。为了有利于研商,大家用不同的整
数来表示不同的特性,数值相同则属性相同。 (注意是数值,不是字符串)
与人类档案略有不同,X 星人的个人档案中还含有他亲生子女的个人档案。
X 星人的个人档案中的属性和儿女档案都可能有重复,这么些重新将被忽视。
X 星人的个人档案中的属性和子女档案可以按擅自顺序在档案中冒出。
【输入】
输入文件的第 1 表现档案集中档案的条数 n(1≤n≤100)。
输入文件的第 2 行至第 n+1 行每行表示一条档案。
每条档案的长度不抢先 100 字符。
输入文件中并未剩余的空格。
输入文件中确保 X 星军队中有且仅有一个法老。
【输出】
出口文件有两行
出口文件首先表现一个整数,表示 AAA 军队领袖档案在档案集中出现的次数。
出口文件第二表现 X 星军队领袖在输入文件第一次出现的档案的序号。
【输入输出样例】
king.in
6
(3,3,(01,3),2,(2,3),(3,2))
(2,(3,1),3,(3,2),(1,3,1))
(2,3,(3,1),(1,3,1))
(((1231231231)))
((1231231231))
(1231231231)
king.out
2
1

机房人民大融汇

(smallunion.c/cpp/pas )
近些年,机房出了一个不团结分子:Dr.Weissman。他时不时欺骗同学们吃一种“助教糖豆”
,使
校友们神志不清,殴打外人,砸烂统计机,破坏机房团结。幸运地,一个和谐家认清了
Dr.Weissman 的大茂山真面目。机房人民并肩作战在联名,共同对抗 Dr.Weissman
及“讲师糖豆” 。
同桌们非凡独具社会责任感:他们担惊受怕“助教糖豆”流向社会,导致动乱。于是,刚才提到
的调和家身先士卒,为了试验,品尝“教师糖豆” 。
各种“教师糖豆”的性能都有所不同。同志们曾经探究出各样糖豆对人的熏陶。具体地,每
个糖豆都有一个破坏值,吃掉这颗糖豆后,身先士卒的和谐家会对机房造成一定的毁坏,破
坏程度为先前积淀的破坏值加上此次食用糖豆的破坏值,而且这颗“教师糖豆”的损坏值会
参加累积。为了减弱实验造成的毁损,同学们预备了几颗“治疗糖豆“,功用是权利将累
积的“破坏值”清零。
出于试验要求,和谐家只可以遵照给定的依次吃掉“教授糖豆”
,但可以每日吃掉一颗或多颗
“治疗糖豆” 。
你能辅助和谐家同志尽量减小实验所造成的破坏吗?
【输入】
先是行,几个数,用空格,分隔开,一个 n,一个 m。 (n,m 均为正整数。 )n
代表“讲师
糖豆”的数码,m 表示“治疗糖豆”的数额。
剩余 n 行,每行 1
个正整数,表示“教师糖豆”的破坏值。和谐家必须遵照给定的依次,一
次一个,吃掉所有“助教糖豆” 。
【输出】
一行,一个数,表示实验造成的微乎其微破坏。
【输入样例】
3 1
1 2 3
【输出样例】
7
【数据规模】
对于 100%的数据,1<=n<=100,m<=n
具有破坏值的加和小于 10^9。

个人档案 9个人档案 10

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 110
int n,m,a[maxn],ans=0x7fffffff;
void dfs(int pos,int sum,int now,int cnt){
    if(pos==n+1){
        ans=min(ans,now);
        return;
    }
    dfs(pos+1,sum+a[pos],now+sum+a[pos],cnt);
    if(cnt<m)dfs(pos+1,a[pos],now+a[pos],cnt+1);
}
int main(){
    freopen("smallunion.in","r",stdin);freopen("smallunion.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(1,0,0,0);
    cout<<ans;
    return 0;
}

30分 暴力

个人档案 11个人档案 12

/*
    f[i][j][k]表示吃了i个糖,j个药,最后一个药在吃k个糖前吃了的最小代价
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#define ll long long
#define inf (1LL<<60)
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
ll ans=inf,f[105][105][105],a[105],sum[105];
ll cal(int l,int r)
{
    if(l==0)return sum[r];
    return sum[r]-sum[l-1];
}
int main()
{
    //freopen("smallunion.in","r",stdin);
    //freopen("smallunion.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                f[i][j][k]=inf;
    f[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
            for(int k=0;k<=i;k++)
                f[i][j][k]=f[i-1][j][k]+cal(k,i);
        for(int j=1;j<=i;j++)
            for(int k=0;k<i;k++)
                f[i][j][i]=min(f[i][j][i],f[i-1][j-1][k]+a[i]);
    }
    for(int i=0;i<=m;i++)
        for(int j=0;j<=n;j++)
            ans=min(ans,f[n][i][j]);
    printf("%lld",ans);
    return 0;
}

100分 动态规划

 

admin

网站地图xml地图