课上实例1

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// 防止出现边界问题 
const int N = 5010;

// n为长,m为宽 
int n, m;
// 本题开两个数组可能会超内存,需优化空间
// 只保留一个前缀和数组
// 原数组和前缀和数组是可以合成一个的 
// s是二维前缀和矩阵
int s[N][N];

int main()
{
    // cnt为所有目标的个数
    // R为边长 
    int cnt, R;
    cin >> cnt >> R; 
    // 如果R的范围大于目标的最大范围
    // 那此时R再大结果也没有区别 
    R = min(5001, R);

    // n和m可能小于R,此时会有边界问题
    // 如果R大于所有坐标最大值,可能会导致枚举坐标时枚举不到
    // 因为后面枚举时是枚举矩形的右下角
    // 这种情况下右下角不存在,会少枚举很多矩阵 
    // 不妨把边界的最大值设置成R一样大,这样右下角是存在的
    // 这里 n = m = R;为了让n和m一定大于等于R
    // 为了让下面的枚举至少枚举一次 
    n = m = R;

    while (cnt -- )
    {
        int x, y, w;
        cin >> x >> y >> w;
        // 一维前缀和规定S0 = 0
        // 二维前缀和规定S0i = Si0 = 0
        // 为了防止出现边界问题
        // 因此特殊规定所有前缀和的问题,坐标都是≥1的 
        // 因此将本题坐标整体向右平移一格,向下平移一格 
        x ++, y ++ ;
        // n为横坐标最大值
        // m为纵坐标最大值 
        n = max(n, x), m = max(m, y);
        // 记录价值 
        s[x][y] += w;
    }

    // 预处理前缀和
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            // 因原数组与前缀和数组合二为一
            // 因此更新前s[i][j]存的是原数组a[i][j]的值 
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;

    // 枚举所有边长是R的矩形,枚举(i, j)为右下角
    for (int i = R; i <= n; i ++ )
        for (int j = R; j <= m; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    cout << res << endl;

    return 0;
}

课上实例2

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// 最坏情况前缀和可能是100000^2 
typedef long long LL;

const int N = 100010;

int n, k;
// s为前缀和数组 
// cnt是每个余数的个数 
LL s[N], cnt[N];

int main()
{
    // 读入较多,用scanf 
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        // 同时计算前缀和 
        s[i] += s[i - 1];
    }

    LL res = 0;
    // 边界s[0 % k == 0]
    // 因此循环之前余数是0的数已经有一个了
    // 思路中是从0开始的,枚举时从1开始 
    cnt[0] = 1;
    // 枚举右端点 
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }

    printf("%lld\n", res);

    return 0;
}

课上实例3

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// 两个分支选p或选q
// m表示当前要凑的总数量
// 如果m == 0,就表示m已经被凑出来了
// 否则枚举当前选哪种糖
// 如果选p并且m - p可以被凑出来,那就是说明m可以被凑出
// 同理如果选q并且m - q可以被凑出来,那就说明m可以被凑出。
bool dfs(int m, int p, int q)
{
    // 如果m是0说明凑出来了 
    if (!m) return true;

    // 否则,当m≥p,爆搜 
    if (m >= p && dfs(m - p, p, q)) return true;
    if (m >= q && dfs(m - q, p ,q)) return true;
    // 都不行返回false 
    return false;
}

int main()
{
    int p, q;

    cin >> p >> q;

    int res = 0;
    // 暴力枚举,当枚举到一个比较大的数,认为有解
    // 枚举到1000,超过1000就认为可以被凑出来 
    for (int i = 1; i <= 1000; i ++ )
    {
        // 找到1000以内最大不能被凑出的数 
        if (!dfs(i, p, q)) res = i;
    }

    cout << res << endl;

    return 0;
}

课上实例4

#include <iostream>

using namespace std;

int main()
{
    int p, q;
    cin >> p >> q;
    // 如果a和b均为正整数且互质
    // 那么由ax+by(x≥0, y≥0)不能凑出的最大数为(a-1)(b-1)-1 
    // 整理后为ab - a - b 
    cout << (p - 1) * (q - 1) - 1 << endl;

    return 0;
}

课上实例5

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int x[N];

int main()
{
    // 读入所有蚂蚁 
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> x[i];

    // 分别表示左边向右走的蚂蚁数量和右边向左走的蚂蚁数量
    int left = 0, right = 0;    
    for (int i = 1; i < n; i ++ )
        // 在左边,向右走 
        if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ;
        // 在右边,向左走 
        else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ;

    if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
    else cout << left + right + 1 << endl;

    return 0;
}

课上实例6

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = n;
    while (n >= 3)
    {
        // n一直等于瓶盖的个数 
        res += n / 3;   // 默认下取整 
        n = n / 3 + n % 3;
    }

    cout << res << endl;

    return 0;
}