洛谷-算法2-5-进阶搜索4

P2960 [USACO09OCT] Invasion of the Milkweed G题目描述农夫约翰一直尽力保持牧场里长满丰盛、美味且健康的草供奶牛食用。然而他输掉了这场战斗因为邪恶的乳草在他的农场西北部站稳了脚跟。牧场通常被划分为一个直角网格高度为 Y1≤Y≤100宽度为 X1≤X≤100其中 (1,1) 位于左下角即排列为正常的 X,Y 坐标网格。乳草最初开始在方格 (Mx​,My​) 生长。每周乳草会传播到它已经占据的任何方格周围的所有非岩石方格最多可以传播到八个方格包括直角方格和对角线方格。在这些方格中仅仅一周后它就准备好继续传播到更多方格。贝茜想在牧场被乳草占领之前尽可能多地享受青草。她想知道牧场能持续多久。如果乳草在时间零时位于方格 (Mx​,My​)那么它在何时完成对牧场的入侵对于给定的输入数据这种情况总会发生牧场由一个图示描述. 代表草* 代表巨石如下例所示X4Y3.... ..*. .**.如果乳草从左下角开始行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 行四个以空格分隔的整数XYMx​ 和 My​* 第 2 行到第 Y1 行第 y1 行描述了牧场的第 (Y1−y) 行其中包含 X 个字符. 代表草* 代表巨石输出格式* 第 1 行一个整数表示乳草占领牧场最后一个非巨石方格的周数。显示翻译题意翻译输入输出样例输入 #1复制4 3 1 1 .... ..*. .**.输出 #1复制4说明/提示由 ChatGPT 4o 翻译实现代码#includebits/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 tot0; f.step0; q.push(f); while(!q.empty()) { fq.front(); q.pop(); totmax(tot,f.step); for(int i0;i8;i) { v.xf.xl[i][0]; v.yf.yl[i][1]; v.stepf.step1; if(v.x1||v.xn||v.y1||v.ym) 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() { cinmnf.yf.x; vis[f.x][f.y]1; for(int in;i0;i--) for(int j1;jm;j) cinMap[i][j]; coutbfs()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 分。各组数据的数据范围如下表所示数据组号1−23−45−78−10N≤10204040M≤10610181061018实现代码#includeiostream #includealgorithm #includecstdio #includecstring #includecctype #define ll long long #define R register #define N 55 using namespace std; templatetypename Tinline void read(T a){ char cgetchar();T x0,f1; while(!isdigit(c)){if(c-)f-1;cgetchar();} while(isdigit(c)){x(x1)(x3)c-0;cgetchar();} af*x; } ll n,m,w[N],mid,suma[121],sumb[121],cnta,cntb,ans; inline void dfs(R int l,R int r,R ll sum,R ll a[],R ll cnt){ if(summ)return; if(lr){ a[cnt]sum; return; } dfs(l1,r,sumw[l],a,cnt); dfs(l1,r,sum,a,cnt); } int main(){ read(n);read(m); for(R int i1;in;i)read(w[i]); midn1; dfs(1,mid,0,suma,cnta); dfs(mid1,n,0,sumb,cntb); sort(suma1,suma1cnta); for(R int i1;icntb;i) ansupper_bound(suma1,suma1cnta,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 排斥外来文化 ji 等于 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≤1001≤K≤1001≤M≤N21≤ki​≤K1≤u,v≤N1≤d≤10001≤S,T≤NSTNOIP2012 普及组第四题实现代码#includecstdio #includecstring int min(int x,int y){return xy?x:y;} int c[105],n; int a[105][105]; int f[105][105]; bool used[105][105][105]; void floyd() { for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;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 t1;tn;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 i1;in;i) { scanf(%d,c[i]); f[i][i]0; } for(int i1;ik;i) for(int j1;jk;j) scanf(%d,a[i][j]); for(int i1;im;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 i1;in;i) for(int j1;jn;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; }