2024.7.2

党同伐异

可以发现, 每次只会是 \(a_i\) 最大或者 \(a_i\) 最小的人被淘汰, 所以留下的肯定是从小到大排序后的一段区间。

还可以发现一个单调性, 越靠近左边就越不可能票左边, 所以可以通过二分求出左右两边各被票了多少。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct Node{
  int x, id;
}a[N];

int l, r, lx, rx, mid, n;

int main(){
  freopen("election.in", "r", stdin);
  freopen("election.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i].x;
    a[i].id = i;
  }
  sort(a + 1, a + n + 1, [](const Node &i, const Node &j){  return i.x < j.x;});
  l = 1, r = n;
  while(l < r){
    lx = l, rx = r + 1;
    while(lx < rx){
      mid = (lx + rx) >> 1;
      if(a[mid].x - a[l].x > a[r].x - a[mid].x){
        rx = mid;
      }
      else{
        lx = mid + 1;
      }
    }
    if(lx - l < r - rx + 1){
      l++;
    }
    else{
      r--;
    }
  }
  cout << a[l].id;
  return 0;
}

时间复杂度 \(O( n \log n)\)

空间复杂度 \(O(n)\)

混乱谜团

考虑对于一个序列 \(1, 2, 3 \dots n\) 进行反转操作

如果反转 \(2, 3, 4, \dots n\), 代价增加 \(n - 2\)

如果反转 \(3, 4, 5, \dots n\), 代价增加 \(n - 3\)

\(\dots\)

反转直接还是相互独立的, 应为不管有多少次 \(< i\) 的操作, \(i, i + 1, \dots n\) 都一定在反转的区间里。

反转 = 填数

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

long long n, k, l, r, a[N];

int main(){
  freopen("chaos.in", "r", stdin);
  freopen("chaos.out", "w", stdout);
  cin >> n >> k;
  k -= (n - 1);
  l = 2, r = n;
  a[1] = 1;
  for(int kk = 2; l != r; ++kk){
    if(n - kk <= k){
      k -= (n - kk);
      a[r] = kk;
      (r > l ? r-- : r++);
      swap(l, r);
    }
    else{
      a[l] = kk;
      (l > r ? l-- : l++);
    }
  }
  a[l] = n;
  for(int i = 1; i <= n; ++i){
    cout << a[i] << ' ';
  }
  return 0;
}

时空复杂度 \(O(n)\)

固若金汤

考虑 DP

状态 \((i, j)\) 表示考虑前 \(i\) 个人, 最后一个人编号 \(i\), 倒数第二个人编号 \(j\)

维护最大值数组 \(s_{i, j}\) 表示末尾为 \(i\) 时 \(a_i\) 和前一个二进制下第 \(j\) 位为 1 的最多人数

转移 ：
\((i, j) = s_{j, k}\) 其中, \(a_i\) 二进制下第 \(k\) 位为 1, \(j \le i\)
\(s_{i, k} = (i, j)\) 其中, \((a_i \operatorname{and} a_j)\) 二进制下第 \(k\) 位为 1

#include<bits/stdc++.h>

using namespace std;

const int N = 2005;

int n, a[N], ans, dp[N], s[N][40], ok;

int main(){
  freopen("defend.in", "r", stdin);
  freopen("defend.out", "w", stdout);
  //freopen("samples3.in", "r", stdin);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  ans = (n >= 2 ? 2 : 1);
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j < i; ++j){
      dp[j] = -1e9;
    }
    dp[i] = 1;
    for(int j = 0; j < 31; ++j){
      s[i][j] = -1e9;
      if(a[i] & (1 << j)){
        for(int k = 1; k < i; ++k){
          dp[k] = max(dp[k], s[k][j] + 1);
        }
      }
    }
    for(int k = 1; k <= i; ++k){
      ok = (a[i] & a[k]);
      for(int j = 0; j < 31; ++j){
        if(ok & (1 << j)){
          s[i][j] = max(s[i][j], dp[k]);
        }
      }
    }
    for(int i = 1; i <= n; ++i){
      ans = max(ans, dp[i]);
    }
  }
  cout << ans;
  return 0;
}

时间复杂度 \(O(n^2 \log_2 V)\)

降维后时间复杂度 \(O(n \log_2 V)\)

替身使者

先对 \(k_i\) 从小到大排序, 这样, 就可以简单的处理宽带

状态 \((i, s)\) 表示考虑前 \(i\) 个替身, 可以完成题目的二进制串为 \(s\) 时的不算宽带最小花费

转移当前状态与上能解决的题目 + 费用

答案 \(\min \limits_{i = 1}^n \{ dp[i][全集] + b \cdot k_i \}\)

#include<bits/stdc++.h>

using namespace std;

const int N = 105, M = (1 << 21) + 5;

struct Node{
  int x, k, w;
}a[N];

long long dp[M], n, m, b, x, ans = 2e18, len;

int main(){
  freopen("standin.in", "r", stdin);
  freopen("standin.out", "w", stdout);
  //freopen("samples3.in", "r", stdin);
  cin >> n >> m >> b;
  for(int i = 1; i <= n; ++i){
    cin >> a[i].x >> a[i].k >> len;
    a[i].w = 0;
    for(int j = 1; j <= len; ++j){
      cin >> x;
      x--;
      a[i].w |= (1 << x);
    }
  }
  sort(a + 1, a + n + 1, [](const Node &i, const Node &j){  return i.k < j.k;});
  for(int s = 1; s < (1 << m); s++){
    dp[s] = 2e18;
  }
  for(int i = 1; i <= n; ++i){
    for(int s = (1 << m) - 1; s >= 0; s--){
      dp[s | a[i].w] = min(dp[s | a[i].w], dp[s] + a[i].x);
    }
    ans = min(ans, dp[(1 << m) - 1] + a[i].k * b);
  }
  cout << (ans == 2e18 ? -1 : ans);
  return 0;
}

时空复杂度 \(O(n2^m)\)