网站原型,抖音广告投放 网页制作教程,wordpress换主机,广昌网站建设1.木棒
167. 木棒 - AcWing题库
乔治拿来一组等长的木棒#xff0c;将它们随机地砍断#xff0c;使得每一节木棍的长度都不超过 5050 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态#xff0c;但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序…1.木棒
167. 木棒 - AcWing题库
乔治拿来一组等长的木棒将它们随机地砍断使得每一节木棍的长度都不超过 5050 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。 解题思路
我们先将所有木棒总长度与其中最长的木棍长度记录下来。将记录小木棍长度的数组排序然后从最长的木棍枚举每根木棒可能的长度优化根据这个小木棒能不能被sum整除来进行第一次判断这个小木棒长度是否正确。进入bfs三个参数u构造了多少小木棍cur构造小木棍的长度cnt数组下标。
我们依次用断掉的木棍来凑出我们枚举的木棍长度并将当前枚举的木棍标记为已使用当前木棍凑不出来就取消当前木棍的已使用标记此处可进行一个优化当第一个木棍与最后一个木棍搜索失败时就一定搜不到了(第一个木棍搜不到了那它就永远凑不出来了。最后一个也是肯定是将前面的都用完之后再用的最后一个不行肯定就是失败了) 优化我们可以将长度相同的小木棍跳过当当前凑的小木棍长度乘凑的小木棍根数等于木棒从长度时就return true; 当当前小木棍长度等于枚举的小木棍长度时就进入下一个小木棍的枚举。
AC代码
#includeiostream
#includealgorithm
#includecstring
using namespace std;int n;
int a[100];
int len0,sum0;
bool judge[100];
//u:构造了多少根小木棍,cur:构造小木棍的长度,cnt:数组下标
bool dfs(int u,int cur,int cnt)
{if(cur*usum)//凑够了{//由于初始传入的len所以当最后一次curlen时没有经过下面u1所以u是刚好的// coutu: uendl;// for(int i0;in;i)// coutjudge[i] ;// coutendl;return true;}if(curlen)//这根木棍达到len了换下一根木棍return dfs(u1,0,0);for(int icnt;in;i){if(judge[i])continue;if(cura[i]len){judge[i]true;if(dfs(u,cura[i],i1))return true;//直接成功judge[i]false;//失败了当没用过}//第一个木棍就搜索不到答案,或者//最后一个木棍搜索失败if(!cur||cura[i]len){return false;}int ji1;while(jna[i]a[j]) j;ij-1;//将重复的i跳过排序的作用}return false;
}int main()
{while(scanf(%d,n)n!0){sum0;len0;for(int i0;in;i){scanf(%d,a[i]);suma[i];//计算所有木棍总长度lenmax(len,a[i]);//len肯定不能比零散的木棍小}memset(judge,false,sizeof(judge));sort(a,an,greaterint());while(1){if(sum%len0dfs(0,len,0))//传入len的话{coutlenendl;break;}len;}}return 0;
}
2. 飞机降落
4957. 飞机降落 - AcWing题库
有 NN 架飞机准备降落到某个只有一条跑道的机场。
其中第 ii 架飞机在 TiTi 时刻到达机场上空到达时它的剩余油料还可以继续盘旋 DiDi 个单位时间即它最早可以于 TiTi 时刻开始降落最晚可以于 TiDiTiDi 时刻开始降落。
降落过程需要 LiLi 个单位时间。
一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不能在前一架飞机完成降落前开始降落。
请你判断 NN 架飞机是否可以全部安全降落。 解题思路
我们可以用一个结构体来存储输入的到达的时刻与可以盘旋的时间与下降所需的时间(根据题目可以看出下降所需时间不算在可以盘旋的时间里)我这里用pairint,pairint,int来存储的看起来会麻烦些。
bool dfs参数cnt来记录有多少飞机已经降落ti表示当前的时刻(注意会有当前时刻到达的飞机都降落完了就要跳到下一个时间)
每一次都要从第一架飞机开始枚举看如果当前这架飞机没有降落并且超过了到达时间盘旋时间就失败了返回false判断一下时间有没有到没有到就将时间改为降落时间(上面要用一个临时变量记录时间这里改变的也是临时变量)然后看这架飞机没走过就将其标记为走过然后递归看这里让这架飞机飞能不能让飞机全飞完不能就取消对这架飞机的标记。当降落的飞机飞机总数时就返回true根据返回值输出 YES或NO
AC代码
#includeiostream
#includealgorithm
#includecstdio
#includecstring
using namespace std;
int t;
int n;
pairint,pairint,int car[15];
bool st[15];//判断飞机是否降落//cnt判断有几架飞机降落了,ti是时间
bool dfs(int cnt,int ti)
{if(cntn) return true;for(int i0;in;i){int tmpti;//可能有的飞机没到点需要改成到的时刻if(!st[i]ticar[i].firstcar[i].second.first)//这一架没降落,并且时间超时return false;if(tmpcar[i].first)//现在没到i这架飞机的到达时刻tmpcar[i].first;if(!st[i]){st[i]true;if(dfs(cnt1,tmpcar[i].second.second)) return true;st[i]false;}}return false;
}
int main()
{scanf(%d,t);while(t--){scanf(%d,n);//分别是到达的时刻还能停留的时间降落所需时间for(int i0;in;i)scanf(%d%d%d,car[i].first,car[i].second.first,car[i].second.second);memset(st,false,sizeof st);if(dfs(0,0)) printf(YES\n);else printf(NO\n);}return 0;
}
3. 母亲的牛奶
1355. 母亲的牛奶 - AcWing题库
农夫约翰有三个容量分别为 A,B,CA,B,C 升的挤奶桶。
最开始桶 AA 和桶 BB 都是空的而桶 CC 里装满了牛奶。
有时约翰会将牛奶从一个桶倒到另一个桶中直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿并且不会有任何牛奶的浪费。
请你编写一个程序判断当 AA 桶是空的时候CC 桶中可能包含多少升牛奶找出所有的可能情况。 解题思路
这几个桶只要有牛奶可以互相倒牛奶只有两种可能把要倒的桶倒满或者把自己倒空
用一个结构体包含abc代表当前各个瓶子奶的容量由于数据量很小所以我们可以用一个三维数组来存它的状态创建一个队列存上面的结构体枚举一个瓶子倒一个瓶子接(不能是同一个瓶子)根据要倒牛奶瓶子的牛奶量和要接牛奶瓶子的剩余空间来更新队列依次直到队列空。
我们遍历状态数组输出所有当A瓶子为空时有过的C的值
AC代码
#includeiostream
#includealgorithm
#includecstdio
#includequeue
using namespace std;
struct node
{int a,b,c;//记录当前abc分别多少牛奶
};
int A,B,C;
bool st[25][25][25];//当值为true说明三个下标表示三个杯子分别盛的容量
queuenode q;
int bfs(int a,int b,int c)
{q.push({a,b,c});//入队int val[3]{A,B,C};st[a][b][c]true;while(!q.empty()){node tq.front();q.pop();for(int i0;i3;i)//枚举第i个桶向第j个桶里倒牛奶{for(int j0;j3;j){if(i!j)//不能自己给自己倒{int s[3]{t.a,t.b,t.c};if(s[i]0)continue;//比较i个桶剩的牛奶与第j桶还能放进去的牛奶哪个更少int cmpmin(s[i],val[j]-s[j]);s[i]-cmp;//i桶减去s[j]cmp;//j桶加上if(!st[s[0]][s[1]][s[2]]){st[s[0]][s[1]][s[2]]true;q.push({s[0],s[1],s[2]});}}}}}
}int main()
{scanf(%d%d%d,A,B,C);//分别能存储的容量bfs(0,0,C);for(int j0;jC;j){for(int i0;iB;i){if(st[0][i][j])printf(%d ,j);}}return 0;
} 4. 全球变暖
1233. 全球变暖 - AcWing题库
你有一张某海域 N×NN×N 像素的照片”.”表示海洋、”#”表示陆地如下所示
.......
.##....
.##....
....##.
..####.
...###.
.......其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿例如上图就有 22 座岛屿。
由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。
例如上图中的海域未来会变成如下样子
.......
.......
.......
.......
....#..
.......
.......请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。 解题思路
就是遍历所有的大陆查看陆地数量与临海的陆地数量是否相同其余就是普通的洪水覆盖模板
AC代码
#includeiostream
#includealgorithm
#includecstdio
#includequeue
#includecstring
using namespace std;int n;
char map[1010][1010];
int dx[4]{1,0,0,-1};
int dy[4]{0,1,-1,0};
queuepairint,int qu;
bool states[1010][1010];int cnt0;
void bfs(int x,int y,int sum1,int sum2)
{qu.push({x,y});states[x][y]true;while(!qu.empty()){auto tqu.front();sum1;qu.pop();bool falgfalse;for(int i0;i4;i){int at.firstdx[i];int bt.seconddy[i];if(a0||b0||an||bn) continue;if(states[a][b]) continue;//已经走过的if(map[a][b].){falgtrue;//说明上一个邻海continue;}qu.push({a,b});states[a][b]true;}if(falg) sum2;//统计临海的数量}if(sum2sum1)cnt;}int main()
{scanf(%d,n);for(int i0;in;i){for(int j0;jn;j){ cinmap[i][j];}}for(int i0;in;i){for(int j0;jn;j){ int cnt10;//记录岛屿边缘数量int cnt20;//记录岛屿陆地数量if(!states[i][j]map[i][j]#)bfs(i,j,cnt1,cnt2);} }coutcntendl;return 0;
}
