HDU5878~HDU5891 2016网络赛青岛

时间:2022-12-14 08:45:01

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、