• 正睿OI补题（搜索）

    搜索

    目录：

    P1036 [NOIP2002 普及组] 选数

    P2392 kkksc03考前临时抱佛脚

    P1025 [NOIP2001 提高组] 数的划分

    P6201 [USACO07OPEN]Fliptile S

    P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins

    P1135 奇怪的电梯

    P1763 埃及分数

    PS:图的遍历用BFS和DFS搜索

    1. //bfs
    2. #include<iostream>
    3. #include<queue>
    4. using namespace std;
    5. queue<int>q;
    6. //使用邻接矩阵的BFS 
    7. void BFS(int u)
    8. {
    9. 	vis[u] = true;
    10. 	q.push(u);
    11. 	while(!q.empty())
    12. 	{
    13. 		int head = q.front();
    14. 		q.pop();
    15. 		for(int w = 1;w <= n;w++){
    16. 			if(edge[v][w] && !vis[w]){
    17. 				vis[w] = true;
    18. 				q.push(w);
    19. 			}
    20. 		}
    21. 	}
    22. }
    23.  
    24.  
    25. //用栈来实现
    26. void dfs(int u)
    27. {
    28. 	vis[u] = 1;
    29. 	for(int i = 1;i <= n;i++)
    30. 	{
    31. 		if(edge[u][i] && !vis[v]) dfs(i);
    32. 	}
    33.  } 
    34. int main()
    35. {
    36. 	
    37. 	return 0;
    38. }

    P1036 [NOIP2002 普及组] 选数

    [NOIP2002 普及组] 选数 - 洛谷

    实力直接回炉重造！！！

    我花了三小时调试这题，没想到，败在括号上！！！

    1. #include
    2. using namespace std;
    3. const int N = 30;
    4. int a[N];
    5. int n,k;
    6. int ans;
    7. bool is_prime(int x)
    8. {
    9. 	for(int i = 2;i * i <= x;i++)
    10. 		if(x % i == 0)return false;
    11. 		return true;
    12.  } 
    13.  
    14. void dfs(int m,int sum,int sta)
    15. {
    16. 	if(m == k)
    17. 	{
    18. 		if(is_prime(sum)) ans++;
    19. 		return;
    20. 	}
    21. 	
    22. 	for(int i = sta;i < n;i++)
    23. 		dfs(m+1,sum+a[i],i+1);
    24. 		return;
    25. }
    26. int main()
    27. {
    28. 	cin>>n>>k;
    29. 	
    30. 	for(int i = 0;i < n;i++)
    31. 		cin>>a[i];
    32. 	
    33. 	dfs(0,0,0);
    34. 	cout<
    35. 	
    36. 	
    37. 	return 0;
    38. }

    P2392 kkksc03考前临时抱佛脚 

    kkksc03考前临时抱佛脚 - 洛谷

    思路：枚举左右脑分别工作即可

    1. #include
    2. using namespace std;
    3. int a[5],b[5][36];//表示a[N]哪一科,而b[ ][ ]表示一科中有多少道题
    4. int minn = -0x3f3f3f3f;
    5. int ans;
    6. int l,r;
    7. void dfs(int p,int n)//p表示几道题
    8. {
    9. 	if(p > a[n])
    10. 	{
    11. 		minn = min(max(l,r),minn);
    12. 		return; 
    13. 	}
    14. 	l += b[n][p];
    15. 	dfs(p+1,n);
    16. 	l -= b[n][p];
    17. 	
    18. 	r += b[n][p];
    19. 	dfs(p+1,n);
    20. 	r -= b[n][p];
    21. } 
    22. int main()
    23. {
    24. 	for(int i = 1;i <= 4;i++)
    25. 	{
    26. 		cin>>a[i];
    27. 	}
    28. 	for(int i = 1;i <= 4;i++)
    29. 	{
    30. 		for(int j = 1;j <= a[i];j++)
    31. 		{
    32. 			cin>>b[i][j];
    33. 		}
    34. 		l = 0,r = 0;//两个头脑都还没开始工作 
    35.         minn = 0x3f3f3f3f;
    36. 		dfs(1,i);
    37. 		ans += minn;
    38. 		
    39. 	}
    40. 	cout<
    41. 	return 0;
    42. }

    P1025 [NOIP2001 提高组] 数的划分

    [NOIP2001 提高组] 数的划分 - 洛谷

    思路：

    记录上一次划分所用的数，保证当前划分所用数不小于上次划分所用分数，当划分次数等于k时比较该次划分所得总分是否与n相同并记录次数。

    1. #include
    2. using namespace std;
    3. int n,k;
    4. int cnt;
    5. void dfs(int m,int sum,int sta)//m为上一次所划分的数，sum表示所得总份数，sta表示划分数中剩余的次数 
    6. {
    7. //处理分完的部分
    8. 	if(sta == k)
    9. 	{
    10. 		if(sum == n)
    11. 		cnt++;
    12. 		return;
    13. 	}
    14. 	
    15. 	for(int i = m;i <= n-sum;i++)//剪枝部分
    16. 		dfs(i,sum+i,sta+1);
    17. 		return;
    18. 	}
    19. int main()
    20. {
    21. 	cin>>n>>k;
    22. 	dfs(1,0,0);
    23. 	cout<
    24. 	return 0;
    25. }

    P6201 [USACO07OPEN]Fliptile S 

    [USACO07OPEN]Fliptile S - 洛谷

    思路：

    因为对于第i行(i>=2)的数字只取决于它正上方的数字(mp[i-1][j])是1还是0，因为这是mp[i-1][j]最后的一次修改机会，我们必须把它更改成0。


    如果mp[i-1][j]=1，这个格子就必须要翻，如果mp[i-1][j]=0，这个格子就一定不能翻。当所有的数都按照规则翻完后，如果图内没有1存在则合法，否则return

    枚举第一行的即可！

    1. #include
    2. using namespace std;
    3. const int INF = 20000007;
    4. const int N = 30;
    5. int a[N][N];
    6. //因为对于第i行(i>=2)的数字只取决于它正上方的数字(a[i-1][j])是1还是0，因为这是a[i-1][j]最后的一次修改机会，我们必须把它更改成0.
    7. //如果a[i-1][j]=1，这个格子就必须要翻，如果a[i-1][j]=0，这个格子就一定不能翻。
    8. int n,m;
    9. int ans[N][N],p[N][N],q[N][N];
    10. int mxn = INF;
    11. void dfs(int x)
    12. {
    13. 	if(x > m)
    14. 	{
    15. 		for(int i = 1;i <= n;i++)
    16. 		for(int j = 1;j <= m;j++)
    17. 		p[i][j] = q[i][j];
    18. 		
    19. 		for(int i = 1;i <= m;i++)
    20. 		if(a[1][i])
    21. 		{
    22. 			p[1][i] ^= 1,p[2][i] ^= 1;
    23. 			p[1][i+1] ^= 1,p[1][i-1] ^= 1;
    24. 		}
    25. 		
    26. 		for(int i = 2;i <= n;i++)
    27. 		for(int j = 1;j <= m;j++)
    28. 		{
    29. 			//重点来了！！！ 
    30. 			if(p[i-1][j] == 1)
    31. 			{
    32. 				a[i][j] = 1;
    33. 				p[i][j] ^= 1;
    34. 				p[i][j+1] ^= 1;
    35. 				p[i][j-1] ^= 1;
    36. 				p[i+1][j] ^= 1;
    37. 				p[i-1][j] ^= 1;
    38. 				//四方位全翻一次 
    39. 			}
    40. 			else a[i][j] = 0;
    41. 			if(p[i-1][j])return;
    42. 		}
    43. 		
    44. 		bool flag = false;
    45. 		for(int i = 1;i <= n;i++)
    46. 		for(int j = 1;j <= m;j++)
    47. 		if(p[i][j])
    48. 		{
    49. 			flag = true;
    50. 			break;
    51. 		}
    52. 		if(!flag)
    53. 		{
    54. 			int tot = 0;
    55. 			for(int i = 1;i <= n;i++)
    56. 			for(int j = 1;j <= m;j++)
    57. 			if(a[i][j])tot++;
    58. 			
    59. 			if(tot >= mxn)return;
    60. 			mxn = tot;
    61. 			
    62. 			for(int i = 1;i <= n;i++)
    63. 			for(int j = 1;j <= m;j++)
    64. 			ans[i][j] = a[i][j];
    65. 		}
    66. 		return;
    67. 	}
    68. 	for(int i = 0;i <= 1;i++)
    69. 	{
    70. 		a[1][x] = i;
    71. 		dfs(x+1);
    72. 	}
    73. }
    74. int main()
    75. {
    76. 	cin>>n>>m;
    77. 	for(int i = 1;i <= n;i++)
    78. 	for(int j = 1;j <= m;j++)
    79. 	cin>>q[i][j];
    80. 	dfs(1);
    81. 	
    82. 	if(mxn == INF)cout<<"IMPOSSIBLE";
    83. 	else
    84. 	{
    85. 		for(int i = 1;i <= n;i++)
    86. 		{
    87. 			for(int j = 1;j < m;j++)
    88. 			cout<" ";
    89. 			cout<
    90. 		}
    91. 	}
    92. 	return 0;
    93.  }

     P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins

    P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    1. #include
    2. using namespace std;
    3. const int N = 30;
    4. int a[N],sl[N][N];//表示维他命的数量
    5. int v,g;
    6. int minn = 0x3f3f3f3f;
    7. int cur[N];//表示当时枚举的子集选中了哪些饲料
    8. int ans[N];//表示全局选中的哪些饲料
    9. bool check(int x)
    10. {
    11.     for(int i = 1;i <= v;i++)
    12.     {
    13.        int sum = 0;
    14.        for(int j = 1;j <= x;j++)
    15.        {
    16.            sum+=sl[cur[j]][i];
    17.        }
    18.        if(sum < a[i])
    19.        {
    20.            return false;
    21.        }
    22.     }
    23.     return true;
    24. }
    25. void dfs(int dq,int cnt)//dq当前枚举的饲料编号，cnt表示当前子集元素的总个数
    26. {
    27.     if(dq == g+1)
    28.     {
    29.         if(check(cnt) == true)
    30.         {
    31.             if(minn > cnt)
    32.         {
    33.            minn = cnt;
    34.            for(int i = 1;i <= cnt;i++)
    35.         {
    36.             ans[i] = cur[i];
    37.         }
    38.         }
    39.         }
    40.         return;
    41.     }
    42.     if(dq <= g)
    43.     {
    44.     cur[cnt+1] = dq;
    45.     //选中
    46.     dfs(dq+1,cnt+1);
    47.     //不选
    48.     dfs(dq+1,cnt);
    49.     cur[cnt+1] = 0;
    50.     }
    51.     
    52.         
    53. }
    54. int main()
    55. {
    56.     cin>>v;
    57.     for(int i = 1;i <= v;i++)
    58.     {
    59.         cin>>a[i];
    60.     }
    61.     cin>>g;
    62.     for(int i = 1;i <= g;i++)
    63.     {
    64.         for(int j = 1;j <= v;j++)
    65.         {
    66.             cin>>sl[i][j];
    67.         }
    68.     }
    69.     dfs(1,0);
    70.     cout<" ";
    71.     for(int i = 1;i <= minn;i++)
    72.     {
    73.         cout<" ";
    74.     }
    75.     cout<
    76.      
    77.     return 0;
    78. }

    P1135 奇怪的电梯 

    奇怪的电梯 - 洛谷

    思路：直接dfs爆搜一边即可

    我自己都服了，我会犯低级错误

     

    没判断按键的数量是否会超过预期数量

    1. //P1135 奇怪的电梯
    2. //直接 dfs往下搜即可
    3. //也可以转化为图的模式 
    4. #include
    5. using namespace std;
    6. const int N = 220;
    7. int a,b,n;
    8. int K[N];
    9. int cnt = 0x3f3f3f3f;
    10. bool vis[N];
    11. void dfs(int m,int sum)//m表示当前搜到的楼层，sum表示按钮次数 
    12. {
    13. 	if(m == b) cnt = min(cnt,sum);
    14. 	return;
    15. 	vis[m] = 1;
    16. 	//不越界就搜
    17. 	if(m+K[m] <= n && !vis[m+K[m]]) dfs(m+K[m],sum+1);
    18. 	if(m-K[m] >= 1 && !vis[m-K[m]]) dfs(m-K[m],sum+1);
    19. 	
    20. 	vis[m] = 0;
    21. 	return;
    22. }
    23. int main()
    24. {
    25.     ios::sync_with_stdio(false);
    26.     cin.tie(0);
    27. 	cin>>n>>a>>b;
    28. 	for(int i = 1;i <= n;i++)
    29. 	{
    30. 		cin>>K[i];
    31. 	}
    32. 	
    33. 	vis[a] = 1;
    34. 	dfs(a,0);
    35. 	
    36. 	if(cnt != 0x3f3f3f3f) cout<
    37. 	else cout<<"-1"<
    38. 	
    39. 	return 0;
    40. }

     P1763 埃及分数

    埃及分数 - 洛谷

    没开ll的后果！！！

     警钟长鸣！！

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e8+10;
    5. ll sum[N];
    6. ll a[N];
    7. int ans;
    8. bool dfs(ll mol,ll x,ll y)
    9. {
    10. 	if(mol == ans + 1)
    11. 	{
    12. 		if(x != 0)
    13. 		{
    14. 			return false;
    15. 		}
    16. 		if(sum[ans] > a[ans])
    17. 		{
    18. 			for(int i = 1;i <= ans;i++)
    19. 			{
    20. 				sum[i] = a[i];
    21. 			}
    22. 		}
    23. 		return true;
    24. 	}
    25. 	bool flag = false;
    26. 	
    27. 	for(ll i = max((ll)(ceil(y/x)),a[mol-1]+1);i <= ceil(y/x) * (ans - mol + 1);i++)//枚举分母
    28. 	{
    29. 		a[mol] = i;
    30. 		ll dx = x * i - y;
    31. 		ll dy = y * i;
    32. 		ll	g = __gcd(dx,dy);
    33. 		dx /= g;
    34. 		dy /= g;
    35. 		if(dfs(mol+1,dx,dy))
    36. 		{
    37. 			flag = true;
    38. 		}
    39. 	 } 
    40. 	 return flag;
    41. }
    42. ll x,y;
    43. int main()
    44. {
    45. 	scanf("%lld %lld",&x,&y);
    46. 	for(ans = 1;;ans++)
    47. 	{
    48. 		sum[ans] = 0x3f3f3f3f;
    49. 		if(dfs(1,x,y) == true)//搜到的每一个加数 
    50. 		{
    51. 			break;
    52. 		}
    53. 	}
    54. 	
    55. 	for(int i = 1;i <= ans;i++)
    56. 	{
    57. 		printf("%lld ",sum[i]);
    58. 	}
    59. 	return 0;
    60. }

  • 相关阅读:
    C++ 多态
    golang协程原理
    力扣第38天----第139题
    ModuleNotFoundError: No module named ‘unstructured‘
    数学建模__动态规划
    GoLand远程开发IDE：使用SSH远程连接服务器进行云端编程
    [附源码]计算机毕业设计springboot校园疫情防范管理系统
    CC2530中文数据手册
    CSAPP Lab6：Malloc
    【C++】设计模式之单例模式
  • 原文地址：https://blog.csdn.net/Demilly123/article/details/127087185