头像

明天也摆烂




离线:16小时前


最近来访(38)
用户头像
程聿书
用户头像
Liuyz.
用户头像
傻强
用户头像
风间澈
用户头像
你与星河皆逝
用户头像
呓念
用户头像
不好好学习请把我丢掉
用户头像
是小张张呀
用户头像
冰冷酒
用户头像
一缕清风
用户头像
无疾而终的春三月
用户头像
lsh_5
用户头像
不掉头发_
用户头像
dnks
用户头像
Apurple
用户头像
Segment_Tree

活动打卡代码 AcWing 907. 区间覆盖

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;

PII edge[N];
int n,s,t;

int main()
{
    scanf("%d%d%d",&s,&t,&n);

    int a,b;
    for(int i=0;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        edge[i]={a,b};
    }
    sort(edge,edge+n);

    int ans=0;
    bool flag=false;
    for(int i=0;i<n;++i)
    {
        int j=i,r=-2e9;
        while(j<n&&edge[j].first<=s)//找到满足<=s的最大的r
        {
            r=max(edge[j].second,r);
            j++;
        }
        if(r<s){ans=-1;break;}

        ans++;
        if(r>=t){flag=true;break;}//标记可以完成s->t

        s=r;
        i=j-1;//while中j<n的循环里面存在j++,因此i=j-1;
    }
    if(flag==false)ans=-1;
    printf("%d",ans);

    return 0;
}


活动打卡代码 AcWing 906. 区间分组

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;

int n;
map<int,int>mp;

int main()
{
    scanf("%d",&n);
    int a,b;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&a,&b);
        mp[a]++;
        mp[b+1]--;//差分做法
    }

    int s=0;
    int ans=0;
    for(auto i:mp)
    {
        s+=i.second;//差分求和等于i.first所在位置的重叠的边数
        ans=max(ans,s);
    }
    printf("%d",ans);

    return 0;
}



左端点算法

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int n;
PII a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]={x,y};
    }
    sort(a,a+n);
    int res=0;
    int r=-2e9;
    for(int i=0;i<n;++i)
    {
        if(a[i].first>r)
        {
            res++;
            r=a[i].second;
        }
        else if(a[i].second<r)
        {
            r=a[i].second;
        }
    }
    printf("%d",res);
    return 0;
}

右端点算法

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int n;
PII a[N];

bool cmp(PII x,PII y)
{
    return x.second<y.second;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]={x,y};
    }
    sort(a,a+n,cmp);
    int res=0;
    int r=-2e9;
    for(int i=0;i<n;++i)
    {
        if(a[i].first>r)
        {
            res++;
            r=a[i].second;
        }
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

左端点算法

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int n;
PII a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]={x,y};
    }
    sort(a,a+n);
    int res=0;
    int r=-2e9;
    for(int i=0;i<n;++i)
    {
        if(a[i].first>r)
        {
            res++;
            r=a[i].second;
        }
        else if(a[i].second<r)
        {
            r=a[i].second;
        }
    }
    printf("%d",res);
    return 0;
}

右端点算法

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int n;
PII a[N];

bool cmp(PII x,PII y)
{
    return x.second<y.second;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]={x,y};
    }
    sort(a,a+n,cmp);
    int res=0;
    int r=-2e9;
    for(int i=0;i<n;++i)
    {
        if(a[i].first>r)
        {
            res++;
            r=a[i].second;
        }
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=21,M=1<<N;

int f[M][N];//M:二进制数,1表示经过,0表示未经过,N表示终点,因此M的第i位必须为1
int n;
int w[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            scanf("%d",&w[i][j]);

    memset(f,0x3f,sizeof f);
    f[1][0]=0;
    for(int i=0;i<1<<n;++i)
        for(int j=0;j<n;++j)
            if(i>>j&1)//如果i的第j位是0,则说明最后没经过j,不能继续
                for(int k=0;k<n;++k)
                    if((i-(1<<j))>>k&1)//同上
                f[i][j]=min(f[i-(1<<j)][k]+w[k][j],f[i][j]);
    printf("%d",f[(1<<n)-1][n-1]);
    return 0;
}



朴素写法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=12,M=1<<N;
int n,m;
long long f[N][M];
bool st[M];
int main()
{
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
        for(int i=0;i<1<<n;++i)
        {
            int cnt=0;//记录二进制中0的个数
            st[i]=true;
            for(int j=0;j<n;++j)
            {
                if((i>>j)&1)//i的二进制的第j位是否为1
                {

                    if(cnt&1)st[i]=false;//如果0是连续奇数个,竖放不合法
                    cnt=0;
                }
                else cnt++;
            }
            if(cnt&1)st[i]=false;//如果0是连续奇数个,竖放不合法
        }

        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=1;i<=m;++i)
            for(int j=0;j<1<<n;++j)
                for(int k=0;k<1<<n;++k)
                    if(!(j&k)&&st[j|k])
                        f[i][j]+=f[i-1][k];
        printf("%lld\n",f[m][0]);
    }
    return 0;
}

