A~F 个人题解

A

#include <iostream>
using namespace std;

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  cout<<(b == a+1 && c == b+1 ? "Yes" : "No")<<'\n';
  
  return 0;
}

B

选a中最大元素和b中最小元素

#include <iostream>
using namespace std;

int main() {
  int n,a[12],b[12],p1 = 1, p2 = 1;
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>a[i], a[i] < a[p1] ? p1 = i : 0;
  for (int i=1; i<=n; i++)
    cin>>b[i], b[i] > b[p2] ? p2 = i : 0;
  cout<<p1<<' '<<p2<<'\n';
  
  return 0;
}

C

x次一个循环只需要关心k%x

#include <iostream>
using namespace std;

int a[200005];

int main() {
  int n,x;
  long long k;
  cin>>n>>k>>x;
  for (int i=1; i<=n; i++)
    cin>>a[i];
  for (int i=x+1-k%x; i<=x; i++)
    cout<<a[i]<<' ';
  for (int i=1; i<=x-k%x; i++)
    cout<<a[i]<<' ';
  for (int i=x+1; i<=n; i++)
    cout<<a[i]<<' ';
  cout<<'\n';
  
  return 0;
}

D

预处理长度为j 模11余数为i的数的个数b[11][11]
枚举每个数作为A 且B的长度为j 此时的合法对数为所有余数与A(乘10^|B|)模11互补的数的个数注意剔除自身

#include <iostream>
using namespace std;

int a[200005];

int pow10(int k) {
  int ret = 1;
  while (k--)
    ret *= 10;
  return ret;
}

int main() {
  int n, b[11][11] = {0};
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>a[i], b[a[i]%11][to_string(a[i]).size()]++;
  long long ans = 0;
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=10; j++) {
      int r = (long long)a[i]*pow10(j)%11;
      ans += b[(11-r)%11][j] - (a[i]%11 == (11-r)%11 && to_string(a[i]).size() == j);
    }
  }
  cout<<ans<<'\n';
  
  return 0;
}

E

n必被计算两次因为n既大于左侧所有数又大于右侧所有数
n-1必被计算一次因为n-1除了小于n 大于其它的任何数
剩余的所有数都至多被计算一次
那么问题就转化为：用n*2,n-1和1~n-2中不重复的正整数构造出k
不妨把n-1放在n的右侧那么一种构造方法就是：

n放在中间，n-1放在最右侧
对于所有你想选的数，放在n的左侧
对于所有不想选的数，放在n和n-1之间

子问题：如何用不重复的正整数构造出k(或者：将k拆分成不重复的正整数之和)
结论：只要k小于1~n所有数之和，就能用1~n中的某些数构造出k，利用贪心容易证明，构造方法是从大向小依次取当前所能取的最大数

#include <iostream>
using namespace std;

bool b[200005];

int main() {
  int n;
  long long k;
  cin>>n>>k;
  if (k < n*2+n-1) {
    cout<<-1<<'\n';
    return 0;
  }
  k -= n*2+n-1; b[n] = true;
  long long t = n-2;
  while (t > 0 && k > 0) {
    t = min(t, k);
    k -= t;
    b[t] = true;
    t--;
  }
  if (t <= 0 && k > 0) {
    cout<<-1<<'\n';
    return 0;
  }
  for (int i=1; i<=n; i++)
    if (b[i])
      cout<<i<<' ';
  for (int i=1; i<=n; i++)
    if (!b[i])
      cout<<i<<' ';
  cout<<'\n';
  
  return 0;
}

F

k的下界是(n-1)/2，否则k次操作不足以让所有乱序排列的n个数都回到原来位置，因为每次操作最多只能让两个数复位
k的上界是n，为了达成最小操作数，每次操作至少都能让1个数复位且最后一次操作能让2个数复位，也就是n个数至多只需要n-1次操作就必能让所有数复位

对于中间的情况，一种构造方法是：

只考虑2个数互换和m个数轮换的情况，其中：

互换可以通过1次操作让2个数复位
轮换可以通过m-1次操作让m个数复位

实际上，互换就是最优情况(n个数通过n/2次操作归位)，轮换就是最坏情况(n个数通过n-1次操作归位)，那么实际上所有情况都可以通过1次轮换和若干次互换全部归位

总操作次数为k，可通过方程求出两种操作涉及的数的个数：
设使用x次互换，即有x*2个数参与互换，剩余n-x*2个数参与轮换
此时的操作次数(n-x*2-1) + x = k
解方程得x = n-k-1

即构造方法是：前n-(n-k-1)*2个数进行轮换，后(n-k-1)*2个数两两互换

#include <iostream>
using namespace std;

int main() {
  int n,k;
  cin>>n>>k;
  if (k <= (n-1)/2 || k >= n) {
    cout<<-1<<'\n';
    return 0;
  }
  int p = n-(n-k-1)*2;
  if (p >= 1)
    cout<<p<<' ';
  for (int i=1; i<=p-1; i++)
    cout<<i<<' ';
  for (int i=p+1; i<=n; i+=2)
    cout<<i+1<<' '<<i<<' ';
  cout<<'\n';
  
  return 0;
}

题解 | 牛客周赛 Round 111 - A~F 个人题解

A

B

C

D

E

F