p2216 [haoi2007]理想的正方形
时间: 2023-11-09 11:09:09 浏览: 35
这是一道IT类问题,关于算法竞赛方面的题目。
题目描述:给定一个 $n \times n$ 的矩阵,每个格子里填有一个数字,要求选出一个 $k \times k$ 的正方形,使得这个正方形内数字的和最大。请编写程序输出这个最大的和。
算法思路:使用前缀和优化暴力枚举的时间复杂度。
时间复杂度:$O(n^2)$
参考代码(C++):
相关问题
【洛谷 P2513】 [HAOI2009]逆序对数列(DP)
这道题目还可以使用树状数组或线段树来实现,时间复杂度也为 $\mathcal{O}(n\log n)$。这里给出使用树状数组的实现代码。
解题思路:
1. 读入数据;
2. 将原数列离散化,得到一个新的数列 b;
3. 从右往左依次将 b 数列中的元素插入到树状数组中,并计算逆序对数;
4. 输出逆序对数。
代码实现:
```c++
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int MAXN = 500005;
struct Node {
int val, id;
bool operator<(const Node& other) const {
return val < other.val;
}
} nodes[MAXN];
int n, a[MAXN], b[MAXN], c[MAXN];
long long ans;
inline int lowbit(int x) { return x & (-x); }
void update(int x, int val)
{
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += val;
}
}
int query(int x)
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += c[i];
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
nodes[i] = {a[i], i};
}
std::sort(nodes + 1, nodes + n + 1);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (i == 1 || nodes[i].val != nodes[i - 1].val) {
++cnt;
}
b[nodes[i].id] = cnt;
}
for (int i = n; i >= 1; --i) {
ans += query(b[i] - 1);
update(b[i], 1);
}
printf("%lld\n", ans);
return 0;
}
```
注意事项:
- 在对原数列进行离散化时,需要记录每个元素在原数列中的位置,便于后面计算逆序对数;
- 设树状数组的大小为 $n$,则树状数组中的下标从 $1$ 到 $n$,而不是从 $0$ 到 $n-1$;
- 在计算逆序对数时,需要查询离散化后的数列中比当前元素小的元素个数,即查询 $b_i-1$ 位置上的值;
- 在插入元素时,需要将离散化后的数列的元素从右往左依次插入树状数组中,而不是从左往右。