算法周周练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