A:符合条件的整数
题意:
思路:
求一段区间的个数,用前缀和的思想就是R - (L - 1),R表示[1,2^m - 1]有多少%7=1的数,L同理,那么关键就是给定一个n,怎么求[1,n]有多少%7=1的数了,通过观察可以发现就是(n - 1)/7。
所以答案就是(2^m - 2) / 7 - (2^n - 2) / 7。注意开闭区间就行。但是好像会爆ll,所以我python写的。
代码:
n,m=map(int,input().split()) ans1 = 1 ans2 = 1 for i in range(0,m): ans1 *= 2 for i in range(0,n): ans2 *= 2 res = ((ans1 - 2) // 7) - ((ans2 - 2) // 7 ) if res <= 0 : print('0') else : print(res)
B:Relic Discovery
题意:
思路:
签到题,直接计算 即可。
D:石子游戏
题意:
思路:
分类讨论一下。
当ai全为偶数的时候,如果偶数的个数是奇数先手必败,如果偶数的个数是偶数,先手必胜,这个很好验证,因为全部为偶数,所以全部直接合并就行,看一下合并次数的奇偶性。
当ai全为奇数的时候,注意到1不能合并也不能分解,所以特殊考虑一下,计算奇数的个数的时候不要算进来,只要奇数的个数>0先手必胜,否则先手必败,这个结论可以拿n个3来验证,因为3只能分解成1+2,所以每次都是最优策略,然后就会发现奇数个数>0先手胜。
其他情况,当包含奇数和偶数的时候,偶数必然最后要合并,所以我们先把偶数全部合并,如果偶数个数是偶数先手必然多一次合并机会,如果偶数个数是奇数就没有这次机会,最后拿偶数去和奇数分解的偶数合并,就得到结论,如果偶数个数是奇数先手败,是偶数先手胜。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; int a[maxn]; void solved(){ int n;cin>>n; int odd = 0,even = 0; int other = 0; for(int i = 1; i <= n; i++){ cin>>a[i]; if(a[i] == 1){other++;continue;} if(a[i] & 1)odd++; else even++; } if(other == 0 && odd == 0){ if(even % 2 == 0)puts("Bob"); else puts("Alice"); }else if(even == 0){ if(odd > 0)puts("Alice"); else puts("Bob"); }else{ if(even % 2 == 0)puts("Alice"); else puts("Bob"); } } int main(){ solved(); return 0; }