当前位置：首页 > news >正文

每日两道算法题：DAY3

news 2025/8/18 10:22:10

题目五：棋盘问题

1.题目来源：

NOIP1997 普及组第一题，红色入门，签到题。

2.题目描述：

3.题目解析：

求出一个棋盘中有多少长方形（不包括正方形）和正方形。

4.算法原理：

暴力枚举

观察数据范围，本题可以暴力枚举出所有的矩形，再去判断是正方形还是长方形。

固定左上角，枚举右下角。

时间复杂度：O（n ^ 4）；100 * 100 * 100 * 100 = 1e8，勉强能过。

加上常数级别的优化（右下角一定在左下角的右下方），就没问题了。

数据范围再大一些的话，就要通过数学推公式的方式解决。

有兴趣的话可以自己下去推一推（计数原理、排列组合）

5.代码实现：

#include <iostream>using namespace std;int n, m;
int ret1, ret2;int main()
{cin >> n >> m; n++; m++;for(int x1 = 1; x1 <= n; x1++)for(int y1 = 1; y1 <= m; y1++)for(int x2 = x1 + 1; x2 <= n; x2++)for(int y2 = y1 + 1; y2 <= m; y2++){if(y2 - y1 == x2 - x1) ret1++;else ret2++;}cout << ret1 << " " << ret2 << endl;return 0;
}

6.总结反思：

数据范围允许暴力的话就暴力解决，能通过题目的代码都是好代码，考场上不要费时间推公式，赛后再推公式。

通过这道题重点掌握枚举所有矩形的方式。

题目六：混合牛奶 Mixing Milk

1.题目来源：

USACO1.3，难度橙色，简单题。

2.题目描述：

3.题目解析：

本体容易混淆为背包问题。但实际上并不是背包问题。

背包问题在每一位奶农那里一定是全买的。

本题是一道简单的模拟题。没什么多说的。

4.算法原理：

贪心、模拟

结构体按价格排序，价格低的排前面。

优先选择单价较小的牛奶去购买。

从最便宜的开始买，买够了就 OK 了。

这个贪心策略不用证明，一看就是对的。

5.代码实现：

#include <iostream>
#include <algorithm>using namespace std;const int N = 2e6 + 10, M = 5050;int n, m;
struct node
{int p, a;
}e[M];bool cmp(node& e1, node& e2)
{return e1.p < e2.p;
}int main()
{cin >> n >> m;for(int i = 1; i <= m; i++) cin >> e[i].p >> e[i].a;sort(e + 1, e + 1 + m, cmp);int ret = 0;int sum = 0;for(int i = 1; i <= m; i++){if(sum + e[i].a <= n){sum += e[i].a;ret += e[i].p * e[i].a;}else {ret += (n - sum) * e[i].p;break;}}cout << ret << endl;return 0;}