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)R)
        {
            central=p[i];R=0;
            for(int j=0;jR)
                {
                    central.x=(p[i].x+p[j].x)/2;
                    central.y=(p[i].y+p[j].y)/2;
                    R=dist(central,p[j]);
                    for(int k=0;kR){
                            //3点确定圆
                            central=Circumcenter(p[i],p[j],p[k]);
                            R=dist(central,p[k]);
                        }
                }
        }
}
int main(){
    scanf("%d",&n);
    double a[N],b[N],c[N];
    for(int i=0;i

D.Some Sum

传送门

题意:

输入一个N,如果在1 ~ 100范围内连续N个数的和是奇数就输出Odd,如果是偶数就输出Even,如果都能满足,就输出Either,N的范围为1 ~ 10

解题思路

1.直接手算,就十种情况

2.考虑连续四个数,由于一定只包含 2 或 2 的倍数个奇数和 2 或 2 的倍
数个偶数,那么他们的和一定是偶数。
而一个奇数和一个偶数的和一定是奇数,那么数字个数模 4 为 2 时和
一定为奇数。
其余情况可以通过移位改变奇偶性,因此为 Either。

Code

#include
using namespace std;
int main()
{
    int n;
    cin>>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 <= n; ++i) {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }

    int top = 0;

    for(int i = 1;i <= n; ++i) {
        --cnt[a[i]];
        if(vis[a[i]]) continue;//如果已经ans选中,那么就直接跳过
        while(top > 0 && ans[top] > a[i] && cnt[ans[top]]) {//选择最优的操作
            vis[ans[top]] = false;
            --top;
        }
        ans[++top] = a[i];
        vis[a[i]] = true;
    }
    for(int i = 1;i <= k; ++i) {
        printf("%d%c",ans[i],i==k?'\n':' ');
    }
    return 0;
}

F.Pulling Their Weight

传送门

题意

输入一个m,然后输入m行数表示的是动物的重量,如果m为奇数,那么就可以踢出一个人,请问怎么分才能使得两边动物的体重和相近,输出中间区分的体重

解题思路

我们先对动物的重量a[N]进行排序,然后对动物计算前缀和,因为动物的总和不会超过20000,所以不用考虑int溢出,然后我们遍历这个重量数组,假设以第i个动物不作为分界线,如果前缀和等于后缀和,并且a[i] a[i+1],那么中间的体重就为a[i],否则为a[i]+1,如果第i个动物作为分界线,并且pre[i-1]pre[m]-pre[i]时,ans就为a[i]

Code

#include
#include
#include
#define N 100005
using namespace std;

int a[N],n,q,m,pre[N];

int main()
{
    int k;
    scanf("%d",&m);
    for(int i = 1; i <= m; ++i) {
      scanf("%d",&a[i]);
    }
    sort(a+1,a+m+1);
    for(int i = 1;i <= m; ++i) {
        pre[i] = pre[i-1] + a[i];
    }
    int ans = 0;
    for(int i = 1;i <= m; ++i) {
        if(pre[i] == pre[m]-pre[i]) {//i未作分界线
            if(a[i] == a[i+1])
                ans = a[i];
            else
                ans = a[i]+1;
        }
        else {
            if(pre[i-1] == pre[m]-pre[i])//i作为分界线
                ans = a[i];
        }
    }
    printf("%d\n",ans);
}

H.On Average They're Purple

传送门

题意

Bob 要从1这个位置到n,Alice 可以进行一些操作使得Bob走过的点为“color change”,Alice 希望 Bob 所走路径上颜色改变的最小次数最大。不难发现Bob要想改变的颜色次数最小,那么Bob走的路一定是1 ~ N 的最短路,当1到n的路径长度为k时,那么此时的颜色改变为k-1,并且不会有更少的情况了

Code

#include
#include
#include//
using namespace std;
const int N=2e5+5;//数据范围
struct edge{//存储边
    int u,v,w,next;//u为起点,v为终点,w为权值,next为前继
};
edge e[N];
int head[N],dis[N],n,m,s,cnt;//head为链中最上面的,dis表示当前答案,n为点数,m为边数,s为起点,cnt记录当前边的数量
bool vis[N];//vis表示这个点有没有走过
struct node{
    int w,to;//w表示累加的权值,to表示到的地方
    bool operator <(const node &x)const{//重载“<”号
        return w>x.w;
    }
};
priority_queueq;//优先队列(堆优化)
void add(int u,int v,int w){
    ++cnt;//增加边的数量
    e[cnt].u=u;//存起点
    e[cnt].v=v;//存终点
    e[cnt].w=w;//存权值
    e[cnt].next=head[u];//存前继
    head[u]=cnt;//更新链最上面的序号
}//链式前向星(加边)
void Dijkstra(){
    memset(dis,127,sizeof(dis));//初始化,为dis数组附一个极大值,方便后面的计算
    dis[s]=0;//起点到自己距离为0
    q.push(node{0,s});//压入队列
    while(!q.empty()){//队列不为空
        node x=q.top();//取出队列第一个元素
        q.pop();//弹出
        int u=x.to;//求出起点
        if(vis[u]) continue;//已去过就不去了
        vis[u]=true;//标记已去过
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;//枚举终点
            if(dis[v]>dis[u]+e[i].w){//若中转后更优,就转
                dis[v]=dis[u]+e[i].w;//更新
                q.push(node{dis[v],v});//压入队列
            }
        }
    }
}
int main(){
    int u,v,w = 1;
    s = 1;
    scanf("%d%d",&n,&m);//输入
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        add(u,v,w);
        add(v,u,w);
    }
    Dijkstra();//DJ
    printf("%d\n",dis[n]-1);
    return 0;
}

J.This Ain't Your Grandpa's Checkerboard

题意

给你一个n X n的棋盘,问你棋盘是否满足一下三个条件

1.每一行都有相同数量的黑色棋子和白色棋子

2.每一列都有相同数量的黑色棋子和白色棋子

3.仍和一行或者一列没有有三个相同的棋子

满足条件输出1,否则输出0

解题思路

这……这不签到题吗,应该不需要思路吧,我们统计每一行和每一列黑子的个数,然后二重循环判断就行……,有手就行

Code

#include
using namespace std;

const int N = 30;

char mp[N][N];
int line[N],row[N];

int main()
{
    int n;
    cin>>n;
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= n ; ++j) {
            cin>>mp[i][j];
            if(mp[i][j] == 'B')
                line[i]++,row[j]++;
        }
    }
    bool fg = true;
    for(int i = 1;i <= n; ++i) {
        for(int j = i + 1;j <= n; ++j) {
            if(line[i] != line[j] || row[i] != row[j]) {
                fg =false;
                puts("0");
                return 0;
            }
        }
    }
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= n - 3; ++j) {
            if(mp[i][j] == mp[i][j+1] && mp[i][j] == mp[i][j+2] && mp[i][j+1] == mp[i][j+2]) {
                puts("0");
                return 0;
            }
            if(mp[j][i] == mp[j+1][i] && mp[j][i] == mp[j+2][i] && mp[j+1][i] == mp[j+2][i]) {
                puts("0");
                return 0;
            }
        }
    }
    puts("1");

}

比赛时,E题和B题一直没切出,是唯一的遗憾,E题到最后我都还是没再看一遍题意,我把子序列看成了子串,导致了我的代码解决的和题目不是一个问题。


本当の声を響かせてよ