string转int

string s="1234";
int x1=stoi(s); // x1=1234
int x2=atoi(s.c_str()); // x2=1234

int转string

int x=1234;
string s=to_string(x); // s="1234"

x|tmp\==0 实际上是 x|(tmp==0)
应该写成(x|tmp)==0

long long范围[-2^63^,2^63^-1] (最大比9e18大一点)
unsigned long long范围[0,2^64^-1] (最大比18*1e18大一点)
int范围[-2^31^,2^31^-1]

double类型 0/负数会输出-0,这点注意特判(int类型没关系)

浮点数的表示里会有负零,负零被表示为指数为编码内任意合法数值、所有系数均为零、符号比特为一的数。和正零等效。
在这里插入图片描述

输出格式如果是比值的,注意特判0或者1

输出5/5 应该输出1
输出0/12 应该输出0

如果要搞long long的最大值,用位运算的话注意写法
内部全部要用long long

ll x=((ll)1<<63)-1;
或者ll x=(1ll<<63)-1;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll x=((ll)1<<63)-1;
    printf("%lld\n",x);
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll ans = -1;
    ans += pow(2,63);
    printf("%lld\n", ans);//9223372036854775807

    ans = -1;
    ans += (1LL<<63);
    printf("%lld\n", ans);//9223372036854775807

    ans = -1;
    ans += (1<<63);
    printf("%lld\n", ans);//-1
    return 0;
}

我们可以看到同样是加上2^63^ 如果用位移运算符,1后面没有加LL,那会得出一个错误的答案(-1)。

在得到的结果会爆int的时候,记得用LL


i j 下标嵌套混乱

@[TOC]

stl内置函数__builtin_popcount()返回一个整数的二进制中1的个数

__builtin_popcount(arr[i]);

简写

string s(50,'a');

等价于:

for(int i=1;i<=50;i++)
    s+='a';

离散化

for(int i=1;i<=n;i++)
{
    cin>>a[i];
    t[i]=a[i];//t是a的备份
}
stable_sort(t+1,t+n+1);
for(int i=1;i<=n;i++)
{
    int k=lower_bound(t+1,t+n+1,a[i])-t;
    a[i]=k;//a是离散化后的数组
}

计算几何

判断点P是否在三角形ABC内部(在边上也算)。
题目:三角魔法

bool istr(int x1,int y1,int x2,int y2,int x3,int y3) // 判断三点是否共线
{
    ll a=(x3-x1)*(y2-y1);
    ll b=(x2-x1)*(y3-y1);
    return a!=b; // 不共线,三点可组成三角形
}
bool judge(int x1,int y1,int x2,int y2,int x3,int y3,int x,int y) 
// 判断(x,y)是否在其他三点的内部
// A(x1,y1) B(x2,y2) C(x3,y3) P(x,y)
// AB=(x2-x1,y2-y1)
// AC=(x3-x1,y3-y1)
// BC=(x3-x2,y3-y2)
// AP=(x-x1,y-y1)
// BP=(x-x2,y-y2)
// CP=(x-x3,y-y3)
{
    ll d=(y-y1)*(x2-x1)-(y2-y1)*(x-x1); // AB×AP
    ll q=(y3-y1)*(x2-x1)-(y2-y1)*(x3-x1); // AB×AC
    if(d*q<0) return false; // 两个叉积异号,说明P,C不在AB的同一侧,那么P在外部
    d=(y-y2)*(x3-x2)-(y3-y2)*(x-x2);  // BC×BP
    q=(y1-y2)*(x3-x2)-(y3-y2)*(x1-x2); // BC×BA
    if(d*q<0) return false; // 两个叉积异号,说明P,A不在BC的同一侧,那么P在外部
    d=(y-y3)*(x1-x3)-(y1-y3)*(x-x3); // CA×CP
    q=(y2-y3)*(x1-x3)-(y1-y3)*(x2-x3); // CA×CB
    if(d*q<0) return false; // 两个叉积异号,说明P,B不在CA的同一侧,那么P在外部
    return true;
}

线段树

洛谷 P3372 【模板】线段树 1
区间修改 区间维护和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N];
ll tr[4*N],add[4*N];
void pushup(int i)
{
    tr[i]=tr[2*i]+tr[2*i+1];
}
void build(int i,int l,int r)
{
    add[i]=0;
    if(l==r)
    {
        tr[i]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    pushup(i);
}
void Add(int i,int l,int r,ll k) // 第i块区间标记加上k
{
    add[i]+=k;
    tr[i]+=(r-l+1)*k;
}
void pushdown(int i,int l,int r) // 下传一层
{
    if(!add[i])return;
    int mid=(l+r)/2;
    Add(2*i,l,mid,add[i]);
    Add(2*i+1,mid+1,r,add[i]);
    add[i]=0;
}
void update(int i,int l,int r,int x,int y,ll k)
{
    if(l>=x&&r<=y)return Add(i,l,r,k);
    pushdown(i,l,r);
    int mid=(l+r)/2;
    if(x<=mid)update(2*i,l,mid,x,y,k);
    if(y>mid)update(2*i+1,mid+1,r,x,y,k);
    pushup(i);
}
ll query(int i,int l,int r,int x,int y)
{
    if(l>=x&&r<=y)return tr[i];
    pushdown(i,l,r);
    int mid=(l+r)/2;
    ll ans=0;
    if(x<=mid)ans+=query(2*i,l,mid,x,y);
    if(y>mid)ans+=query(2*i+1,mid+1,r,x,y);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m,x,y,opt;
    ll k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>x>>y>>k;
            update(1,1,n,x,y,k);
        }
        else
        {
            cin>>x>>y;
            ll ans=query(1,1,n,x,y);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

P3373 【模板】线段树 2
如果区间更新是乘法,记得Mul函数中还要更新add[i]懒标记。

n!阶乘的位数

#include <bits/stdc++.h>
#define e 2.7182818284
#define p acos(-1.0)
using namespace std;
int main()
{
    int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        printf("%d\n",(int)(log10(2*p*n)*0.5+n*log10(n/e))+1);
    }
    return 0;
}

图论——非负权单源最短路(dijkstra算法)

LOJ #119. 非负权单源最短路
注意重载运算符的写法,要写const;距离数组dis要开long long,long long最大值(1ll<<63)-1;数组开1e3不够

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,M=1e5+10,inf=(1ll<<63)-1;
int n,m,s,t,x,y,z;
ll dis[N]; // dis[i]存起点到i的最短距离
bool vis[N]; // vis[i]标记i点是否已经求出最短距离
int head[N],cnt;
struct edge
{
    int to,w,next;
}e[M<<1];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z)
{
    add(x,y,z);
    add(y,x,z);
}
struct node
{
    int u; // u是点的坐标
    ll d; // d是到当前点的最短距离
    bool operator < (const node &s) const // 重载运算符,一定要写const
    {
        return d>s.d; // d小的优先
    }
};
ll dijkstra(int s,int t) // 起点s 终点t
{
    priority_queue<node,vector<node> >q; // 优先队列
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    memset(vis,0,sizeof(vis));
    q.push({s,0});
    dis[s]=0;
    while(!q.empty())
    {
        node tmp=q.top();q.pop();
        int u=tmp.u;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
    return dis[t];
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
    }
    printf("%lld\n",dijkstra(s,t));
    return 0;
}