本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC15553-数学考试

题目链接

https://ac.nowcoder.com/acm/problem/15553

题目描述

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间， 即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）

输出一个整数，qwb能获得的最大分数。

测试样例

输入

2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出

6
7

解题思路

这道题看似简单，但是时间卡的很死，暴力TLE，所以需要使用前缀和，然后统计长度时从第k为寻找即可。同时两个区间要没有交集，因此一个从l查找，一个从l+k查找即可避免。解题代码非常巧，多积累，这种前缀和的思想很重要。

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[2000005];
int main()
{

    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            //前缀和，a[i]就是1~i的所有数之和
            cin >> a[i], a[i] += a[i - 1];
        }
        ll ma = -1e18, ans = -1e18;
        //从k开始找，意味着一定是长度大于等于k的数之和
        for (int i = k; i + k <= n; i++)
        {
            //寻找第一个最大值，a[i]-a[i-k]保证了长度一定是k
            ma = max(ma, a[i] - a[i - k]);
            //很巧，ans刚好是找a[i+1]~a[i+k]的数之和，避免了两个区间交叉的情况出现
            ans = max(ans, ma + a[i + k] - a[i]);
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

NC15172-情人节的电灯泡

题目链接

https://ac.nowcoder.com/acm/problem/15172

题目描述

情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1 <= n <= 1000）的格子，每一个格子都有一个电灯泡，可能是亮的，也可能是灭的（1代表亮， 0代表灭），现在有两种操作，一种是给你一个坐标，对于那个坐标上的灯泡，如果他是亮的，那么熄灭他，反之如果他是灭的，那么打开它。第二种操作是给你两个坐标，第一个坐标代表一个子矩阵的左上角，另一个坐标是右下角，请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧！！！单身狗们！！！！

第一行两个整数，n（1 <= n <= 1000）和m（1 <= m <= 100000），分别代表正方形格子的边长和询问次数。
接下来n行，每一行有n个bool形数字（0或1），代表灯泡的状态。
接下来m行，每一行第一个数字f（1或2）代表操作的类型，如果f是1，那么接下来输入一个坐标（x, y）(1 <= x, y <= n)，对于当前位置的灯泡状态进行改变，如果是2，那么接下来输入两个坐标（x1, y1）(1 <= x1, y1 <= n)， （x2, y2）(1 <= x2, y2 <= n)，确定子矩阵的位置，输出子矩阵中亮着的灯泡数量并换行。对于每一个2操作，输出子矩阵中亮着的灯泡数量并换行。

测试样例

输入

6 4
0 0 1 0 1 0
1 0 1 1 0 1
1 0 0 0 0 0
1 1 0 0 1 0
0 0 0 0 1 1
0 0 0 0 1 0
2 2 2 4 5
1 1 1
2 1 1 6 6
1 2 6

输出

4
14

解题思路

大水题，直接模拟即可，以后再也不摸鱼了www。

解题代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int _map[N][N];

void find(int a, int b, int c, int d)
{
    int sum = 0;
    for (int i = a; i <= c; i++)
    {
        for (int j = b; j <= d; j++)
        {
            if (_map[i][j])
                sum++;
        }
    }
    cout << sum << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> _map[i][j];
        }
    }
    while (m--)
    {
        int index;
        cin >> index;
        if (index == 1)
        {
            int x, y;
            cin >> x >> y;
            _map[x][y] = !_map[x][y];
        }
        else
        {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            find(a, b, c, d);
        }
    }
    system("pause");
    return 0;
}