A、题意:给出一个整数n
, 找出一个大于等于n
的最小整数m
, 使得m的质因数只有2 3 5 7
分析:预处理出质因数2 3 5 7的数,超过maxt就行,然后找
B、题意:求1/1^2+1/2^2+...+1/n^2
分析:题坑,意思是n很大
感觉上越到后来值越小,实际上这个是趋向π^2/6,于是小范围的n直接递推,大范围的就输出π^2/6
C、
D、题意:有一壶水, 体积在 LL
和 RR
之间, 有两个杯子, 你要把水倒到两个杯子里面, 使得杯子水体积几乎相同(体积的差值小于等于1), 并且使得壶里剩下水体积不大于1. 你无法测量壶里剩下水的体积, 问最小需要倒水的次数
分析:贪心,始终抓住体积差为1,先向A杯子倒L/2,再向B杯子倒L/2+1,再向A杯子倒2,再向B杯子倒2……直到壶空了或者壶里剩1,省下一次倒。最后再注意特判下小数据
E、题意:问 n
个手势的石头剪刀布游戏是否能保证出每种手势胜率都一样
分析:当游戏平衡时,我出一个手势,对方出的n-1个输赢手势中肯定一半赢我,一半输我,所以n-1为偶数时候游戏平衡 否则不平衡
F、题意:n个点m条边的无向图,找一个欧拉路或者欧拉回路,使得路径经过点的异或和最大
分析:首先并查集判连通
统计度数为奇数的点的个数,如果为0,说明是欧拉回路,如果为2说明是欧拉路,否则不存在
对于欧拉路,并不需要找出具体的路径,易得一个点对ans的贡献为(d[x]/2 mod 2)*v[x],特别的起点和终点就一次
对于欧拉回路,不一样的对方是起点要多异或一次,所以要枚举起点
G、题意:n
个有序序列的归并排序.每次可以选择不超过k
个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T
, 问k
最小是多少
分析:二分k,然后就是石子合并问题,但是很有可能合到最后个数不够k个,所以可以提前合并最小的一些数然后再合并
值得一提的是,如果直接丢进priority_queue中会TLE,事实上,可以将排好序的丢进队列A,合并后的数直接丢进队列B(易得B是非单减),这样可以省去priority_queue的一个log复杂度
H、
I、题意:给出 n 个点的无向带权树,问删掉每条边后的直径总和
分析:先可以跑出这个树的直径(spfa) s->t
如果删的边不在s->t上,那么这次结果显然就是s->t长度
如果删的边在s->t上,很显然就在两边的子树中找,那么思路就出来了,可以提前dp预处理找出以a、b为根的子树的最长链
J、题意:01背包,100个物品,但重量是[0,1e9]间的随机数
分析:肯定不能DP了
按性价比排序,然后搜索剪枝
可行性剪枝的话就这么考虑:对于第k个,如果后面的性价比按第k个性价比来,同样重量的情况下,求出最大价值,如果比目前最优解还大,那么就剪枝掉
K、 题意:1000个点10000条边的无向图,敌人从n走一条最短路到1,在第i条路设置障碍的代价是wi,求最少的代价使得敌人至少会遇到一次障碍
分析:就是先弄出最短路路,再在上面跑最小割(最大流)
具体的先spfa跑遍最短路,如果d[x]-d[y]=map[x][y]那么x->y就是最短路上的一条边
然后跑最大流
L、题意:50个数,10W个询问,每次问删掉第i,j,k个数后,是否存在一种选10个数和为87的方案,只需要输出 ’Yes’ 或者 ’No’
分析:先预处理出f[i][j][k]表示去除i,j,k是否可以
求f[i][j][k]明显是个01背包
如果按一般那么些会TLE
这里可以用上bitset优化:bitset<90> dp[11]
第一维表示用了几个数(背包重量),第二维表示和
状态转移时候就是dp[j]|=dp[j-1]<<a[i]
ACM奇技淫巧——bitset,我就服你
M、