二分查找
l 对于满足条件最左边
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
l 对于满足条件最右边
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
}
l 对于不满足条件最左边
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}
else{
r=mid;
}
}
l 对于不满足条件最右边
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)){
r=mid-1;
}
else{
l=mid;
}
}
求凸包模板
const int maxn = 50010;
struct Point {
int x, y;
bool operator < (Point const& rhs) const {//重载为类的成员函数的时候，形参时运算符//的右操作数
return (x < rhs.x) || (x == rhs.x && y < rhs.y);
}
}p[maxn], ch[maxn];
int Cross(Point const& O, Point const& A, Point const& B)
{
int xoa = A.x - O.x;
int xob = B.x - O.x;
int yoa = A.y - O.y;
int yob = B.y - O.y;
return xoa * yob - xob * yoa;
}
double Dis(Point const& A, Point const& B)
{
double xoa = A.x - B.x;
double xob = A.y - B.y;
return sqrt(xoa * xoa + xob * xob);
}
int Andrew(Point p[], int n, Point ch[])
{
sort(p, p + n);
int m = 0;
for (int i = 0; i < n; i++) { //下凸包
while (m > 1 && Cross(ch[m - 2], ch[m - 1], p[i]) < 0) m--;
ch[m++] = p[i];
}
int k = m;
for (int i = n - 2; i >= 0; i--) { //上凸包
while (m > k && Cross(ch[m - 2], ch[m - 1], p[i]) < 0) m--;
ch[m++] = p[i];
}
if (n > 1) m--;
return m;
}
int main()
{
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
int m = Andrew(p, n, ch); //求凸包
………………
}
return 0;
}
Kmp
void getnext(char *p)
{
int lenp=strlen(p);
nextt[0]=-1;
int k=-1;
int j=0;
while(j<lenp-1)
{
//p[k]表示前缀，p[j]表示后缀（并没有“真”！）
if(k==-1||p[j]==p[k])//j在这
{
j++;//j+1在这
k++;//k=k+1
//---->若p[k]=p[j]，则next[j+1]=next[j]+1;
//下一个位置的next
if(p[j]!=p[k])//当p[k]！=p[j]时，与主串不匹配时可以返回到这
{
nextt[j]=k;
}
else//当p[j]=p[k]时与主串匹配时你在j位置不匹配匹配串返回这里当前
//还是 不能与主串匹配，然后还是要返回next[]即next[next[k]]
nextt[j]=nextt[k];//优化了
}
else
{
k=nextt[k];
}
}
return;
}
int KMP(char *s,char *p)
{
int i=0;
int j=0;
int lens=strlen(s);
int lenp=strlen(p);
while(i<lens&&j<lenp)
{
//如果j=-1(表示第一次开始或者重新开始匹配)，即失配于首字符
if(j==-1||s[i]==p[j])
{
j++;
i++;
}
else
{
//如果j!+-1,或者当前匹配失败 ，则
j=nextt[j]; // i不变，j=next[j]
}
}
if(j==lenp)
return 1;//匹配成功
else
return 0;
}
欧拉筛
bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数
void euler()
{
memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
isprime[1] = false; // 1不是素数
for(int i = 2; i <= n; ++i) // i从2循环到n（外层循环）
{
if(isprime[i]) prime[++cnt] = i;
// 如果i没有被前面的数筛掉，则i是素数
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
// 筛掉i的素数倍，即i的prime[j]倍
// j循环枚举现在已经筛出的素数（内层循环）
{
isprime[i * prime[j]] = false;
// 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
if(i % prime[j] == 0) break;
// 最神奇的一句话，如果i整除prime[j]，退出循环
// 这样可以保证线性的时间复杂度
}
}
}
Miller Rabin素数判定
ll qmul(ll a,ll b,ll mod)//快速乘
{
ll c=(ld)a/mod*b;
ll res=(ull)a*b-(ull)c*mod;
return (res+mod)%mod;
}
ll qpow(ll a,ll n,ll mod)//快速幂
{
ll res=1;
while(n)
{
if(n&1) res=qmul(res,a,mod);
a=qmul(a,a,mod);
n>>=1;
}
return res;
}
bool MRtest(ll n)//Miller Rabin Test
{
if(n<3||n%2==0) return n==2;//特判
ll u=n-1,t=0;
while(u%2==0) u/=2,++t;
ll ud[]={2,325,9375,28178,450775,9780504,1795265022};
for(ll a:ud)
{
ll v=qpow(a,u,n);
if(v==1||v==n-1||v==0) continue;
for(int j=1;j<=t;j++)
{
v=qmul(v,v,n);
if(v==n-1&&j!=t){v=1;break;}//出现一个n-1，后面都是1，直接跳出
if(v==1) return 0;//这里代表前面没有出现n-1这个解，二次检验失败
}
if(v!=1) return 0;//Fermat检验
}
return 1;
}
大数因数分解Pollard_rho
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
const int times = 50;
int number = 0;
map<long long, int>m;
long long Random( long long n )
{
return ((double)rand( ) / RAND_MAX*n + 0.5);
}
long long q_mul( long long a, long long b, long long mod ) //快速乘法取模
{
long long ans = 0;
while(b)
{
if(b & 1)
{
ans += a;
}
b /= 2;
a = (a + a) % mod;
}
return ans;
}
long long q_pow( long long a, long long b, long long mod ) //快速乘法下的快速幂，叼
{
long long ans = 1;
while(b)
{
if(b & 1)
{
ans = q_mul( ans, a, mod );
}
b /= 2;
a = q_mul( a, a, mod );
}
return ans;
}
bool witness( long long a, long long n )//miller_rabin算法的精华
{
long long tem = n - 1;
int j = 0;
while(tem % 2 == 0)
{
tem /= 2;
j++;
}
long long x = q_pow( a, tem, n ); //得到a^(n-1) mod n
if(x == 1 || x == n - 1) return true;
while(j--)
{
x = q_mul( x, x, n );
if(x = n - 1) return true;
}
return false;
}
bool miller_rabin( long long n ) //检验n是否是素数
{
if(n == 2)
return true;
if(n < 2 || n % 2 == 0)
return false;
for(int i = 1; i <= times; i++) //做times次随机检验
{
long long a = Random( n - 2 ) + 1; //得到随机检验算子 a
if(!witness( a, n )) //用a检验n是否是素数
return false;
}
return true;
}
long long gcd( long long a, long long b )
{
if(b == 0)
return a;
return gcd( b, a%b );
}
long long pollard_rho( long long n, long long c )//找到n的一个因子
{
long long x, y, d, i = 1, k = 2;
x = Random( n - 1 ) + 1;
y = x;
while(1)
{
i++;
x = (q_mul( x, x, n ) + c) % n;
d = gcd( y - x, n );
if(1<d&&d<n)
return d;
if(y == x)//找到循环，选取失败，重新来
return n;
if(i == k) //似乎是一个优化，但是不是很清楚
{
y = x;
k <<= 1;
}
}
}
void find( long long n, long long c )
{
if(n == 1)
return;
if(miller_rabin( n ))
{
m[n]++;
number++;
return;
}
long long p = n;
while(p >= n)
p = pollard_rho( p, c-- );
find( p, c );
find( n / p, c );
}
int main( )
{
long long tar;
while(cin >> tar)
{
number = 0;
m.clear();
find( tar, 2137342 );
printf( "%lld = ", tar );
if(m.empty())
{
printf( "%lld\n", tar );
}
for(map<long long, int>::iterator c = m.begin(); c != m.end();)
{
printf( "%lld^%d", c->first, c->second );
if((++c) != m.end())
printf( " * " );
}
printf( "\n" );
}
return 0;
}
马拉车算法
char s[maxn],ss[maxn];
int p[maxn];
int len,center;
int cnt=1;
void init(){
memset(s,0,sizeof s);
cnt=1,s[0]='@';
int len=strlen(ss);
for(int i=0;i<len;i++){
s[cnt++]='#';
s[cnt++]=ss[i];
}
s[cnt++]='#';
}
void manacher(){
p[0]=center=0;
int maxright=0;
for(int i=1;i<cnt;i++){
if(i<maxright) p[i]=min(maxright-i,p[2*center-i]);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(p[i]+i>maxright){
maxright=p[i]+i;
center=i;
}
}
}
倍增求LCA
int LCA(int x,int y){
if(dep [x]>dep[y])swap(x,y);
int k=dep [y]-dep [x];
for(int i=Log2[k];i >0;i--){
if((k>>i)&1)y=f[i][y];
}
if (x =y)return x;
for(int i Log2[n];i >0;i--){
if(f [i][x]!f[i][y])x=f[i][x],y=f[i][y]
}
return f [O][x];
}