爱奇艺2020校招编程题汇总

有一个x*y*z的立方体，要在这个立方体上砍k刀，每一刀可以看作是用一个平行于立方体某一面的平面切割立方体，且必须在坐标为整数的位置切割，如在x=0.5处用平面切割是非法的。

问在切割k刀之后，最多可以把立方体切割成多少块。

假设有N个人要玩游戏，每轮游戏必须选出一个人当裁判，剩下的N-1个人作为玩家。现在第i个人要求作为玩家进行至少A_i轮游戏，那么至少需要进行多少轮游戏才能满足所有人的要求？

第一行包含一个整数N，2≤N≤10⁵。

第二行包含N个空格隔开的整数A₁到A_N，0≤A_i≤10⁹。

输出至少需要进行的游戏轮数。

给定一个大小为N-1且只包含0和1的序列A₁到A_N-1，如果一个1到N的排列P₁到P_N满足对于1≤i<N，当A_i=0时P_i<P_i+1，当A_i=1时P_i>P_i+1，则称该排列符合要求，那么有多少个符合要求的排列？

第一行包含一个整数N，1<N≤1000。

第二行包含N-1个空格隔开的整数A₁到A_N-1，0≤A_i≤1。

输出符合要求的排列个数对10⁹+7取模后的结果。

第一行一个字符串S。

第二行一个字符串T。两个字符串保证均只含小写字母。（1≤|S|≤500000, 1≤|T|≤100）

有一个非常经典的概率问题，是一个袋子里面有若干个红球和若干个蓝球，两个人轮流取出一个球，谁先取到红球谁就赢了，当人的先后顺序和球的数量确定时，双方的胜率都可以由计算得到，这个问题显然是很简单的。

现在有一个进阶版的问题，同样是一个袋子里面有n个红球和m个蓝球，共有A，B，C三人参与游戏，三人按照A，B，C的顺序轮流操作，在每一回合中，A，B，C都会随机从袋子里面拿走一个球，然而真正分出胜负的只有A，B两个人，没错，C就是来捣乱的，他除了可以使得袋子里面减少一个球，没有其他任何意义，而A，B谁 先拿到红球就可以获得胜利，但是由于C的存在，两人可能都拿不到红球，此时B获得胜利。

输入仅包含两个整数n和m,表示红球和蓝球的数量，中间用空格隔开。(0<=n,m<=1000)

请你输出A获胜的概率，结果保留5位小数。

首先给出一个长度为2ⁿ的序列，我们定义一个值v，这个值是由如下计算方法得到的，首先将A序列的第2*i-1位和第2*i位(i=1,2,..,2^n-1)进行OR操作得到新数列A'，然后再对A'序列操作，将A' 序列的第2*i位和第2*i-1位(i=1,2,...,2^n-2)进行XOR操作得到A''，对A''按照第一次操作方式进行OR操作，因为序列长度为2ⁿ,所以显然进行n次操作之后就只剩下一个数字了此时这个数字就是v。

例如A={1，2，3，4}，第一次操作之后为{1|2=3，3|4=7}，第二次操作后，{3^7=4},所以v=4。

但是显然事情并没有那么简单，给出A序列后，还有m个操作，每个操作表示为“a b”，表示将A[a]改为b，之后再对A序列求v值。

输入第一行包含两个正整数n，m，分别表示A序列的长度为2^n,操作数量为m。（1<=n<=17,1<=m<=10^5）

输入第二行包含n个正整数，中间用空格隔开，表示A序列。（0<=ai<=2^30）

接下来有m行，每行包含两个正整数a，b，表示一次操作，即把A[a]变成b。(1<=a<=2^n, 0<=b<=2^30)

输出包含m行，第i行表示进行了第i次操作之后，A序列的v值。