会飞的小蛇-CSDN博客

原创计算几何基础

计算几何基础计算几何学了一些，感觉学的太乱，整理一下。

2020-08-14 16:55:31 321 1

原创 AtCoder Beginner Contest 223(A,B,C,D,E,G)题解

A - Exact Price题意：你钱包里有一张或更多的100100100块，问你钱包里钱的总数会不会是xxx。思路：判断xxx是不是100100100的倍数，以及特判000。代码：#include<bits/stdc++.h>#define fi first#define se second#define ll long long#define mp make_pair#define pb push_back#define ls x<<1#define

2021-10-19 01:40:56 543

原创 HDU-7133 Subpermutation

HDU-7133 Subpermutation思路：首先把排列ppp分成两组，一组是1∼m1\sim m1∼m，令一组是m+1∼nm+1\sim nm+1∼n。第一种情况：1∼m1\sim m1∼m在一个排列内部，那么就相当于把1∼m1\sim m1∼m插入m+1∼nm+1\sim nm+1∼n中包括首尾的任意一个空隙。这两个部分自身也可以任意排列，所以一共有m!(n−m)!(n−m+1)m!(n-m)!(n-m+1)m!(n−m)!(n−m+1)种方法。第二种情况。1∼m1\sim m1∼m分

2021-10-16 14:17:58 389

原创 Codeforces Round #748 (Div. 3)

Codeforces Round #748 (Div. 3)A.Elections题意：给出三个人的票数，一个人票数要严格高于其余两人才能当选，问每个人当选需要在得到多少票。思路：枚举这个人要再得到多少票能超过另一个人，取最大值。代码：#include<bits/stdc++.h>#define fi first#define se second#define ll long long#define mp make_pair#define pb push_back#de

2021-10-14 22:17:40 201

原创 HDU多校day7-1006Link with Grenade

Link with Grenade题意：有一个人在三维空间中静止不动，在单位球面上等概率随机选择一点，朝那个点扔一个炸弹。炸弹的初始速度为v m/sv\space m/sv m/s，在t st\space st s后爆炸，爆炸的半径是r mr\space mr m。炸弹受到重力的影响，重力加速度视为10m/s210 m/s^210m/s2。问此人不被炸弹炸到的概率为多少。思路：先考虑一下特殊情况：肯定会被炸到：可以想到，如果炸弹竖直向

2021-08-13 12:43:52 180

原创 CF1548D1. Gregor and the Odd Cows (Easy)

CF1548D1. Gregor and the Odd Cows (Easy)题意：给出平面上nnn个点，求选三个点构成的三角形满足面积是整数，且三角形内部的整数点的个数是奇数的个数。其中x,yx,yx,y均为偶数，且不存在任意三点共线。思路：由pick定理可知：S=a+b2−1S=a+\cfrac{b}{2}-1S=a+2b−1，其中aaa为三角形内部整点数，bbb为三角形边上整点数。由于x,yx,yx,y均为偶数，所以三角形面积SSS也肯定为偶数。所以可得2S=2a+b−12S=2a+b

2021-08-09 08:12:10 181

原创 HDU多校day3-1010Road Discount

