NBUACM-BeginnerRound10.26

Posted on Edited on In Word count in article: 765 Reading time ≈ 3 mins.
  • 啥也不会，随便打打 T_T

https://ac.nowcoder.com/acm/contest/94184

A 小 y 的序列

题目描述

又是一年 CSP，机房的 oier 都在刷题，alan 却在发呆想着小 y，正巧忽然听到隔壁机房某神 zlk 熟悉的声音：“找规律就可以了吧，这个序列感觉很熟悉啊，就是 这其实就是一个 的序列哦，突然隔壁的声音大了起来，zlk，你好像有个数写错了（大雾）~
课后，alan 在纸上写下了这个题目，让 szm 做：给一个长度为 n 的序列 a，你希望改最少的数，使得这个序列满足 吗？。

输入描述

第一行一个整数 ；
第二行 个整数（每两个数之间有个空格），分别表示 到 。

输出描述

输出一个整数 Ans，表示最少需要改多少个数

示例 1

输入

1
2
6
3 4 6 8 13 18

输出

1
1

备注

对于 30%的数据
对于 100%的数据
输入的其他数据的绝对值均小于等于 1e9

Solution

参考了懒狗大佬的 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
inline int a(int n, int a1) {
  return n * (n - 1) / 2 + a1;      // 计算An，以a1为首项
}
unordered_map<int, int> Hash;
int main() {
  int n, x, ai;
  int ct = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x;
    ai = a(i + 1, 0);
    Hash[x - ai]++;                 // 以a1=x-ai为首项的数列元素的计数
    ct = max(ct, Hash[x - ai]);     // 找到满足符合最多项的a1的项计数
  }
  cout << n - ct << endl;
  return 0;
}

B 小 y 的游戏

题目描述

小 y 是一个喜欢打游戏的女孩子，但是 Alan 就从来玩游戏，然后小 y 在游戏里遇到了问题
在游戏中有只怪物，其中第 i 只怪物的血量是。然后操作手柄的你有一种攻击武器，称为“三连冲击波”，每使用一次这个攻击武器，你都可以选择三只怪物被杀伤，它的杀伤力是这样的：
一、首先被冲击的那只怪物的能量会减少 。
二、其次被冲击的那只怪物的能量会减少 。（ 时有效）
三、最后被冲击的那只怪物的能量会减少 。（ 时有效）
（N 为还活着的怪物的数量）
当某只怪物的能量为 或者低于 时，该怪物就会灭亡。你可以按照你的意愿来确定每一次使用攻击武器时，怪物受到冲击的次序。你的任务是计算，至少要使用多少次攻击武器，才能消灭 只怪物？小 y 喜欢 Alan 能帮他解决这个问题，如果你是 Alan, 你能解决这个问题吗？
注意：

  1. 当怪物的能力小于等于 时，你依然可以对它进行攻击。
  2. 在一轮攻击中，同一只怪物不能被攻击多次。

输入描述

多组测试数据。
第一行，一个整数 ，表示有 组测试数据。 。
每组测试数据格式如下：
第一行，一个整数 。 。
第二行,有 个正整数: 第 个正整数是 ，。

输出描述

共 T 行，每行一个整数表示答案。

示例 1

输入

1
2
3
4
5
6
7
8
9
10
20
60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60
20
18 42 44 33 23 7 42 44 8 23 26 48 11 58 43 15 4 29 24 52
3
9 2 2
3
45 17 3
3
3 5 18

输出

1
2
3
4
5
93
46
2
6
3

Solution

参考懒狗大佬的 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T, n, ans;
int a[25], dp[25][1201][1201];
bool judge(int t) {
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j * 9 <= a[i] + 8; ++j) {
      for (int k = 0; j * 9 + k * 3 <= a[i] + 8; ++k) {
        int x = max(0, a[i] - j * 9 - k * 3);
        if (j + k + x > t) continue;
        for (int p = j; p <= 93; ++p) {
          for (int q = k; q <= 93; ++q) {
            dp[i][p][q] = min(dp[i][p][q], dp[i - 1][p - j][q - k] + x);
          }
        }
      }
    }
  }
  for (int i = 0; i <= t; i++)
    for (int j = 0; j <= t; j++)
      if (dp[n][i][j] <= t) return true;

  return false;
}
int main() {
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      if (a[i] < 0) a[i] = 0;
    }
    int l = 0, r = 93;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (judge(mid)) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    cout << l << "\n";
  }
  return 0;
}
未完待续