shicj's blog

直接处理即可。 小问题：math 库中没有 cot⁡\cotcot 函数。 解决：用公式 cot⁡(x)=tan⁡(π2−x)\cot(x)=\tan(\dfrac{\pi}{2}-x)cot(x)=tan(2π​−x)。 定义 cot⁡\cotcot 函数： 1double cot(double x){return tan(pi/2-x);} 输出： 1printf("%.6lf\n",x-0.5+(atan(cot(pi*x)))/pi); 代码就不用了吧。

可以发现，这道题目主要要解决的问题是如何从输入的密文中分出加密之前每行的字母（之后按照 V 形遍历输出明文即可）。 先想到找每一行的规律，但找不出来，于是想到用模拟的方法，按照要求先模拟一遍加密，模拟中记下每个位置对应在行数。 这一部分代码如下： 1234567//用sum记录第j行的字符个数for(int i=1;i<=n;){ for(int j=1;j<=h&&i<=n;j++,i++) sum[j]++; for(int j=h-1;j>=2&&i<=n;j--,i++) sum[j]++;} 接下来，把每一个字母放进每一行： 1234//q[]是一个字符型队列数组，用来记录每一行的字母for(int i=1,j=1;i<=h;i++) for(int k=1;k<=sum[i];k++,j++) q[i].push(s[j]); 再模拟一遍，输出结果： 12345678910for(int...

题意 求一年有 2n2^n2n 天，mmm 个人出现两人生日相同的概率。答案输出对 106+310^6+3106+3 的取模分子和分母（约分后）。 思路 首先想不进行优化的数学计算方法，求出两人生日相同的概率不容易，但我们可以求出所有人生日不同的概率（也就是排列数除以所有情况数），再用 111 减掉，即得公式 p=1−A2nm2nmp=1-\frac{A_{2^n}^{m}}{2^{nm}} p=1−2nmA2nm​​ 展开 A2nmA^m_{2^n}A2nm​ 得到 p=1−(2n)(2n−1)(2n−2)⋯(2n−m+1)2nmp=1-\frac{\left(2^{n}\right)\left(2^{n}-1\right)\left(2^{n}-2\right)\cdots\left(2^{n}-m+1\right)}{2^{nm}} p=1−2nm(2n)(2n−1)(2n−2)⋯(2n−m+1)​ 然后可以很容易想到用快速幂进行进行计算，求得分子和分母。 但是，题目要求约分。容易看出，分数线上下同除的数一定是...

upd 2024.11.20 “（否则选出这个点后 S2S_2S2​ 就不连通了）” S2S_2S2​ 改为 S1S_1S1​ upd 2024.10.10 “且选出的点不是剩余点集 S2S_2S2​ 的割点” S2S_2S2​ 改为 S1S_1S1​ 题意 给定一个无向图 GGG，点数为 n1+n2n_1+n_2n1​+n2​，边数为 mmm,保证 GGG 是一个点双连通分量且无重边。 请将 GGG 划分为两个无交集的点集 S1S_1S1​，S2S_2S2​ 满足 ∣S1∣=n1|S_1|=n_1∣S1​∣=n1​，∣S2∣=n2|S_2|=n_2∣S2​∣=n2​，且 S1S_1S1​，S2S_2S2​ 的导出子图均连通。 保证有解。 思路 因为 $ 1 \le n_1 , n_2 \le 2000 ，，， 1 \le m \le 5000 $ 所以可以考虑一个点一个点地选取和划分，每一次选取花费时间 O(log⁡m)O\left(\log\right.m)O(logm) 或更少。 因此可以定义 S2S_2S2​ 为空集，所有点都在 S1S_1S1​...

一道思维题，我自己没能想出来，研究了很久，最后参考了题解想了很久才做出来，但题解写得比较简略，于是在此记录一下。 解题思路 因为是无限延伸的完全二叉树，所以只要不对树根进行U操作，所有的命令都是合法的。 因为是无限复读指令，所以每一次执行指令之后的相对的位移是一样的。 于是，可以将要遍历的整棵树分成几个相同（也可以有包含关系）且连续的部分（这样可以用重复执行相同指令串来处理），然后处理每一个部分的过程就是要求出的指令串。 每一部分的具体操作中一定会遍历起点到终点的边一遍和其他的边两遍，于是有 $tot = 2 \times ( sum - 1 ) - d $（ tottottot 是步骤数， sumsumsum 是点数， ddd 是起点到终点的边数），具体参考图片： 然后，考虑分部分的方法，可以进行 O(n)O(n)O(n)...