Byte 8.29 written test replay (in question recall)

Question 1 natural numbers a and b

Simple topic meaning

Give the number a and B, and then give a number + 1 in the first round, a number + 2 in the second round, and a number + i in the i round. You can choose which number to add in each round. Ask you to become the same minimum number of rounds.

thinking

Add 1 to the first addition and 2 to the second addition, then add 1.2 to the first i 3... i, that is, the arithmetic sequence of i. If you want a and b to be equal, First of all, the sum of the arithmetic sequence is larger than the difference between a and b (otherwise, even if they are all added to the small number, the small number cannot be equal to the large number). Of course, this is not always the case, such as 1 and 3. It is obviously impossible to add 1 to 3 and 3. If you want a and b to be the same at this time, the condition to be satisfied is that the additional part is an even number, so that it can be evenly distributed. For example, 1 and 3 are finally added If you add 5 and 5 instead of 3 and 3, the additional part is 4. This 4 is divided into two parts, 2, and divided into two numbers on average.
To sum up: the two conditions are that the sum of the arithmetic sequence is greater than the original difference, and the extra part from the original difference is even. Then, we first calculate the minimum i that meets the first condition. If the second condition cannot be met at this time, we will continue the i + + operation (the variable now in the source code) until the second condition is met. It can be proved that up to four i + + operations can make it meet the second condition.

code

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    int cha = abs(b - a);
    int now = sqrt(cha * 2);
    while (true) {
      if (now * (now + 1) / 2 >= cha && (now * (now + 1) / 2 - cha) % 2 == 0)
        break;
      now++;
    }
    cout << now << endl;
  }
}

Question 2 Xiao Ming plays games

Simple topic meaning

thinking

Since every day's progress is positive, we can first prefix and calculate the three attributes of each day. For each skill, if the attribute on day i is enough to learn this skill, then i+1 can certainly learn it (because the attribute on day i+1 must be higher than i); similarly, if the attribute on day i cannot learn this skill, then i-1 can certainly not learn it.
After satisfying the monotone condition, we can use the dichotomy to judge the result.

code

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

const int maxn = 1e5 + 5;
struct node {
  int a, b, c;
};
node grow[maxn], pre[maxn];
int main() {
  int n, m, a, b, c;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a >> b >> c;
    pre[i].a = pre[i - 1].a + a;
    pre[i].b = pre[i - 1].b + b;
    pre[i].c = pre[i - 1].c + c;
  }
  for (int i = 1; i <= m; i++) {
    cin >> a >> b >> c;
    int l = 1, r = n, ans = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (pre[mid].a >= a && pre[mid].b >= b && pre[mid].c >= c) {
        ans = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    cout << ans << " ";
  }
}

Question 3 Gobang

Simple topic meaning

thinking

Because the data range is very small, you can enumerate whether each position plays chess, and then check the whole chessboard to judge whether the chessboard is connected into five pieces at this time. The specific check method is to enumerate each position of the chessboard and extend 5 bits from this position to eight directions. If a[i][j]=1 all the time, it means that there are chess in these five positions, that is, they are connected into five pieces. As long as a certain direction of a certain position can be connected into five, it indicates that there are five connected in the chessboard at this time, that is, the check is successful, and playing chess in this position can win.

code

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

int a[11][11], n;
bool check() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      bool flag1 = true, flag2 = true, flag3 = true, flag4 = true;
      bool flag5 = true, flag6 = true, flag7 = true, flag8 = true;
      for (int k = 0; k <= 4; k++) {
        if (j + k > n || a[i][j + k] == 0)
          flag1 = false;
        if (j - k < 1 || a[i][j - k] == 0)
          flag2 = false;
        if (i + k > n || a[i + k][j] == 0)
          flag3 = false;
        if (i - k < 1 || a[i - k][j] == 0)
          flag4 = false;
        if (i + k > n || j + k > n || a[i + k][j + k] == 0)
          flag5 = false;
        if (i + k > n || j - k < 1 || a[i + k][j - k] == 0)
          flag6 = false;
        if (i - k < 1 || j + k > n || a[i - k][j + k] == 0)
          flag7 = false;
        if (i - k < 1 || j - k < 1 || a[i - k][j - k] == 0)
          flag8 = false;
      }
      if (flag1 || flag2 || flag3 || flag4 || flag5 || flag6 || flag7 || flag8)
        return true;
    }
  return false;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      cin >> a[i][j];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (a[i][j] != 0)
        continue;
      a[i][j] = 1;
      if (check())
        cout << i << " " << j << endl;
      a[i][j] = 0;
    }
}

Question 4 playing cards

Simple topic meaning

thinking

Since the data range is only 26, enumerate whether each card is reserved or used, and the result can be calculated in the time of 2 ^ 26. We can enumerate with recursion

code

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

int n = 26, ans = -1;
int a[27], b[27];
void dfs(int dep, int now, int pre1, int pre2) {
  if (dep == n) {
    int sum = now + pre1 + pre2 + 3 * a[dep];
    if (sum > b[dep])
      ans = max(ans, sum);
    return;
  }
  if (a[dep] + now + pre1 + pre2 > b[dep])
    dfs(dep + 1, now + a[dep], 0, pre1);
  if (3 * a[dep] + now + pre1 + pre2 > b[dep])
    dfs(dep + 1, now, 3 * a[dep], pre1);
}
int main() {
  for (int i = 1; i <= n; i++)
    cin >> b[i];
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  dfs(1, 0, 0, 0);
  cout << ans << endl;
}