A. 给定一个n问n的因子中是否存在奇数

数据范围:T<=1e4,n<=1e14

思路

分类讨论：如果n是奇数则可以被他自身整除，如果n是偶数就将2除干净得到是奇数输出yes否则no

复杂度O(Tlog(n))

B. 给定一个n问n是否可以由若干个2020和若干个2021组成

数据范围:T<=1e4,n<=1e6

思路

设n=x*2020+y*2021,枚举x,若n-x*2020可以整除2021则为合法方案

复杂度O(T*500)

C. 给定k对关系,问有多少对(a,b),(c,d),使得a!=c,b!=d

数据范围:T<=1e4,k<=2e5

思路

容斥原理：选中一对(a,b),将c和a相同的对减去，d和b相同的对减去再加上同时a==c和d==b的对,答案再除以2

复杂度O(Tn)

D. 给定n个物品，每个物品有一个重量和花费，求在重量大等于m的条件的最小花费

数据范围:T<=1e4,n<=2e5,m<=1e9

思路

注意到花费的取值只可能是1和2，我们将物品花费为1的分为一组，花费为2的分为一组，
组内物品质量按从大到小排序，将质量求一个前缀和，枚举花费1的物品重量共用了多少，
再二分花费为2的物品重量，最后取最小

复杂度O(Tnlog(n))

E. 给定正整数n,k,和数组a,求从a中选择k个数使得其和最大有多少种方案，结果对1e9取模

数据范围:T<=1e3,n,k<=1e3,a[i]<=n

思路

考虑和的最大值为定值，假设现在有一个排好序的a数组，
从后向前的一段一定会被用过且和最大，假设现在第i个元素为a[i]，
且a[i]在数组中出现了x次（因为a排序了，这x个数连续），
则这x个a[i]有[0,x]个累加到了最大值中，最终的方案数就是从x中选择y个a[i],其中y为k减去后面用了多少个数

复杂度O(Tn^2)

G.定义一个数组是好的，当且仅当数组中的任意两个数存在a|b或者b|a,问最少删除几个数能得到一个好数组

数据范围:T<=10,n<=2e5,a[i]<=2e5

思路

考虑dp，用f[i]表示以a[i]结尾的，在i前面选择多少个数使得数组是好数组
转移:f[i]=max(f[i],f[j]+1){1<=j<i|a[i]%a[j]==0}
复杂度为O(n^2)会tle
考虑优化:因为每个a[j]比然是a[i]的约数，只枚举约数复杂度为O(nsqrt(n)).
实现时只需记录每个约数所在的位置进行转移即可

复杂度O(Tnsqrt(n))