题目2016中国大学生程序设计竞赛 - 网络选拔赛

代码在这里

A题

题意：给一个数n，问是否是73和137的倍数，n的长度为1000W。
每次乘10取模就可以了吧？

B题

题意：给N个数(n<=300)，其中最大的质因子不超过2000，从中选出一些数，问选出的数的乘积是完全平方数的方案数。
做法：发现2000内质数个数大约是300个，选出来的数中包含的所有质数的指数和都必须是偶数，也就是把n个数看做n个01变量，每个质数的指数和都是一个方程，高斯消元解异或方程即可。答案即为 (2^自由元个数)-1

C题

题意：有一棵树，每个点有个收益，每条边有个代价，每次经过这条边都要花费代价，但点上的收益只能取一次。问从每个点出发能得到的最大收益分别是多少。
树形DP：

1. dp[0]表示从x出发只向子树走，最后又回到x的最大收益。
2. dp[1]表示从x出发向上走，不走x的子树，最后回到x的最大收益（不算x本身的收益）（也即dp[0]+dp[1]就是从x出发绕一圈回来的最大收益）
3. dp[2]表示从x出发只向子树走，在其中一些子树中兜一圈再向某一子树走下去不回来的最大收益。（枚举向哪个儿子向下延伸，记录最大和次大（初始值都是value[x])
4. dp[3]表示从x出发直接向父亲走，不向x的子树走，不回来的最大收益(类似dp[1])

转移：（这里dp[0][x] - max(0, dp[0][son] - 2 * cost[edge])指从x出发只向子树走，但不走son这个子树，最后又回到x的最大收益）

1. dp[0][x] = value[x] + $ \sum $ max(0, dp[0][son] - 2 * cost[edge])
2. dp[1][x] = dp[1][fa] - dp[0][fa] - max(0, dp[0][x] - 2 * cost[edge]) - 2 * cost[edge]
3. dp[2][x] = value[x] + max{max(0, dp[2][son] - cost[edge]) + dp[0][x] - max(0, dp[0][son] - 2 * cost[edge])}
4. dp[3][x] 有两种情况：

- dp[3][fa] + dp[0][fa] - max(0, dp[0][son] - 2 * cost[edge]) - cost[edge] ，即链继续向上延伸  
- dp[2][fa] + dp[1][fa] - max(0, dp[0][son] - 2 * cost[edge]) - cost[edge] ，即链从fa转向向下延伸。
这里如果x刚好是fa取最大的dp[2]的那个儿子，则dp[2][fa]需要取次大值。

ans[x] = max(dp[0][x] + dp[3][x], dp[1][x] + dp[2][x])

D题

题意：有10种礼物，每种有a[i]个，你需要给每个人两个礼物，要求相邻两个人的第一个礼物不能相同，但第二个礼物没有要求。问最多能有多少人？
贪心，每次从与上一个人礼物不同的里面，选择剩余数量最多的一个给当前这个人，用堆维护下就可以了。那么什么时候停呢？

• 直到当前剩下的礼物只剩一种，且最后一个人拿的礼物也是这种。
• 发出去的礼物数量达到total/2，因为剩下的礼物要给每个人发第二个礼物。

H题

题意：给定三维空间内N个点(N<=200)，问有多少个合法的四面体。合法的要求是：1.有至少4条棱长度相等。2.若只有两条棱相等，则剩下的两条边不能相邻。
稍微画一画我们会发现，这个玩意长得挺有特点的：两个点到另两个点的距离都相等，有点像两个等腰三角形底边相接。
那么我们就有了一个算法：枚举两个点，再筛选出到这两个点距离相等的点，以上过程为O(N^3)，之后我们对筛选出的这些点按距离排序O(N^3log(N))，对于每一个不同的棱长，我们选两个点出来就可以了。但是会有一些需要额外处理的地方：共面的情况需要排除，正四面体的情况会重复计算。
O(n^2)枚举边长相等的两个点是否共面or构成正四面体的话，整体复杂度会是O(N^4)，但是由于题目中限制点都是整点，所以其实很难卡到上界，实测可过……

K题

题意：给一个字符串，只包含26个小写字母，任意确定字母到数字的映射关系，问最长上升子序列。
签到题。即问串中共出现多少种不同的字母。

By 闫鸿宇

An undergraduate at Shanghai Jiao Tong University who studies CS.

• ← Previous Post
• Next Post →