模板

模板：

矩阵快速幂：

//矩阵快速幂模板

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<&#39;0&#39;||ch>&#39;9&#39;)&&ch!=&#39;-&#39;)ch=getchar();
    if(ch==&#39;-&#39;)t=true,ch=getchar();
    while(ch<=&#39;9&#39;&&ch>=&#39;0&#39;)x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;


struct mat{
    ll a[110][110];//矩阵的大小 
};
mat in,out;//in输入的矩阵，out输出的矩阵 

mat mull(mat x, mat y){
    mat c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            c.a[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                c.a[i][j]=c.a[i][j]%mod+x.a[i][k]*y.a[k][j]%mod;

    return c;
} 

mat pow(mat x,ll y){
    mat ans;
    for(int i=1;i<=n;i++)//初始化成单位矩阵 就是对角线唯一，其余为零 
        ans.a[i][i]=1;
    while(y){
        if(y&1) ans=mull(ans,x);
        y>>=1;
        x=mull(x,x);        
    }
    return ans;    
}

int main(){
     sf("%lld%lld",&n,&m);
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
             sf("%lld",&in.a[i][j]);
     out=pow(in,m);
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
             if(j!=n)
            printf("%lld ",out.a[i][j]);
            else printf("%lld\n",out.a[i][j]);
    return 0;
}

最短路：
floyed：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<&#39;0&#39;||ch>&#39;9&#39;)&&ch!=&#39;-&#39;)ch=getchar();
    if(ch==&#39;-&#39;)t=true,ch=getchar();
    while(ch<=&#39;9&#39;&&ch>=&#39;0&#39;)x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()

//k是中间结点,i是起点,j是终点
void floyed(ll dp[][1010]){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dp[i][j]>dp[i][k]+dp[k][j]){
                    dp[i][j]=dp[i][k]+dp[k][j];
                }
            }
        }
    }
}
int main(){
    sf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dp[i][j]=inf;
        }
        dp[i][i]=0;
        //如果需要判断又没没有回路把这个删掉。 
    }
    for(int i=0;i<m;i++){
        sf("%d%d%d",&x,&y,&z);
        dp[x][y]=dp[y][x]=z;
    }
    floyed(dp);

    //可以判断是否存在负环
    for(int i=0;i<n;i++){
        if(mp[i][i]<0){
            flag=true;
        }
    }
    if(flag) cout<<"存在负环"<<endl;
    else cout<<"不存在负环"<<endl;
// cout<<mp[0][n-1]<<endl;
    return 0;
}

二分图：
二分图定义：简单的理解就是两个点集，其中在内部没有连接的边。
其充要条件是：图 G 中至少存在两个点，且图中所有回路的长度均为偶数。
完全二分图：其中一个点集中与另一点集中的点一定有相对应的边连接，也就是没有孤立的点。
完全二分图

二分图中匹配的概念：
在边集中，任意两条边都没有公共顶点。
二分图中最大匹配的概念：
在匹配的条件下，使得边集中边最多。
二分图中的完全匹配概念：
简单来说，对于一个二分图，左点集中的每一个点都与右点集的一个点匹配，或者右点集中的每一个点都与左点集的一个点匹配。
二分图中的完美匹配概念：
对于一个二分图，左点集与右点集的点数相同，若存在一个匹配，包含左点集、右点集的所有顶点，则称为完美匹配。
简单来说，对于一个二分图，左点集中的每一个点都与右点集的一个点匹配，并且右点集中的每一个点都与左点集的一个点匹配。
二分图的判定：

int n;//节点数
vector<int> G[N];//G[i]表示i节点邻接的点
int color[N];//color[i]=0,1,2 表i节点不涂颜色、涂白色、涂黑***ool bipartite(int u)//判断无向图是否可二分
{
    for(int i=0;i<G[u].size();i++)//枚举结点
    {
        int v=G[u][i];//相邻节点
        if(color[v]==color[u])//若两结点颜色相同，无法二分
            return false;
        if(!color[v])//若结点没涂颜色
        {
            color[v]=3-color[u];//改变结点颜色，使v的颜色与u的颜色对立
            if(!bipartite(v))//若点v不满足二分图话，则无法二分
                return false;
        }
    }
    return true;
}

