2021年度训练联盟热身训练赛第一场

A.Weird Flecks, But OK

传送门

题意

给你n个点的三维坐标，然后给你一个圆柱形的钉子，问你钉子的直径最小为多大的时候，能够将这n个点在三维空间中覆盖，钉子只能垂直覆盖

解题思路

通过分析我们可以发现我们只需要求三个面的最小圆覆盖面的直径就行，暴力每个点的复杂度为O(N^3),此时的N为5k，显然是不行的，所以我们可以使用Welzl 算法，对三个面算出最小覆盖圆的直径，然后取min，注意的是，有的面算出来可能为0，我们将0删掉即可,时间复杂度为O(N)

Code

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define inf 999999.0
#define zero(a) fabs(a)n;
    if(n&1) {
        puts("Either");
    }
    else {
        n/=2;
        if(n&1)
            puts("Odd");
        else
            puts("Even");
    }
}

E.Early Orders

传送门

题意：

输入一个n和k，然后给你n个数，每个数都是在1 ~ k范围内的，问你找到一个子序列，该子序列满足1 - k的每个数都出现且只能出现一次，并且字典序最小

解题思路

我们从前往后在这n个数里面选够k个满足条件的数，尽量选择字典序小的数，我们可以用一个单调栈，实现选择字典序最小，用ans数组记录这个字典序最小的答案，当我们枚举到了第i个数的时候，我们先比较ans最后一位数和当前第i位数的大小关系，如果当前第i位数比ans数组最后一位数小，且ans数组最后一位数在后面仍然存在，就可以将ans最后一位数去掉，一直到不满足条件，最后将第i位数放入ans数组末尾，这样就可以得到一个字典序最小的满足条件的子序列

Code

#include
using namespace std;

const int N = 200005;
int a[N];
int cnt[N];//记录的是cnt[i]在当前位置后存在的个数
int ans[N];//记录最优解
bool vis[N];//记录是否已经被ans选中
int n,k;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 1;i  a[i] && cnt[ans[top]]) {//选择最优的操作
            vis[ans[top]] = false;
            --top;
        }
        ans[++top] = a[i];
        vis[a[i]] = true;
    }
    for(int i = 1;i