蓝桥31天|今天3道题Day18|C++

#include 
using namespace std;
const int N=5e5+100;
const int M=5e6+100;
int prime[N],cnt;
bool st[M];
bool isprime(){
   for(int i=2;i 
#include 
using namespace std;
int main()
{
  cout<<1299743;
  return 0;
}
 
2.分考场 

 原题链接
 注意剪枝，不然会超时
 
#include 
using namespace std;
const int N=110;
bool g[N][N];
int room[N][N];
int ans=N;
int n,m;
void dfs(int x,int sum){
    if(sum>=ans)return;//剪枝，不剪会超时
    if(x>n){
        ans=min(sum,ans);
        //printf("%dn",sum);
        return;
    }
   

    for(int i=1;i<=sum;i++){
        int j=0;
        while(room[i][j]&&!g[x][room[i][j]])j++;
        //找到一个空位且与该教室人没有关系
        if(room[i][j]==0){
            room[i][j]=x;
            dfs(x+1,sum);
            room[i][j]=0;
        }

    }

    room[sum+1][0]=x;
    dfs(x+1,sum+1);
    room[sum+1][0]=0;

}
int main(){

    scanf("%d%d",&n,&m);
    for(int i=0;i 
3.合根植物 

 
 
 原题链接
 法一：当作连通块问题
 
#include 
#include 
using namespace std;
typedef pair PII;
#define x first
#define y second
const int N=1e3+10;
bool g[N][N];
bool vis[N][N];
int m,n,k;
long long ans;
queueq;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void bfs(int x,int y){
   q.push({x,y});
   vis[x][y]=true;
   while(!q.empty()){
    PII t=q.front();
    q.pop();
    //printf("t.x==%d t.y==%dn",t.x,t.y);
    for(int i=0;i<4;i++){
        int sx=t.x+dx[i],sy=t.y+dy[i];

        if(sx>=1&&sx<=m&&sy>=1&&sy<=n&&!vis[sx][sy]&&g[(t.x-1)*n+t.y][(sx-1)*n+sy]){
            q.push({sx,sy});
            vis[sx][sy]=true;
        }
    }
   }
   return;
}
int main(){
    scanf("%d%d%d",&m,&n,&k);
    for(int i=0;i 

 运行错误：
 运行时错误，非法的内存访问，数组越界，指针漂移，调用禁用的系统函数。
 Segmentation fault:
 段错误，检查是否有数组越界，指针异常，访问到不应该访问的内存区域
 
原因是出现了非法内存访问 a,b的值可能远大于1e3
 更改g[N][N]为vector[M],新增check函数
 
#include 
#include 
using namespace std;
typedef pair PII;
#define x first
#define y second
const int N=1e3+10;
const int M=1e6+10;
//bool g[N][N];
vectorg[M];
bool vis[N][N];
int m,n,k;
long long ans;
queueq;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
bool check(int nx,int ny){
    int len=g[nx].size();
    for(int i=0;i=1&&sx<=m&&sy>=1&&sy<=n&&!vis[sx][sy]&&check(nx,ny)){
            q.push({sx,sy});
            vis[sx][sy]=true;
        }
    }
   }
   return;
}
int main(){
    scanf("%d%d%d",&m,&n,&k);

    for(int i=0;i 
法二：并查集
 
#include 
using namespace std;
const int N=1e6+10;
int p[N];
bool vis[N];
int findp(int x){
    if(p[x]!=x)p[x]=findp(p[x]);
    return p[x];
}
int main(){
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=n*m;i++){
        p[i]=i;
    }
    for(int i=0;i 
4.大胖子走迷宫 

 
 
 待补