记第一场CF赛，完成3道题

代码更新（降低时间复杂度和修改写法）：21.1.23

A题 Required Remainder

题意：给你 x、y、n 求最大的k (k<=n) 使得k%x==y

做法：模拟

寻找最大整除数，一开始while循环找，直接TLE2

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     int t, x, y,n; cin >> t;
  5.     while (t--) {
  6.         cin >> x >> y >> n;
  7.         cout << (n - y) / x * x + y << endl;
  8.     }
  9.     return 0;
  10. }

B题 Multiply by 2, divide by 6

题意：给你一个数n 每次两个操作：乘2 除6 求最少的操作 得到1

做法：循环整除6，每次+1，然后循环整除3，每次加2

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     long long a, n, k, t;
  5.     cin >> t;
  6.     while (t--) {
  7.         cin >> a;
  8.         k = 0, n = 0;
  9.         while (a % 6 == 0) { a /= 6; ++k; }
  10.         while (a % 3 == 0) { a /= 3; k+=2; }
  11.         if (a != 1)k = -1;
  12.         cout << k << endl;
  13.     }
  14. }

C. Move Brackets

题意：给你只包含’(‘ ‘)’ 的字符串，每次操作可以选择一个字符 要么移到最后面 要么移到最前面，求最少的操作使得字符串是括号匹配的字符串

做法：先统计 ‘(‘ 个数，遇 ‘)’ k> 0时 k—

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     int t,n, k; char c; cin >> t;
  5.     while (t--) {
  6.         k = 0;
  7.         cin >> n; while (n--) {
  8.             cin >> c;
  9.             if (c == '(')k++;
  10.             else if (k > 0)--k;
  11.         }
  12.         cout << k << endl;
  13.     }
  14. }

第四题开始就没做出来了，记录dalao们的题解

D. Zero Remainder Array

题意：给你n长度的整数数组 a ，一个x 每次操作可以选择一个 下标i 让a[i]+=x 然后x自增1 操作2是 不选择下标 单独的x自增1

做法：a[i]对k取模 得到离k（k-a[i]%k）的距离，统计离k距离相同数量最多的，num 和 mx 答案就是 (num-1)*k+mx+1；

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int main() {
  5.     int t;
  6.     cin >> t;
  7.     while (t--) {
  8.         ll n, k, ans = 0, a;
  9.         cin >> n >> k;
  10.         map<ll, ll> mp;
  11.         for (int i = 0; i < n; ++i) cin >> a, mp[(k - (a % k)) % k]++;
  12.         for (auto it : mp)
  13.             if (it.first) ans = max(ans, (it.second - 1) * k + it.first + 1);
  14.         cout << ans << '\n';
  15.     }
  16.     return 0;
  17. }

E1. Reading Books (easy version)

题意：给n本书，以及一个K 每本书 可能是 （Alice 喜欢 Bob 不喜欢）（Alice 不喜欢 Bob 喜欢）（Alice 不喜欢 Bob 不喜欢） 每本书有一个阅读时间t[i] 每次只能选择一本书进行阅读。现在要求ALICE 和Bob 都至少读k本自己喜欢的书，并且时间消耗最少。

做法：

三种情况分开保存，（Alice 喜欢 Bob 不喜欢）a数组， （Alice 不喜欢 Bob 喜欢）b数组，（Alice 不喜欢 Bob 不喜欢）c数组

对a数组 b数组分别选前k个，不足k个从c里面选。都满k个后 再从c里面选共同的 同时去掉 a里面、b里面得到 的两个最大值。

  1. // Author : RioTian
  2. // Time : 21/01/23
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 1e5 + 10;
  7. int _;
  8. vector<int> a, b, c;
  9. void solve() {
  10.     int n, k, t, x, y, ans = 0;
  11.     cin >> n >> k;
  12.     for (int i = 1; i <= n; ++i) {
  13.         cin >> t >> x >> y;
  14.         if (x == 1 && y == 1)
  15.             c.push_back(t);
  16.         else if (x == 1)
  17.             a.push_back(t);
  18.         else if (y == 1)
  19.             b.push_back(t);
  20.     }
  21.     sort(a.begin(), a.end()), sort(b.begin(), b.end()),
  22.         sort(c.begin(), c.end());
  23.     n = min(a.size(), b.size());
  24.     for (int i = 0; i < n; ++i) c.push_back(a[i] + b[i]);
  25.     sort(c.begin(), c.end());
  26.     if (c.size() < k)
  27.         ans = -1;
  28.     else {
  29.         for (int i = 0; i < k; ++i) ans += c[i];
  30.     }
  31.     cout << ans << endl;
  32. }
  33. int main() {
  34.     // freopen("in.txt", "r", stdin);
  35.     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  36.     solve();
  37. }

