');}

NOIP2011 提高组

Author Avatar
Actinoi 10月 14, 2020

铺地毯

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

  1. #include <cstdio>
  2. struct node {
  3.     int a, b, g, k;
  4. } carpet[10001];
  5. int main() {
  6.     int n, x, y;
  7.     scanf("%d", &n);
  8.     for (int i = 1; i <= n; i++)
  9.         scanf("%d %d %d %d", &carpet[i].a, &carpet[i].b, &carpet[i].g, &carpet[i].k); //左下角的坐标以及在 x 轴和 y 轴方向的长度
  10.     scanf("%d %d", &x, &y);
  11.     int ans = -1;
  12.     for (int i = 1; i <= n; i++) {
  13.         int leftx = carpet[i].a, lefty = carpet[i].b, rightx = carpet[i].a + carpet[i].g, righty = carpet[i].b + carpet[i].k;
  14.         if (leftx <= x && rightx >= x && lefty <= y && righty >= y) ans = i;
  15.     }
  16.     printf("%d\n", ans);
  17.     return 0;
  18. }

选择客栈

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

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

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

  1. #include <cstdio>
  2. #include <cstring>
  3. #define MAXN 200001
  4. struct node{
  5.     int color, cost;
  6. } hotel[MAXN];
  7. int prefix[51][MAXN], suffix[51][MAXN];
  8. int main() {
  9.     int n, k, p;
  10.     scanf("%d %d %d", &n, &k, &p);
  11.     for (int i = 1; i <= n; i++) {
  12.         scanf("%d %d", &hotel[i].color, &hotel[i].cost);
  13.         for (int j = 0; j < k; j++)
  14.             prefix[j][i] = prefix[j][i - 1];
  15.         prefix[hotel[i].color][i]++;
  16.     }
  17.     for (int i = n; i >= 1; i--) {
  18.         for (int j = 0; j < k; j++)
  19.             suffix[j][i] = suffix[j][i + 1];
  20.         suffix[hotel[i].color][i]++;
  21.     }
  22.     int last = 0;
  23.     long long ans = 0;
  24.     for (int i = 1; i <= n; i++) {
  25.         if (hotel[i].cost <= p) {
  26.             for (int j = 0; j < k; j++)
  27.                 ans += (prefix[j][i] - prefix[j][last]) * suffix[j][i];
  28.             ans--, last = i;
  29.         }
  30.     }
  31.     printf("%lld\n", ans);
  32.     return 0;
  33. }

Mayan 游戏

无（大雾

计算系数

首先当 a=b=1 时，枚举 x 、 y 的幂数，可以得到以下值：

x: 

  1. 1 0
  2. 2 1 0
  3. 3 2 1 0
  4. 4 3 2 1 0

y: 

  1. 0 1
  2. 0 1 2
  3. 0 1 2 3
  4. 0 1 2 3 4

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

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

  1. 1 1
  2. 1 2 1
  3. 1 3 3 1
  4. 1 4 6 4 1

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

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

  1. #include <cstdio>
  2. #define MOD 10007
  3. long long polynomial[1001][1001], x[1001][1001];
  4. void make(int k) {
  5.     polynomial[1][1] = polynomial[1][2] = 1;
  6.     for (int i = 2; i <= k; i++) polynomial[i][1] = 1;
  7.     for (int i = 2; i <= k; i++)
  8.         for (int j = 2; j <= i + 1; j++)
  9.             polynomial[i][j] = (polynomial[i - 1][j] + polynomial[i - 1][j - 1] + MOD) % MOD;
  10.     for (int i = 1; i <= k; i++)
  11.         for (int j = i, cnt = 1; j >= 0; j--, cnt++)
  12.             x[i][cnt] = j;
  13. }
  14. long long pow(int base, int power) {
  15.     long long ans = 1;
  16.     for (int i = 1; i <= power; i++)
  17.         ans = (ans * base + MOD) % MOD;
  18.     return ans;
  19. }
  20. int main() {
  21.     int a, b, k, n, m;
  22.     scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);
  23.     //构建 k 层杨辉三角
  24.     make(k);
  25.     for (int i = 1; i <= k; i++) {
  26.         if (x[i][m + 1] == n) {
  27.             printf("%lld\n", (((pow(a, n) * pow(b, m) + MOD) % MOD) * polynomial[i][m + 1] + MOD) % MOD);
  28.             return 0;
  29.         }
  30.     }
  31.     return 0;
  32. }

聪明的质监员

二分答案

