Codeforces Round 736 (Div. 2 & 1) [CF-1549 & CF-1548]

叔叔我啊

发布于：2021年8月1日

字数：1.4k字

时长：7分钟

A - Gregor and Cryptography

Gregor is learning about RSA cryptography, and although he doesn't understand how RSA works, he is now fascinated with prime numbers and factoring them.

Gregor's favorite prime number is . Gregor wants to find two bases of . Formally, Gregor is looking for two integers and which satisfy both of the following properties.

, where denotes the remainder when is divided by , and

.

Help Gregor find two bases of his favorite prime number!

题目中要寻找两个数，使得它们对给定的数同余。因为没有指定两个数的条件，所以可以先固定其中一个余数再固定另一个。

#include <iostream>

using namespace std;

int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int p;
    cin >> p;
    cout << '2' << ' ' << p - 1 << endl;
  }
}

:hourglass:	:open_file_folder:	:bulb:
15	4.2	朴素

B - Gregor and the Pawn Game

There is a chessboard of size by . The square in the -th row from top and -th column from the left is labelled .

Currently, Gregor has some pawns in the -th row. There are also enemy pawns in the -st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from to ) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from to either or ) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.

Gregor wants to know what is the maximum number of his pawns that can reach row ?

Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row , it is stuck and cannot make any further moves.

题目要求使得最多的白子到达黑子位置。白字只有三种移动方法，向左、向前、向右。其中向左和向右需要其目标位置上存在黑子，向前需要保持其目标位置为空。只要从左到右贪心即可。

#include <iostream>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int N;
    cin >> N;
    string A, B;
    cin >> A >> B;
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
      if (B[i] == '0')
        continue;
      if (i - 1 >= 0 && A[i - 1] == '1') {
        A[i - 1] = '2';
        ++cnt;
      } else if (A[i] == '0') {
        A[i] = '2';
        ++cnt;
      } else if (i + 1 < N && A[i + 1] == '1') {
        A[i + 1] = '2';
        ++cnt;
      }
    }
    cout << cnt << endl;
  }
}

:hourglass:	:open_file_folder:	:bulb:
140	4.9	贪心

C - Web of Lies

When you play the game of thrones, you win, or you die. There is no middle ground.

Cersei Lannister, A Game of Thrones by George R. R. Martin

There are nobles, numbered from to . Noble has a power of . There are also "friendships". A friendship between nobles and is always mutual.

A noble is defined to be vulnerable if both of the following conditions are satisfied:

the noble has at least one friend, and

all of that noble's friends have a higher power.

You will have to process the following three types of queries.

Add a friendship between nobles and .

Remove a friendship between nobles and .

Calculate the answer to the following process.

The process: all vulnerable nobles are simultaneously killed, and all their friendships end. Then, it is possible that new nobles become vulnerable. The process repeats itself until no nobles are vulnerable. It can be proven that the process will end in finite time. After the process is complete, you need to calculate the number of remaining nobles.

Note that the results of the process are not carried over between queries, that is, every process starts with all nobles being alive!

有个节点，每一个点都有一个权值，这些点之间有条关系。一个节点如果和其他节点有关系且和该节点相连的所有点权值都比此节点大的话，这个节点就是脆弱的。

接下来会有次操作

给和之间增加一条关系
移除和的关系
移除脆弱节点后剩余的节点个数

分析题目可以知道，脆弱节点的形成只会在增加关系中形成。

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n, m, q, u, v, T, a;
  cin >> n >> m;
  vector<int> i(n);
  function<void(int)> f = [&](int x) {
    cin >> u >> v;
    u = min(u, v);
    a += !(i[u] += x) - (i[u] == 1 & x == 1);
  };
  while (m--)
    f(1);
  cin >> q;
  while (q--) {
    cin >> T;
    if (T == 3)
      cout << a + n << endl;
    else
      f((T == 1) - (T == 2));
  }
  return 0;
}

:hourglass:	:open_file_folder:	:bulb:
1123	5.1	贪心

D - Integers Have Friends

British mathematician John Littlewood once said about Indian mathematician Srinivasa Ramanujan that "every positive integer was one of his personal friends."

It turns out that positive integers can also be friends with each other! You are given an array of distinct positive integers.

Define a subarray to be a friend group if and only if there exists an integer such that , where denotes the remainder when is divided by .

Your friend Gregor wants to know the size of the largest friend group in .

给出一个数组，求这个数组中一段连续区间使得这个区间中所有数字除以一个数字余数相同，使这个区间尽可能大，输出区间长度。

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

using LL = long long;

void solve() {
  int n;
  cin >> n;
  vector<LL> a(n), b(n - 1);
  for (auto &x : a)
    cin >> x;
  if (n == 1) {
    cout << 1 << endl;
    return;
  }
  for (int i = 1; i < n; ++i)
    b[i - 1] = abs(a[i] - a[i - 1]);
  int ans = 0;
  function<void(int, int)> dfs = [&](int l, int r) {
    if (r - l <= ans)
      return;
    if (r - l == 1) {
      if (b[l] != 1)
        ans = r - l;
    } else {
      int m = (l + r) / 2;
      if (b[m] != 1) {
        vector<LL> L{b[m]}, R{b[m]};
        for (int i = m - 1; i >= l; --i) {
          auto now = gcd(L.back(), b[i]);
          if (now == 1)
            break;
          L.emplace_back(now);
        }
        ans = max(ans, (int)L.size());
        for (int i = m + 1; i < r; ++i) {
          auto now = gcd(R.back(), b[i]);
          if (now == 1)
            break;
          R.emplace_back(now);
        }
        ans = max(ans, (int)R.size());
        for (int i = 0, j = R.size() - 1, nl = L.size(); i < nl; ++i) {
          while (gcd(R[j], L[i]) == 1)
            --j;
          ans = max(ans, i + 1 + j);
        }
      }
      dfs(l, m);
      if (m + 1 < r)
        dfs(m + 1, r);
    }
  };
  dfs(0, n - 1);
  cout << ++ans << endl;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int cas = 1;
  cin >> cas;
  while (cas--) {
    solve();
  }
  return 0;
}