A. Restoring Three Numbers

Description:

Polycarp has guessed three positive integers $a$, $b$ and $c$. He keeps these numbers in secret, but he writes down four numbers on a board in arbitrary order — their pairwise sums (three numbers) and sum of all three numbers (one number). So, there are four numbers on a board in random order: $a+b$, $a+c$, $b+c$ and $a+b+c$.
You have to guess three numbers $a$, $b$ and $c$ using given numbers. Print three guessed integers in any order.
Pay attention that some given numbers $a$, $b$ and $c$ can be equal (it is also possible that $a=b=c$).

Input:

The only line of the input contains four positive integers $x_1, x_2, x_3, x_4$ ($2 \le x_i \le 10^9$) — numbers written on a board in random order. It is guaranteed that the answer exists for the given number $x_1, x_2, x_3, x_4$.

Output

Print such positive integers $a$, $b$ and $c$ that four numbers written on a board are values $a+b$, $a+c$, $b+c$ and $a+b+c$ written in some order. Print $a$, $b$ and $c$ in any order. If there are several answers, you can print any. It is guaranteed that the answer exists.

Sample Input:

3 6 5 4

Sample Output:

2 1 3

Sample Input:

40 40 40 60

Sample Output:

20 20 20

Sample Input:

201 101 101 200

Sample Output:

1 100 100

题目链接

给出 $a+b,a+c,b+c,a+b+c$ 求 $a、b、c$

求最大值挨个减一下就行

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  std::vector<int> arr(4);
  for (auto &v : arr) std::cin >> v;
  std::sort(arr.begin(), arr.end());

  std::cout << arr[3] - arr[0] << ' ' << arr[3] - arr[1] << ' ' << arr[3] - arr[2] << '\n';
  return 0;
}

B. Make Them Equal

Description:

You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You can choose any non-negative integer $D$ (i.e. $D \ge 0$), and for each $a_i$ you can:

  • add $D$ (only once), i. e. perform $a_i := a_i + D$, or
  • subtract $D$ (only once), i. e. perform $a_i := a_i - D$, or
  • leave the value of $a_i$ unchanged.

It is possible that after an operation the value $a_i$ becomes negative.
Your goal is to choose such minimum non-negative integer $D$ and perform changes in such a way, that all $a_i$ are equal (i.e. $a_1=a_2=\dots=a_n$).

Print the required $D$ or, if it is impossible to choose such value $D$, print -1.

For example, for array $[2, 8]$ the value $D=3$ is minimum possible because you can obtain the array $[5, 5]$ if you will add $D$ to $2$ and subtract $D$ from $8$. And for array $[1, 4, 7, 7]$ the value $D=3$ is also minimum possible. You can add it to $1$ and subtract it from $7$ and obtain the array $[4, 4, 4, 4]$.

Input:

The first line of the input contains one integer $n$ ($1 \le n \le 100$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — the sequence $a$.

Output

Print one integer — the minimum non-negative integer value $D$ such that if you add this value to some $a_i$, subtract this value from some $a_i$ and leave some $a_i$ without changes, all obtained values become equal.
If it is impossible to choose such value $D$, print -1.

Sample Input:

6
1 4 4 7 4 1

Sample Output:

3

Sample Input:

5
2 2 5 2 5

Sample Output:

3

Sample Input:

4
1 3 3 7

Sample Output:

-1

Sample Input:

2
2 8

Sample Output:

3

题目链接

数列每个数可以 $+D、-D、不变$ ,求最小的 $D$ 使得数列经过操作后全部数字相同

数列中不同数字最多不能超过三个,三个时其中两差值须向等

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);
  
  int n; std::cin >> n;
  std::vector<int> arr(n);
  for (auto &v : arr) std::cin >> v;
  std::sort(arr.begin(), arr.end());
  arr.erase(unique(arr.begin(), arr.end()), arr.end());

  int size = (int)arr.size();
  if (size > 3) {
    std::cout << -1 << '\n';
    return 0;
  }
  if (size == 3) {
    if (abs(arr[2] - arr[1]) == abs(arr[1] - arr[0])) {
      std::cout << arr[1] - arr[0] << '\n';
      return 0;
    }
    std::cout << -1 << '\n';
    return 0;
  }
  if (size == 2) {
    if ((arr[1] - arr[0]) & 1) {
      std::cout << arr[1] - arr[0] << '\n';
      return 0;
    }
    std::cout << (arr[1] - arr[0]) / 2 << '\n';
    return 0;
  }
  if (size == 1) {
    std::cout << 0 << '\n';
    return 0;
  }
  return 0;
}

C. Gourmet Cat

Description:

Polycarp has a cat and his cat is a real gourmet! Dependent on a day of the week he eats certain type of food:

  • on Mondays, Thursdays and Sundays he eats fish food;
  • on Tuesdays and Saturdays he eats rabbit stew;
  • on other days of week he eats chicken stake.

