第一题 地毯

题目背景

此题约为NOIP提高组Day2T1难度。

题目描述

在 n × n的格子上有 m 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 n , m。意义如题所述。

接下来 m 行，每行两个坐标 ( x 1 , y 1 )  和 ( x 2 , y 2 ) ，代表一块地毯，左上角是 ( x 1 , y 1 )，右下角是 ( x 2 , y 2 ) 。

输出格式

输出 n 行，每行 n 个正整数。

第 i 行第 j 列的正整数表示 ( i , j )这个格子被多少个地毯覆盖。

样例 #1

样例输入 #1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

覆盖第一、二个地毯后：

覆盖所有地毯后：

数据范围

对于 20 % 的数据，有 n ≤ 50，m ≤ 100。

对于 100 % 数据，有 n , m ≤ 1000。

NOIP2015 普及组 T3

解题思路

1）差分的题目。

2）本质就是用O(1)复杂度来实现O(N)的操作。

参考代码

#include<bits/stdc++.h> 
using namespace std;
int a[1050][1050];
int main()
{
  int n,m,x1,y1,x2,y2;
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>x1>>y1>>x2>>y2;
    for(int j=x1;j<=x2;j++)
    {
      a[j][y1]++;
      a[j][y2+1]--;
    }
  }
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      a[i][j]+=a[i][j-1];
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

第二题 海底高铁

题目背景

题目描述

该铁路经过 N 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 i段铁路连接了城市 i和城市 i + 1 ( 1 ≤ i < N )。如果搭乘的比较远，需要购买多张车票。第 i 段铁路购买纸质单程票需要 A i 博艾元。

虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 i 段铁路，需要花 C i 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 B i ( B i < A i ) 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 i段铁路的 IC 卡，无法乘坐别的铁路的车。

Uim 现在需要出差，要去 M  个城市，从城市 P 1 出发分别按照 P 1 , P 2 , P 3 , ⋯   , P M 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数，N , M 。

接下来一行，M 个数字，表示 P i 。

接下来 N − 1 行，表示第 i段铁路的 A i , B i , C i 。

输出格式

一个整数，表示最少花费

样例 #1

样例输入 #1

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

样例输出 #1

6394

提示

2 到 3 以及 8到 9买票，其余买卡。

对于 30 % 数据 M = 2。

对于另外 30 % 数据 N ≤ 1000 ， M ≤ 1000。

对于 100 % 的数据 M , N ≤ ， A i , B i , C i ≤ 。

解题思路

1）利用差分和前缀和来求出每一段需要的次数。

2）总花费加上每一段路径费用的较小值。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p[100010];
ll t[100010];
ll a[100010],b[100010],c[100010],x,y,n,m,ans=0;
int main()
{
  cin>>n>>m;
  for(ll i=1;i<=m;i++)
    cin>>p[i];
  for(ll i=1;i<=n-1;i++)
    cin>>a[i]>>b[i]>>c[i];
  for(ll i=1;i<=m-1;i++)
  {
    x=min(p[i],p[i+1]);
    y=max(p[i],p[i+1]);
    t[x]++;
    t[y]--;
  }
  for(ll i=1;i<=n;i++)
  {
    t[i]+=t[i-1];
  }
  for(ll i=1;i<=n-1;i++)
    ans+=min(a[i]*t[i],(b[i]*t[i]+c[i]));
  cout<<ans;
  return 0;
}

第三题【CSGRound2】光骓者的荣耀

题目背景

小 K 又在做白日梦了。他进入到他的幻想中，发现他打下了一片江山。

题目描述

小 K 打下的江山一共有 n 个城市，城市 i和城市 i + 1有一条双向高速公路连接，走这条路要耗费时间 a i 。

小 K 为了关心人民生活，决定定期进行走访。他每一次会从 1  号城市到 n 号城市并在经过的城市进行访问。其中终点必须为城市 n。

不仅如此，他还有一个传送器，传送半径为 k，也就是可以传送到 i − k和 i + k。如果目标城市编号小于 1则为 1，大于 n  则为 n。

但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。

注意：他可以不访问所有的城市，使用传送器不耗费时间。

输入格式

两行，第一行 n , k。

第二行 n − 1个整数，第 i个表示a i 。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

4 0
1 2 3

样例输出 #1

6

样例 #2

样例输入 #2

4 1
1 2 3

样例输出 #2

3

提示

样例解释 1：

样例 1,2 的图示均为以下图片：

不使用传送器直接走，答案为 6，可以证明这个是最小值。

样例解释 2：

在 3  处使用，传送到 4，答案为 3 ，可以证明这个是最小值。

数据范围：

对于所有数据，a i > 0

解题思路

1）利用差分和前缀和来求出每一段需要的次数。

2）总花费加上每一段路径费用的较小值。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum[1000001];
ll n,k;
int main()
{
  cin>>n>>k;
  if(k>=n-1)
  {
    cout<<0<<endl;
    return 0;
  } 
  for(int i=1;i<=n-1;i++)
  {
    ll x;
    cin>>x;
    sum[i]=sum[i-1]+x;
  }
  ll cnt=sum[k];
  for(int i=2;i<=n-k;i++)
  {
    cnt=max(cnt,sum[i+k-1]-sum[i-1]);
  }
  cout<<sum[n-1]-cnt<<endl;
  return 0;
}

第四题 最大加权矩形

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 n × n矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 [ − 127 , 127 ],例如

 0 –2 –7  0 
 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

9  2
-4  1
-1  8

和为 15 。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：n，接下来是 n 行 n 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

样例 #1

样例输入 #1

4
0 -2 -7 0
 9 2 -6 2
-4 1 -4  1 
-1 8  0 -2

样例输出 #1

15

提示

1 ≤ n ≤ 120

解题思路

1）二维前缀和。

2）枚举每个左上角和右下角，若左上角的下标为(x1,y1)，右下角的下标为(x2,y2)，则矩形中加权和为s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]。

3）找到最大矩形和。

参考代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL a[125][125];
LL s[125][125];
int main()
{
  int N;
  cin>>N;
  for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
    {
      cin>>a[i][j];
      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
  LL ans=INT_MIN;
  for(int x1=1;x1<=N;x1++)
    for(int y1=1;y1<=N;y1++)
      for(int x2=x1;x2<=N;x2++)
        for(int y2=y1;y2<=N;y2++)
          ans=max(ans,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
  cout<<ans;
    return 0;
}