铺地毯

直接枚举哪张地毯覆盖在当前地毯上面。

#include <cstdio>
struct node {
    int a, b, g, k;
} carpet[10001];
int main() {
    int n, x, y;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d %d", &carpet[i].a, &carpet[i].b, &carpet[i].g, &carpet[i].k); //左下角的坐标以及在 x 轴和 y 轴方向的长度
    scanf("%d %d", &x, &y);
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        int leftx = carpet[i].a, lefty = carpet[i].b, rightx = carpet[i].a + carpet[i].g, righty = carpet[i].b + carpet[i].k;
        if (leftx <= x && rightx >= x && lefty <= y && righty >= y) ans = i;
    }
    printf("%d\n", ans);
    return 0;
}

选择客栈

首先先维护一个前缀和 prefix[i][j] 表示在第号位置之前有多少号元素。

接着维护一个后缀和 suffix ，道理相同。

接着枚举每一个点，把它当作咖啡馆，看看是不是符合要求，如果符合要求的话，那么它所带来的价值便是前缀和后缀和。但是，这样做无疑会使一些点重复更新，因此，每次前面更新的点为 prefix[i][j] - prefix[i][last] 个，代表上一个被更新的元素。

#include <cstdio>
#include <cstring>
#define MAXN 200001
struct node{
    int color, cost;
} hotel[MAXN];
int prefix[51][MAXN], suffix[51][MAXN];
int main() {
    int n, k, p;
    scanf("%d %d %d", &n, &k, &p);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &hotel[i].color, &hotel[i].cost);
        for (int j = 0; j < k; j++)
            prefix[j][i] = prefix[j][i - 1];
        prefix[hotel[i].color][i]++;
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < k; j++)
            suffix[j][i] = suffix[j][i + 1];
        suffix[hotel[i].color][i]++;
    }
    int last = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (hotel[i].cost <= p) {
            for (int j = 0; j < k; j++)
                ans += (prefix[j][i] - prefix[j][last]) * suffix[j][i];
            ans--, last = i;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Mayan 游戏

无（大雾

计算系数

首先当时，枚举、的幂数，可以得到以下值：

和容易可以找到上面的规律。

接着，枚举展开后每一项的系数，可以得到：

然后可以发现，这就是杨辉三角。

因此，构造出与杨辉三角就行了，然后如果 x[i][m + 1] = n 时，输出系数就可以啦。

#include <cstdio>
#define MOD 10007
long long polynomial[1001][1001], x[1001][1001];
void make(int k) {
    polynomial[1][1] = polynomial[1][2] = 1;
    for (int i = 2; i <= k; i++) polynomial[i][1] = 1;
    for (int i = 2; i <= k; i++)
        for (int j = 2; j <= i + 1; j++)
            polynomial[i][j] = (polynomial[i - 1][j] + polynomial[i - 1][j - 1] + MOD) % MOD;
    for (int i = 1; i <= k; i++)
        for (int j = i, cnt = 1; j >= 0; j--, cnt++)
            x[i][cnt] = j;
}
long long pow(int base, int power) {
    long long ans = 1;
    for (int i = 1; i <= power; i++)
        ans = (ans * base + MOD) % MOD;
    return ans;
}
int main() {
    int a, b, k, n, m;
    scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);
    //构建 k 层杨辉三角
    make(k);
    for (int i = 1; i <= k; i++) {
        if (x[i][m + 1] == n) {
            printf("%lld\n", (((pow(a, n) * pow(b, m) + MOD) % MOD) * polynomial[i][m + 1] + MOD) % MOD);
            return 0;
        }
    }
    return 0;
}

聪明的质监员

二分答案

而直接每次枚举的话，时间复杂度为无疑会。

考虑到区间会重复，因此每次先处理一个前缀和就行了。

当 y 比 s 小的时候，尽可能多的让元素进来，因此便减小值。

#include <cstdio>
#define MAXN 200001
struct node{
    long long weight, price;
} stone[MAXN];
long long prefix[MAXN][3], section[MAXN][3];
long long n, m, s;
long long ans = 9223372036854775807;
long long max(long long a, long long b) {return a > b ? a : b;};
long long min(long long a, long long b) {return a < b ? a : b;};
long long abs(long long a) {return a < 0 ? -a : a;};
int main() {
    scanf("%lld %lld %lld", &n, &m, &s);
    long long left = 1, right = 0;
    for (long long i = 1; i <= n; i++) {
        scanf("%lld %lld", &stone[i].weight, &stone[i].price);
        right = max(right, stone[i].weight);
    }
    for (long long i = 1; i <= m; i++) {
        scanf("%lld %lld", &section[i][1], &section[i][2]);
    }
    while (left <= right) {
        long long w = (left + right) >> 1;
        for (long long i = 1; i <= n; i++) {
            if (stone[i].weight >= w) {
                prefix[i][1] = prefix[i - 1][1] + 1;
                prefix[i][2] = prefix[i - 1][2] + stone[i].price;
            } else {
                prefix[i][1] = prefix[i - 1][1];
                prefix[i][2] = prefix[i - 1][2];
            }
        }
        long long y = 0;
        for (long long i = 1; i <= m; i++) {
            y += (prefix[section[i][2]][1] - prefix[section[i][1] - 1][1]) * (prefix[section[i][2]][2] - prefix[section[i][1] - 1][2]);
        }
        //当 y 比 s 小的时候，尽可能多的让元素进来
        if (y < s) right = w - 1;
        else left = w + 1;
        ans = min(ans, abs(s - y));
    }
    printf("%lld\n", ans);
    return 0;
}

观光公交

#include <cstdio>
#define MAXN 10001
int max(int a, int b) {return a > b ? a : b;}
int time1[MAXN], arrive_time[MAXN], last_time[MAXN], tmp_time[MAXN], tree[MAXN], now_people[MAXN], prefix[MAXN];
struct node {
    int t, start, end;
} people[MAXN];
int place_off[MAXN];
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d", &time1[i]); //读入第 i 号节点到第 i + 1 号节点所用时间
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &people[i].t, &people[i].start, &people[i].end);
        place_off[people[i].end]++; //统计当前节点有多少人要下车
        last_time[people[i].start] = max(last_time[people[i].start], people[i].t);
    }
    //计算达到每个点的时间
    for (int i = 2; i <= n; i++) {
        arrive_time[i] = max(last_time[i - 1], arrive_time[i - 1]) + time1[i - 1];
    }
    while (k--) {
        //进行 k 轮比较运算，找出最优解到底应该放在哪里
        long long ans_number = 0, ans_pos = 0;
        //每个在下一个点以及以后下车的人的时间都会变快，但是，当发现当前节点的 last 值比减一要大，也就是哪怕早到这个点，全车的人也都需要等他时，就 break 掉
        for (int i = 2; i <= n; i++) {
            if (!time1[i - 1]) continue;
            long long tmp = 0;
            //为什么不用考虑人等车的时间？
            //因为每个人都要等最后一个人上车之后才离开，没必要
            for (int j = i; j <= n; j++) {
                tmp += place_off[j];
                if (last_time[j] >= arrive_time[j]) break;
            }
            if (tmp > ans_number) {
                ans_number = tmp;
                ans_pos = i;
            }
        }
        time1[ans_pos - 1]--;
        for (int i = ans_pos; i <= n; i++) {
            arrive_time[i]--;
            if (last_time[i] > arrive_time[i]) break;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        ans += (arrive_time[people[i].end] - people[i].t);
    }
    printf("%lld\n", ans);
    return 0;
}

铺地毯

选择客栈

Mayan 游戏

计算系数

x:

y:

聪明的质监员

观光公交