二分图-匈牙利算法：
交替路：
从一个未匹配点出发经过未匹配边->未匹配点->未匹配边....形成的路径。
未匹配点，边的概念是在二分图匹配中如果匹配的两个点叫匹配点，其边就是匹配边，未匹配的点就是未匹配点，其边就是未匹配边。
定义：设 M 为二分图 G 已匹配边的集合，若 P 是图 G 中一条连通两个未匹配点的路径（起点在 X/Y 部，终点在 Y/X 部），且属 M 的边（匹配边）与不属 M 的边（非匹配边）在 P 上交替出现，则称 P 为相对 M 的一条增广路径。

由于增广路的第一条边是没有参与匹配的，第二条边参与了匹配，...，最后一条边没有参与匹配，并且起点和终点还没有被选择过，显然 P 有奇数条边。
其中这样理解第一条边不参加匹配，第二条边参加匹配，因为你要建增广路，方式是交替路的方式，所以说如果第一条边认为是匹配边的话第一天边就不能连起来，就像下面的9->4如果任务他是匹配边，这个边就建不上，之后如果认为4->8为未匹配边的话，4这个点已经是匹配点了，不能再连边了，所以之间把他认为是匹配边，儿8还是未匹配点，这样才能继续之后的建图。

简单来说，从一个未匹配点出发，走交替路，若途径另一未匹配点（除起点外），则这条交替路称为增广路。

如下图，左图中的一条增广路如右图所示，图中的匹配点均用红色标出
主图 解释

增广路的性质：

1，增广路的长度一定是一定是奇数，起点跟终点一定是分别属于两个点集。均未匹配。保证不成环。
2，未匹配边比匹配边多1，因为是未->已->未->......->已->未。
3,P 经过取反操作可以得到一个更大的匹配 M’。
4，M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。
3,4不是特别懂先放这吧

增广路定理：

由于增广路中间的匹配节点不存在其他相连的匹配边，因此交换增广路中的匹配边与非匹配边不会破坏匹配的性质。

由增广路性质可知，只要把增广路中的匹配边和非匹配边交换，交换后，图中的匹配边数目比原来多了 1 条。

故而，可以通过不停地找增广路来增加匹配中的匹配边和匹配点，找不到增广路时，即达到最大匹配，这就是增广路定理。
其实说简单点就是扩展路线。使得最长

匈牙利树

匈牙利树一般由 DFS 构造（类似于 DFS 树），其是从一个未匹配点出发进行 DFS（必须走交替路），直到不能再扩展为止。（达到最长路径）

如下图，通过左侧的二分图，进行 DFS 可以得到右侧的树，但这棵树存在一叶结点为非匹配点（7号），而匈牙利树要求所有叶结点均为匹配点，故这棵树不是匈牙利树。
图片说明 图片说明
但若原图中不含 7 号结点，那么从 2 号结点出发就会得到一棵匈牙利树，如下图
图片说明
图片说明
前导概念：
K-正则图：各顶点的度都是K的无向简单图。
最大匹配数：最大匹配的匹配边数
最大独立集数：选取最多的点集，使得点集中任意两点不相连。
最小点覆盖数：选取最少的点集，使得任意一条边至少有一个端点在点集中。
最大独立集数可以与最小点覆盖数比较理解
性质
最大匹配数=最小覆盖数
最大独立集数=顶点数-最大匹配数

最大匹配数/最小覆盖数

DFS:代码短容易理解 路线多时时间复杂度要高。

int n,m;
bool vis[N];//判断是否在交替路 
vector<int> G[N];//存边 
int link[N];//存连接点

bool dfs(ll x){
    for(int i=0;i<G[x].size();i++){
        int j=G[x][i];
        if(!vis[j]){
            vis[j]=1;
            if(link[j]==-1||dfs(link[j])){//如果是未匹配点，说明交替路是增广路
                link[j]=x;//交换路径
                return 1;                
            }
        }
    }
    return 0;    //不存在增广路，返回失败
} 

int print(){
    int ans=0;
    for(int i=1;i<=n;i++){//从左侧开始每个结点找一次增广路
        memset(vis,0,sizeof vis);
        if(dfs(i)) ans++;//找到一条增广路    
    }
    printf("%lld\n",ans);
}
int main (){
    while(~scanf("%lld%lld",&n,&m)){
        memset(link,-1,sizeof link);//全部初始化为未匹配点
        for(int i=0;i<N;i++)//每次清空 
            G[i].clear();
        while(m--){
            int l,r;
            scanf("%lld%lld",&l,&r);
            G[l].push_back(r);//建图 无向图 
            G[r].push_back(l);
        }
        print();//输出最大匹配数  
    }

    return 0;
}

