混了半学期开始好好补题
好好做人ing
题目来自洛谷，题解听从里面大佬的指点，所以
慢慢爬吧。。。
A.地毯
一个简单的前缀和
由于数据比较小可以直接暴力过，但是数据大的话怎么办呢
直接tle？
#include<iostream>
using namespace std;
int ar_1[2000][2000];
int main()
{
int n, m;
cin >> n>>m;
for (int i = 1; i <=m;++i){
//暴力枚举加遍历
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int j = x1; j <= x2;++j){
for(int k= y1; k <= y2;++k){
++ar_1[j][k];
}
}
}
for (int i = 1; i <= n;++i){
for (int j = 1; j <= n;++j){
cout << ar_1[i][j]<<" ";
}
cout << endl;
}
return 0;
}
对于此类问题我们可以采用前缀和的策略求解，大致思路，如果给出在一定范围内对数组做相同加减操作，我们可以记录首位位置与数值大小，并对首位和(末尾+1)的两个数做操作，并在最后对数组依次递推的方式求值，从而使原来O(n3)的时间复杂度降低到O(n2)从而极大的优化算法,代码如下
#include<iostream>
using namespace std;
int ar_1[1024][1024];
int main()
{
int n, m, x1, x2, y1, y2;
cin >> n >> m;
while(m--){
cin >> x1 >> y1 >> x2 >> y2;
for (int i = x1; i <= x2;++i){
++ar_1[i][y1];
--ar_1[i][y2+1];
}
}
for (int i = 1; i <= n;i++){
for (int j = 1; j <= n;++j){
ar_1[i][j] += ar_1[i][j - 1];
cout << ar_1[i][j] << " ";
}
cout << endl;
}
return 0;
}
就一题？
B.最大加权矩形
题目简介，在N*N的正方形中找到加权最重的矩形
题目分析，直接暴力求解？
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time:19.52
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 128;
int n;
int arr[N][N],temp_arr[N];
ll ans, cnt;
int js(int x,int y,int z)
{
int temp_1=0;
for (int i = x; i <= y;++i)
{
temp_1 += arr[i][z];
}
return temp_1;
}
int main()
{
//读数
cin >> n;
for (int i = 0; i < n;++i)
{
for (int j = 0; j < n;++j)
{
cin >> arr[i][j];
}
}
//压缩遍历
for (int i = 0; i < n;++i)
{
for (int j = i; j < n;++j)
{
for (int k = 0; k < n;++k)
{
temp_arr[k] = js(i, j, k);
}
cnt = 0;
for (int k = 0; k < n; ++k)
{
if(cnt<0)
cnt = 0;
cnt += temp_arr[k];
ans = max(cnt, ans);
}
}
}
if(ans>0)
cout << ans;
else cout << 0;
return 0;
}
天啊四个for真的能行吗？
我们可不可以对他用前缀和的方式对他优化呢？
要怎么优化呢？
如果我们读数时使其每一个都加上一行或者是上一列的权重会有什么结果？
不难发现我们用加上权重的值去将去前面某个位置的值可以直接得到这两个值之间的权重和（左开右闭区间）从而简便了算法
代码如下
/*
* Referce:前缀和加动态规划
* @Author:FollyFish
* @Date:3.11
* @Time:20.24
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 128;
int ar_1[N][N];
int ans;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n;++i)
{
for (int j = 1; j <= n;++j)
{
int temp;
cin >> temp;
ar_1[i][j]=temp+ar_1[i - 1][j];//读数时进行操作
}
}
for (int i = 1; i <= n;++i)//和第一个代码思路一致
{
for (int j = 0; j < i;++j)
{
int sum = 0;
for (int k = 1; k <= n;++k)
{
int temp=ar_1[i][k]-ar_1[j][k];
if(sum<0)
sum = 0;
sum += temp;
ans = max(sum, ans);
}
}
}
cout << ans;
return 0;
}
这样我们就少了一个for得到一个O(n3)的算法
-----------------------手写的分割线-------------------------
在来两题？
可。
C.领地选择
思路与B题一致练练手吧
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time: 21.17
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1024;
int mp[N][N];
int n, m, c,ans=-2147483647;//int所能去的最小值
int x, y;
int main()
{
cin >> n >> m >> c;
for (int i = 1; i <= n;++i)
{
for (int j = 1; j <= m;++j)
{
int temp;
cin >> temp;
mp[i][j] = temp + mp[i - 1][j];
}
}
for (int i = c; i <= n; ++i)
{
for (int k = c; k <= m; ++k)
{
int temp=0;
for (int j = k - c+1; j <= k;++j)
{
temp += (mp[i][j] - mp[i-c][j]);
}
if(ans<temp){
x = k - c + 1;
y = i - c + 1;
ans = max(ans, temp);
}
}
}
cout <<y<<" "<<x;
return 0;
}
想不到吧还有一题，在练练吧
相信你已经很熟练了吧
/*
* Referce:
* @Author:FollyFish
* @Date:3.11
* @Time:22.00
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+8;
int n,m;
ll ar[N];
struct o{
int ai, bi, ci;
} money[N];
ll ans;
ll js(int x)
{
return min(ar[x] * money[x].ai , (money[x].ci + money[x].bi * ar[x]));
}
int main()
{
cin >> n>> m;
int temp_1, temp_2,left,right;
cin >> left;
--m;
while(m--){
//需要得到一个正序的数列
cin >> right;
temp_1 = max(left, right);
temp_2 = min(left, right);
++ar[temp_2];
--ar[temp_1];
left = right;
}
for (int i = 1; i <= n-1;++i){
cin>>money[i].ai>>money[i].bi>>money[i].ci;
}
for (int i = 1; i <= n;++i)
ar[i + 1] += ar[i];
for (int i = 1; i <= n;++i){
ans += js(i);
}
cout << ans;
return 0;
}
手写的文末~~ >…<