洛谷-算法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复制

4

说明/提示

（由 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复制

8

说明/提示

样例解释

八种方案分别是：

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

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

实现代码：

#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复制

10

说明/提示

输入输出样例 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; }