Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)

Problem 1501A. Alexey and Train

按题意，比较到站的最大值.

  1. using ll = long long;
  2. int a[105], b[105], c[105];
  3. int main() {
  4.     // ios_base::sync_with_stdio(false), cin.tie(0);
  5.     int _;
  6.     for (cin >> _; _--;) {
  7.         int n, s = 0;
  8.         scanf("%d", &n);
  9.         for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
  10.         for (int i = 1; i <= n; i++) {
  11.             scanf("%d", &c[i]), s += a[i] - b[i - 1] + c[i];
  12.             if (i == n) break;
  13.             s = max(s + (b[i] - a[i] + 1) / 2, b[i]);
  14.         }
  15.         cout << s << "\n";
  16.     }
  17.     return 0;
  18. }

Problem 1501B. Napoleon Cake

从后往前比较.

  1. int arr[200001];
  2. int res[200001];
  3. int main() {
  4.     ios_base::sync_with_stdio(false), cin.tie(0);
  5.     int _ = 1;
  6.     for (cin >> _; _--;) {
  7.         int n, i, mn = 1e9;
  8.         cin >> n;
  9.         for (i = 1; i <= n; i++) cin >> arr[i];
  10.         for (i = n; i >= 1; i--) {
  11.             mn = min(mn, i - arr[i]);
  12.             res[i] = (mn < i);
  13.         }
  14.         for (i = 1; i <= n; i++) cout << res[i] << " ";
  15.         cout << endl;
  16.     }
  17.     return 0;
  18. }

Problem 1501C. Going Home

把两数之和想象成坐标，x 和 y

使用双指针然后存储和存储一下，如果能匹配并且 坐标不重复即可输出。

数组开大点，这个导致WA好几次了….

  1. const int N = 5000003;
  2. int x[N], y[N], a[N];
  3. int main() {
  4.     ios_base::sync_with_stdio(false), cin.tie(0);
  5.     int n;
  6.     cin >> n;
  7.     for (int i = 1; i <= n; ++i) cin >> a[i];
  8.     for (int i = 1; i <= n; ++i)
  9.         for (int j = i + 1; j <= n; ++j) {
  10.             int s = a[i] + a[j];
  11.             if (x[s] && y[s] && x[s] != i && y[s] != j && x[s] != j &&
  12.                 y[s] != i) {
  13.                 cout << "YES\n";
  14.                 cout << i << " " << j << " " << x[s] << " " << y[s] << "\n";
  15.                 return 0;
  16.             }
  17.             x[s] = i;
  18.             y[s] = j;
  19.         }
  20.     cout << "NO\n";
  21.     return 0;
  22. }