ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

Pollard Rho大质数分解学习笔记

目录问题流程代码生日悖论 end 问题给定n，要求对n质因数分解普通的试除法已经不能应用于大整数了，我们需要更快的算法流程大概就是找出\(n=c*d\) 如果\(c\)是素数，结束，不是继续递归处理。具...

Pollard Rho

2019-02-07

0 576

Miller_Rabin整理笔记

目录问题别的正事代码问题一个数到底是不是素数别的首先列一下我们可以求素数的东西根号暴力求 \(O(nloglogn)\)的埃氏筛 \(O(n)\)的欧拉筛还有我们要学习的Miller_Rabin算法对了，还...

Miller_Rabin 数学

2019-02-04

0 477

bsgs整理

目录 bsgs问题或 poj2417：概述代码 exbsgs 鸣谢 \(gzy gzy gzy\) bsgs问题或 poj2417：给定质数\(p\)，给定\(a\),\(b\),\((a,p)=1\) 求出最小的...

bsgs 数学

2019-02-04

0 554

一个数的(勾股数)组

大概一开始还以为是勾股的数组呢、、题目-->codeforces 求一个数所在的任意勾股数组算了，不胡扯扯了，还是看原博客吧应该是中国人写的，翻译友好 #include <iostream> #define ll long long using namespace s...

木得标签

2019-01-13

0 474

bzoj4709 柠檬单调栈,DP,斜率优化

目录思路错误代码 /* 思路 s是值等于a[i]的前缀和转移方程$f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1))$ 不难写出暴力方程(by wxyww) //@baol...

单调栈 DP 斜率优化

2019-01-13

0 574

bzoj 3437 小p的农场

bzoj 3437 小p的农场思路 \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{b[k]*(i-k)}+a[i])\) \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{(b[k]*i-b[k]*k)}+a[i])\) 再来前缀...

DP 斜率优化

2019-01-12

0 529

luoguP4072 [SDOI2016]征途

[SDOI2016]征途大体大概就是推推公式，发现很***的\(n^3\)DP get60 进一步我们发现状态不能入手，考虑优化转移套个斜率优化板子每一层转移来一次斜率优化思路先便便式子 \[s^2=m^{2}*\frac{\sum_{1}^{m}(a_{i}-\overline...

DP 斜率优化

2019-01-04

0 610

P2761 软件补丁问题

P2761 软件补丁问题思路貌似不用网络流，直接状态压缩用spfa跑最短路，直接判断是否能过位运算太渣了，WA了好几发代码 #include <bits/stdc++.h> using namespace std; const int N = 21, M = 101, ...

DP 状态压缩

2018-12-28

0 416

12.27 cf div3 解题报告

12.27 cf div3 解题报告 wxy.wxy,带上分拉，全场做了个无脑小白比赛场地 A： T1，跟着模拟就好了 B： sort一遍之后去除的数一定是a[1]或者a[n] 比较去除谁小就输出谁 C：他的二进制有多少个1 如果>k说明无解他的二进制位都放优先队列里 ...

CF

2018-12-28

0 504

网络流24题 P2754 [CTSC1999]家园

思路如图,建立分层图跑dinic 每次在残余网络里加边继续跑跑到ans>=k时候的i就是答案诶呀啊，忘记弄箭头了，最后一列是向上的箭头，不过聪明的你们应该没啥影响代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(i...

网络流最大流

2018-12-27

0 522