2020牛客暑期多校训练营（第五场）

D Drop Voicing（dp）

题意：

有一个

1. ：将倒数第二个数放到开头，前面的数向后平移
2. ：将倒数第二个数放到开头，前面的数向后平移

若干连续的 称为 。计算要使该排列排成 所需的最少的

可以把一个数转移到任意位置。比如对于序列 : 。

我想把 移动到

1. 进行两次 操作序列变成
2. 进行三次 操作序列变成
3. 进行两次 操作序列变成

所以 的最少次数就是找到最长的一个环状 然后把其他元素插进去，这个环状是因为可以通过 操作改变序列的顺序，然后就是求每个位置往后的 长度 的 ，找到这些 的最大值用

AC代码：

const int N = 5e5 + 50;
int a[N], dp[N];
int n, m;

int main()
{
  sd(n);
  rep(i, 1, n)
  {
    sd(a[i]);
    a[n + i] = a[i];
  }
  int ans = 0;
  rep(pos, 1, n)
  {
    int sum = 0;
    rep(i, pos, pos + n - 1)
      dp[i] = 1;
    rep(i, pos, pos + n - 1)
    {
      rep(j, pos, i - 1)
      {
        if (a[j] < a[i])
          dp[i] = max(dp[i], dp[j] + 1);
      }
      sum = max(sum, dp[i]);
    }
    ans = max(ans, sum);
  }
  pd(n - ans);
  return 0;
}

E Bogo Sort（大数，求环）

题意：

已知一个长度为 的序列 ，用序列 将排列 (未知)进行置换，要求找到排列使其被

置换群，其实就是找环。比如 为 ， 为 ，那么 被 置换一次后为 ，再被置换一次为 ，又变为了原数组，即 构成一个环， 自身构成一个环。
本题实际上就是要求出每个环的长度，然后求所有环的长度的

这道题给出的模数其实是迷惑人的，因为根本到不了怎么大，所以不用考虑，至于如何求多个数的

例如：求

在 中有一个 ，一个 ；在 中有两个 ，一个 ；在 式中有两个；

所以 最多有两个，最多有一个， 最多有一个；最后

所以先把每个环的质因子分解出来，然后取幂次最高的那个，然后把所有质因子按照幂次都乘上即可。

AC代码：

const int N = 4e5 + 50;
int n, m;
int a[N], vis[N];
int cnt[N];
vector<int> v;

namespace bigI
{
typedef vector<ll> VI;
const int bas = 1e4;

void print(VI A)
{
  if (A.size() == 0)
    return;
  printf("%lld", A.back());
  for (int i = A.size() - 2; i >= 0; --i)
    printf("%04lld", A[i]);
  puts("");
}

VI mul(VI A, ll b)
{
  static VI C;
  C.clear();
  ll t = 0;
  for (int i = 0; i < (int)A.size() || t; ++i)
  {
    if (i < (int)A.size())
      t += A[i] * b;
    C.push_back(t % bas);
    t /= bas;
  }
  return C;
}
} // namespace bigI
using namespace bigI;

int dfs(int p)
{
  if (vis[p])
    return 0;
  vis[p] = 1;
  return dfs(a[p]) + 1;
}//找环

int main()
{
  sd(n);
  rep(i, 1, n)
    sd(a[i]);
  rep(i, 1, n)
  {
    if (vis[i])
      continue;
    int x = dfs(i);
    v.pb(x);
  }
  for (auto i : v)
  {
    int now = i;
    int res = 0;
    for (int j = 2; j * j <= now; j++)
    {
      res = 0;
      while (now % j == 0)
        res++, now = now / j;
      cnt[j] = max(cnt[j], res);
    }
    if (now > 1)
      cnt[now] = max(cnt[now], 1);
  }
  VI ans = {1};
  rep(i, 2, n)
  {
    while (cnt[i])
    {
      ans = mul(ans, i);
      cnt[i]--;
    }
  }
  print(ans);
  return 0;
}

F DPS（签到）

题意：

编写一个程序，输出显示对敌人造成伤害的直方图，其中空格的长度为 (向上取整)，必须通过将最后一个空格替换为

这个思路很明显，按照题意模拟就行，注意精度问题。

AC代码：

const int N = 2e5 + 50;
int d[110];
int main()
{
    int n;
    sd(n);
    rep(i, 1, n)
        sd(d[i]);
    int maxn = 0;
    rep(i, 1, n)
        maxn = max(maxn, d[i]);
    rep(i, 1, n)
    {
        int len = ceil(50.0 * d[i] / maxn);
        printf("+");
        rep(j, 1, len)
            printf("-");
        printf("+");
        puts("");
        printf("|");
        rep(j, 1, len - 1)
            printf(" ");
        if (d[i])
            printf("%c", (d[i] == maxn) ? '*' : ' ');
        printf("|%d\n", d[i]);
        printf("+");
        rep(j, 1, len)
            printf("-");
        printf("+");
        puts("");
    }
    return 0;
}

I Hard Math Problem

题意：

给出一个 的网格，每个格子可放 中的一个，要求 的上下左右至少要有一个 和一个 ，问 都取无穷大时放

取一条斜线，在斜线上交错摆 和 ，这样斜线之上和之下的两条斜线都可以摆放 ，则占比为

GHGHGH
HEHEHE
GHGHGH
HEHEHE
GHGHGH
HEHEHE

AC代码：

int main()
{
    double ans=2.0/3.0;
    printf("%.6lf\n",ans);
    return 0;
}