洛谷-算法2-5-进阶搜索4-深圳市維司達科技有限公司

P2960 [USACO09OCT] Invasion of the Milkweed G

题目描述

农夫约翰一直尽力保持牧场里长满丰盛、美味且健康的草供奶牛食用。然而，他输掉了这场战斗，因为邪恶的乳草在他的农场西北部站稳了脚跟。

牧场通常被划分为一个直角网格，高度为 Y（1≤Y≤100），宽度为 X（1≤X≤100），其中 (1,1) 位于左下角（即，排列为正常的 X,Y 坐标网格）。乳草最初开始在方格 (Mx,My) 生长。每周，乳草会传播到它已经占据的任何方格周围的所有非岩石方格，最多可以传播到八个方格（包括直角方格和对角线方格）。在这些方格中仅仅一周后，它就准备好继续传播到更多方格。

贝茜想在牧场被乳草占领之前尽可能多地享受青草。她想知道牧场能持续多久。如果乳草在时间零时位于方格 (Mx,My)，那么它在何时完成对牧场的入侵（对于给定的输入数据，这种情况总会发生）？

牧场由一个图示描述，'.' 代表草，'*' 代表巨石，如下例所示，X=4，Y=3：

.... ..*. .**.

如果乳草从左下角开始（行=1，列=1），那么地图将按如下方式演变：

.... .... MMM. MMMM MMMM ..*. MM*. MM*. MM*M MM*M M**. M**. M**. M**. M**M week 0 1 2 3 4

乳草在 4 周后占领了整个牧场。

输入格式

* 第 1 行：四个以空格分隔的整数：X，Y，Mx 和 My

* 第 2 行到第 Y+1 行：第 y+1 行描述了牧场的第 (Y+1−y) 行，其中包含 X 个字符（'.' 代表草，'*' 代表巨石）

输出格式

* 第 1 行：一个整数，表示乳草占领牧场最后一个非巨石方格的周数。

显示翻译

题意翻译

输入输出样例

输入 #1复制

4 3 1 1 .... ..*. .**.

输出 #1复制

说明/提示

（由 ChatGPT 4o 翻译）

实现代码：

#include<bits/stdc++.h> using namespace std; char Map[105][105]; int n,m,l[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; bool vis[105][105]; struct mmp { int x,y,step; }f,v; queue <mmp> q; int bfs() { int tot=0; f.step=0; q.push(f); while(!q.empty()) { f=q.front(); q.pop(); tot=max(tot,f.step); for(int i=0;i<8;i++) { v.x=f.x+l[i][0]; v.y=f.y+l[i][1]; v.step=f.step+1; if(v.x<1||v.x>n||v.y<1||v.y>m) continue; if(vis[v.x][v.y]) continue; if(Map[v.x][v.y]=='*') continue; q.push(v); vis[v.x][v.y]=1; } } return tot; } int main() { cin>>m>>n>>f.y>>f.x; vis[f.x][f.y]=1; for(int i=n;i>0;i--) for(int j=1;j<=m;j++) cin>>Map[i][j]; cout<<bfs()<<endl; return 0; }

P4799 [CEOI 2015] 世界冰球锦标赛 (Day2)

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式

第一行，两个正整数 N 和 M(1≤N≤40,1≤M≤1018)，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，N 个以空格分隔的正整数，均不超过 1016，代表每场比赛门票的价格。

输出格式

输出一行，表示方案的个数。由于 N 十分大，注意：答案 ≤240。

输入输出样例

输入 #1复制

5 1000 100 1500 500 500 1000

输出 #1复制

说明/提示

样例解释

八种方案分别是：

一场都不看，溜了溜了
价格 100 的比赛
第一场价格 500 的比赛
第二场价格 500 的比赛
价格 100 的比赛和第一场价格 500 的比赛
价格 100 的比赛和第二场价格 500 的比赛
两场价格 500 的比赛
价格 1000 的比赛

有十组数据，每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示：

数据组号	1−2	3−4	5−7	8−10
N≤	10	20	40	40
M≤	106	1018	106	1018

