爱飞鱼的blog

自适应辛普森积分 123456789101112131415161718192021const double eps=1e-10;double a,b,c,d,l,r;double f(double x){ //积分函数 return (c*x+d)/(a*x+b);}double simpson(double l,double r){//辛普森公式 return (r-l)*(f(l)+f(r)+4*f((l+r)/2))/6;}//二次函数特性double asr(double l,double r,double ans){//自适应//分段simpson，如果划分足够小，低于误差就可以 auto m=(l+r)/2,a=simpson(l,m),b=simpson(m,r); if(fabs(a+b-ans)<eps) return ans; return asr(l,m,a)+asr(m,r,b);}int main(){ ...

当我们枚举到第 iii 个变量，且前 iii 个变量都不是自由元时，如果第 i∼ni\sim ni∼n 行中这个变量的系数均为 000，那么第 iii 个变量是自由元。 [a1,1a1,2a1,3a1,4a1,50a2,2a2,3a2,4a2,5000a3,4a3,5000a4,4a4,50000a5,5|c1c2c3c4c5]\left[\begin{matrix} a_{1,1} & a_{1,2} & a_{1, 3} & a_{1,4} & a_{1,5} \\ 0 & a_{2,2} & a_{2, 3} & a_{2,4} & a_{2,5} \\ 0 & 0 & \color{red}{0}& a_{3,4} & a_{3,5} \\ 0 & 0 & 0 & a_{4,4} & a_{4,5} \\ 0 & 0 & 0 & 0 & a_{5,5} \end{matrix} \middle...

Kummer定理 设 vp(n)v_p(n)vp​(n)表示 n 的质因数分解中质数 p 的幂次，则： vp(n!)=∑i=1∞[npi]v_p(n!)=\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]vp​(n!)=i=1∑∞​[pin​] 推论： vp(Cn+mm)=vp((n+m)!)−vp(m!)−vp(n!)=∑i=1∞[n+mpi]−∑i=1∞[mpi]−∑i=1∞[npi]=∑i=1∞([n+mpi]−[mpi]−[npi])\begin{aligned} v_p(\text{C}_{n+m}^m)&=v_p((n+m)!)-v_p(m!)-v_p(n!) \\ &=\sum\limits_{i=1}^\infty\left[\dfrac{n+m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]...

Codeforces Round 960 (Div. 2)A-E A题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个mxmxmx。每次轮到自己操作的时候就选一个数组里的数，满足a[i]>=mxa[i]>=mxa[i]>=mx,然后令mx=a[i]mx=a[i]mx=a[i].双方轮流做直到一方无法操作，则另一方取胜。 Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。 12345678910void solve(){ cin>>n; map<int,int>mp; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)mp[a[i]]++; bool flag=0; ...

E题 链接：https://ac.nowcoder.com/acm/contest/78292/E 来源：牛客网 小苯非常喜欢等比数列。有一天他得到了一个长为 nnn 的数组 aaa，他想从里面选一些数字使得被选中的数字构成一个等比数列，请问他最多可以选择多少个数字呢 输入包含两行。 第一行一个正整数 n (1≤n≤2×105)n\ (1\leq n \leq 2 \times 10^5)n (1≤n≤2×105)，表示数组 aaa 的长度。 第二行 nnn 个正整数 ai (1≤ai≤2×105)a_i \ (1 \leq a_i \leq 2 \times 10^5)ai​ (1≤ai​≤2×105)，表示数组 aaa...

赛时困得睡着了 B题 https://www.acwing.com/problem/content/5562/ 第二题赛事一直在想模拟加贪心，却发现非常难实现，我们需要转变思维，这时候一般有3种可能 双指针？二分？dp？ 后来清醒了一点我们判断一个答案是不是合法很容易，我们再考虑答案求最大值，显然具有单调性，所以我们考虑二分答案，前缀和u优化判断 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374// Problem: 摆放棋子// Contest: AcWing// URL: https://www.acwing.com/problem/content/5562/// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor...

AtCoder Beginner Contest 366 D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥 123456789101112131415161718192021222324252627282930313233343536373839404142434445int a[N][N][N];void solve() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { cin >> a[i][j][k]; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++)...

Codeforces Round 918 (Div. 4) D:本题从实现上来说正难则反，应该倒着做 在我正着做的时候，由于在访问后面元素的时候没有判边界，导致数组越界，出现奇怪字符在最后答案中。 1234567891011121314151617181920212223242526272829303132333435363738int n, m;int a[N];bool check(char c){ if(c=='a'||c=='e')return true; else return false;}void solve(){ cin>>n; string s;cin>>s; string ans; string tmp="."; for(int i=0;i<n;){ //cerr<<i<<"...

Codeforces Round 940 (Div. 2) and CodeCraft-23 前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。 A题：题意：给出n个木棍，最多组成多少个多边形 Solution：统计各长度木棍的数量，全部贪心成三角形 123456789void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; map<int,int>mp; for(int i=1;i<=n;i++)mp[a[i]]++; int ans=0; for(auto...

Codeforces Round 960 (Div. 2)A-E A题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个mxmxmx。每次轮到自己操作的时候就选一个数组里的数，满足a[i]>=mxa[i]>=mxa[i]>=mx,然后令mx=a[i]mx=a[i]mx=a[i].双方轮流做直到一方无法操作，则另一方取胜。 Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。 12345678910void solve(){ cin>>n; map<int,int>mp; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)mp[a[i]]++; bool flag=0; ...