Polycarp plans to go on a trip and already packed his backpack. His backpack contains:

  • $a$ daily rations of fish food;
  • $b$ daily rations of rabbit stew;
  • $c$ daily rations of chicken stakes.

Polycarp has to choose such day of the week to start his trip that his cat can eat without additional food purchases as long as possible. Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

Input:

The first line of the input contains three positive integers $a$, $b$ and $c$ ($1 \le a, b, c \le 7\cdot10^8$) — the number of daily rations of fish food, rabbit stew and chicken stakes in Polycarps backpack correspondingly.

Output

Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

Sample Input:

2 1 1

Sample Output:

4

Sample Input:

3 2 2

Sample Output:

7

Sample Input:

1 100 1

Sample Output:

3

Sample Input:

30 20 10

Sample Output:

39

题目链接

一共有三种食物, $\texttt{Polycarp}$ 按周为单位每日吃固定的食物,求在输入粮食储配的情况下他可以维持饮食的最大天数

枚举开始吃食物的日期计算最大天数取最大值

AC代码:

#include <bits/stdc++.h>

std::vector<int> arr, buf;
std::vector<int> d = {-1, 0, 1, 2, 0, 2, 1, 0};

int Calc(int s) {
  int ret = 0;
  for (int i = s; i <= 7; ++i) {
    if (buf[d[i]]) --buf[d[i]];
    else return ret;
    ++ret;
  }
  int cir = std::min(buf[0] / 3, std::min(buf[1] / 2, buf[2] / 2));
  buf[0] -= cir * 3; buf[1] -= cir * 2; buf[2] -= cir * 2;
  ret += 7 * cir;
  for (int i = 1; i <= 7; ++i) {
    if (buf[d[i]]) --buf[d[i]];
    else return ret;
    ++ret;
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  arr.assign(3, 0);
  for (auto &v : arr) std::cin >> v;

  int ans = 0;
  for (int i = 1; i <= 7; ++i) {
    buf = arr;
    ans = std::max(ans, Calc(i));
  }

  std::cout << ans << '\n';
  return 0;
}

D. Walking Robot

Description:

There is a robot staying at $X=0$ on the $Ox$ axis. He has to walk to $X=n$. You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel.
The $i$-th segment of the path (from $X=i-1$ to $X=i$) can be exposed to sunlight or not. The array $s$ denotes which segments are exposed to sunlight: if segment $i$ is exposed, then $s_i = 1$, otherwise $s_i = 0$.
The robot has one battery of capacity $b$ and one accumulator of capacity $a$. For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can't use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can't use the accumulator if its charge is zero).
If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).
If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.
You understand that it is not always possible to walk to $X=n$. You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally.

Input:

The first line of the input contains three integers $n, b, a$ ($1 \le n, b, a \le 2 \cdot 10^5$) — the robot's destination point, the battery capacity and the accumulator capacity, respectively.
The second line of the input contains $n$ integers $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 1$), where $s_i$ is $1$ if the $i$-th segment of distance is exposed to sunlight, and $0$ otherwise.

Output

Print one integer — the maximum number of segments the robot can pass if you control him optimally.

Sample Input:

5 2 1
0 1 0 1 0

Sample Output:

5

Sample Input:

6 2 1
1 0 0 1 0 1

Sample Output:

3

题目链接

机器人有普通电池和太阳能电池,每走一单位长度需耗一单位电量,在有阳光的点若使用普通电池到达则可增加太阳能电池一单位电量,初始机器人的普通电池与太阳能电池均为满电,求机器人行走的最远距离

显然的贪心:优先使用太阳能电池,但在有太阳能且太阳能电池未满电的情况下优先使用普通电池

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, init_b, init_a; std::cin >> n >> init_b >> init_a;
  int a = init_a, b = init_b;
  std::vector<int> s(n);
  for (auto &v : s) std::cin >> v;

  for (int i = 0; i < n; ++i) {
    if (b == 0 && a == 0) {
      std::cout << i << '\n';
      return 0;
    }
    if (s[i] == 0) {
      if (a) --a;
      else --b;
    }
    else {
      if (b) {
        if (a < init_a) {
          --b;
          ++a;
        else --a;
      }
      else --a;
    }
  }
  std::cout << n << '\n';
  return 0;
}

E. Two Teams

Description:

There are $n$ students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.
The $i$-th student has integer programming skill $a_i$. All programming skills are distinct and between $1$ and $n$, inclusive.
Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and $k$ closest students to the left of him and $k$ closest students to the right of him (if there are less than $k$ students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).
Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.

Input:

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of students and the value determining the range of chosen students during each move, respectively.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the programming skill of the $i$-th student. It is guaranteed that all programming skills are distinct.

Output

