算法周周练9(ABDE)
A.符合条件的整数
题意:
求[2^n,2^m)区间里有多少个整数x满足x%7==1
思路:
考虑周期性。可以求从1 ~ 2^n和1 ~ 2^m里符合条件的数,相减即是答案。
计算过程会爆int,应该用long long.(我以为也会爆ll,所以用的ull)
代码:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43894353
B. Relic Discovery
思路:
签到题,模拟。
代码:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43894546
D.石子游戏
题意:
\1. 把石子数为奇数的一堆石子分为两堆正整数个石子
\2. 把两堆石子数为偶数的石子合并为一堆
两人都足够聪明,会按照最优策略操作。现在Alice想知道自己先手,谁能最后赢得比赛。
思路:
计算出石子为奇数和偶数的个数。
如果有偶数,当偶数的个数是偶数的时候A赢,其余都是B赢。
如果没有偶数,当全为1时B赢,否则A赢。
分析:对于每一个奇数(大于1),都可以拆成一个偶数和1,而两个偶数又可以合成一个偶数,所以大于1的奇数的操作次数为偶数次,对答案无贡献。对于偶数,可以考虑两两合并的操作,每次合并都相当于偶数的个数减少一,所以想让偶数最后只剩下一个,经历的次数为偶数个数-1;当该数为奇数时,说明B无法操作,A胜利;反之,B胜利。
代码:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43912081
E. 凸多边形的划分
思路:
> 设dp[i] [j] (i<j)表示从顶点i到顶点j的凸多边形三角剖分后所得到的最大乘积,当前我们可以枚举点k,考虑凸多边形(i,j)中剖出三角形(i,j,k),凸多边形(i,k),凸多边形(k,j)的最大乘积和。我们可以得到状态转移方程:(1<=i<k<j<=n)
for(int k=l+1;k<r;k++) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
但我们可以发现,由于这里为乘积之和,在输入数据较大时有可能超过long long范围,所以还需用高精度计算。
代码:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43894271