BFS版本

int n,m;//左边点数,右边点数
int vis[N];//vis[i]表示是否在交替路中
int link[N];//存连接点
int pre[N];//存前驱结点
vector<int> G[N];//存边
queue<int> Q;
int hungarian(){
    memset(vis,-1,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(link,-1,sizeof(link));

    int ans=0;//记录最大匹配数
    for(int i=1;i<=n;i++){
        if(link[i]==-1){//若点未匹配
            pre[i]=-1;//没有前驱
            while(!Q.empty())//清空队列
                Q.pop();

            Q.push(i);
            bool flag=false;
            while(!Q.empty() && !flag){
                int x=Q.front();
                for(int j=0;j<G[x].size();j++){//对x的每个邻接点
                    if(!flag)//如果falg为真，则说明找到一未匹配点，不必继续下去
                        break;

                    int y=G[x][j];
                    if(vis[y]!=i){//不在交替路中
                        vis[y]=i;//存入交替路
                        Q.push(link[y]);//交换路径
                        if(link[y]>=0)//在已匹配点中
                            pre[link[y]]=x;
                        else {//找到未匹配点，交替路变增广路
                            flag=true;
                            int d=x;
                            int e=y;
                            while(d!=-1){//找到一个未匹配点，无法构成匈牙利树，让所有点不断的往回更新，重选下一个
                                int temp=link[d];
                                link[d]=e;
                                link[e]=d;
                                d=pre[d];
                                e=temp;
                            }
                        }
                    }
                }
                Q.pop();
            }
            if(link[i]!=-1)//统计最大匹配数
                ans++;
        }
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        printf("%d\n", hungarian());//输出最大匹配数
    }
    return 0;
}

最大独立集

int n,m;
bool vis[N];
int link[N];
bool G[N][N];
bool dfs(int x){
    for(int y=1;y<=m;y++){
        if(G[x][y]&&!vis[y]){
            vis[y]=true;
            if(link[y]==-1 || dfs(link[y])){
                link[y]=x;
                return true;
            }
        }
    }
    return false;
}
int hungarian(){
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){
        memset(link,-1,sizeof(link));
        memset(G,true,sizeof(G));

        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            G[x][y]=false;//不满足条件则连一条边
        }

        int mate=hungarian();//最大匹配数
        int res=n-mate;//最大独立集

        printf("%d\n",res);
    }
    return 0;
}

与最短路中的dj建图思路有些相似。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010,M = 1e5+10;
int n1,n2,m;
int h[N], e[M], ne[M], idx; //邻接表
int match[N];
bool st[N];

void add(int a,int b)//建图过程 
{
   e[idx] = b, ne[idx] = h[a], h[a] = idx++;     
} 

bool find(int x)
{
    for(int i = h[x]; i!=-1; i=ne[i]) // 遍历 x 男孩喜欢所有的女孩 
    {
          int j = e[i];
          if(!st[j]) // 如果st[j] = true 就不考虑这个女孩 
          {
             st[j] = true; // 标记 j 这个女孩，作用是如果这个女孩有男朋友，我们去找她男朋友有没有可能和别的女孩在一起时，就不需要考虑他现对象 j 了 
           if(match[j] == 0 || find(match[j]))// 女孩还没有对象或女孩的男朋友可以和其他喜欢的女生在一起 
           {
                match[j] = x;
                return true;
           }     
        }
    } 
    return false;
}

int main()
{
    int p;
    while(~scanf("%d",&p)){
        if(p==0) return 0;
        else cin>>n1>>n2;
        memset(h,-1,sizeof(h));
        memset(e,0,sizeof e);
        memset(ne,0,sizeof(ne));
        memset(match,0,sizeof match);
        for(int i=1;i<=p;i++)
        {
            int a, b;
            cin>>a>>b;
            add(a,b);
        }
        int res = 0; 
    for(int i=1; i<=n1;  i++) 
    {
        memset(st,false,sizeof(st)); 
        if(find(i)) res++;  
    } 
        cout << res<<endl;

    }

}

回文子序列

马拉车算法（吴老师的分析）

