E5-D
E5-D 中位数
题目描述
Bellalabella 学到了中位数的知识，Bellalabella 想知道对于一个长度为 nnn 的序列 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an，所有前缀的中位数是多少。
由于 Bellalabella 学艺不精，不知道长度为偶数的序列的中位数的定义，因此她只需要你求出长度为奇数的所有前缀的中位数。
一个长度为 2n−12n−12n−1 的序列的中位数是将这个序列从小到大排序后第 n 个位置的数，例如$ [1,3,2]$ 中位数为 2，[2,3,2]2，[2,3,2]2，[2,3,2] 中位数为 222。
输入格式
第一行一个正整数 t（1≤t≤10）t（1≤t≤10）t（1≤t≤10），表示数据组数。
对于每组数据，第一行一个正奇数 n（1≤n≤105）n（1≤n≤10^5）n（1≤n≤105），含义同题目描述。
第二行 nnn 个整数 a1,a2,…,an（0≤ai≤105）a_1,a_2,…,a_n（0≤a_i≤10^5）a1,a2,…,an（0≤ai≤105），含义同题目描述。
对于得分占比 50%50\ ...
拓展欧几里得-求解线性同余方程
拓展欧几里得
欧几里得算法
原理
辗转相除法：用aaa除以bbb，得到余数rrr和结果qqq，再用除数bbb除以余数rrr得到新余数r2r2r2，再用除数rrr除以r2...r2...r2...直至余数为0此时的除数即为最大公因数。
辗转相除法的依据：
gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)
gcd(a,b)=gcd(b,a%b)
应用
求两个数的最大公约数。
拓展欧几里得
裴属定理
1 1cpp
a0x0+b0y0=gcd(a0,b0)a_0x_0+b_0y_0=gcd(a_0,b_0)
a0x0+b0y0=gcd(a0,b0)
即如果ax+by=max+by=max+by=m有解，那么mmm一定是gcd(a,b)gcd(a,b)gcd(a,b)的整数倍。
解释
联系辗转相除法的依据，我们可以得到：
b0x1+(a0%b0)y1=gcd(a0,b0)=gcd(b0,b0%a0)b_0x_1+(a_0\%b_0)y_1=gcd(a_0,b_0)=gcd(b_0,b_0\%a_0)
b0x1+(a0%b0)y1=gcd(a0 ...
最小生成树
最小生成树
一个有nnn个顶点的图，边个数一定大于等于n−1n-1n−1。图的最小生成树指的是在这些边中选择n−1n-1n−1条边，形成一棵包含所有顶点的树，这n−1n-1n−1条边的权值之和在所有方案中最小。
Prim算法
基本描述
PrimPrimPrim算法从点出发，每次选择与已加入节点距离最小的节点。时间复杂度为O(n2+m)O(n^2+m)O(n2+m)一般在稠密图中使用。
代码实现
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>using namespace std;#define Max 200000010int graph[5050][5050];long long Prim(int n){ int vis[5050] = {0}; ...
C5-D
C5-D 外接圆
题目描述
小 A 想给小 B 寄几盒蒜。
R2R^2R2 平面上有五个特殊点$ A,B,C,D,E$，任意两点不重合，任意三点不共线。
小 A 可以任意选择 A,B,C,D,E{A,B,C,D,E}A,B,C,D,E 中不同的三个点 P1,P2,P3P_1,P_2,P_3P1,P2,P3，并记 △P1P2P3△P_1P_2P_3△P1P2P3 的外接圆为 C。小 A 只能在 C 上移动。
记以 ${A,B,C,D,E}∖{P_1,P_2,P_3} $中剩余的两个点 P4,P5P_4,P_5P4,P5 所在的直线为 ℓ。小 B 只能在 ℓ 上移动。
小 A 想最小化两人之间的最短距离，使得寄蒜所支付的邮费最少。形式化地说，你需要求出 minC,ℓminP∈C,Q∈ℓ∣PQ∣min_{C,ℓ}min_{P∈C,Q∈ℓ}|PQ|minC,ℓminP∈C,Q∈ℓ∣PQ∣，其中 ∣PQ∣=(xP−xQ)2+(yP−yQ)2|PQ|=\sqrt{(x_P−x_Q)^2+(y_P−y_Q)^2}∣PQ∣=(xP−xQ)2+(yP−yQ)2为线段 $PQ ...
E4-D
E4-D CYCLES
题目描述
题目描述
在这循环往复的季节里，
对你的倾诉仍未说出口。
「我，任何改变都没有吗？」
给定 n 个点 m 条边的带权有向图 G。G 上的点依次标号 1,2,…,n1,2,…,n1,2,…,n。第 iii 条边$ u_i→v_i$ 的起点为 uiu_iui，终点为 viv_ivi，边权为 wiw_iwi。
对于 G 上的环$ p_1→p_2→⋯→p_k→p_1$，定义环的权值为环上所有边的边权平均值。
请你求出 G 上环的权值的最小值。如果 G 上没有环，则认为答案为 0。
输入
本题测试点包含多组数据。
第一行，一个正整数 T（1≤T≤10）T（1≤T≤10）T（1≤T≤10），表示数据组数。
对于每组数据：
第一行，两个正整数$ n,m（1≤n≤10^3，1≤m≤10^3）$，表示 G 的点数与边数。
接下来 m 行，每行三个正整数 ui,vi,wi（1≤ui≤n，1≤vi≤n，1≤wi≤106，ui≠vi）u_i,v_i,w_i（1≤u_i≤n，1≤v_i≤n，1≤w_i≤10^6，u_i≠v_i）ui,vi,wi（1≤ui≤n，1≤ ...
求简单多边形面积
PolygonArea
题目描述
莫卡想请你帮她计算一个包含 nnn 个点的简单多边形面积。
输入
第一行包含一个正整数 nnn，代表点数。
接下来n行，每行两个整数 xi,yix_i,y_ixi,yi，代表点的坐标，点的坐标按照逆时针顺序给出。
3≤n≤1000,0≤∣xi∣,∣yi∣≤1063≤n≤1000,0≤|x_i|,|y_i|≤10^63≤n≤1000,0≤∣xi∣,∣yi∣≤106。
输出
输出一个正整数，代表简单多边形面积的两倍。
输入样例
12345425 2540 4010 2040 0
输出样例
1600
鞋带公式
S=12∣∑i=1nxi∗(yi+1−yi−1)∣=12∣∑i=1nyi∗(xi+1−xi−1)∣S=\frac{1}{2}|\sum_{i=1}^{n}x_i*(y_{i+1}-y_{i-1})|=\frac{1}{2}|\sum_{i=1}^{n}y_i*(x_{i+1}-x_{i-1})|
S=21∣i=1∑nxi∗(yi+1−yi−1)∣=21∣i=1∑nyi∗(xi+1−xi−1)∣
设xix_ixi下标从1到n ...