实现代码：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cctype> #define ll long long #define R register #define N 55 using namespace std; template<typename T>inline void read(T &a){ char c=getchar();T x=0,f=1; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} a=f*x; } ll n,m,w[N],mid,suma[1<<21],sumb[1<<21],cnta,cntb,ans; inline void dfs(R int l,R int r,R ll sum,R ll a[],R ll &cnt){ if(sum>m)return; if(l>r){ a[++cnt]=sum; return; } dfs(l+1,r,sum+w[l],a,cnt); dfs(l+1,r,sum,a,cnt); } int main(){ read(n);read(m); for(R int i=1;i<=n;i++)read(w[i]); mid=n>>1; dfs(1,mid,0,suma,cnta); dfs(mid+1,n,0,sumb,cntb); sort(suma+1,suma+1+cnta); for(R int i=1;i<=cntb;i++) ans+=upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1; printf("%lld\n",ans); return 0; }

P1078 [NOIP 2012 普及组] 文化之旅（疑似错题）

题目背景

本题不保证存在可以通过满足本题数据范围的任意数据做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。

本题为错题。不建议尝试或提交本题。关于此类题目的详细内容

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 N,K,M,S,T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 1 到 N），文化种数（文化编号为 1 到 K），道路的条数，以及起点和终点的编号（保证 S 不等于 T）；

第二行为 N 个整数，每两个整数之间用一个空格隔开，其中第 i 个数 Ci，表示国家 i 的文化为 Ci。

接下来的 K 行，每行 K 个整数，每两个整数之间用一个空格隔开，记第 i 行的第 j 个数为 aij，aij=1 表示文化 i 排斥外来文化 j（i 等于 j 时表示排斥相同文化的外来人），aij=0 表示不排斥（注意 i 排斥 j 并不保证 j 一定也排斥 i）。

接下来的 M 行，每行三个整数 u,v,d，每两个整数之间用一个空格隔开，表示国家 u 与国家 v 有一条距离为 d 的可双向通行的道路（保证 u 不等于 v，两个国家之间可能有多条道路）。

输出格式

一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出 −1）。

输入输出样例

输入 #1复制

2 2 1 1 2 1 2 0 1 1 0 1 2 10

输出 #1复制

-1

输入 #2复制

2 2 1 1 2 1 2 0 1 0 0 1 2 10

输出 #2复制

说明/提示

输入输出样例 1 说明

由于到国家 2 必须要经过国家 1，而国家 2 的文明却排斥国家 1 的文明，所以不可能到达国家 2。

输入输出样例 2 说明

路线为 1→2。

数据范围

对于 100% 的数据，有：

2≤N≤100
1≤K≤100
1≤M≤N2
1≤ki≤K
1≤u,v≤N
1≤d≤1000
1≤S,T≤N
S=T

NOIP2012 普及组第四题

实现代码：

#include<cstdio> #include<cstring> int min(int x,int y){return x<y?x:y;} int c[105],n; int a[105][105]; int f[105][105]; bool used[105][105][105]; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!a[c[k]][c[i]]&&!a[c[j]][c[k]]&&!used[i][k][c[j]]&&!used[k][j][c[i]]&&f[i][k]+f[k][j]<f[i][j]) { for(int t=1;t<=n;t++) used[i][j][t]=used[i][k][t]||used[k][j][t]; used[i][j][c[k]]=true; f[i][j]=f[i][k]+f[k][j]; } } int main() { memset(f,0x3f,sizeof(f)); int k,m,s,t,u,v,w; scanf("%d%d%d%d%d",&n,&k,&m,&s,&t); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); f[i][i]=0; } for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); if(!a[c[v]][c[u]]&&c[u]!=c[v]) f[u][v]=min(w,f[u][v]); if(!a[c[u]][c[v]]&&c[u]!=c[v]) f[v][u]=min(w,f[v][u]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { used[i][j][c[i]]=true; used[i][j][c[j]]=true; } floyd(); if(f[s][t]==0x3f3f3f3f) printf("-1\n"); else printf("%d\n",f[s][t]); return 0; }