有趣的问题

 ~~雾~~ *** ## Problem 1 > 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 > 要求：时间复杂度 $\mathcal O(n)$，不要开数组。 很经典的异或awa 设数组为 $a$。 异或大家都知道罢： > 首先将两个数字转二进制，不足位补 $0$。 > 新数字的一位如果两个数字的那一位相同就为 $0$ 否则为 $1$。 > $a$ 异或 $b$ 记做 $a\oplus b$ 显然两个相同的数异或后为 $0$（$n\oplus n=0$） 当所有数字异或后相同的均消掉肯定只剩下那个唯一的。 ```cpp #include<iostream> using namespace std; int n,tmp,ans; //用 tmp 辗转 int main() { cin>>n; for (int i=0;i<n;i++) { cin>>tmp; ans^=tmp; //在 C/C++ 中按位异或写作 "^" } cout<<ans; return 0; } ``` *** ## Problem 2 > 有一个 $n$ 个元素的数组，除了**两个**数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几。 > 要求：时间复杂度为 $O(n)$，不要开数组。 这就是两个 **Problem 1** 的结合。 考虑分治。 因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的。 异或后得到这个数字二进制形式中任意一个为 $1$ 的位都是我们要找的那一位。再然后，以这一位是 $1$ 还是 $0$ 为标准，将数组的 $n$ 个元素分成两部分。 - 将这一位为 $0$ 的所有元素做异或就得出第一个数 - 将这一位为 $1$ 的所有元素做异或就得出另一个数。 *** ## Problem 3 > 判断 $n$ 是否是 $2$ 的正整数的幂。 按位与运算： > 首先将两个数字转二进制，不足位补 $0$。 > 新数字的一位如果两个数字的那一位都为 $1$ 才为 $1$ 否则为 $1=0$。 众所周知 $2^k$ 的二进制是一个 $1$ 然后 $k$ 个 $0$。 $2^k-1$ 是 $k$ 个 $1$。 所以 $n$ 与 $n-1$ 与一下判断是否为 $0$ 即可。 ```cpp #include<iostream> using namespace std; int main() { int n; cin>>n; if (n<=0) cout<<"false"; else if (n&(n-1)) cout<<"false"; else cout<<"true"; return 0; } ``` *** ## Problem 4 > 判断 $n$ 是否是 $4$ 的正整数幂。 首先 $4$ 的正整数幂显然也是 $2$ 的正整数幂。 显然 $4$ 的正整数幂二进制 $1$ 的位置都是在奇数位（推一下就知道了）。 判这个用与运算即可，与上 `1010101010101010101010101010101010101010101010101010101010101...` 就行了。 ```cpp #include<iostream> using namespace std; int main() { int n; cin>>n; if (n<=0) cout<<"false"; else if ((n&(n-1))) cout<<"false"; else if ((n&0x55555555)==n) cout<<"true"; //PS : 32 位的 10101010101010...=0x55555555 else cout<<"false"; return 0; } ``` *** ## Problem 5 > 判断 $n$ 是否是 $3$ 的正整数幂。 由数论知 $3^k$ 的质因子只有 $3$。 输入的是 `int`，`int` 中最大的 $3^k$ 为 $3^{19}=1162261467$ 判下除 fa 即可。 ```cpp #include<iostream> using namespace std; int main() { int n; cin>>n; if (n>0&&!(1162261467%n)) cout<<"true"; else cout<<"false"; return 0; } ``` *** ## Problem 6 > 喜羊羊和灰太狼用几堆石子在做游戏。共有偶数堆石子排成一行，每堆都有正整数颗石子 $piles_i$ 。石子的总数是奇数所以没有平局。喜羊羊和灰太狼轮流进行，喜羊羊先手。 每回合玩家从行的开始或结束处取走整堆石头。 不能取石子时手中石子最多的玩家获胜。求喜羊羊是否具有必胜策略。 **解答 $1$：** 考虑 dp。 我们使灰太狼得分时，都会从喜羊羊的分数中扣除，这样只需比较最后结果即可。 令 $dp_{i,j}$ 为喜羊羊可以获得的最大分数，其中剩下的堆中的石子数是 $piles_i,piles_{i+1},\dots,piles_j$。 先考虑喜羊羊只能取 $piles_i$ 或 $piles_j$。 分类讨论喜羊羊选取的石子堆： - 选择 $plies_i$：$dp_{i,j}=plies_i+dp_{i+1,j}$； - 选择 $plies_j$：$dp_{i,j}=plies_j+dp_{i,j-1}$。 喜羊羊得分要最大化，即： $$dp_{i,j}=\max\{plies_i+dp_{i+1,j},plies_j+dp_{i,j-1}\}$$ 灰太狼同理： $$dp_{i,j}=\min\{-piles_i+dp_{i+1,j},-piles_j+dp_{i,j-1}\}$$ 灰太狼注意： - 得分只有前面有负号，因为转移性质。 - 得分最小化 根据 $n$ 的奇偶性 dp 即可。 *** **解答 $2$：** 因为石头的数量是奇数，因此只有两种结果，输或者赢。 喜羊羊先开始随便拿石头，然后比较石头数量： - 如果石头数量多于对手，赢了； - 如果石头数量少于对手，自己拿石头的顺序和对手拿石头的顺序对调，还是赢。 所以喜羊羊必胜。 *** ## Problem 7 > 给定整数 $n$，求 $n!$ 尾数中零的数量。 > 要求：时间复杂度 $\mathcal O(n\log n)$。 尾数零考虑分解因子 $2$ 和 $5$。 显然 $n!$ 中 $5$ 因子远小于 $2$ 因子，所以统计 $5$ 因子即可。 每次 $\div 5$ 求和即可。 ```cpp #include<iostream> using namespace std; int main() { int n,ans=0; cin>>n; while (n) n/=5,ans+=n; cout<<ans; return 0; } ``` *** ## Problem 8 > 你有 $4$ 张写有 $1$ 到 $9$ 数字的牌。你需要判断是否能通过 `*`，`/`，`+`，`-`，`(`，`)` 的运算得到 $24$。 > 1. 除法运算符 `/` 表示实数除法，而不是整数除法。例如 $4 / (1 - 2/3) = 12$ 。 > 2. 每个运算符对两个数进行运算。特别是我们不能用 `-` 作为一元运算符。例如，$[1, 1, 1, 1]$ 作为输入时，表达式 $-1 - 1 - 1 - 1$ 是不允许的。 > 3. 你不能将数字连接在一起。例如，输入为 $[1, 2, 1, 2]$ 时，不能写成 $12 + 12$ 。 就四张牌，打表进省一： 人类智慧知，无解情况如下： ``` 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1119, 1122, 1123, 1124, 1125, 1133, 1159, 1167, 1177, 1178, 1179, 1189, 1199, 1222, 1223, 1299, 1355, 1499, 1557, 1558, 1577, 1667, 1677, 1678, 1777, 1778, 1899, 1999, 2222, 2226, 2279, 2299, 2334, 2555, 2556, 2599, 2677, 2777, 2779, 2799, 2999, 3358, 3388, 3467, 3488, 3555, 3577, 4459, 4466, 4467, 4499, 4779, 4999, 5557, 5558, 5569, 5579, 5777, 5778, 5799, 5899, 5999, 6667, 6677, 6678, 6699, 6777, 6778, 6779, 6788, 6999, 7777, 7778, 7779, 7788, 7789, 7799, 7888, 7899, 7999, 8888, 8889, 8899, 8999, 9999 ``` 为了装逼，用 van 国码（Unicode）加密一下： ``` 对撒剘劥圞剜劏哱掶桺泛揋掵従剟剣彫寣污悫壛梄甏咍哲汭剤堧点卋嬞勆叛汬泐塵栋劚嚮咃宠吖剗楗囧力桻攋壯劯嗏桹劙剢剚焧啫栕炸栫栖嚲彳剛撑烃洿宋汷彲剙揁妷埻撧汢吩壙劇剭埼吕剝汣敯憇勇剥咎囻匓 ``` 用个查找就行。 *** ## Algorithm 1 [平方根倒数速算法](https://baike.baidu.com/item/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95/4075273?fr=aladdin)，字面意思，做法玄学。 > 此算法首先接收一个 $32$ 位带符浮点数，然后将之作为一个 $32$ 位整数看待，将其右移一次（取半），并用十六进制“毒瘤数字”`0x5f3759df` 减之，如此即可得对输入的浮点数的平方根倒数的首次近似值；而后重新将其作为原来的浮点数，以牛顿迭代法反复迭代，以求出更精确的近似值，直至求出符合精确度要求的近似值。在计算浮点数的平方根倒数的同一精度的近似值时，此算法比直接使用浮点数除法要快四倍。 这是百度百科上的。 在利用到 3D 图形渲染的一些游戏或者程序当中，法向量的单位化计算显得尤为重要。在三维欧几里得空间当中，某一向量 $v=(v_x,v_y,v_z)$ 的单位化是指计算 $v'=\dfrac{v}{||v||_2}$。其中 $||v||_2$ 表示向量的二范数，也即 $||v||_2=\sqrt{v_x^2+v_y^2+v_z^2}$。其中设 $x=v^2_x+v^2_y+v^2_z$，$x$ 的计算主要是乘法与加法，所以性能上不会有太大瓶颈。而 $v'=v\times x^{-\frac{1}{2}}$计算的时候，$x^{-\frac{1}{2}}$ 数值求解的速度如何将会极大影响向量单位化的运行效率。平方根倒数速算法正是为了解决这个问题而出现的。 *** **Code:** ```cpp float I_am_fun(float x) //float 精度感人 { float x2=x*0.5f; int i=*(int*)&x; i=0x5f3759df-(i>>1); x=*(float*)&i; x=x*(1.5F-(x2*x*x)); return x; } ``` 这个方法从本质上来介绍的话，就是先近似计算一个初始值，然后带入牛顿迭代法来计算最后的较为精确的 $x^{-\frac{1}{2}}$。涉及的中间变量有 $x\to \dfrac12\log_2x\to \log_2x^{-\frac{1}{2}}\to x^{-\frac{1}{2}}$。首先计算 `i=*(int*)&x` 是为了获得浮点数 $x$ 对应的整数表示 $I_x$。然后利用 $I_x$ 去求出 $\log_2y=\dfrac12\log_2x$ 中 $I_y$ 对应的整数表示，这也就是 `i=0x5f3759df-(i>>1)` 的作用。求得了整数表示 $I_y$ 之后，将该数强转回浮点数，也即求到了 $y=x^{-\frac12}$ 的近似值。最后一句使用牛顿迭代法 $y^2-\dfrac1x=0$ 对进行一遍迭代求解，也就是将上面得到 $y$ 的带入牛顿迭代法的公式当中作为初始值计算一遍，最后得到较为精确的结果。这个算法的核心地方在于 $\log_2y=\dfrac12\log_2x$ 如何利用这一等式得到 $I_x$ 与 $I_y$ 的关系，而这也就是 `0x5f3759df` 的重要意义所在。具体的数学推导以及中间的“毒瘤数字” `0x5f3759df` 是怎么算出来的可以参见[维基百科](https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/Fast_inverse_square_root)。 ## Operation 1 `A+B` 的奇异解法。 二进制模拟。 假设有两个二进制数 $a,b$，异或有“半加”之名，所以不进位加法就是 $a\oplus b$。 考虑进位，只需要同一位两个数字都是 $1$ 即可进位，也就是与运算。 ```cpp #include<iostream> namespace My_APlusB { static bool OutputTheCommandInput=false; #include<cstring> #include<cstdio> using namespace std; namespace Command { inline void trytohelp(){puts("try to input '/help'.");} void help() { puts("使用 command(const char* str) 来使用命令行") puts("使用 add(int a,int b) 来获取 a+b 的值"); puts("使用 /help 来寻求帮助\n"); puts("内部变量如下："); puts("\t1. OutputTheCommandInput，终端输出输入"); puts("您可以自己调用 namespace 修改，也可以使用/change 命令修改"); puts("使用方法：/change 变量名 值，当然你也可以使用 default 值来回到初始状态，特殊的，/change default 会使所有变量回到初始状态"); } } void command(const char* str) { using namespace Command; if (OutputTheCommandInput) cout<<"<<"<<str<<'\n'; if (str[0]!='/'){puts("[Syntax Error]The command first character must \'/\'");trytohelp();return ;} if (!strcmp(str,"/help")) {help();return ;} if (!strcmp(str,"/change OutputTheCommandInput true")) {OutputTheCommandInput=true;puts("sure");return ;} if (!strcmp(str,"/change OutputTheCommandInput false")) {OutputTheCommandInput=false;puts("sure");return ;} if (!strcmp(str,"/change OutputTheCommandInput default")) {OutputTheCommandInput=false;puts("sure");return ;} if (!strcmp(str,"/change default")) { OutputTheCommandInput=false; puts("sure"); return ; } puts("[Syntax Error]Unknown Command.");trytohelp(); } //请自动忽略上面 int add(int a,int b) { while (b){int tmpa=a^b,tmpb=(a&b<<1);a=tmpa,b=tmpb;} } } ```