2020多校训练-第五场

D.Drop Voicing

题意：
有两种操作，
op1:把倒数第二个移到首位
op2:把第一个移到末尾
求总共最少需要多少次操作2是的序列升序

题解：
找规律发现n-最大LIS

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a, b) memset(a, b, sizeof(a))
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rd(a) scanf("%d", &a)

int n, ans;
int a[505];
int f[505];

void solve()
{
  rap(k, 1, n){
    mem(f, 0);
    rap(i, 1, n){
      f[i] = 1;
      rap(j, 1, i - 1){
        if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
      }
      ans = max(ans, f[i]);
    }
    int t = a[1];
    rap(i, 1, n - 1)  a[i] = a[i + 1];
    a[n] = t;
  }
  printf("%d\n", n - ans);
}

int main(){
  rd(n);
  rap(i, 1, n)  rd(a[i]);
  solve();
  return 0;
}

E.Bogo Sort

题意：
今天，Tonnnny学习了一种称为Bogo Sort的新算法。 老师给了Tonnnny Bogo Sort的代码：

bool is_sorted(int a[], int n) {
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            return false;
        }
    }
    return true;
}
void bogo_sort(int a[], int n) {
    while (!is_sorted(a, n)) {
        shuffle(a, a + n);
    }
}

老师说，函数shuffle 是等概率地随机排列长度为n 的数组a，这个算法的期望复杂度为O(n⋅n!)。

但是，Tonnnny是一个坚定的男孩——他一点也不喜欢随机！ 因此，Tonnnny改进了Bogo Sort。 他选择了一个最喜欢的长度为N 的排列 p，然后用排列 p 替换随机的shuffle，因此改进的算法，Tonnnny Sort，可以解决长度为N 的数组的排序问题——至少Tonnnny如此认为。

int p[N] = {....}; // Tonnnny最喜欢的n的排列
void shuffle(int a[], int n) {
    int b[n];
    for (int i = 0; i < n; i++) {
        b[i] = a[i]
    }
    for (int i = 0; i < n; i++) {
        a[i] = b[p[i]];
    }
}

void tonnnny_sort(int a[], int n) {
    assert (n == N); // Tonnnny指定的
    while (!is_sorted(a, n)) {
        shuffle(a, a + n);
    }
}

Tonnnny对新算法感到满意，因此决定让您每天给他一个长度为N的不同数组，以使用Tonnnny Sort对其进行排序。

您是Tonnnny最好的朋友。 即使您发现该算法有某种错误，也希望让Tonnnny多快乐一会。 给定 N 和 p，您需要计算Tonnnny可以开心的最大天数，因为在那之后，您将不能给Tonnnny一个可以用Tonnnny Sort排序的之前没出现过的数组。

答案可能非常大。 Tonnnny只喜欢最多N位的数字，因此请改为输出答案mod10^N。

题解：
并查集求所有环的LCM

代码：

import java.io.*;
import java.math.BigInteger;
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    static int N = 200010;  
    static int[] arr = new int[N];
    static  int[] p = new int[N];  
    static  int[] size = new int[N];
    static class UFind {

        UFind(int n){
            for(int i = 1; i <= n; i++){
                p[i] = i;
                size[i] = 1;
            }
        }

        public int find(int x) { 
            if(p[x] != x){
                p[x] = find(p[x]);
            }
            return p[x];
        }

        public void union(int a, int b) { 
            int pa = find(a);
            int pb = find(b);
            if(pa == pb)    return;
            if(pa != pb){
                p[pa] = pb;
                size[pb] += size[pa];
            }
        }
    }

        public static void main(String[] args) throws IOException {

            Scanner sc = new Scanner(System.in);
            int n;
            n = sc.nextInt();
            for(int i = 1; i <= n; i ++) {
                arr[i] = sc.nextInt();
            }

            UFind uf = new UFind(n);

            for(int i = 1; i <= n; i ++) {
                int u = uf.find(i);
                int v = uf.find(arr[i]);
                uf.union(u, v);
            }
            BigInteger sum = BigInteger.ONE;
            BigInteger Mod = (BigInteger.TEN).pow(n);

            for(int i = 1; i <= n; i ++) {
                if(uf.find(i) == i) {
                    BigInteger k = BigInteger.valueOf(size[i]);
                    BigInteger d = sum.gcd(k);
                    sum = sum.multiply(k).divide(d);
                }
            }
            sum.mod(Mod);
            System.out.println(sum);

        }

}

F.DPS

题意：
s_i=\lceil 50\frac{d_i}{\max _id_i} \rceil
找到di的最大值maxi di，然后将每个di通过公式转换成si

题解：
模拟题没啥好说的

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)

int n;
ll a[105];
ll k[105];

void solve(ll t, ll k, ll mx)
{
  if(t == mx){
    printf("+");
    rap(i, 1, k)  printf("-");
    printf("+\n");
    printf("|");
    rap(i, 1, k - 1)  printf(" ");
    printf("*|%lld\n", t);
    printf("+");
    rap(i, 1, k)  printf("-");
    printf("+\n");
  }
  else{
    printf("+");
    rap(i, 1, k)  printf("-");
    printf("+\n");
    printf("|");
    rap(i, 1, k)  printf(" ");
    printf("|%lld\n", t);
    printf("+");
    rap(i, 1, k)  printf("-");
    printf("+\n");
  }
}

int main()
{
  rd(n);
  ll mx = 0;
  for(int i = 1; i <= n; i ++){
    rlld(a[i]);
    if(a[i] > mx){
      mx = a[i];
    }

  }
  for(int i = 1; i <= n; i ++){
    k[i] = (long long)ceil(50.0 * a[i] / mx);
    solve(a[i], k[i], mx);
  }
}

I.Hard Math Problem

题意：
给你n*m的矩阵，以及三个角色：G\ H\ E
要求H旁边有G\ E使得占比最大，求出最大值。

题解：
GHHGHH
HHEHHE
HGHHGH
EHHEHH
很容易发现答案就是2/3

代码：

#include<bits/stdc++.h>
using namespace std;

void solve()
{
  double k = 2.0 / 3.0;
  printf("%.6lf\n", k);
}

int main()
{
  solve();
}