#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 907. 区间覆盖
活动打卡代码
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;
}
活动打卡代码
AcWing 908. 最大不相交区间数量
左端点算法
#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;
}
活动打卡代码
AcWing 291. 蒙德里安的梦想
朴素写法
#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;
}
活动打卡代码
AcWing 285. 没有上司的舞会
#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;
}
活动打卡代码
AcWing 861. 二分图的最大匹配
#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;
}
活动打卡代码
AcWing 860. 染色法判定二分图
#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;
}