而直接每次枚举 m 的话，时间复杂度为 O(nm) 无疑会 TLE 。

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

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

  1. #include <cstdio>
  2. #define MAXN 200001
  3. struct node{
  4.     long long weight, price;
  5. } stone[MAXN];
  6. long long prefix[MAXN][3], section[MAXN][3];
  7. long long n, m, s;
  8. long long ans = 9223372036854775807;
  9. long long max(long long a, long long b) {return a > b ? a : b;};
  10. long long min(long long a, long long b) {return a < b ? a : b;};
  11. long long abs(long long a) {return a < 0 ? -a : a;};
  12. int main() {
  13.     scanf("%lld %lld %lld", &n, &m, &s);
  14.     long long left = 1, right = 0;
  15.     for (long long i = 1; i <= n; i++) {
  16.         scanf("%lld %lld", &stone[i].weight, &stone[i].price);
  17.         right = max(right, stone[i].weight);
  18.     }
  19.     for (long long i = 1; i <= m; i++) {
  20.         scanf("%lld %lld", &section[i][1], &section[i][2]);
  21.     }
  22.     while (left <= right) {
  23.         long long w = (left + right) >> 1;
  24.         for (long long i = 1; i <= n; i++) {
  25.             if (stone[i].weight >= w) {
  26.                 prefix[i][1] = prefix[i - 1][1] + 1;
  27.                 prefix[i][2] = prefix[i - 1][2] + stone[i].price;
  28.             } else {
  29.                 prefix[i][1] = prefix[i - 1][1];
  30.                 prefix[i][2] = prefix[i - 1][2];
  31.             }
  32.         }
  33.         long long y = 0;
  34.         for (long long i = 1; i <= m; i++) {
  35.             y += (prefix[section[i][2]][1] - prefix[section[i][1] - 1][1]) * (prefix[section[i][2]][2] - prefix[section[i][1] - 1][2]);
  36.         }
  37.         //当 y 比 s 小的时候，尽可能多的让元素进来
  38.         if (y < s) right = w - 1;
  39.         else left = w + 1;
  40.         ans = min(ans, abs(s - y));
  41.     }
  42.     printf("%lld\n", ans);
  43.     return 0;
  44. }

观光公交

  1. #include <cstdio>
  2. #define MAXN 10001
  3. int max(int a, int b) {return a > b ? a : b;}
  4. int time1[MAXN], arrive_time[MAXN], last_time[MAXN], tmp_time[MAXN], tree[MAXN], now_people[MAXN], prefix[MAXN];
  5. struct node {
  6.     int t, start, end;
  7. } people[MAXN];
  8. int place_off[MAXN];
  9. int main() {
  10.     int n, m, k;
  11.     scanf("%d %d %d", &n, &m, &k);
  12.     for (int i = 1; i <= n - 1; i++) {
  13.         scanf("%d", &time1[i]); //读入第 i 号节点到第 i + 1 号节点所用时间
  14.     }
  15.     for (int i = 1; i <= m; i++) {
  16.         scanf("%d %d %d", &people[i].t, &people[i].start, &people[i].end);
  17.         place_off[people[i].end]++; //统计当前节点有多少人要下车
  18.         last_time[people[i].start] = max(last_time[people[i].start], people[i].t);
  19.     }
  20.     //计算达到每个点的时间
  21.     for (int i = 2; i <= n; i++) {
  22.         arrive_time[i] = max(last_time[i - 1], arrive_time[i - 1]) + time1[i - 1];
  23.     }
  24.     while (k--) {
  25.         //进行 k 轮比较运算，找出最优解到底应该放在哪里
  26.         long long ans_number = 0, ans_pos = 0;
  27.         //每个在下一个点以及以后下车的人的时间都会变快，但是，当发现当前节点的 last 值比减一要大，也就是哪怕早到这个点，全车的人也都需要等他时，就 break 掉
  28.         for (int i = 2; i <= n; i++) {
  29.             if (!time1[i - 1]) continue;
  30.             long long tmp = 0;
  31.             //为什么不用考虑人等车的时间？
  32.             //因为每个人都要等最后一个人上车之后才离开，没必要
  33.             for (int j = i; j <= n; j++) {
  34.                 tmp += place_off[j];
  35.                 if (last_time[j] >= arrive_time[j]) break;
  36.             }
  37.             if (tmp > ans_number) {
  38.                 ans_number = tmp;
  39.                 ans_pos = i;
  40.             }
  41.         }
  42.         time1[ans_pos - 1]--;
  43.         for (int i = ans_pos; i <= n; i++) {
  44.             arrive_time[i]--;
  45.             if (last_time[i] > arrive_time[i]) break;
  46.         }
  47.     }
  48.     long long ans = 0;
  49.     for (int i = 1; i <= m; i++) {
  50.         ans += (arrive_time[people[i].end] - people[i].t);
  51.     }
  52.     printf("%lld\n", ans);
  53.     return 0;
  54. }