这里来一发需要开毒瘤优化，并且几率很小一遍过的模拟退火题解... 友情提醒：如果你很久很久没有过某一个点，您可以加上特判 可以像 P1337 [JSOI2004]平衡点 / 吊打XXX 那道题目一样 如果不会退火可以拿那道题练手... 个人看来这题和那题差不多，主要区别在get_ans()的函数上面 如何get_ans呢？ （图很垃圾，别介意） 先看这张图： 假设中间的黑点是目前确定的圆心，要get的ans是离这个点最远的圆上的点 那么初中数学老师就会教你：距离=两个圆心的距离+选中圆的半径 像这样： 显然最远的点只要O（n）遍历取最大值就好了 然后套上退火的模板就好了...

本片题解设计两种解法 果然是签到题... 因为返回值问题T了好久... 第一眼：搜索大水题？  然后...竟然A了 1 #include<cstdio> 2 #include<queue> 3 #include<iostream> 4 #include<cstring> 5 #define int long long 6 using namespace std; 7 inline int read(){ 8 int ans=0,f=1;char chr=getchar(); 9 while(!is...

又是DP？ 好吧，或者说是博弈论，但是我不会啊。 先搞个O（n^3）的记忆化搜索，然后瞎搞好像发现两个状态几乎一样？ 竟然过了样例，然后竟然A了... 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 inline int read(){ 6 char chr=getchar(); int f=1,ans=0; 7 while(!isdigit(chr)) {if(chr=='-') f...

日常吐槽：最大值赋太大79分卡了好久好久   算法：DP   分析：数学分析一下即可 最优解肯定是介个样子的：   抽象一点的话：     也就是说两个点（i,j）之间如果能够连上线，则必定中间点对（i,k(k∈(i,j))）没有斜率比它（i,j）大的 然后DP暴力更新，O(NM)---->O(N^2)   1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define i...

知识点：Floyd+初赛数学水平   难点：最短路计数？   分析：  n<=100，每个点都要输出，又和最短路有关      “红(chi)果(luo)果(luo)”的告诉你要Floyd啊      最短路显然不要说了，看看如何计数： 过两个点的最短路条数： \begin{matrix} \sum_{k,dis[i][k]+dis[k][j]<dis[i][j]} cnt[i][k]*cnt[k][j] \end{matrix}        然后一直更新就好了，看公式难理解的话直接看代码 1 #include<iostream> 2 #...

知识点：差分约束、 难点：找到正确的不等关系然后建图 关于建图：   一段时间内的收入及前缀和，l~r天的收入用前缀和表达即sum[r]-sum[l-1];   对于每一个账本，如果它是假的，可能会出现这种情况： sum[1,2]=1,sum[2,3]=1,sum[1,3]=1   显然：第一天第二天第三天收入为2，与sum[1,3]=1矛盾，我们要做的就是找到这个矛盾的地方     然后有一个显然的建图方法：sum[v]−sum[u−1]=c，sum[u-1]-sum[v]=−c。   然后跑SPFA套模板即可     1 #include<iostrea...

不知道为什么巨佬会把这道题加到咱的列表里来... 正解：找规律？或者，这个算分治嘛？   分析：刚开始定性思维分解成1,2,4,8,16,32……不够的话补1    然而发现当n=5时就不对了，进一步分析：    对于一个数字，比如说20。       怎么凑20呢？     方法              ——>          确定的数列    10+10；        10    5+5          5,10    2+3          3,5,10    1+1          1,3,5,10    1           1,1,3,...

正解：貌似有个叫基尔霍夫矩阵的东西？？？反正我不会   非正解：打表找规律（要真是省选，打30分钟的表可以A一道题还是很值的对吧）   我们要求一个。。。有N+1个节点的2*N条边的图的生成树的个数，N<=100，那就先打个爆搜？应该有30分吧   1 #pragma GCC optimize(2) 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define int __int128 7...

难点：找出DP方程? 易错点：开long long 知识点：DP+任意一种最短路算法（Floyd都可以）   关于转移方程： 我们令DP[I]为第I天花费的最小“成本” 那么就有： DP[i]=min{DP[j]+(i-j)*L+k} 0<j<i-1 我们可以这样理解，从第j天到第i天都采用当前（第i天）的最优方案 然后暴力更新即可？ 一些易错点加在注释里面了   1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #define int...

难点：找到正确方式建图 知识点：Kruskal   分析：这种题肯定要把点权转换到边权上，但肯定无法搞到和其他点相连的边上，怎么办呢？那就再造一个点呗，这个“超级点”和所有点相连，且边权=点权，于是就可以消除点权对选择的影响，代码实现很简单，思路不好想   1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 inline int read(){ 7 ...

这种答案跟序列排列顺序有关的,n比较小的（稍微大一点的也可以）,求最优解的，一般都可以随机化过 随机化不一定是模拟退火或是什么遗传蚁群 哪怕只是直接随机化一个序列，只要你随机的次数够多，它都能找到正解 ——沃·兹基硕德 不久前还看到一个斜率优化的题目，有人用二重循环A掉,原因竟是第二重循环只在前500个元素中寻找最优解...然后就切掉了.... 所以这道题的解法很明显了呀... 用退火的板子，但根本不用调参... 相当于就是在暴力的随机版本...随便找几个解的情况判断可行性 没想到交了两次就过了（91-->100） 1 #include<iostream&...

首先这是一道计数类DP，那我们得先推式子，经过瞎掰乱凑，经过认真分析，我们可以得到这样的方程 F(N)=F(0)+F(1)+....+F(N-M-1) 所有F初值为1，F(1)=2 ANS=F(N+M); 那显然我们有这样的代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 const int M=1e9+7; 6 using namespace std; 7 inline int read()...

得分100+100+20=220 其实估分是100+60+10=170啊 T1:地平线   题目描述： 老胡带着奶牛去都市观光。在落日的余晖里，他们看到了一幢接一幢的摩天高楼的轮廓在地平线上形成美丽的图案。以地平线为 X 轴，每幢高楼的轮廓是一个位于地平线上的矩形，彼此间可能有重叠的部分。奶牛一共看到了 N 幢高楼，第 i 幢楼的高度是 Hi，两条边界轮廓在地平线上的坐标是Ai 到 Bi。请帮助奶牛们计算一下，所有摩天高楼的轮廓覆盖的总面积是多少。 输入： 第一行：单个整数 N。 第二行到第 N + 1 行：第 i + 1 行有三个整数 Ai，Bi 和 Hi ...

摆脱了110魔咒... 30+100+0=130 诶呀第三题没开long long一分都没有啊... T1Gcd     题目描述： 给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对. 输入： 一个整数N 输出： 如题 样例输入： 4 样例输出： 4 数据规模：     30%：N<=5000 100%: N<=10^7   这道题似乎以前听过啊...然而不太会诶，枚举gcd，然后找互质的数，突然一下子就忘记欧拉函数这个东西了...然后暴力于是30分   正解：欧拉...