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();
}
文章评论