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
#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; }
#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; }
世界人民大团结
(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
#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; }
/* 以自然数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; }
擒贼先擒王
(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。
#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; }
/* 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; }