原题：寻找最大值 原题大意给定N个数A1, A2, A3, … AN，小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。 算法分析这题时间空间限制不太紧，暴力就可以过，但是可以用高维前缀维护最大值和次大值来做。因为2^20可以枚举的到，而且枚举x&y的结果z，不会丢解，因为z相当于x&y的子集，就是说z是x的子集，z也是y的子集。 http://www.cnblogs.com/forever97/p/hihocoder1496.html 程序代码#include <cstdio> #include <algorithm> using namespace std; int T, n; //高维前缀的数据结构 struct info { int val[2]; info operator + (const info & rhs)const{ int t_val[2] = {val[0], val[1]}; for ...

原题：Headmaster’s Headache 原题大意有一个学校想要聘请老师，要求每个学科都有两个以上的老师授课，并且要使总费用最小。有S（最多8个）个学科，现任的M（最多20个）个老师（你必须继续聘请他们），N（最多100个）份申请。后来的M行每行有至少两个整数，表示现任的老师的工资，和他所教授的课程（可能不止一个）。再后来的N行每行有也有至少两个整数表示聘请这个老师所需的费用，以及他所教授的课程（可能不止一个）。 算法分析这题属于集合类型的动态规划,因为最多只有8门课，所以考虑状态压缩，用d(i,s1,s2)来表示状态，s1是恰好有一个人教的课程集合，s2是至少有两个人教的集合,i表示第i个决策阶段。状态转移方程为 d(i,s1,s2) = min{d(i+1,s1’,s2’) + c[i],d(i+1,s1,s2)}。把所有人一起编号0~m-1是在职教师，m~n+m-1是应聘者。 程序代码#include <cstdio> #include <iostream> #include <algorithm> #include <strin ...

原题：Dome of Circus 原题大意在一个三维空间里，已知有N个点，求一个最小的圆锥使所有的点都包含其中。 算法分析 试着只考虑一个点。 R的最小值和H之间有，形如R=k*H+b的关系。 令高度为H时体积最小值为f(H)，便会发现f(H)是单峰的 考虑所有的点，那么高度为H时体积最小值为 max{f(H)}，归纳得，很多个单峰函数取max后仍是单峰函数所以就可以三分答案了。三分可以用来求出凸或凹函数的最值。 http://blog.csdn.net/pi9nc/article/details/9666627 程序代码#include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int maxn = 10005; const double EPS = 1e-4; int T, n; double x[maxn], y[maxn], z[maxn]; double f(double h){ double r = 0.0; ...

原题：Gems Fight 原题大意有 G 种颜色的宝石，放在 B 个袋子里（每种颜色可以放多个）。两人轮流选袋子（每个袋子只能被选 1 次），每次将选出来的袋子中的宝石放到 cooker 中，cooker 可能会起反应。反应条件是 cooker 中出现 S 个一样颜色的宝石，而且一旦起反应，每 S 个一样颜色的宝石就会获得 1 个魔法石（同时反应）。作为奖励，每次反应结束后当前玩家可以再选一个袋子继续游戏。游戏目标是自己获得的魔法石尽量多，双方都采取最优策略的情况下，问最终两个玩家的魔法石之差。 算法分析数据范围很小，毫不犹豫地状压。dp[S]：集合S被取走，此景此境，先手最多能赢后手多少分。遍历不在集合中的袋子，如果拿了i号袋子后不能合成魔法石，那么dp[S] = max(dp[S], -dp[S|1 << i]), 否则就可以连任dp[S] = max(dp[S], dp[S|1 << i] + 拿i号袋子获得的收益。 程序代码#include <cstdio> #include <algorithm> using namespac ...

原题：A Lot of Games 原题大意给出N个字符串，有2名选手，s一开始是个空串，每回合轮流往里面填字母，使得s为N个字符串其中一个的字串，若不能再往里面填字母则输，输了的下回合先手，问最后一回合谁赢 算法分析单局游戏可分成如下几种情况：1.先手必胜（1,0） 2.先手必败（0,1） 3.先手可决定游戏胜败（1,1） 4.游戏胜败由后手决定 （0,0）属于哪种情况，可种一棵字典树，然后dfs一遍，判断树上每个节点的状态。 情况1:两个玩家轮流胜利，第k局谁是胜者，由k的奇偶性决定。情况2:很不幸，先手会一直输到底。情况3:先手可前k-1局都输掉，在第k局击杀对手。情况4:先手被后手按情况3的思路干掉。 程序代码#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn = 1e5+5; const int SON = 26; int node_num = 0, n, k; char s[maxn]; struct N ...