2019年电信学院第二届新生程序设计竞赛解题报告

2019年电信学院第二届新生程序设计竞赛-by wff325000

A:学长的象棋

签到题

两点之间距离的平方等于5(勾股定理)即可走到。

B:学长的图形

签到题

两个四分之一圆的面积之和减去矩形面积即阴影部分面积。

C:学长的游戏

easy

解法1:从大到小排序,第一个方块的长度大于等于1,第二个方块答案大于2,第三个方块答案大于等于3...以此类推,逐一遍历,直到第i+1个方块长度大于等于i+1不成立,答案即为i。

解法2:每次暴力查询序列内最长的不曾访问过的方块(O(n^2)),然后依照解法1求解,访问过的方块标记。

D:学长的字符

easy

同时遍历两个字符串的对应位置,将两个字符串不相同的位置记录,不相同的字符对(Syi,Tyi)数量等于2且Sy0==Ty1&&Sy1==Ty0即yes,否则no。

E:学长的城堡

medium

楼层之差较大时对5取模,特判差值为1以及10以内楼层转移的情况。

F:学长的险恶

medium

卡N^2的排序,排序后按题意模拟即可,需要注意的是,每组数据之间需要空行,即第一组数据之前以及最后一组数据之后不能加空行;如果序列中不存在重复数据,则仅输出排序后的序列,注意不要多输出空行。

G:学长的阴谋

medium

简单搜索,深搜/广搜都可以做,和救公主没啥区别说实话。

H:学长的沙包

hard

解法1:沙包在第m次传递的情况为,总情况数=在1号手上的情况数+不在1号手上的情况数,即第m次在1号手上的情况数=总情况数-不在1号手上的情况数,f[i]代表第i轮在1手上的种数,f[i+1]可以代表第i轮不在1手上的种数,然后f[i]+f[i+1]=(n-1)^i,f[i]+f[i+1] 就是所有情况数,通过递推可以得到f[m]。

解法2:dp,设dp[i][0]为第i次传递不在1号手上的情况数,dp[i][1]为第i次传递在1号手上的情况数

那么动态转移方程为, dp[i][0] = dp[i-1][0] * (n - 2) + dp[i-1][1] * (n - 1);

                                   dp[i][1] = dp[i-1][0];

答案计算过程可能爆int,用64位整数。

I:学长的情书

hard

解法1:记录每i个偶数第一次出现的下标,则ans+= (b[i] - b[i - 1]) * (b[i + k] - b[i + k - 1]);注意首尾位置的处理。

解法2:逐一遍历,遍历第i个值的时候,他对i以后的值的贡献h[i]++,ans+=h[i-k]。

ans即答案。

J:学长的黑锅

a+b+c=d,a是b,c的因子,则(1+k1+k2)a=d,所以a为d的因子,且a<=d/3;

k1+k2=d/a-1,所以当a选定后,k1,k2解的个数为d/a-2。

所以遍历2~sqrt(d),求d的因子a,ans+=d/a-2,注意特判a^2==d的情况。

K:学长的扑克

签到题

没啥好说的

L:学长的模拟

hard

超级大模拟,也没啥好说的,自闭。


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

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

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