个人题解

A

每个数输出两次

#include <iostream>
using namespace std;

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=n; i++)
    cout<<i<<' '<<i<<' ';
  cout<<'\n';
  
  return 0;
}

B

第一次出现一组第二次出现一组

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
  int n,x;
  cin>>n;
  n *= 2;
  unordered_set<int> st;
  vector<int> v1, v2;
  while (n--) {
    cin>>x;
    if (st.find(x) != st.end())
      v2.push_back(x);
    else
      v1.push_back(x), st.insert(x);
  }
  for (auto &x: v1)
    cout<<x<<' ';
  cout<<'\n';
  for (auto &x: v2)
    cout<<x<<' ';
  cout<<'\n';
  
  return 0;
}

C

从前往后贪心地模拟一遍如果可以就是可以
因为既然所有数都要删除那么第一个数就必须被删除以此类推

#include <iostream>
using namespace std;

int a[400005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (int i=1; i<=n*2; i++)
      cin>>a[i];
    int p = 1;
    for (int i=2; i<=n*2; i++)
      if (a[i] == a[p])
        p = i+1, i++;
    cout<<(p == n*2+1 ? "Yes" : "No")<<'\n';
  }
  
  return 0;
}

D

思维题一开始没想到
操作的两个区间必不相交否则没收益
则最大收益的做法就是选择最左边的右端点和最右边的左端点
交换后权值增大这两个区间之间的距离的两倍

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> a[200005];

int main() {
  int n,x;
  cin>>n;
  long long ans = 0;
  for (int i=1; i<=n*2; i++) {
    cin>>x;
    a[x].push_back(i);
    if (a[x].size() == 2)
      ans += a[x][1] - a[x][0] - 1;
  }
  sort(a+1, a+1+n, [](vector<int> &v1, vector<int> &v2) {
    return v1[1] < v2[1];
  });
  vector<int> v1 = a[1];
  sort(a+1, a+1+n);
  vector<int> v2 = a[n];
  if (v1[1] < v2[0])
    ans += (v2[0]-v1[1])*2;
  cout<<ans<<'\n';
  
  return 0;
}

E

dp 前缀和
考虑第i个元素删或不删

#include <iostream>
using namespace std;

int a[400005], pre[200005];
long long s[400005], dp[400005];

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=n*2; i++) {
    cin>>a[i];
    s[i] = s[i-1] + a[i];
    if (pre[a[i]] == 0)
      pre[a[i]] = i;
  }
  long long mx = 0;
  for (int i=1; i<=n*2; i++)
    dp[i] = max(dp[i-1], pre[a[i]] == i ? 0 : s[i] - s[pre[a[i]]-1] + dp[pre[a[i]]-1]), mx = max(mx, dp[i]);
  cout<<mx<<'\n';
  
  return 0;
}

F

排序按顺序操作直到1 1 2 2 ...
一个经典的结论: 概率为p 则操作次数期望为1/p

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1e9+7;

int b[200005];

long long pow(long long a, int k) {
  return k ? pow(a*a%M, k/2)*(k%2?a:1)%M : 1;
}

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=n*2; i++)
    cin>>b[i];
  sort(b+1, b+1+n*2);
  long long ans = 0;
  for (int i=1; i<=n*2; i++)
    ans += (i+1)/2 * 100 * pow(b[i], M-2)%M;
  cout<<ans%M<<'\n';
  
  return 0;
}

G

看完题解回来补题

设 $f(k)$ 为概率为 $p\%$ 时，从 $k-1$ 变为 $k$ 的操作次数期望
则 $f(k) = p\% * 1 + (1-p\%) * (1 + f(k-1) + f(k))$

$p\%$ 的概率走 $1$ 步到达
$(1-p\%)$ 的概率走 $1$ 步回到 $k-2$
再走 $f(k-1)$ 步到 $k-1$
再走 $f(k)$ 步到 $k$

化简得 $f(k) = [(1-p\%)*f(k-1) + 1]/p\% = [(100-p)*f(k-1) + 100]/p$

对其再求前缀和得到从 $0$ 变为各个数的操作次数期望
概率只有 $100$ 种可能性可以直接全部预处理

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1e9+7;

int b[200005];
long long dp[101][100005];

long long pow(long long a, int k) {
  return k ? pow(a*a%M, k/2)*(k%2?a:1)%M : 1;
}

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=100; i++)
    for (int j=1; j<=n; j++)
      dp[i][j] = ((100-i)*dp[i][j-1]%M + 100) * pow(i, M-2)%M;
  for (int i=1; i<=100; i++)
    for (int j=1; j<=n; j++)
      dp[i][j] += dp[i][j-1];
  for (int i=1; i<=n*2; i++)
    cin>>b[i];
  sort(b+1, b+1+n*2);
  long long ans = 0;
  for (int i=1; i<=n*2; i++)
    ans += dp[b[i]][(i+1)/2];
  cout<<ans%M<<'\n';
  
  return 0;
}

题解 | 牛客周赛 Round 100 - 个人题解

A

B

C

D

E

F

G