我的个人记载
  • About Me
不知名小站
Never Give Up
  1. 首页
  2. 多校训练
  3. 正文

2020多校训练-第五场

2020年08月14日 83点热度 0人点赞 0条评论

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();
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年08月14日

框框

喜欢算法,喜欢编程。

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复

框框

喜欢算法,喜欢编程。

文章归档
  • 2020年10月
  • 2020年8月
  • 2020年7月
  • 2020年1月
  • 2019年11月
  • 2019年8月
  • 2019年7月
分类目录
  • 2008年哈尔滨区域赛
  • 2018焦作网络赛
  • Greater New York Region 2014
  • kuangbin并查集专题
  • Kuangbin数论专题
  • NZPC 2017
  • upc个人训练赛
  • 位运算
  • 博弈论
  • 多校训练
  • 搜索
  • 数据结构
  • 数论
  • 杭电多校训练第五场
  • 深入理解计算机基础/CSAPP
  • 算法模板
  • 线段树

COPYRIGHT © 2020 我的个人记载. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

苏ICP备19034952号-1