Print a string of $n$ characters; $i$-th character should be 1 if $i$-th student joins the first team, or 2 otherwise.

Sample Input:

5 2
2 4 5 3 1

Sample Output:

11111

Sample Input:

5 1
2 1 3 5 4

Sample Output:

22111

Sample Input:

7 1
7 2 1 3 5 4 6

Sample Output:

1121122

Sample Input:

5 1
2 4 5 3 1

Sample Output:

21112

题目链接

两个人轮流选数,每次选择数列中的最大值及其左右 $k$ 个数并将其从数列中去除,求最后数字的归属

基本思路就是模拟,两个人轮流选择,每轮记录最大值位置

对每个数记录左侧未被去除的最近数字和右侧未被去除的最近数字

从最大值向左右延申选择

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, k; std::cin >> n >> k;
  std::vector<int> arr(n + 1);
  std::vector<int> l(n + 2), r(n + 2);
  std::map<int, int> pos, rev;
  for (int i = 1; i <= n; ++i) {
    std::cin >> arr[i];
    pos[arr[i]] = i;
    l[i] = i - 1; r[i] = i + 1;
  }

  int max = n, cur = 1;
  std::vector<int> ans(n + 1, 0);
  std::vector<bool> vis(n + 1, false);
  while (max) {
    int m = pos[max];
    for (int t = 0; m && t <= k; ++t, m = l[m]) {
      vis[arr[m]] = true;
      ans[m] = cur;
    }
    int l_lim = m;
    m = pos[max];
    for (int t = 0; m <= n && t <= k; ++t, m = r[m]) {
      vis[arr[m]] = true;
      ans[m] = cur;
    }
    int r_lim = m;
    r[l_lim] = r_lim; l[r_lim] = l_lim;
    while (max >= 0 && vis[max]) --max;
    cur = cur == 1 ? 2 : 1;
  }

  for (int i = 1; i <= n; ++i) std::cout << ans[i];
  std::cout << '\n';
  return 0;
}

F. Shovels Shop

Description:

There are $n$ shovels in the nearby shop. The $i$-th shovel costs $a_i$ bourles.
Misha has to buy exactly $k$ shovels. Each shovel can be bought no more than once.
Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.
There are also $m$ special offers in the shop. The $j$-th of them is given as a pair $(x_j, y_j)$, and it means that if Misha buys exactly $x_j$ shovels during one purchase then $y_j$ most cheapest of them are for free (i.e. he will not pay for $y_j$ most cheapest shovels during the current purchase).
Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).
Your task is to calculate the minimum cost of buying $k$ shovels, if Misha buys them optimally.

Input:

The first line of the input contains three integers $n, m$ and $k$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le k \le min(n, 2000)$) — the number of shovels in the shop, the number of special offers and the number of shovels Misha has to buy, correspondingly.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the cost of the $i$-th shovel.
The next $m$ lines contain special offers. The $j$-th of them is given as a pair of integers $(x_i, y_i)$ ($1 \le y_i \le x_i \le n$) and means that if Misha buys exactly $x_i$ shovels during some purchase, then he can take $y_i$ most cheapest of them for free.

Output

Print one integer — the minimum cost of buying $k$ shovels if Misha buys them optimally.

Sample Input:

7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

Sample Output:

7

Sample Input:

9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

Sample Output:

17

Sample Input:

5 1 4
2 5 7 4 6
5 4

Sample Output:

17

题目链接

$n$ 个商品,$m$ 个优惠:每满 $a$ 件商品其中花费最少的 $b$ 个就会免费,求最少花费

将商品按照价格排序,记录排序后数组的前缀和,再记录对于 $a$ 个商品的优惠条件下 $b$ 的最大值(因为优惠可以重复使用),最后利用动态规划解决

转移方程:$\texttt{dp[i]=min(dp[i]},\texttt{dp[j]+prefix[i]-pref[j+max_offer(i-j)]})$

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, m, k; std::cin >> n >> m >> k;
  std::vector<int> arr(n + 1, 0), pref(n + 1, 0);
  for (int i = 1; i <= n; ++i) std::cin >> arr[i];
  std::sort(arr.begin(), arr.end());
  for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + arr[i];
  std::map<int, int> mp;
  for (int i = 1, a, b; i <= m; ++i) {
    std::cin >> a >> b;
    if (a <= k) mp[a] = std::max(mp[a], b);
  }

  std::vector<int> dp(k + 1);
  for (int i = 1; i <= k; ++i) {
    dp[i] = pref[i];
    for (int j = 0; j < i; ++j) {
      dp[i] = std::min(dp[i], dp[j] + pref[i] - pref[j + mp[i - j]]);
    }
  }
  
  std::cout << dp[k] << '\n';
  return 0;
}
Last modification:April 22nd, 2019 at 02:07 pm
如果觉得我的文章对你有用,请随意赞赏