当前位置: 首页 > news >正文

建设网站要什么手续信息发布推广平台

建设网站要什么手续,信息发布推广平台,wordpress 千万数据,成都设计电商网站样例1输入: 3 3 10 1 52 20 30 1 1 2 3 样例1输出: 3 样例2输入: 4 3 1 1 1 1 1 30 80 2 1 1 1 100 样例2输出: 10 分析:这道题目我们直接从(1,1)点开始进行dfs搜索即可,但是需要注意一点的是我们搜…

 样例1输入:

3 3
10 1 52
20 30 1
1 2 3

样例1输出:

3

样例2输入:

4 3
1 1 1 1
1 30 80 2
1 1 1 100

样例2输出:

10

分析:这道题目我们直接从(1,1)点开始进行dfs搜索即可,但是需要注意一点的是我们搜索的时候并不是沿着一条路径进行搜索,而是从当前已经走过的所有点中选出一个点然后沿着不同方向去搜索,这样我们就可以搜出所有的连通块,每次搜出一个连通块时还需要检测剩余的部分是否是一个连通块,那么检测剩余部分是否是一个连通块我们可以用并查集来实现。这样大体的步骤就实现了,接下来就是剪枝了,为了防止同样的状态被多次搜索,我们可以用哈希优化一下,随意设置一个哈希函数,然后求出每个连通块对应的哈希值然后进行去重即可,还有可以优化的一点就是我们每次尽可能选取值大的点进行搜索,这样得到目标值的连通块内的点就会尽可能小

需要说明的一点就是:由于蓝桥原题是没有明确说明两部分都必须连通的,所以也就没必要加上判断连通的那部分,而且他数据中都是一笔画形成的连通块,没有考虑周全,所以本代码在这两方面进行了优化,但会在洛谷上提交时会有一个点超时,那是因为本代码充分考虑到其余部分是否连通以及连通块形状任意这两个问题。

细节见代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<unordered_set>
using namespace std;
typedef pair<int,int> PII;
const int N=12;
const int P=13331;//P用于哈希
unordered_set<unsigned long long>st;
PII p[N*N];//存放当前已选的点
int a[N][N];
bool vis[N][N];
int fu[N*N],sum,ans,n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool cmp(PII x,PII y)
{return a[x.first][x.second]>a[y.first][y.second];
}
int find(int x)
{if(fu[x]!=x) return fu[x]=find(fu[x]);return x;
}
bool check_connect(int cnt)//检查剩余的n*m-cnt个点是否连通 
{for(int i=1;i<=n*m;i++) fu[i]=i;int t=n*m-cnt;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!vis[i][j]){for(int k=0;k<4;k++){int nx=i+dx[k],ny=j+dy[k];if(nx<1||nx>n||ny<1||ny>m) continue;if(vis[nx][ny]) continue;int fx=find((i-1)*m+j),fy=find((nx-1)*m+ny);if(fx==fy) continue;t--;fu[fx]=fy;}}return t==1;
} 
bool check_exit()//检查当前连通块是否已经被搜索过,是的话返回true,否则返回false 
{unsigned long long t=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(vis[i][j])t=t*P+i*(P-3)+j*(P+102);if(st.count(t)) return true;//哈希去重st.insert(t);return false;
}
void dfs(int s,int cnt)//s和cnt分别代表当前已经选出来的数的和及个数 
{if(s==sum/2){if(check_connect(cnt)) ans=min(ans,cnt);//检查其他格子是否为一个连通块 return ;}if(s>sum/2||cnt>=ans) return ;//剪枝 PII next[N*N];//存放下一次搜索的点 int t=0;for(int i=1;i<=cnt;i++){int nowx=p[i].first,nowy=p[i].second;for(int j=0;j<4;j++){int nx=nowx+dx[j],ny=nowy+dy[j];if(nx<1||nx>n||ny<1||ny>m) continue;if(vis[nx][ny]) continue;next[++t]={nx,ny};}}sort(next+1,next+t+1,cmp);for(int i=1;i<=t;i++){if(next[i]==next[i-1]) continue;p[cnt+1]=next[i];vis[next[i].first][next[i].second]=true;if(!check_exit())//检查当前连通块是否已经被搜索过dfs(s+a[next[i].first][next[i].second],cnt+1);vis[next[i].first][next[i].second]=false;}
}int main()
{cin>>m>>n;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);sum+=a[i][j];}if(sum&1){printf("0");return 0;}ans=0x3f3f3f3f;vis[1][1]=true;p[1]={1,1};dfs(a[1][1],1);if(ans==0x3f3f3f3f) ans=0;printf("%d",ans);return 0;
}

http://www.hrbkazy.com/news/23895.html

相关文章:

  • 深圳网站建设讯美怎么样进行网络推广
  • 高埗做网站sem竞价是什么
  • 大气企业网站360优化大师app下载
  • 提供网站建设工具的公司aso推广平台
  • 网站建设计划书实验总结2023国内外重大新闻事件10条
  • 公关公司排行杭州百度首页优化
  • 如何建设高校网站站长工具seo综合查询推广
  • 上海wordpress开发上海百度seo
  • 做微商网站的公司应用关键词优化
  • 哪里有网站建设加盟合作营销助手
  • 手机网卡seo公司优化
  • 网站的联网信息怎么填站长之家字体
  • 外贸网站如何引流html网站模板免费
  • 主流网站开发技术框架广州seo推广营销
  • 在百度上建网站怎么建设steam交易链接在哪看
  • wordpress标签云美化包头seo
  • 文化传播公司做网站宣传好吗南京高端品牌网站建设
  • 网站建设使用的工具关键词优化推广
  • sketch可以做网站交互么邯郸seo推广
  • 手机app游戏制作软件杭州百度百家号seo优化排名
  • 沈阳网站app制作成都谷歌seo
  • 在网站上做广告如何在网上推广产品
  • 做网站文案用哪个软件seo数据
  • 学生做网站软件app推广员好做吗
  • 免费建设网站领地网络营销教材电子版
  • 免费建工作室网站黄冈网站推广软件视频下载
  • 网站建设服务增值税税率seo优化在哪里学
  • 阿里云wordpress安装目录aso优化渠道
  • 建立购物网站营销和运营的区别是什么
  • 两个公司的网站建设搜索引擎优化方法包括