TEST 8

A. 搬草啦

signed main() {
    IOS;
    int n;
    cin >> n;
    vector<int> v(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        sum += v[i];
    }
    int tmp = sum / n;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i] < tmp) {
            res += tmp - v[i];
        }
    }
    cout << res << endl;

    return 0;
}

B. 电泳技术

• 直接模拟写就好了

  #define MAX 1000005
  int a[MAX], b[MAX], l1, l2;
  
  signed main() {
      IOS;
      int n, m;
      cin >> n >> m;
      for (int i = 1; i <= n; i++) {
          int x, y;
          cin >> x >> y;
          while (y--)
              a[++l1] = x;
      }
      for (int i = 1; i <= m; i++) {
          int x, y;
          cin >> x >> y;
          while (y--) 
              b[++l2] = x;
      }
      int k1 = a[1], k2 = b[1], ans = 0;
      for (int i = 2; i <= l1; i++) {
          if (k1 >= k2 && k1 + a[i] < k2 + b[i])
              ans++;
          else if (k1 <= k2 && k1 + a[i] > k2 + b[i])
              ans++;
          k1 += a[i], k2 += b[i];
      }
      cout << ans << endl;
  
      return 0;
  }

C. 活泼奶牛来拍照1.0

• cmp的很奇妙的用法

  #define MAX 200005
  int d[6][MAX], ans[MAX];
  
  bool cmp(int a, int b) {
      int res = 0;
      for (int i = 1; i <= 5; i++) {
          if (d[i][a] < d[i][b]) {
              res++;
          } else {
              res--;
          }
      }
      return res > 0;
  }
  
  signed main() {
      IOS;
      int n;
      cin >> n;
      for (int i = 1; i <= 5; i++) {
          for (int j = 1; j <= n; j++) {
              int x;
              cin >> x;
              d[i][x] = j;
              ans[j] = j;
          }
      }
      sort(ans + 1, ans + 1 + n, cmp);
      for (int i = 1; i <= n; i++) {
          cout << ans[i] << endl;
      }
  
      return 0;
  }

D. 移动盒子

• 用链表模拟一下就好了

  #define MAX 200005
  struct node {
      node *l, *r;
      int idx;
  } a[MAX];
  
  void erase(int idx) {
      a[idx].l->r = a[idx].r;
      a[idx].r->l = a[idx].l;
  }
  
  void insert(int idx, int x) {
      a[x].l->r = &a[idx];
      a[idx].l = a[x].l;
      a[idx].r = &a[x];
      a[x].l = &a[idx];
  }
  
  signed main() {
      IOS;
      int n, m;
      cin >> n >> m;
      int re = 0;
      for (int i = 1; i <= n; i++) {
          a[i].l = &a[i - 1];
          a[i].r = &a[i + 1];
          a[i].idx = i;
      }
      a[0].r = &a[1];
      a[n + 1].l = &a[n];
      a[0].idx = 0;
      a[n + 1].idx = n + 1;
      for (int i = 1; i <= m; i++) {
          int op;
          cin >> op;
          op--;
          if (op == 2) {
              int x, y;
              cin >> x >> y;
              int endx = a[x].r->idx, endy = a[y].r->idx;
              if (endx == y) {
                  erase(y), insert(y, x);
              } else if (endy == x) {
                  erase(x), insert(x, y);
              } else {
                  erase(x), erase(y);
                  insert(x, endy), insert(y, endx);
              }
          } else if (op == 3) {
              re ^= 1;
          } else {
              op ^= re;
              int x, y;
              cin >> x >> y;
              if (op == 0) {
                  erase(x);
                  insert(x, y);
              } else {
                  if (a[y].r->idx == x) {
                      continue;
                  }
                  int endy = a[y].r->idx;
                  erase(x);
                  insert(x, endy);
              }
          }
      }
  
      vector<int> ans;
      int ind = a[0].r->idx;
      while (ind != n + 1) {
          ans.push_back(ind);
          ind = a[ind].r->idx;
      }
      if (re) {
          reverse(ans.begin(), ans.end());
      }
      int res = 0;
      for (int i = 0; i < ans.size(); i++) {
          //cout << ans[i] << ' ';
          if (i % 2 == 0) {
              res += ans[i];
          }
      }
      cout << res << endl;
  
      return 0;
  }

E. 数学课上的报酬

• 用单调栈才是最好的维护方法

  string c, s;
  signed main() {
      IOS;
      int n, m;
      cin >> n >> m;
      cin >> s;
      s = ' ' + s;
      deque<char> q;
      for (int i = 1; i <= n; i++) {
          while (!q.empty() && q.back() < s[i]) {
              q.pop_back();
          }
          q.push_back(s[i]);
          if (i > m) {
              cout << q.front();
              q.pop_front();
          }
      }
      return 0;
  }

F. 纸牌游戏

• 用堆去维护，重载二分 + HASH

  #define ull unsigned long long
  #define MAX 1010
  ull Hash[MAX][MAX], base[MAX], bs = 101, a[MAX][MAX];
  int n, len[MAX];
  struct node
  {
      int x, y;
      bool operator<(node nd) const
      {
          int l = 1, r = min(1001 - y, 1001 - nd.y), res = 0;
          int k = min(len[x] - y + 1, len[nd.x] - nd.y + 1);
          while (l <= r)
          {
              int mid = (l + r) / 2;
              ull res1 = Hash[x][y + mid - 1] - Hash[x][y - 1] * base[mid];
              ull res2 = Hash[nd.x][nd.y + mid - 1] - Hash[nd.x][nd.y - 1] * base[mid];
              if (res1 == res2)
              {
                  l = mid + 1, res = mid;
              }
              else
              {
                  r = mid - 1;
              }
          }
          if (res == k)
              return len[x] - y < len[nd.x] - nd.y;
          int k1 = y + res, k2 = nd.y + res;
          return a[x][k1] >= a[nd.x][k2];
      }
  };
  priority_queue<node> q;
  signed main()
  {
      IOS;
      cin >> n;
      base[0] = 1;
      for (int i = 1; i <= 1000; i++)
      {
          base[i] = base[i - 1] * bs;
      }
      for (int i = 1; i <= n; i++)
      {
          int L;
          cin >> len[i];
          for (int j = 1; j <= len[i]; j++)
              cin >> a[i][j];
          for (int j = 1; j <= 1000; j++)
              Hash[i][j] = Hash[i][j - 1] * bs + a[i][j];
          q.push({i, 1});
      }
      while (!q.empty())
      {
          node tp = q.top();
          q.pop();
          int x = tp.x, y = tp.y;
          cout << a[x][y] << " ";
          if (y == len[x])
              continue;
          else
              q.push({x, y + 1});
      }
      return 0;
  }