2012年ACM校集训队暨第一梯队选拔赛2解题报告

点几题做的人少的-by wqf582

A:Pump

本题题意就是想要给一个水池里面注水,现在有n个水泵是工作的,正的表示注水的,注满需要a[i]小时,负的表示抽水的,抽光需要a[i]小时,对于输出有三种情况:

①保持所有水泵开着,需要几小时(整数)注满。如样例1,每小时可以注水1/2+1/3=5/6,所以需要两小时注满。

②关掉一部分水泵(肯定是关抽水的水泵),可以注满,问最少关几个。

③无论如何也不能注满水池(只有一种情况:所有的都是抽水的水泵)。

先判断是否全为负,即为情况③;

否则,用一个double型的变量num统计所有工作的水泵每小时的工作总量num+=1.0/a[i],若统计的num为正,则为情况①,输出[1/num]向上取整;

否则为情况②,先将负数排好序,用循环每次num+(1.0/绝对值最小的负数),并统计加了几个,直到num为正结束,输出“NO 统计个数”。

B:Conflicting Lists

题意简单说就是给你两个长度为n的数列a和b,要求两数列的前k个元素,满足a中的数字必须在b中出现,同时b中的数字也必须在a中出现,求这个最小的k。

可以用哈希的方法解决,同时对a和b数列进行哈希,统计出现过的数字个数和每个数字出现的次数,当哈希到第k个元素的时候,恰好出现过k个元素,每个元素出现两遍,则说明符合条件,输出此k即可。

C:0/1 Tiles

规律题,推到6个的时候,就可以很明显看出是斐波那契数列,然后取模15746

D:Please your Friends

题目意思就是给你若干个好朋友想要的礼物编号,你手上每个礼物只有一个,问你能不能找到一种分配礼物的方法,满足所有好朋友。这里输入的处理可能有点麻烦,用stringstreanm会方便点:

 

while(gets(s),s[0]!='E')
{
stringstream ss;
m=0;
do{
ss.clear();
ss<<s;
map[m].n=0;
while(ss>>map[m].a[map[m].n])
map[m].n++;
m++;
gets(s);
}while(strcmp("",s));
...
}
这题数据范围没给,我开了100*100,感觉够用了。然后我是是用深搜做的用个used[]数组标记哪些礼物用过了,自上往下搜,每一层循环找没有用过的礼物,找到就做标记,深入下一层,之后去掉标记;若找不到就返回上一层。
核心代码:
void dfs(int c)//c为当前层数
{
int i;
for(i=0;i<map[c].n&&!flag;i++)
{
if(!used[map[c].a[i]])//若礼物没发
{
if(c==m-1)//若当前层数为最后一层
flag=1;
used[map[c].a[i]]=1;
dfs(c+1);
used[map[c].a[i]]=0;//回溯
}
}
}

 

E:Pair Isograms

F:Candy Store

G:Numbers

H:Root of String


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.