这场是真的输麻了，D嗑错了 + C FST

A. Greatest Convex

题目描述：

题目分析

在 1~k 中找出一个尽可能大的数 x 使得 $x!\times (x-1)!\ mod\ k=0$ 也就是说能被 k 整除。那么化简一下式子得到 $(x+1)\times (x-1)!\ mod\ k=0$ 然后要在 k 以内找到尽可能大的数 x 成立，很显然，x=k-1 的时候是最优的。所以我们的标程就是输入一个值我们输出 k-1 就行。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
void solve(){
    scanf("%d",&n);
    printf("%d\n",n-1);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Quick Sort

题目描述：

题目分析

给定一个排列，让你进行如下操作：

  • 选择任意k个不同的数值，提取出来升序排序插入到排列最末尾。

其实不难发现：

  1. 如果排列本来遵循了 $p_i=i$ 的条件，那么我们完全不用动这一部分的排列。
  2. 如果某个数在一次操作中被选中，那么比它大的所有的未被选中的数都要被选中。如果 1 不在它本来的位置，那么我们移动1是非常不理智的，因为这意味着剩余的所有数都需要被选中移动，这显然不能达到最优。

于是对于比较小的数，我们不选择移动，而是移动它们之前的比它大的数，留下比它小的数，这显然是最优的一个选择。那么显然能得到以下规律：

  • 对于1而言，我需要移动1之前所有的数
  • 对于2而言，我需要移动2之前所有非1的数
  • 对于3而言，我需要移动3之前所有非1，2的数
  • ……

所以最后我们就寻找一个尽可能长的子序列，这个子序列为 1,2,3...n，对子序列的定义不清楚的可以自己查查。

既然我们最后就是找到一个特定序列的长度，那就变得很容易了，直接 O(n) 扫一遍，扫到 1 之后扫 2 然后 3 ，4这样下去，得到一个长度为 m 的子序列，它们都是不需要去移动的。除此之外都需要被移动，那么结果就是 (n-m) 每次操作最多移动 k 个数，那么就向上取整除就好了。(n-m+k-1)/k

标程中 m 和 k 调换了意义

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int flag=1;
    for(int i=1;i<=n;i++){
        if(flag==a[i]){
            flag++;
        }
    }
    //printf("flag:%d\n",flag);
    printf("%d\n",(n-flag+m)/m);
}
signed main(){
    #ifndef ONLINE_JUDGE
        //freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Elemental Decompress

题目描述

题目分析

FST了，不过还是可以讲讲暴力的思路。

题目给定一个数组 ${a_i}$ 要求我们构造两个排列，使得 $\max(p_i,q_i)=a_i$。这里想当然的暴力去写了，就是先选当前这个数组的值作为排列 $p_i$ 的值，也就是使得 $p_i=a_i$，当然为了满足排列的定义，我们需要定义一个标记数组判断当前的数是否有被使用过，如果被使用过那么这个值给到 $q_i$ 如果 $q_i$ 也被是用了，那么此题无解，最常见的就是出现了三个一模一样的数，这必然是不可能的。

第一次出现给到 $p_i$ 第二次出现给到 $q_i$ 那么第三次出现直接判无解。

很完美，那么这一波处理下来才完成了一半，另一半需要根据当前排列的情况和另外一个排列选择的数决定，不难发现选择当前没有选择的符合条件的最大数是最优的。但是这里需要亿点点复杂度，所以我直接贪过去了，就直接 $O(n)$ 去扫，虽然过了 pretest 但是还是 FST了。

（正解待补）

标程（假的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define maxn 200005
#define LOSE {puts("NO");return;}
using namespace std;
int a[maxn],b[maxn];
int p[maxn],q[maxn];
bool pp[maxn],qq[maxn];
char s[maxn];
int n,m;
void solve(){
    scanf("%d",&n);
    memset(p,0,sizeof(int)*(n+1));
    memset(pp,0,sizeof(int)*(n+1));
    memset(q,0,sizeof(int)*(n+1));
    memset(qq,0,sizeof(int)*(n+1));
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        if(!pp[a[i]]){
            pp[a[i]]=1;
            p[i]=a[i];
        }
        else if(!qq[a[i]]){
            qq[a[i]]=1;
            q[i]=a[i];
        }
        else LOSE
    }
    
    for(int i=1;i<=n;i++){
        if(!p[i]){
            int num=q[i];
            while(pp[num]){
                num--;
            }
            if(num==0) LOSE
            p[i]=num;
            pp[num]=1;
        }
        else{
            int num=p[i];
            while(qq[num]){
                num--;
            }
            if(num==0) LOSE
            q[i]=num;
            qq[num]=1;
        }
    }
    puts("YES"); 
    for(int i=1;i<=n;i++){
        printf("%d ",p[i]);
    }putchar(10);
    for(int i=1;i<=n;i++){
        printf("%d ",q[i]);
    }putchar(10);
    for(int i=1;i<=n;i++){
        assert(max(p[i],q[i])==a[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        //freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

D. Lucky Permutation

题目描述

题目分析

何为 Lucky permutation？就是有且仅有一个逆序对的 permutation。这题正解是寻找排列环。遵循这样的逻辑：

  1. 从位置 $i$ 开始找，设立终值 $end=i$
  2. 拿到当前的 $i$ 使得 $i=p_i$
  3. 判断 $i$ 是否等于当前终值，是则结束，不是则重复步骤2

那么我们要让这里的排列有序，也就是达到 $p_i=i$ 的状态就需要 $k-1$ 步操作。

如果说要让它最后有序，那么这样找也就能算出操作了，但是这里还需要一点就是有一个逆序对，所以我们要考虑的就是我们能否在交换过程中少交换一次让它自然形成逆序对？

那就直接考虑在交换的过程中有没有处于相邻状态的值即可。我们用 vis 数组保存初始搜索点的值，值一样表示处于同一个排列环，如果存在一个 $i$ 使得 $vis[i]==vis[i+1]$ 那么这就可以少一步操作，否则多一步操作。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define maxn 200005
#define LOSE {puts("NO");return;}
using namespace std;
int a[maxn],b[maxn],vis[maxn]; 
char s[maxn];
int n,m,flag;
queue<int>q;
int dfs(int pos){
    int cnt=1;
    int endvalue=pos;
    vis[pos]=endvalue;
    while(a[pos]!=endvalue){
        pos=a[pos];
        vis[pos]=endvalue;
        cnt++;
    }
    return cnt;
}
void solve(){
    scanf("%d",&n);
    flag=0;
    memset(vis,0,sizeof(int)*(n+1));
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        
        if(!vis[i]){
            //printf("i:%d\n",i);
            int k=dfs(i);
            ans+=k-1;
        }
    }
    for(int i=1;i<n;i++){
        if(vis[i]==vis[i+1]){
            flag=1;
            break;
        }
    }
 
    if(flag)ans-=1;
    else ans+=1;
    printf("%d\n",ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        //freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

只能说还是很难的，上分之路命途多舛，写完这篇题解已经是深夜了，深夜到了 emo 的时间，等会看看能不能再写一篇闲扯淡文章吧。