图片说明
• 对于p[i]，如果i<mx，设j是i关于id对称点，如图所示，则基于以下三
种情况，可以求出p[i]的值：
这一点的话细心分析！就可以理解了
• （1）以j为中心的回文串有一部分在以id为中心的回文串之外。因为mx
是以id为中心的最长回文的右边界，所以以i为中心的回文串不可能会
有字符在以id为中心的回文串之外；否则mx就不是以id为中心的最长回
文的右边界。所以，在这种情况下，p[i]=mx–i。
• （2）以j为中心的回文串全部在以id为中心的回文串的内部，则
p[i]=p[j]，而且p[i]不可能再增加。
• （3）以j为中心的回文串的左端正好与以id为中心的回文串的左端重合。
则p[i]=p[j]或p[i]=mx–i，并且p[i]还有可能会继续增加，即while
(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++;
• 所以，if (i < mx) p[i] = min(p[2 * id - i], mx- i)；其中2*id - i为i关于id的
对称点，即上面的j点，而p[j]表示以j为中心的最长回文半径，因此可
以利用p[j]来加快求解p[i]。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define M 1000010
using namespace std;
char str[M],str_new[2*M]; //原串和辅助串
int p[2*M],len; //p[i]表示以第 i 个字符为中心的最长回文的半径;字符串长度 len
void init() { //构造辅助串
    len=strlen(str); //计算字符串长度
    str_new[0]='@'; //辅助串的首字符
    str_new[1]='#'; //辅助串的间隔字符
    for(int i=0; i<len; i++) { //逐个字符地构造辅助串
        str_new[i*2+2]=str[i];
        str_new[i*2+3]='#';
    }
    str_new[len*2+2]='$'; //辅助串的尾字符
}
void Manacher() { //计算和输出最长回文的半径
    memset(p,0,sizeof(p)); //p[i]表示以第 i 个字符为中心的最长回文的半径，所有最长回文的半径初始化为 0
    int mx=0,di,ans=0; //以 id 为中心的最长回文的右边界为 mx，即 mx=id+p[id],mx 和最长回文的长度 ans 初始化为 0
    for(int i=1; i<len*2+2; i++) { //枚举每一个可能的中心字符
        if(mx>i) //根据 i 位置在 mx 位置的左侧还是右侧，调整以最长回文的半径的最长回文半径的初始值
            p[i]=min(mx-i,p[di*2-i]);
        else
            p[i]=1;
        for(; str_new[i-p[i]]==str_new[i+p[i]]; p[i]++); //以 i 位置为中心计算最长回文半径 p[i]
        if(p[i]+i>mx) //若以 i 为中心的右边界大于 mx，则中心 id 调整为 i，重新计算右边界 mx
            mx=p[i]+i,di=i;
        ans=max(ans,p[i]); //调整最长回文的半径
    }
    printf("%d\n",--ans); //输出最长回文的半径
}
int main() {
    int t=1; //测试用例编号初始化
    while(~scanf("%s",str)) { //反复输入字符串，直至输入"END"为止
        if(!strcmp(str,"END")) break;
        printf("Case %d: ",t++); //输出测试用例编号
        init(); //构造辅助串
        Manacher(); //计算和输出最长回文的半径
    }
}

hash 循环节

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
char s[1001000];/// 输入字符串 
int mod=10009;//模 
int len,k=131;///s的长度为len 
ll now;
ll hash[1001000];//hash[i] 存储以第i个字符为尾的前缀的散列值 
ll cal(int x,ll y)//计算和返回 y^x%mod 的结果值 
{
    ll re=1;//结果值初始化 
    while(x)//分析次幂x的没一个二进制位 
    {
        if(x&1) re=(re*y)%mod;//若当前位为1，则累乘当前位的权并取模 
        x>>=1;y=(y*y)%mod;        //次幂x右移一位 ，计算该位的权后并取模 
    }
    return re;                //返回结果值 
}
bool check(int x)            //若所有长度为x的相邻子串对应的散列函数值相等 ，则返回 true 负责返回false 
{
    ll cc=cal(x,(ll)k);    //计算 k^x%mod 
    for(int i=(x<<1);i<=len;i+=x) //搜索 字符i(2*x<i<len).若任意长度i的子串S_i-x+1...i的散列值不等于长度为x的前缀的散列值，则返回false，否则返回true 
    {
        if((hash[i]-(hash[i-x]*cc)%mod+mod)%mod!=hash[x])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    while(1)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        if(len==1 && s[1]=='.')
        {
            return 0;
        }
        for(int i=1;i<=len;i++)/// 计算所有前缀的散列值 
        {
            hash[i]=(hash[i-1]*k+s[i])%mod;
        }
        for(int i=1;i<=len;i++)    /// 枚举可能的子串长度 
        {
            if(len%i==0 && check(i)) //若s能过划分出长度i的子串且所有相邻子串的 
            {
                printf("%d\n",len/i);
                break;
            }
        }
    }
}

哈希模板

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const LL base1=131;
const LL base2=131;
const LL mod1=1e9+7;
const LL mod2=1e9+9;
char ss[10][10010];
struct node{
    LL hash1,hash2;
}a[10011];
LL make_hash1(char s[])
{
    LL ans=0;
    for(int i=0;i<strlen(s);i++)
     ans=(ans*base1+(LL)(s[i]))%mod1;
    return ans;
}
LL make_hash2(char s[])
{
    LL ans=0;
    for(int i=0;i<strlen(s);i++)
     ans=(ans*base2+(LL)(s[i]))%mod2;
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%s",ss[i]),a[i].hash1=make_hash1(ss[i]),a[i].hash2=make_hash2(ss[i]);

    cout<<"***********"<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<ss[i]<<" "<<a[i].hash1<<" "<<a[i].hash2<<endl;
    }
    return 0;
}//求子串哈希值hash=((hash[r]−hash[l−1]∗mod^(r−l+1))%mod+mod)%mod

