P10314 [SHUPC 2024] 函数 题解
直接处理即可。
小问题：math 库中没有 函数。
解决：用公式 。
定义 函数：
1 | double cot(double x){return tan(pi/2-x);} |
输出：
1 | printf("%.6lf\n",x-0.5+(atan(cot(pi*x)))/pi); |
代码就不用了吧。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 shicj's blog！
相关推荐
2025-04-14
CF1185E Polycarp and Snakes 题解
...
2025-03-19
CF1481D AB Graph 题解
分类讨论。 【111】当 mmm 是奇数时，构造 $ \text{abababab} \cdots$ 的串即可满足题意，于是直接交替输出 111 和 222 凑足 m+1m+1m+1 个即可。 【222】当 mmm 是偶数时： 【2.12.12.1】存在一个点对，来回字母一样，如下图： 这时显然和【111】相同处理即可。 【2.22.22.2】存在三个点，路径上字母相同，如下图： 这时构造一个 ⋯1→2→1→2→3→2→3⋯\cdots 1\rightarrow2\rightarrow\boxed{1\rightarrow2\rightarrow3}\rightarrow2\rightarrow3\cdots⋯1→2→1→2→3→2→3⋯...
2025-03-18
CF1487E Cheap Dinner 题解
提供一种简单的线段树写法。 首先，给出朴素的 DP，令 dpi,jdp_{i,j}dpi,j 表示前 iii 种食物，第 iii 种选择了 jjj 的最小花费，显然得出转移： dpi,j=min(j,k) is OKdpi−1,k+ci,jdp_{i,j}=\min\limits_{\text{(j,k)\ is\ OK}}dp_{i-1,k}+c_{i,j} dpi,j=(j,k) is OKmindpi−1,k+ci,j 边界： dp1,i=c1,idp_{1,i}=c_{1,i} dp1,i=c1,i 接下来将取最小值的枚举优化，一种简单的想法是，以 dpi−1dp_{i-1}dpi−1 建立线段树，每次枚举 kkk 时，将所有不符合条件的数字设置为正无穷，处理完这个 jjj 之后再将修改复原，这样的均摊时间复杂度为 O(nlogn)O(n\log...
2025-03-06
CF1638D Big Brush 题解
正难则反，倒序操作，操作的一定是四个同色格子（或者其中有已经完成操作的点，其他同色），可以从此入手进行 DFS。 遍历每一个点，对其进行 DFS，首先检查是否已经完成处理（被标记为 000）、越界或者不符合条件（有杂颜色），如果没有问题，标记这四个格子（改为 000），对其四周的格子进行搜索，具体的，分别是以下 888 个点： 1234dfs(x-1,y);dfs(x-1,y+1);dfs(x+2,y);dfs(x+2,y+1);dfs(x,y-1);dfs(x+1,y-1);dfs(x,y+2);dfs(x+1,y+2); 于是给出代码，注意倒序输出： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<bits/stdc++.h>using namespace std;int n,m;int...
2024-02-19
CF1916F Group Division 题解
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(logm)O\left(\log\right.m)O(logm) 或更少。 因此可以定义 S2S_2S2 为空集，所有点都在 S1S_1S1...
2024-07-26
CF1970C2 Game on Tree (Medium) 题解
0x00 题目大意 给出一棵树，在一个点上放一个棋子，两人轮流移动棋子到相邻位置，不可重复经过某个点，两人决策最优，问谁获胜。 0x01 初步分析 看一下样例，画个图分析一下： 然后看一下可以怎样移动： 发现每一条路径都去往叶子节点，显而易见，每个叶子节点的状态是确定的： 这个状态可以很快求出，接下来研究如何向上转移。 0x02 深入分析 由于叶子节点状态已知，所以考虑自底向上分析。 在这里，每一个节点上由谁选择（移到下一个点）很重要，我们用绿色字体标出每个节点上由谁选择： 可以看出，由谁选择取决于节点的深度。 易得，在最优决策中，总是要选择可以使得自己获胜的点，如果没有，则在这一点上出发对方获胜，否则自己获胜。 于是可以自底向上标出每一个点上的获胜者： 这时看一看起始节点上谁获胜就行了。 0x03 具体实现 在代码中，可以如图中用字符表示状态（这样直观但代码量大），但更推荐用布尔值来实现，这样可以把判断获胜者的运算转化为深度模 222 和逻辑运算，具体的写法可以自己琢磨。 求获胜者的步骤可以直接写在搜索的回溯部分，这样便于实现。 0x04...
评论