E2

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  5. typedef pair<ll, int> pli;
  7. pli av[200001], bv[200001], cv[200001], dv[200001];
  9. int main() {
  10.     int n, k, m;
  11.     scanf("%d %d %d", &n, &m, &k);
  13.     int aa = 0, bb = 0, cc = 0, dd = 0;
  14.     ll as = 0, bs = 0, cs = 0, ds = 0;
  16.     for (int i = 0; i < n; i++) {
  17.         int a, b, c;
  18.         scanf("%d %d %d", &a, &b, &c);
  19.         if (b == 1 && c == 1) av[aa++] = {a, i};
  20.         else if (b == 1) bs += a, bv[bb++] = {a, i};
  21.         else if (c == 1) cs += a, cv[cc++] = {a, i};
  22.         else ds += a, dv[dd++] = {a, i};
  23.     }
  25.     sort(av, av + aa); sort(bv, bv + bb);
  26.     sort(cv, cv + cc); sort(dv, dv + dd);
  28.     int mai = -1, mbi = -1, mci = -1, mdi = -1;
  29.     int bi = bb, ci = cc, di = dd, q;
  30.     ll ans = 1e18, ret;
  32.     for (int i = 0; i <= aa; i++) {
  33.         if (i) as += av[i-1].first;
  34.         q = max(0, k - i);
  36.         for (int j = 0; j < 3; j++) {
  37.             if (bi < bb) bs += bv[bi++].first;
  38.             if (ci < cc) cs += cv[ci++].first;
  39.             if (di < dd) ds += dv[di++].first;
  40.         }
  42.         if (q > bb || q > cc || (i + 2*q) > m || i+bb+cc+dd < m) continue;
  44.         while (i+bi+ci+di > m) {
  45.             ll bt = (bi>q?bv[bi-1].first:-1e18);
  46.             ll ct = (ci>q?cv[ci-1].first:-1e18);
  47.             ll dt = (di>0?dv[di-1].first:-1e18);
  49.             if (bt >= ct && bt >= dt) bs -= bv[--bi].first;
  50.             else if (ct >= bt && ct >= dt) cs -= cv[--ci].first;
  51.             else ds -= dv[--di].first;
  52.         }
  54.         ret = as + bs + cs + ds;
  55.         if (ans > ret) {
  56.             ans = ret;
  57.             mai = i, mbi = bi, mci = ci, mdi = di;
  58.         }
  59.     }
  61.     if (ans > 1e17) return !printf("-1");
  62.     printf("%lld\n", ans);
  63.     for (int i = 0; i < mai; i++) printf("%d ", av[i].second + 1);
  64.     for (int i = 0; i < mbi; i++) printf("%d ", bv[i].second + 1);
  65.     for (int i = 0; i < mci; i++) printf("%d ", cv[i].second + 1);
  66.     for (int i = 0; i < mdi; i++) printf("%d ", dv[i].second + 1);
  67. }

F. Cyclic Shifts Sorting

题意：给你n长度 整数数组 a[i] 每次选择一个下标i 然后对(i,i+1,i+2)进行向右移动 i+2移到i。问最少的操作使得这个数组是递增的数组，如果不能得到则输出-1

做法：

复杂模拟，每次找到最小的那个值，然后不断的反转 移到前面去，进行n-2轮后 得到两种情况：

第一种：1 2 3 4 5 有序

第二种：1 2 3 5 4 无序。

对于第二种则需要将 5 4 的位置倒一下 选择n-2下标：

1 2 4 3 5

接着对 4 3 倒一下：

1 3 2 4 5

此时发现 只有前面出现两个相同的时候才可以得到有序的数组。

例如：

1 2 3 3 5 4 => 1 2 3 4 3 5 => 1 2 3 3 4 5

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. int n, t[502], p, w;
  5. vector<int> sol;
  6. void q(int a) {
  7.     sol.push_back(a);
  8.     swap(t[a + 2], t[a]), swap(t[a + 1], t[a + 2]);
  9. }
  10. int main() {
  11.     cin >> w;
  12.     while (w--) {
  13.         cin >> n, sol.clear();
  14.         for (int i = 1; i <= n; i++) cin >> t[i];
  15.         for (int i = 1; i <= n - 2; i++) {
  16.             p = i;
  17.             for (int j = i; j <= n; j++)
  18.                 if (t[j] < t[p]) p = j;
  19.             if (p == n) p -= 2, q(p);
  20.             if ((p - i) % 2) q(p - 1), p++;
  21.             while (p > i) p -= 2, q(p);
  22.         }
  23.         if (t[n] < t[n - 1])
  24.             for (int i = 1; i <= n - 2; i++)
  25.                 if (t[i] == t[i + 1]) {
  26.                     for (int j = i; j <= n - 2; j++) q(j), q(j);
  27.                     break;
  28.                 }
  29.         if (t[n - 2] == t[n]) q(n - 2);
  30.         if (t[n] < t[n - 1])
  31.             cout << -1 << "\n";
  32.         else {
  33.             cout << sol.size() << "\n";
  34.             for (int i = 0; i < sol.size(); i++) cout << sol[i] << " ";
  35.             cout << "\n";
  36.         }
  37.     }
  38.     return 0;
  39. }