用vector保留合法方案的优化方法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N=12,M=1<<N;
int n,m;
long long f[N][M];
bool st[M];
vector<int>state[M];
int main()
{
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
        for(int i=0;i<1<<n;++i)
        {
            int cnt=0;//记录二进制中0的个数
            st[i]=true;
            for(int j=0;j<n;++j)
            {
                if((i>>j)&1)//i的二进制的第j位是否为1
                {

                    if(cnt&1)st[i]=false;//如果0是连续奇数个,竖放不合法
                    cnt=0;
                }
                else cnt++;
            }
            if(cnt&1)st[i]=false;//如果0是连续奇数个,竖放不合法
        }

       for(int i=0;i<1<<n;++i)//用vector保留合法的方案数
       {
           state[i].clear();//清空上回循环??????
           for(int j=0;j<1<<n;++j)
           {
               if(!(j&i)&&st[j|i])
               state[i].push_back(j);
           }
       }

        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=1;i<=m;++i)
            for(int j=0;j<1<<n;++j)
                for(auto k:state[j])
                    f[i][j]+=f[i-1][k];
        printf("%lld\n",f[m][0]);
    }
    return 0;
}



#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=6010;

int happy[N];
int h[N],e[N],ne[N],idx;
int n;
int f[N][2];
bool father[N];

void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

void dfs(int u)
{
    f[u][1]=happy[u];//取本身的happy值

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];

        dfs(j);

        f[u][1]+=f[j][0];//下层的本身不取happy的都可以加
        f[u][0]+=max(f[j][0],f[j][1]);//加下一层每个节点的最大值,无论本身是否去happy值
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&happy[i]);

    memset(h,-1,sizeof h);//初始化!!!!!!!!!
    int a,b;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        father[a]=true;
        add(b,a);
    }

    int root=1;
    while(father[root])root++;
    dfs(root);

    printf("%d",max(f[root][0],f[root][1]));

    return 0;
}


活动打卡代码 AcWing 901. 滑雪

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N=310;

int n,m;
int g[N][N];
int f[N][N];

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int dp(int a,int b)
{
    int &v=f[a][b];//v相当于f[a][b]且随着v的改变而改变(cpp独有)
    if(v!=-1)return v;//已经算过,防止再次计算

    v=1;//把没有算过的f[a][b]赋值一开始能滑过本身的那一步--1
    for(int i=0;i<4;++i)
    {
        int x=a+dx[i],y=b+dy[i];
        if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]<g[a][b])
        {
            v=max(dp(x,y)+1,v);
        }
    }
    return v;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            scanf("%d",&g[i][j]);

    memset(f,-1,sizeof f);
    int res=1;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            res=max(res,dp(i,j));

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



#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=510,M=100010;

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])//遍历此男子的所有有好感的女子
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=true;
            if(!match[j]||find(match[j]))//女子目前没对象或女子现对象能找到下家
                {
                    match[j]=x;//女子改对象
                    return true;
                }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d%d",&n1,&n2,&m);

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }

    int res=0;
    for(int i=1;i<=n1;++i)
    {
        memset(st,0,sizeof st);//下个男子得重新遍历妹子
        if(find(i))res++;
    }
    printf("%d",res);
    return 0;
}



#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=100010,M=200010;

int n,m;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])//遍历相邻的节点
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c))return false;//染成和c节点不同的数(3-c),如果递归过程矛盾就false
        }
        else if(color[j]==c)return false;//如果相邻节点颜色和u点相同,返回false
    }
    return true;
}


int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }

    bool flag=true;
    for(int i=1;i<=n;++i)//遍历所有需要判断的节点
    {
        if(!color[i])//如果没有染过颜色就进行染色
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
    }
    if(!flag)puts("No");
    else puts("Yes");
    return 0;
}