- 博客(15)
- 收藏
- 关注
RSS订阅原创 2020 Multi-University Training Contest #1 1010 Math is Simple
2020 Multi-University Training Contest #1 1010 Math is Simple题意hdu-6760 Math is Simple给定一个n，求解如下式子题解设a+b=n时，设g(n)=∑a=1n1a(n−a)[gcd(a,n−a)==1][a<n−a]g(n)=\sum_{a=1}^n\frac{1}{a(n-a)}[gcd(a,n-a)==1][a<n-a]g(n)=∑a=1na(n−a)1[gcd(a,n−a)==1][a<n
2020-07-27 10:34:29
124
原创 2020牛客暑期多校训练营（第五场）C Easy
2020牛客暑期多校训练营（第五场）C Easy题意C Easy有两个长度为k的序列A，B满足∑i=1kai=N\sum_{i=1}^ka_i=N∑i=1kai=N,∑i=1kbi=M\sum_{i=1}^kb_i=M∑i=1kbi=M求P=∏i=1kmin(ai,bi)P=\prod_{i=1}^kmin(a_i,b_i)P=∏i=1kmin(ai,bi)的种类。题解设n<mn<mn<m，满足条件的a和b的方案构造的生成函数如下(x+x2…+…+xn)k(y1
2020-07-27 01:08:37
562
2
原创 2020 Multi-University Training Contest #1 1005 Fibonacci Sum
2020 Multi-University Training Contest #1 1005 Fibonacci Sum题意hdu 6755 Fibonacci Sum求后面的值。题解根据斐波那契通项式 F(n)=15(an−bn)F(n) = \frac{1}{\sqrt5}(a^n-b^n)F(n)=51(an−bn)其中a=1+52a=\frac{1+\sqrt5}{2}a=21+5,b=1−52b=\frac{1-\sqrt5}{2}b=21−5带入式子可得S(n)=15
2020-07-25 11:02:58
123
原创 2020 Multi-University Training Contest #1 1004 Distinct Sub-palindromes
2020 Multi-University Training Contest #1 1004 Distinct Sub-palindromes题意hdu 6754 Distinct Sub-palindromes构造一个仅由小写字母组成的字符串，要求构成回文串数目最小的构造数目。题解可以发现，当n <= 3时，可以随意构造，种类数为26^n.当n>3时，abcabc……这样带循环节的肯定是回文串种类最少的，只有a、b、c三种。所以种类数为262524。（这题被mod骗了orz）代码
2020-07-25 10:02:48
113
原创 2020牛客暑期多校训练营（第四场）I Investigating Legions
2020牛客暑期多校训练营（第四场）I Investigating Legions题意I Investigating Legions有N个点（30-300）和M（1~N/30）个团，每个点仅属于一个团（等概率在0~M-1选择一个整数作为它的团）。• 有一个常数 S（20~100）。按以下的方式生成 01 矩阵 a：如果 i 和 j 属于同一个团，a[i][j]=1，否则a[i][j]=0。同时该值有 1/S 的概率被翻转。• 给出 N 和 S 和 a（M 不给出），要还原每个点属于的团。题
2020-07-22 10:24:38
206
原创 2020牛客暑期多校训练营（第四场）H Harder Gcd Problem
2020牛客暑期多校训练营（第四场）H Harder Gcd Problem题意H Harder Gcd Problem将1~n的数两两匹配，匹配要求两两不互质，求最大的匹配数目和匹配过程。解法打完素数筛，从大到小遍历素数表，将该素数没有被找到过的的倍数取出，如果取出的数目为偶数，则刚好两两匹配。如果为奇数，则留下2的倍数（因为都留2的倍数方便匹配）。最后将留下的2的倍数两两匹配。代码#include<bits/stdc++.h>typedef long long ll;usi
2020-07-22 09:45:44
152
原创 2020牛客暑期多校训练营（第四场）B Basic Gcd Problem
2020牛客暑期多校训练营（第四场）B Basic Gcd Problem题意B Basic Gcd Problem给定c，x求解最大的Fc（x）。解法要求最大的Fc（x），要尽可能多的使gcd（i，x）剩下的数包含的因子数尽可能多。在打素数筛时顺手加个贡献就可以了。然后快速幂求解。代码#include<bits/stdc++.h>#define ll long long#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f
2020-07-22 09:36:39
196
原创 2020牛客暑期多校训练营（第三场）F Two Matchings
2020牛客暑期多校训练营（第三场）F Two Matchings题意F Two Matchings给出a，b，求c / d - e / f = a / b的一个可行解。且d, f < b做法如果gcd(a, b)> 1, 一定有解如下 c = a / gcd(a,b) + 1, d = f = b / gcd(a,b),e = 1。如果b = 1或者为素数，则一定无解。如果b 只含有一个素因数，比如27 = 3^3,也一定无解。b 拆分成 d * f， 所以c * f - d
2020-07-22 09:13:36
128
原创 2020牛客暑期多校训练营（第三场） C Operation Love
2020牛客暑期多校训练营（第三场） C Operation Love题面C Operation Love给出20个点表示一个手掌，要判断是左手还是右手。解决方法如图所示，最底下那条边长度为9，且其他所有边都在其一侧，遍历每个点对，判断长度为9的边其他点是否在同一侧，这里可以用叉积解决。找到底边后，通过左右两点坐标做垂线，找到左右两边的长度。然后课可以根据叉积的正负，两边的长度和对应直线的位置（ax+c的c）来判断左右手。ac代码#include<bits/stdc++.h>#
2020-07-22 08:53:09
107
原创 计算几何——极角排序
极角排序极角所谓极角，指的就是以x轴正半轴为始边，建立极坐标，逆时针转过的角，这个角的范围是[0,2π]。用途1、计算凸包链接：2、一些奇奇怪怪的路径题只能向左转，只能向右转就可以先极角排序找出最近的拐点。比如：...
2019-09-26 11:05:16
1260
原创 计算几何——叉积
计算几何——叉积叉积是计算几何的基础，首先我们要知道点，和线的表达。struct point{ double x,y;};//点struct line{ point a,b;};//线struct Vector{ point a,b;叉积和点乘点乘可用于计算两个角的夹角的cos值。叉积1、计算三角形面积2、计算多边形面积3、极角排序链接：...
2019-09-25 14:53:51
805
原创 单调栈&单调队列
单调栈&单调队列单调栈和单调队列简单的来说就是单调的栈和单调的队列（orz）。单调栈单调栈是维护一端，且先进后出，从栈底到栈顶单调。拿单调递增栈举例，当压入一个元素前，将栈顶元素弹出直到栈顶元素小于压入元素，从而保证队列的单调性。比如，用数列{5,4,6,2,4,3,6,5}，以此构造一个单调递增栈。根据这个原理，我们就可以写单调栈了~（推荐使用数组模拟）int a[N];i...
2019-08-19 21:49:56
142
原创 矩阵快速幂
矩阵快速幂前置知识线性代数矩阵乘法（ √ ）基础快速幂原理首先是矩阵乘法A×B中 a的列必须等于b的行，A×B的每一行就是A中对应的行*B中对应的列。然后我们就可以写一个结构体来重载乘法以及其他运算符。//别问我为什么我zz地用了class，问就是我chunclass mat{public: int n,m; ll v[maxn][maxn]; mat...
2019-08-15 15:39:35
92
原创 poj 1755 Triathlon 半平面交判断不等式是否有解
题意：n人参加铁人三项，已知每个人三段各自的速度ui,vi,wi，可以改变3段比赛的路程判断每个人是否能最先到达终点。题解：半平面交可以判断不等式方程组是否有解。首先构造方程组，设三段路程分别为s1，s2.对于第i个人，他所用时间 ti= s1/u1 + s2/vi+ s3/wi。所以对于第j个人，若要赢，则 s1( 1/uj - 1/ui ) + s2( 1/vj - 1/ui ) + s3...
2019-08-08 22:51:11
361
原创 zkw 线段树
ZKW线段树欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：全新的界面设计 ，将会带...
2019-08-05 13:56:24
256
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人