KMP模板

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000005;
char s1[Maxn],s2[Maxn];
int l1,l2,fail[Maxn];
void Fail(){//构造fail数组
    for(int i=2,j=0;i<=l2;++i){
        while(j&&s2[j+1]!=s2[i])j=fail[j];
        if(s2[j+1]==s2[i])++j;
        fail[i]=j;
    }
}
void Match(){
    for(int i=1,j=0;i<=l1;++i){
        while(j&&s2[j+1]!=s1[i])j=fail[j];
        if(s2[j+1]==s1[i])++j;
        if(j==l2){
            //找到一个串，自行维护
            j=fail[j];
        }
    }
}
int main(){
    scanf("%s%s",s1+1,s2+1);
    l1=strlen(s1+1);
    l2=strlen(s2+1);
    Fail();
    Match();
    return 0;
}

凸包

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
const double pi=acos(-1.0);
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

struct point {
    double x,y;
    point(){

    }
    point(int a,int b){
        x=a;y=b;
    }
    point operator - (const point b)const {
        return point(x-b.x,y-b.y);
    }
    double operator * (const point b)const {
        return x*b.x+y*b.y;
    }
}point1;

point p[maxn];
int top=1,n,m,res[maxn];
bool cmp(point a,point b){
    if(a.x!=b.x) return  a.x<b.x;
    return a.y<b.y;
}
double dis(point a,point b){///求两点的距离
    return sqrt((a-b)*(a-b));
}
bool multi(point a,point b,point c){
    return (b.x - a.x)*(c.y - a.y) >= (c.x - a.x)*(b.y - a.y);
}
void Graham(int n){
    int i,len;
    sort(p,p+n,cmp);
    if(n==0) return; res[0]=0;
    if(n==1) return; res[1]=1;
    if(n==2) return; res[2]=2;
    for(int i=2;i<n;i++){
        while(top&&multi(p[i],p[res[top]],p[res[top-1]])) top--;
        res[++top]=i;
    }
    len=top;
    res[++top]=n-2;
    for(int i=n-3;i>=0;i--){
        while(top!=len&&multi(p[i],p[res[top]],p[res[top-1]])) top--;
        res[++top]=i;
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        sf("%lf%lf",&p[i].x,&p[i].y);
    Graham(n);
    double sum=0.0;
    for(int i=0;i<top-1;i++){
        sum+=fabs(p[res[i]].x*p[res[i+1]].y-p[res[i]].y*p[res[i+1]].x);
    }
    sum+=fabs(p[res[top-1]].x*p[res[0]].y-p[res[top-1]].y*p[res[0]].x);
    sum=sum/2;
    pf("%d\n",int(sum/50));
    return 0;
}

素数筛

int pri[N+9>>1],now;
bool vis[N+9];
void init(){
    for(int i=2;i<=N;i++){
        if(!vis[i])pri[++now]=i;
        for(int j=1;j<=now&&pri[j]*i<=N;j++){
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
}
全部评论

相关推荐

01-22 16:54
清华大学 Java
工作后依然坚持刷抖音
工作后依然坚持刷抖音，对我来说不是“逃避”，而是一种爱好——像看书、听歌、打游戏一样，是一天忙碌之后的放松方式。白天在会议、代码、任务之间切换，脑子里充满了逻辑和计划。晚上刷抖音时，短短几分钟就能看到各种有趣的生活片段、创意视频和搞笑段子，那种轻松的节奏像是给紧绷的神经按下了“暂停键”。它不是浪费时间，而是一种能让人快速恢复情绪的方式。更重要的是，抖音带来的并不只是消遣。很多时候我会在视频里看到新的想法、新的兴趣，甚至是一些实用的生活技巧。它像一扇窗口，让我看到不同的人和不同的世界，也让生活在忙碌之外有了更多的色彩。当然，爱好也需要边界。工作之余的刷抖音，是一种“有节制的享受”，而不是无意识的...
上班以后，你还有哪些坚持...
点赞 评论 收藏
分享
头像
01-20 10:50
蚌埠坦克学院 嵌入式软件开发
让AI写一个Linux操作系统属实太为难了
最近我突然想起一个问题：让&nbsp;AI&nbsp;写一个&nbsp;Linux&nbsp;操作系统，这事儿是不是太难了？说出来可能有点好笑，但确实是我自己提的。那一瞬间我也觉得自己有点冲动——好像只要把“写一个操作系统”丢给&nbsp;AI，就能轻松实现一样。可是想想就知道不现实。Linux&nbsp;不是一个简单的程序，而是一整套复杂的系统：内核、驱动、文件系统、网络、调度……每一部分都要精细设计、反复测试。更别提它要在真实硬件上稳定运行，哪怕一个小错误都会崩溃，甚至造成数据损坏。AI&nbsp;可以帮你写示例、解释原理、生成代码片段，但它无法替代长期的工程实践和硬件调试。就像让&nbsp;AI&nbsp;去盖一栋楼，AI可以画图、出方案，但真正动工、验收、修复问题，还得靠人...
你给AI提过哪些离谱的需...
点赞 评论 收藏
分享
01-14 21:22
字节跳动_后端开发(实习员工)
点赞 评论 收藏
分享
01-20 16:25
门头沟学院 Java
看不惯的一直都没改变
一、学历至上：能力被学历&nbsp;“踩在脚下”在这个竞争激烈的求职市场，学历似乎成了一道难以逾越的鸿沟。“本科及以上学历”“985、211&nbsp;院校优先”&nbsp;这样的字眼在招聘信息中随处可见，仿佛学历就是衡量一个人能力的唯一标准&nbsp;。我有个朋友，大专学的是计算机专业，在校期间就参与了好几个项目，技术能力相当出色。毕业后，他投递了一家知名互联网公司的程序员岗位，满心期待能凭借自己的实力获得认可。可仅仅因为学历是大专，连简历筛选这一关都没过。而那些学历更高但实践经验和技术能力远不如他的求职者，却轻松获得了面试机会。这种学历歧视真的合理吗？一个岗位，最重要的难道不是能否胜任工作吗？很多专科生、普通院校的学生，他们在大...
找工作以来，你最看不惯_...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 除了Java，最推荐学什么技术？ #
1714次浏览 55人参与
# AI时代的工作 VS 传统时代的工作，有哪些不同？ #
2085次浏览 71人参与
# 你的landing期是如何度过的？ #
2158次浏览 42人参与
# 滴滴求职进展汇总 #
299062次浏览 2445人参与
# 秋招报数：你投了多少家公司？ #
148345次浏览 946人参与
# 机械制造面试点评 #
84007次浏览 471人参与
# 你觉得早上几点上班合适？ #
94315次浏览 353人参与
# 机械人与华为的爱恨情仇 #
147203次浏览 1030人参与
# 机械只有转码才有出路吗？ #
159401次浏览 1653人参与
# 我和mentor的爱恨情仇 #
102881次浏览 925人参与
# 你觉得mentor喜欢什么样的实习生 #
45509次浏览 989人参与
# 如何提高实习转正率？ #
80877次浏览 488人参与
# 实习期间如何提升留用概率？ #
231079次浏览 1788人参与
# 你觉得什么岗位会被AI替代 #
35302次浏览 236人参与
# 聊聊你的被动加班经历 #
8504次浏览 101人参与
# 秋招提前批，你开始投了吗 #
705835次浏览 8437人参与
# 面试常问题系列 #
268816次浏览 4687人参与
# 京东求职进展汇总 #
1138650次浏览 8519人参与
# 牛客十周岁生日快乐 #
207843次浏览 1937人参与
# 为了秋招你都做了哪些准备？ #
31500次浏览 532人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务