目录
P6183 [USACO10MAR] The Rock Game S
P9011 [USACO23JAN] Air Cownditioning II B
P10294 [CCC 2024 J5] Harvest Waterloo
P1706 全排列问题
题目描述
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n。
输出格式
由 1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。
输入输出样例
输入 #1复制
3输出 #1复制
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1说明/提示
1≤n≤9。
思路
用dfs来写，其实就是n个for循环而已，比如 3个数1 2 3来进行排列 那就是for for for，然后前面的for现在的i不能被后面再用所以再来个visited，防止重新用了前面已经排的数
#include<bits/stdc++.h>
using namespace std;
vector<int>path;
vector<vector<int>>res;
vector<bool> visited(100000);
int n;
void dfs(){
if(path.size()==n) {
res.push_back(path);
return ;
}
for(int i=1;i<=n;i++){
if(!visited[i]){
visited[i]=1;
path.push_back(i);
dfs();
path.pop_back();
visited[i]=0;
}
}
}
int main(){
cin>>n;
dfs();
for(auto i:res){
for(auto j:i){
printf("%5d", j); // 使用 printf 保证 5 个场宽
}
cout<<endl;
}
}B3618 寻找团伙
题目描述
世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 n 个人里面挑选一部分人共襄盛举。
要办这件事，一共涉及 k 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。
你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执不下，导致整个团队丧失这方面的能力。相应地，如果这项能力只有奇数个人拥有，那么他们总能形成一个多数派，帮团队去做这方面的工作。
需要注意的是，团队拥有的每一项能力，对计划的成功率的贡献是不一样的。第一项能力最重要，它的权重是 2k−1；第二项能力的权重是 2k−2；依次类推。第 k 项能力最不重要，权重只有 1。
计划的成功率得分，即是团队拥有的所有能力对应的权重之和。
你希望计划成功率最大。因此，你需要选出合适的人士，来参与到你的宏图伟业中。
输入格式
第一行，两个正整数 n,k。分别表示供你挑选的人的数量，以及能力的种类数。
接下来 n 行，每行表示每个人拥有的能力。这一行首先有一个整数 c，表示该人士拥有多少种能力；接下来是 c 个 [1,k] 之间的正整数，表示该人士拥有哪些能力。输出格式
仅一行，一个整数，表示计划的成功率得分。
输入输出样例
输入 #1复制
5 5 1 1 1 2 1 3 1 4 1 5输出 #1复制
31输入 #2复制
3 5 3 1 2 3 4 2 3 4 5 2 3 4输出 #2复制
28输入 #3复制
3 5 2 1 2 3 5 3 2 3 4 2 5输出 #3复制
30输入 #4复制
21 60 0 0 3 60 27 48 0 1 48 2 52 14 2 4 31 0 0 2 28 43 2 6 31 0 1 7 3 45 6 48 0 1 51 0 2 28 20 2 37 51 1 8 53 59 39 29 23 53 27 13 16 44 34 38 24 9 32 58 54 31 1 7 45 3 30 36 17 48 42 22 18 21 6 11 25 33 37 52 10 60 49 57 2 28 8 14 5 47 4 41 35 43 50 46 26 12输出 #4复制
1152884121210322895说明/提示
样例解释
第一组样例，共 5 个人，每个人拥有的能力不一样。最终选择的结果是让这 5 个人都参与计划，得分 16+8+4+2+1=31。
第二组样例，我们选择只让 1 参与。那么团队具有能力 1,2,3，得分 16+8+4=28。
第三组样例，我们让 1,2,3 参与。由于团队中有偶数个成员拥有能力 5，故团队并不拥有能力 5。奇数个成员拥有能力 2，故团队拥有能力 2。最终，团队具有能力 1,2,3,4。得分 16+8+4+2=30。
数据规模与约定
对于 100% 的数据，有 n≤21,k≤60。
思路
很明显就是选或不选某个人呗，然后搞个ans全局变量记录答案，当每个人都搜索一遍后就ans搞一下，看看每个方案哪个ans最大就ok，这是整体思路，，，里面还需要一些位运算，好吧这个位运算的是看的题解，
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, a[21+10], ans;
void dfs(ll i,ll now) {
if(i>n) {//都搜索过一遍后
ans=max(ans,now);
return;
}
//异或的性质就是相同为0，不同为1，那相同就是偶数，奇数就是不同，
//eg.比如选了1和3 那这个人的能力值就是101，另一个只选了3那就是100异或后就是001，正好符合题目要求
dfs(i+1,now^a[i]);//选这个人，抑或上他的分值,用来异或就不用再多考虑奇数偶数情况，因为上面说了异或的性质
dfs(i+1,now);//不选
}
int main(){
cin>>n>>k;//n个人，k个能力
for(ll i=1;i<=n;i++){
int c;
cin>>c;
for(ll j=1;j<=c;j++) {
int x;
cin>>x;
a[i]|=(1ll<<(k-x)); //记录二进制分值，等价于a[i] += (1ull << (k - x))或a[i] += (1ull * pow(2, k - x))
}
}
dfs(0,0);//第一个参数是第几号人，因为第一个人也要判断选或不选，所以从0开始，
//第二个参数是当前的团伙的总能力值
cout << ans;
return 0;
}B3621 枚举元组
题目描述
n 元组是指由 n 个元素组成的序列。例如 (1,1,2) 是一个三元组、(233,254,277,123) 是一个四元组。
给定 n 和 k，请按字典序输出全体 n 元组，其中元组内的元素是在 [1,k] 之间的整数。
「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。
输入格式
仅一行，两个正整数 n,k。
输出格式
若干行，每行表示一个元组。元组内的元素用空格隔开。
输入输出样例
输入 #1复制
2 3输出 #1复制
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3输入 #2复制
3 3输出 #2复制
1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3说明/提示
对于 100% 的数据，有 n≤5,k≤4。
思路
可以注意到输出的类似于全排列，但是他能输出 1 1,2 2，3 3说明for for两个前面的for用了一个数后后面还可以用，那我们就不需要visited数组来保证一个数只用一次了，比前面的那个全排列还要简单，只要记着dfs里面的basecase是path.size()==n就好，看代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<int>>res;
vector<int>path;
bool visited[6];//不需要用到
void dfs(){
if((int)path.size()==n){
res.push_back(path);
return ;
}
for(int i=1;i<=k;i++){
path.push_back(i);
dfs();
path.pop_back();
}
}
int main(){
cin>>n>>k;
dfs();
for(auto i:res){
for(auto j:i){
cout<<j<<' ';
}
cout<<endl;
}
}B3622 枚举子集（递归实现指数型枚举）
题目描述
今有 n 位同学，可以从中选出任意名同学参加合唱。
请输出所有可能的选择方案。
输入格式
仅一行，一个正整数 n。
输出格式
若干行，每行表示一个选择方案。
每一种选择方案用一个字符串表示，其中第 i 位为
Y则表示第 i 名同学参加合唱；为N则表示不参加。需要以字典序输出答案。
输入输出样例
输入 #1复制
3输出 #1复制
NNN NNY NYN NYY YNN YNY YYN YYY说明/提示
对于 100% 的数据，保证 1≤n≤10。
思路
依旧是for for for组成，我们只要搞个数组里面放Y N，然后遍历，然后递归层数就是由n决定，当存了n个for后就行，依旧不需要visited数组
#include<bits/stdc++.h>
using namespace std;
int n;
char a[2]{'Y','N'};
vector<string>res;
string path;
void dfs(){
if((int)path.size()==n){
res.push_back(path);
return ;
}
for(int i=0;i<=1;i++){
path.push_back(a[i]);
dfs();
path.pop_back();
}
}
int main(){
cin>>n;
dfs();
sort(res.begin(),res.end());
for(auto i:res){
for(auto j:i){
cout<<j;
}
cout<<endl;
}
}B3623 枚举排列（递归实现排列型枚举）
题目描述
今有 n 名学生，要从中选出 k 人排成一列拍照。
请按字典序输出所有可能的排列方式。
输入格式
仅一行，两个正整数 n,k。
输出格式
若干行，每行 k 个正整数，表示一种可能的队伍顺序。
输入输出样例
输入 #1复制
3 2输出 #1复制
1 2 1 3 2 1 2 3 3 1 3 2说明/提示
对于 100% 的数据，1≤k≤n≤10。
思路
求排列方式，那就需要visited数组，在求排列的方式基础上加了后就行，看代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<int>>res;
vector<int> path;
bool visited[15]={false};
void dfs(){
if((int)path.size()==k){
res.push_back(path);
return ;
}
for(int i=1;i<=n;i++){
if(!visited[i]){
path.push_back(i);
visited[i]=1;
dfs();
visited[i]=0;
path.pop_back();
}
}
}
int main(){
cin>>n>>k;
dfs();
for(auto i:res){
for(auto j:i){
cout<<j<<' ';
}
cout<<endl;
}
}B3625 迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n×m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1,1) 的位置，问能否走到 (n,m) 位置。
输入格式
第一行，两个正整数 n,m。
接下来 n 行，输入这个迷宫。每行输入一个长为 m 的字符串，
#表示墙，.表示空地。输出格式
仅一行，一个字符串。如果机器猫能走到 (n,m)，则输出
Yes；否则输出No。输入输出样例
输入 #1复制
3 5 .##.# .#... ...#.输出 #1复制
Yes说明/提示
样例解释
路线如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
数据规模与约定
对于 100% 的数据，保证 1≤n,m≤100，且 (1,1) 和 (n,m) 均为空地。
思路
这个题用dfs，bfs都行，先来个bfs吧哈哈，我的队列是用数组模拟的，数组模拟的常数时间会更快，这也算是bfs模版了，不是很难看看应该就行了，之后我也会写关于bfs的文章
其实这个题根洪水填充差不多，只不过这个是一个点往外一直蔓延，看看能不能蔓延到最后一个点
多讲点吧，用数组模拟的话，因为这是要存坐标，所以我们就需要一个二维的[0]存x,[1]存y
大家平时见到的控制上下左右的数组可能是两个数组，我这里用了一个更方便一些，不懂得可以自己试一下就能理解了，不懂bfs的可以正好学学，这就纯是一个模板
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
vector<string>grid(N);
bool visited[N][N];
int mv[5]={-1,0,1,0,-1};
int q[N][2];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>grid[i];
}
visited[0][0]=1;
int l=0,r=0;
q[r][0]=0;
q[r++][1]=0;
while(l<r){
int size=r-l;
for(int i=0,nx,ny,x,y;i<size;i++){
x=q[l][0];
y=q[l++][1];
if(x==n-1&&y==m-1) {
cout<<"Yes";
return 0;
}
for(int k=0;k<=4;k++){
nx=x+mv[k];
ny=y+mv[k+1];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&!visited[nx][ny]&&grid[nx][ny]=='.'){
visited[nx][ny]=true;
q[r][0]=nx;
q[r++][1]=ny;
}
}
}
}
cout<<"No";
return 0;
}下面是dfs，其实都差不多
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
bool visited[N][N];
int n,m;
vector<string> grid(N);
int mv[5]={-1,0,1,0,-1};
bool dfs(int x,int y) {
// 到达终点
if (x ==n-1&&y==m-1) {
return true;
}
// 标记当前点已访问
visited[x][y]=true;
for (int i=0;i<=4;i++) {
int nx=x+mv[i];
int ny=y+mv[i];
if (nx>=0&&nx<n&&ny>=0&&ny<m&&grid[nx][ny]=='.'&&!visited[nx][ny]) {
if (dfs(nx,ny)){
return true;
}
}
}
return false;
}
int main(){
cin>>n>>m;
for (int i=0;i<n;i++) {
cin>>grid[i];
}
// 起点或终点是墙，直接输出No
if (grid[0][0]=='#'||grid[n-1][m-1]=='#') {
cout<<"No"<<endl;
return 0;
}
bool result=dfs(0, 0);
cout <<(result?"Yes":"No")<<endl;
return 0;
}P6183 [USACO10MAR] The Rock Game S
题目描述
在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。
游戏板由 n 个相同的洞组成，这些洞最初都是空的。一头母牛要么用石头盖住一个空的洞，要么揭开一个先前被盖住的洞。游戏状态的定义是所有洞是否被石头覆盖的情况。
游戏的目标是让奶牛到达每个可能的游戏状态一次，最后回到初始状态。
以下是他们其中一次游戏的示例（空的洞用
O表示，用石头盖住的洞用X表示）：
时刻 洞 1 洞 2 洞 3 描述 0 O O O 一开始所有的洞都是空的 1 O O X 盖上洞 3 2 X O X 盖上洞 1 3 X O O 打开洞 3 4 X X O 盖上洞 2 5 O X O 打开洞 1 6 O X X 盖上洞 3 7 X X X 盖上洞 1 现在牛被卡住玩不下去了！他们必须打开一个洞，然而不管他们打开哪个洞，他们都会到达一个他们已经到达过的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时刻 2 已经访问过的状态（
X O X）。下面是一个 3 个孔的有效解决方案：
时间 洞 1 洞 2 洞 3 描述 0 O O O 一开始所有的洞都是空的 1 O X O 盖上洞 2 2 O X X 盖上洞 3 3 O O X 打开洞 2 4 X O X 盖上洞 1 5 X X X 盖上洞 2 6 X X O 打开洞 3 7 X O O 打开洞 2 8 O O O 打开洞 1，恢复到原来的状态 现在，奶牛们厌倦了这个游戏，它们想找你帮忙。
给定 n，求游戏的有效解决方案序列。如果有多个解决方案，则输出任意一个。
输入格式
仅一行，一个整数 n。
输出格式
共 2n+1 行，每行一个长度为 n 的字符串，其中只包含字符
O和X，该行中的第 i 个字符表示第 i 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是O。输入输出样例
输入 #1复制
3输出 #1复制
OOO OXO OXX OOX XOX XXX XXO XOO OOO说明/提示
样例 1 说明
见题目描述。
数据规模与约定
对于 100% 的数据，有 1≤n≤15。
总结
这段代码通过深度优先搜索的方式，生成一个格雷码序列。格雷码的特点是相邻的两个码之间只有一个位不同。 代码首先输出全'O'的状态，然后递归地翻转每一位，生成新的格雷码状态。 使用 vis 数组来避免重复访问相同的状态，从而保证生成的是一个有效的格雷码序列。ans数组存储生成的序列，最后output函数负责按要求输出。
实际上这段代码找到的是一种特殊的格雷码序列，它从全'O'开始，每次只翻转一位，直到遍历完所有可能的状态。 由于题目要求"找到一组即可"，所以找到任何一种满足条件的格雷码序列就可以直接输出并退出。
总而言之，该程序使用DFS算法巧妙地探索格雷码空间，并用vis数组进行状态标记避免重复，最终找到并输出一个合法的格雷码序列。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[20];//记录格雷码一个a[i]记录0或1
int vis[1<<20];//记录每一个格雷码的是否走过
int ans[1<<20][20];//记录每一个状态的格雷码
void output(){
for(int i=1;i<=1<<n;i++){
for(int j=1;j<=n;j++){
cout<<(ans[i][j]?'X':'O');
}
cout<<endl;
}
}
int calc(){//将当前格雷码转化为10进制用来存储状态
int res=0;
for(int i=1;i<=n;i++){
res=res*2+a[i];
}
return res;
}
void dfs(int pos){
if(pos==(1<<n)){
output();
exit(0) ;
}
for(int i=1;i<=n;i++){
a[i]=!a[i];//从第一位开始到第n位，每个都翻转一遍看哪个状态没走过
if(vis[calc()]){
a[i]=!a[i];//如果走过就翻转回去
continue;
}
vis[calc()]=1;//没走过现在走过了
for(int j=1;j<=n;j++){
ans[pos][j]=a[j];//把翻过的a[i]给存到最终答案这里
}
dfs(pos+1);
vis[calc()]=0;//回溯
a[i]=!a[i];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cout<<'O';
cout<<endl;
vis[0]=true;//提前输出了，000不能再走了
dfs(1);//从001开始搜素
return 0;
}P10448 组合型枚举
题目描述
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如
1 3 5 7排在1 3 6 8前面）。输入输出样例
输入 #1复制
5 3输出 #1复制
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5说明/提示
对于所有测试数据满足 0≤m≤n , n+(n−m)≤25。
思路
组合嘛，他不能重复，也就是说1 2 3有了后，就不能有2 3 1等等，所以就是我们要的是1 2 3
1 2 4 ，1 2 5,1 3 4,1 3 5,1 4 5,2 3 4这样子，每个数必须比前面那个大，这样就保证每次组合都是新的，不重复，我们也不会少某个组合
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>path;
vector<vector<int>>res;
bool visited[100];
void dfs(int start){
if(path.size()==m){
res.push_back(path);
return;
}
for(int i=start;i<=n;i++){
path.push_back(i);
dfs(i+1);//从i+1开始我们就能保证后面的一定比前面那个大了
path.pop_back();
}
}
int main(){
cin>>n>>m;
dfs(1);
for(auto i:res){
for(auto j:i){
cout<<j<<' ';
}
cout<<endl;
}
}P10483 小猫爬山
题目描述
Freda 和 rainbow 饲养了 N(N≤18) 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了
Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1,C2,…CN。当然，每辆缆车上的小猫的重量之和不能超过 W(1≤Ci,W≤108)。每租用一辆缆车，Freda 和 rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第一行包含两个用空格隔开的整数，N 和 W。 接下来 N 行每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
输入输出样例
输入 #1复制
5 1996 1 2 1994 12 29输出 #1复制
2
思路
装箱问题：将 n 个物品装入若干个容量为 m 的容器，要求每个容器内物品总重量不超过 m，目标是找到使用最少容器数量的方案。
直接看代码吧
#include<bits/stdc++.h>
using namespace std;
int n,m,cat[20],ans=20,w[20];
void dfs(int u,int v){
if(v>=ans) return ;//如果当前用的缆车数大于等于之前记录的最少缆车数量，那就直接返回不用再装了
if(u==n){//已经全搜过了就不用再搜了，同时更新答案
ans=v;
return;
}
//第一种选择，用之前用过的缆车
for(int i=0;i<v;i++){
if(w[i]+cat[u]<=m){
w[i]+=cat[u];
dfs(u+1,v);
w[i]-=cat[u];
}
}
//第二种，用新的
w[v]=cat[u];
dfs(u+1,v+1);//继续去搜索之后的猫
}
int main(){
cin>>n>>m;
ans=n;
for(int i=0;i<n;i++){
cin>>cat[i];
}
sort(cat,cat+n,greater<int>());
dfs(0,0);
cout<<ans;
return 0;
}P8604 [蓝桥杯 2013 国 C] 危险系数
题目描述
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF(x,y)：
对于两个站点 x 和 y(x=y), 如果能找到一个站点 z，当 z 被敌人破坏后，x 和 y 不连通，那么我们称 z 为关于 x,y 的关键点。相应的，对于任意一对站点 x 和 y，危险系数 DF(x,y) 就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
输入格式
输入数据第一行包含 2 个整数 n(2≤n≤1000)，m(0≤m≤2000)，分别代表站点数，通道数。
接下来 m 行，每行两个整数 u,v(1≤u,v≤n,u=v) 代表一条通道。
最后 1 行，两个数 u,v，代表询问两点之间的危险系数 DF(u,v)。
输出格式
一个整数，如果询问的两点不连通则输出 −1。
输入输出样例
输入 #1复制
7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6
思路
遍历图，从初始点dfs然后把所有能走到终点的路都走一遍，记录有几条路，记录每个节点走几次，如果有节点走的次数跟路径相同，那就说明这个节点是每条路都要走的，哪题一消失，那我们包到不了终点，这个就是关键点
#include<bits/stdc++.h>
using namespace std;
int n,m;
int M;
int cnt;
bool visited[1010];
int ans[1010];
int ans1;
int x,y;
void dfs(int x,vector<vector<int>>& graph){
if(x==y){
cnt++;
for(int i=1;i<=M;i++){
//遍历一下所有编号，可能有的编号不存在
//所以判断一下是否存在
ans[i]+=visited[i]?1:0;
}
return;
}
visited[x]=1;
for(auto i:graph[x]){
if(!visited[i])
dfs(i,graph);
}
visited[x]=false;//这节点走完就回溯
}
int main(){
cin>>n>>m;
vector<vector<int>>graph(1010);
while(m--){
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
M=max(max(M,u),v);//记录一下最大节点的编号
}
cin>>x>>y;
dfs(x,graph);//从u开始搜索
for(int i=1;i<=M;i++){
if(ans[i]==cnt) ans1++;
}
cout<<ans1-1;//减去初始点
} P9011 [USACO23JAN] Air Cownditioning II B
题目描述
农夫约翰的 N 头奶牛 (1≤N≤20) 住在一个谷仓里，谷仓里有连续的牛栏，编号为 1−100 。 奶牛 i 占据了编号 [si,ti] 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 i 占用的每个牛栏的温度必须至少降低 ci 单位。
谷仓包含 M 台空调，标记为 1−M (1≤M≤10)。第 i 台空调需要花费 mi 单位的金钱来运行 (1≤mi≤1000) ，如果运行，第 i 台空调将牛栏 [ai,bi] 所有牛栏的温度降低 pi（1≤pi≤106）。 空调覆盖的牛栏范围可能会重叠。
请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。
输入格式
第一行两个整数，分别为 N 和 M。
第 2 至 (N+1) 行，每行三个整数，分别为 si、ti 和 ci 。
第 (N+2) 至 (M+N+1) 行，每行四个整数， 分别为 ai、bi、pi 和 mi。
输出格式
一个整数，表示最少花费的金钱。
题意翻译
输入输出样例
输入 #1复制
2 4 1 5 2 7 9 3 2 9 2 3 1 6 2 8 1 2 4 2 6 9 1 5输出 #1复制
10说明/提示
样例解释 1
一种花费最少的可能解决方案是选择那些冷却区间为 [2,9] 、[1,2] 和 [6,9] 的空调，成本为 3+2+5=10 .
对于 100% 的数据，1≤N≤20， 1≤M≤10, 1≤ai,bi,si,ti≤100, 1≤ci,pi≤106， 1≤mi≤1000。
思路
就是一路两搜索，选或不选这个空调，就好，只不过多注意细节，可以利用差分，我这里就没用
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,k,ans=1e9;//n头牛，m个空调
//第i头牛占据s[i]到t[i]的牛栏 ，每头牛i占的栅栏必须降低c[i]
//第i个空调需要花M[i],第i个空调能让a[i]到b[i]降低p[i]
int s[N],t[N],c[N],a[N],b[N],p[N],M[N],w[N];
bool check(){
for(int i=1;i<=k;i++){
//如果还有某个牛所处区域的空调没到达c[i]
//因为我们是预处理最开始都等于c[i]所以这里是判断是否大于0
if(w[i]>0) return false;
}
return 1;
}
void dfs(int deep,int s){
if(deep>m){
//如果搜索完一遍
if(check())
ans=min(ans,s);
return;
}
for(int i=a[deep];i<=b[deep];i++) w[i]-=p[deep];
dfs(deep+1,s+M[deep]);//选这个空调
for(int i=a[deep];i<=b[deep];i++) w[i]+=p[deep];
dfs(deep+1,s);//不选当前这个第deep号空调
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i]>>t[i]>>c[i];
k=max(k,t[i]);
for(int j=s[i];j<=t[i];j++){
w[j]+=c[i];
}
}
for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>M[i];
dfs(1,0);
cout<<ans;
} P10294 [CCC 2024 J5] Harvest Waterloo
题目描述
有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。
农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。
你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 1 美元，一个中等大小的南瓜值 5 美元，而一个大南瓜值 10 美元。
输入格式
输入的第一行是一个整数 R>0 表示南瓜地的行数。
第二行是一个整数 C>0 表示南瓜地的列数。
接下来 R 行描述了整个南瓜地。每行包含 C 个字符并且每个字符要么表示一个南瓜，要么表示干草：
S表示小南瓜，M表示中等大小的南瓜，L表示一个大南瓜，*表示干草。下一行包含一个整数 A 满足 0≤A<R，最后一行是一个整数 B 满足 0≤B<C。表示农民一开始在第 A 行第 B 列的位置。南瓜地的左上角称为第 0 行第 0 列。
输出格式
输出一个整数 V 表示农民能够收割的南瓜的总价值。
输入输出样例
输入 #1复制
6 6 **LMLS S*LMMS S*SMSM ****** LLM*MS SSL*SS 5 1输出 #1复制
37输入 #2复制
6 6 **LMLS S*LMMS S*SMSM ***SLL LLM*MS SSL*SS 2 4输出 #2复制
88【数据范围】
本题采用捆绑测试。
对于所有数据，保证 1≤R,C≤105，1≤R×C≤105。
下面的表格显示了 15 分的分配方案：
分值 描述 范围 1 南瓜地很小并且不存在干草。 R×C≤100 4 南瓜地很小并且干草把南瓜地分割为一些矩形区域。 R×C≤100 5 南瓜地很小并且干草可以在任意位置。 R×C≤100 5 南瓜地可能很大并且干草可以在任意位置。 R×C≤105
思路
依旧是简单点洪水填充问题，直接看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
vector<string> grid(N);
void dfs(int i,int j){
if(i<0||j<0||i==n||j==m||(grid[i][j]!='L'&&grid[i][j]!='M'&&grid[i][j]!='S'))
return;
if(grid[i][j]=='L') grid[i][j]='l';
if(grid[i][j]=='S') grid[i][j]='s';
if(grid[i][j]=='M') grid[i][j]='m';
dfs(i,j+1);
dfs(i,j-1);
dfs(i+1,j);
dfs(i-1,j);
}
int l,s,m1;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>grid[i];
}
int x,y;
cin>>x>>y;
dfs(x,y);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='l') l+=10;
if(grid[i][j]=='m') m1+=5;
if(grid[i][j]=='s') s++;
}
}
cout<<l+m1+s;
}