Road Discount题意：nnn个点mmm条边，每条边有一个原价aaa和折扣bbb。你最多只能使用kkk 次折扣，对k∈[0,n)k\in[0,n)k∈[0,n)输出最少的花费使图连通。思路：用最小的花费使图连通就是MST，然后原价边和折扣边就可以看成黑白边。问题就是恰好包含kkk条白边的最小生成树。那么对于每条白边，我们通过对其权值加上一个ccc。由于边权的范围是[1,1000][1,1000][1,1000]，那么对于每个c∈[−1000,1000]c\in[-1000,1000]c∈[

2021-07-29 00:08:40 150

原创（二分+最小生成树）洛谷P2619 [国家集训队]Tree I

洛谷P2619 [国家集训队]Tree I思路：很显然的最小生成树，但是强制我们用needneedneed条白色的边。我们可以二分一个值xxx，让所有的白色边都加上xxx。这样就能够让白边靠前或者靠后。最终的答案就是最小生成树求出来的权值减去加上的总和。代码：#include<bits/stdc++.h>#define fi first#define se second#define ll long long#define mp make_pair#define pb push

2021-07-28 22:41:57 147

原创牛客多校day4-D.Rebuild Tree

Rebuild Tree题意：一个nnn个结点的树，删掉kkk条边，加上kkk条边，输出还是一个树的方案数模998244353998244353998244353。思路：删kkk条边之后形成k+1k+1k+1个连通块，设每个连通块的大小为sis_isi，则生成树的个数为nk−1∏i=1k+1sin^{k-1}\prod\limits_{i=1}^{k+1}s_ink−1i=1∏k+1si。考虑如何求∏i=1k+1si\prod\limits_{i=1}^{k+1}s_ii=1∏k+1si

2021-07-28 19:56:40 103

原创牛客多校day4-B.Sample Game

Sample Game题意：1∼n1\sim n1∼n个数，每个数都有一个随机概率pip_ipi，进行如下操作：按照概率随机生成一个数。如果生成的数字不小于之前生成的任意一个数字，回到步骤111，否则到步骤333。如果生成数字的个数为nnn，那么贡献为n2n^2n2。求期望贡献。思路：生成的序列肯定是一个非降的形式。我们假设最后数列的长度为lenlenlen,那么可以得到长度大于iii的概率P(len>i)=∏i=1npitiP(len>i)=\prod\limits_{i

2021-07-28 17:50:26 156

原创牛客多校day3-B.Black and white

Black and white题意：给你一个矩阵，原本都是白色。你可以将一个格子改成黑色，花费ci,jc_{i,j}ci,j。如果两行两列相交的444个格子有333个染成黑色了，就能免费把第四个染成黑色。问最少要多少代价才能将整个棋盘变黑。思路：如果我们把(i,j)(i,j)(i,j)相连，就会发现。如果两行两列444个格子有333个染黑的时候，就形成了一颗树的样子。所以就是将行列拆开然后求最小生成树。因为是一个完全图，所以用prim算法。代码：#include<bits/stdc+

2021-07-25 15:26:56 159

原创牛客多校2L.WeChat Walk

WeChat Walk题意：有nnn个人存在好友关系，在qqq个时间段中，每段时间都只有一人增加步数，求每个人在自己的好友列表中保持第一的时间段总数。思路：因为步数w≤104w\le10^4w≤104,所以我们可以按照步数从大到小枚举。假设在ttt时刻，uuu的步数是www。那么他只有在好友在之前没有更新过最大值或者更新最大值的时刻大于ttt。如果都满足，那么uuu保持第一的时间就是自己上一次更新最大值和自己好友最近一次更新最大值的时间的最小值减去ttt。令fxf_xfx表示xxx最近一次更新最

2021-07-23 20:52:34 153

原创 HDU多校day2-1002I love tree

I love tree题意：给你一棵树，有两种操作：1 x y1\space x\space y1 x y,从xxx到yyy简单路径的结点权值分别加上12,22,⋯ ,len(x,y)21^2,2^2,\cdots,len(x,y)^212,22,⋯,len(x,y)2。2 x2\space x2 x，询问xxx的权值。思路：假设这不是对于路径的操作，是对于数组的操作，如果对区间[l,r][l,r][l,r]分别加上12,22,⋯

2021-07-23 10:46:59 295 2

原创 HDU多校day2-1010I love permutation

I love permutation题意：给一个正整数aaa和一个奇质数p(a<p)p(a<p)p(a<p)。令数组b[1⋯p−1]b[1\cdots p-1]b[1⋯p−1]的元素为bi=axmod pb_i=ax\mod pbi=axmodp，求bbb中逆序对的数列模222的结果。思路：又一个定理，如果a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1,a2,⋯,an模ppp是一个完全剩余系，且gcd⁡(k,b)=1\gcd(k,b)=1gcd(k,b)=

2021-07-22 22:21:36 320 4

原创 HDU多校day1-1007Pass!

Pass!题意：nnn个人，最开始，第一个人拿球。每秒每个人可以把球传给任意一个其他人。ttt秒过后，球回到第一个人的传球序列方案数取模998244353998244353998244353后为xxx。给nnn和xxx求满足条件最小的ttt。思路：由于最后一秒要回到第一个人，那么时间为ttt的时候，球在111手上。由于不能传球给自己，那么时间为t−1t-1t−1的时候，球肯定在x(x≠1)x(x\neq 1)x(x=1)手上。设ttt秒的时候，方案数为f(t)f(t)f(t)。我们可以讨论时

2021-07-21 22:19:08 162

原创牛客多校day1G. Game of Swapping Numbers

G. Game of Swapping Numbers题意：给长度为nnn的序列A,BA,BA,B,操作恰好kkk次交换一组Ai,AjA_i,A_jAi,Aj,令∑i=1n∣Ai−Bi∣\sum\limits_{i=1}^{n}|A_i-B_i|i=1∑n∣Ai−Bi∣的值最大。思路：很巧妙的一个贪心。我们其实相当于给A,BA,BA,B序列分配相等数量的正负号。交换相同符号的位置不会影响结果，改变两个符号才会影响结果，将问题变成和序列的顺序无关的情况，只和符号的改变有关。如果不存在操

2021-07-18 17:20:20 157

原创最小树形图（朱刘算法）

思路：最小树形图就是在有向图中，以一个点为根的有向生成树，并且边权值和最小。思路大体上是贪心。1、贪心地选取每个点最小的入边。2、存在环则缩点，将其余边权值减去这个边终点的最小入边值。因为这相当于删除这个边的原来入边，再加上另外一条边。3、重复1，2直到无环。复杂度为O(NM)O(NM)O(NM)。Tarjan更快的算法还不会。代码：#include<bits/stdc++.h>#define pii pair<int,int>#define ll long lo

2021-05-17 20:00:02 447

原创图的绝对中心

图的绝对中心的定义是图上一个点（可以在结点上也可以在边上）到图上所有点的距离最大值最小。我们可以得到，到图绝对中心距离相等的点有两个。我们用d(i,j)d(i,j)d(i,j)表示结点iii到jjj的最短距离，rk(i,j)rk(i,j)rk(i,j)表示第iii个结点到其他结点距离中第jjj小的那个。假设图的绝对中心在结点上，那么肯定用距离最远的来更新，所以ans=min⁡(ans,d(i,rk(i,n))∗2)ans=\min(ans,d(i,rk(i,n))*2)ans=min(ans,d(i,

2021-04-30 21:36:41 607 2

原创（Prufer序列）洛谷P4430小猴打架

洛谷P4430小猴打架思路：求nnn个结点，通过不同的连接方式生成的树有多少种。通过Prufer序列，nnn个结点不同的生成树有nn−2n^{n-2}nn−2种。又因为这n−1n-1n−1条边可以以任意顺序连上，所以乘上这n−1n-1n−1条边全排列的数量，即(n−1)!nn−2(n-1)!n^{n-2}(n−1)!nn−2种。代码：#include<bits/stdc++.h>#define pii pair<int,int>#define int long long

2021-04-01 12:24:58 147

原创（同余最短路）洛谷P3403跳楼机

洛谷P3403跳楼机思路：由题，我们可到达的楼层为ax+by+cz(a,b,c≥0)ax+by+cz(a,b,c\ge0)ax+by+cz(a,b,c≥0)。我们假设一个数kkk是只通过操作2，3得到的，即k=by+czk=by+czk=by+cz。式子就变成了求满足ax+k≤hax+k\le hax+k≤h中xxx的数量。易得，通过操作1，能够到达的楼层数量为⌊h−kx⌋+1\lfloor\cfrac{h-k}{x}\rfloor+1⌊xh−k⌋+1。考虑去掉重复的部分。因为如果存在k1≡k2(

2021-03-28 09:34:52 142

原创（Prufer序列）洛谷P2624 [HNOI2008]明明的烦恼

洛谷P2624 [HNOI2008]明明的烦恼思路：设要求度数的点有kkk个，sum=∑i=1k(di−1)sum=\sum\limits_{i=1}^{k}(d_i-1)sum=i=1∑k(di−1)。如果di=0d_i=0di=0或sum>n−2sum>n-2sum>n−2都是

2021-03-26 23:34:50 140

原创（Prufer序列）牛客挑战赛48C.铬合金之声

牛客挑战赛48C.铬合金之声思路：首先由题很显然的一个结论就是，这是由nnn个点构成的有n−mn-mn−m棵无根树的森林。考虑权值的计算。假设第iii棵树的大小为sis_isi,权值就为∏i=1n−msi\prod\limits_{i=1}^{n-m}s_ii=1∏n−msi。但是这样的话，又要考虑乘上方案数，并且每种方案都需要分开考虑。很巧妙的一步就是，将无根树转换为有根树，因为有根树的方案数就等于无根树的方案数乘上结点树，恰好是我们需要的贡献。所以转换成了求nnn个点构成n−mn-mn−m

2021-03-25 19:37:16 132

原创 CF156D. Clues

CF156D. Clues题意：给一个nnn个点mmm条边的无向图，用最少的边使它们连通的方案数，取模ppp后输出。思路：通过并查集判断点连通，统计每个连通块的大小。连通块为111的时候特判一下，其他的情况就是模板题了，答案为nk−2∏i=1knumin^{k-2}\prod\limits_{i=1}^{k}num_ink−2i=1∏knumi,kkk为连通块的数量，numinum_inumi为每个连通块的大小。（证明）代码：#include<bits/stdc++.h>#d

2021-03-25 17:06:25 173

原创树/图连通方案数

1、通过Cayley定理，可以得到nnn个结点的无根树个数为nn−2n^{n-2}nn−2,证明参考Purfer序列。2、那么一棵结点数为nnn的有根树，就是在无根树的基础上面选定一个根，那么就是nn−1n^{n-1}nn−1种。3、nnn个结点，每个结点度数为did_idi的树。首先满足∑i=1ndi−1=n−2,di≠0\sum\limits_{i=1}^{n}d_i-1=n-2,d_i\neq 0i=1∑ndi−1=n−2,di=0。由Purfer序列的性质可以得到，度数为did_id

2021-03-24 20:58:14 705 4

原创（生成树计数）洛谷P2290 [HNOI2004]树的计数

洛谷P2290 [HNOI2004]树的计数思路：通过Purfer序列我们可以得到，度数为did_idi的点会在序列中出现di−1d_i-1di−1次。那么就相当于这些数求全排列的方案数，所以答案就为(n−2)!∏i=1n(di−1)!\cfrac{(n-2)!}{\prod\limits_{i=1}^{n} (d_i-1)!}i=1∏n(di−1)!(n−2)!。以及再加上一些特判，比如n=1,∑i=1ndi−1≠n−2n=1,\sum\limits_{i=1}^{n} d_i-1\neq

2021-03-24 20:43:14 94

原创（费用流）洛谷P4068 [SDOI2016]数字配对

洛谷P4068 [SDOI2016]数字配对思路：二分图，将偶数个质因子和奇数个质因子分成二分图，跑费用流即可。代码：#include<bits/stdc++.h>#define pii pair<int,int>#define int long long#define cl(x,y) memset(x,y,sizeof(x))#define loop(x,y,z) for(x=y;x<=z;x++)#define reve(x,y,z) for(x=y;x&

2021-01-26 01:02:39 107

原创（最短路+费用流）洛谷P4542 [ZJOI2011]营救皮卡丘

洛谷P4542 [ZJOI2011]营救皮卡丘思路：定义dis[u][v](u>v)dis[u][v](u>v)dis[u][v](u>v)为uuu到vvv且不经过编号大于vvv节点的最短路。用最短路可以求得。然后建图跑费用流。建图：拆点，把iii拆成i,i′i,i^{'}i,i′。1、SSS到000建(S,0,k,0)(S,0,k,0)(S,0,k,0)。2、SSS到节点iii建(S,i,1,0)(S,i,1,0)(S,i,1,0)。3、节点i′i^{'}i′到TTT建(i

2021-01-25 00:07:13 135

原创（费用流）洛谷P4307 [JSOI2009]球队收益 / 球队预算

洛谷P4307 [JSOI2009]球队收益 / 球队预算思路：非常有意思的一道题目。我们可以发现球队支出的费用与胜负有关，并且一场比赛一定有一个赢，一个输。我们不妨假设对于所有的比赛，每个球队都输掉的情况，并且找出mmm个赢球的球队支出最小的情况。假设一直球队从输一场球变成赢一场球，那么应该增加的费用为：c(a+1)2+d(b−1)2−(ca2+db2)=c(2a+1)−d(2b+1)c(a+1)^2+d(b-1)^2-(ca^2+db^2)=c(2a+1)-d(2b+1)c(a+1)2+d(b

2021-01-24 22:10:07 110 1

原创（费用流）洛谷P4237 荒芜的海洋

洛谷P4237 荒芜的海洋思路：建图：将点iii拆成入点iii和出点i′i^{'}i′。1、对于每个雇佣兵建(S,pi,1,qi)(S,p_i,1,q_i)(S,pi,1,qi)的边。2、对于每个岛建(i,i′,inf,ai),ai(i,i^{'},inf,a_i),a_i(i,i′,inf,ai),ai指岛上的怪兽数量。3、对于每条路建(u′,v,inf,w)(u^{'},v,inf,w)(u′,v,inf,w)和(v′,u,inf,w)(v^{'},u,inf,w)(v′,u,inf

2021-01-24 21:16:59 127

原创（质因数分解+二分图）LightOJ1356Prime Independence

LightOJ1356Prime Independence题意：给你nnn个数，你选出最多的一个集合满足不存在其中任意两数a,ba,ba,b满足a=k×b,ka=k\times b,ka=k×b,k是一个质数。思路：最大独立点集=n−=n-=n−二分图最大匹配数。我们可以通过唯一分解定理判断数字xxx的因子个数，可以知道如果因子个数同为奇数或者偶数，那么它们肯定不可能匹配。所以按照因数的奇偶将图分成二分图，进行连边。注意我们在判断两个数之间是否需要连边的时候，应该是记录一个数的因子进行除法判断得到

2021-01-24 01:12:36 163

原创（费用流）洛谷P4014 分配问题、P4015 运输问题

洛谷P4014 分配问题思路：显然一个最小费用最大流，一个最大费用最大流。只需要将权值取反再求一次即可。代码：#include<bits/stdc++.h>#define pii pair<int,int>#define ll long long#define cl(x,y) memset(x,y,sizeof(x))#define loop(x,y,z) for(x=y;x<=z;x++)#define reve(x,y,z) for(x=y;x>=z

2021-01-22 23:22:26 146

原创（费用流）洛谷P3967 [TJOI2014]匹配

洛谷P3967 [TJOI2014]匹配思路：第一问很简单，就是带权二分图的完美匹配。用最大费用最大流可以求出。第二问就是求最大费用最大流的必经边，那么枚举删除每条边看看费用是否会改变，改变的话就是必经边。由于第一问已经求出了匹配的方案，所以不用枚举删除每条边，只需要枚举去删除每组匹配的边即可。代码权值取反，算的是最小费用最大流。代码：#include<bits/stdc++.h>#define pii pair<int,int>#define ll long lon

2021-01-22 23:02:20 133

原创（费用流）洛谷P3965 [TJOI2013]循环格

洛谷P3965 [TJOI2013]循环格思路：非常好的一题网络流，一开始根本想不到。可以发现，循环格满足入度=出度=111。简单证明就是，一个n×mn\times mn×m的矩阵，每个格点都有一条出边，出度为111，如果入度=000，那么就无法到达，所以形成不了循环格；如果入度>1>1>1，那么就会存在其他点的入度为000。那么我们就可以将一点(i,j)(i,j)(i,j)拆成(i,j)(i,j)(i,j)和(i,j)′(i,j)^{'}(i,j)′。建图：1、SSS向(i,

2021-01-22 22:24:12 113

原创（费用流+01分数规划）洛谷P3705 [SDOI2017]新生舞会

洛谷P3705 [SDOI2017]新生舞会思路：∵C=∑a∑b\because C=\cfrac{\sum a}{\sum b}∵C=∑b∑a∴∑a−C∑b=0\therefore \sum a-C\sum b=0∴∑a−C∑b=0二分，令w=a−mid×bw=a-mid\times bw=a−mid×b，如果mid>cmid>cmid>c，那么∑w<0\sum w<0∑w<0,否则∑w>0\sum w>0∑w>0。现在就转化为是权值为a−

2021-01-22 18:15:46 98

原创（费用流）洛谷P3440 [POI2006]SZK-Schools

洛谷P3440 [POI2006]SZK-Schools思路：这就相当于一个带权的二分图匹配。设学校用点i∈[1,n]i\in[1,n]i∈[1,n]表示，注意这里不是学校的原始编号，因为会重合。用第iii个学校的原来编号为mim_imi。新的编号用点j∈[n+1,2×n]j\in[n+1,2\times n]j∈[n+1,2×n]表示。1、SSS向每个iii建(S,i,1,0)(S,i,1,0)(S,i,1,0)的边。2、每个jjj向TTT建(j,T,1,0(j,T,1,0(j,T,1,0的边

2021-01-22 17:10:23 108 1

原创（费用流）洛谷P3356 火星探险问题

洛谷P3356 火星探险问题思路：这题建图并不是很难，和洛谷P2045 方格取数加强版很相似。将一个点(i,j)(i,j)(i,j)拆成入点(i,j)(i,j)(i,j)和出点(i,j)′(i,j)^{'}(i,j)′。1、SSS向(1,1)(1,1)(1,1)建流量为kkk，费用为000的边。2、(n,m)′(n,m)^{'}(n,m)′向TTT建流量为kkk，费用为000的边。3、每个点对向东或者向南可以走的点连流量为infinfinf，费用为000的边。4、每个点(i,j)(i,j)(i

2021-01-22 16:55:11 141

原创（费用流）洛谷P2604 [ZJOI2010]网络扩容

洛谷P2604 [ZJOI2010]网络扩容思路：很显然第一问最大流，第二问费用流。对于第一问，可以将流量的费用全部设为000,建(u,v,c,0)(u,v,c,0)(u,v,c,0)的边,这样跑费用流就可以得到答案。在这个残留网络上，我们可以再建一个(u,v,inf,w)(u,v,inf,w)(u,v,inf,w)的边，再设一个超级源点SSS连向111，建(S,1,k,0)(S,1,k,0)(S,1,k,0)的边，再跑一次费用流就可以了。可以理解为第一问是免费的一个流量，第二问是加上单位流量需要的

2021-01-22 15:09:50 119

空空如也

空空如也