从零开始的Codeforces提升之路

薛定谔方程难

发布于 2024-11-18 08:17:59

15600

代码可运行

文章被收录于专栏：我的C语言我的C语言

运行总次数：0

代码可运行

1、前言

对于我来说，看这个分数就知道，我是一个真正的小菜鸡，从现在开始，我将持续更新，我会持续更新，期待一年之后的蜕变，如果获得什么奖状，或者说拿到什么成就的话会及时更新。 如果说正在看文章的你也是一个小白的话，不如及时关注一下，如果有时间的话，我会在每一场比赛结束之后都大概的写一下总结，写一下比赛时候的进度。（其实对于现在的我来说的话，每一场比赛有些情况下我都打不完就结束了，因为实在不会）。如果你是大佬的话，也可以关注关注我，指导一下我（大佬求教）。 我会尽力做好，快速提升自己。

2、阶段

现在的我是一个小灰名，所以该阶段的目标就是把1200分数一下的题心能够做到写的又快又准。所以在比赛结束之后，我会讲解符合我这个阶段的题目的解析，并且阐述我在写题目的过程中遇到的困难。这样的话能够快速找到不足，快速的提升自己。

3、codeforces 983

3、1、Circuit

Circuit 这个题目的话是我当时直接写出来的，对于我来讲都没啥难度(嘻嘻)，题目的要求就是需要确定给出的这段0 1，能够让最多多少个灯是开的，最少多少个灯是开的。对于最多能够使多少个灯是开的的情况下的话，我们只需要找到0，1中个数最多的一项就能得到答案。因为在这样的情况下的话，如果是1个数多的话，那么必定会有多处来的1和1匹配在一个灯控制上，但是这样的话就是让灯重新变为关的状态。所以对于这样的情况每一个0必然能够匹配的上一个1。所以这就是最多的开灯的情况。对于最少的话，就是看1取模，如果能够等于0的话，那就最少为0，反之则为1。

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int cnt1=0,cnt0=0;
        for(int i=0;i<2*n;i++)
        {
            int tmp=0;
            cin>>tmp;
            if(tmp==1)cnt1++;
            else
            cnt0++;
        }
        cout<<cnt1%2<<" ";
        cout<<min(cnt1,2*n-cnt1)<<endl;
    }
}

所以理解题目意思，大概就能够做出这道题目了。如果没做出来的话也不需要太伤感，因为对于我这个newbie来说，我做了21分钟。(还是太菜了，加油)

3、2、Medians

Medians 对于这题来说，需要我们理解一下，因为整个数组都是奇数所以，如果我们想要简单的去分配数组的话，不妨假设我们需要选的那个数就构成唯一的，处在中间的数组。这样的话就只需要看剩余两边的数的个数是奇数还是偶数再来判断。如果我们需要选的数是奇数的话，那么左右两边剩下的都是偶数，那么我们只需要将所选定的数的数组向前扩充一位，向后也扩充一位，这样的话我们就能够实现左边剩下的是奇数，右边也是奇数了。如果我们选的数字是偶数的情况的话，左边和右边剩下来的都是奇数，那么我们就能直接把这个数组分为三段，直接能够实现要求。当然了，存在一个特殊的情况，就是当我们选择的数是1或者是n的时候，是没有结果的。

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(n==1)
        {
            cout<<1<<endl;
            cout<<1<<endl;
            continue;
        }
        if(k==1||k==n)
        {
            cout<<-1<<endl;
            continue;
        }
        
        if(k%2==0)
        {
            cout<<3<<endl;
            cout<<1<<" "<<k<<" "<<k+1<<endl;
        }
        else
        {
            cout<<3<<endl;
            cout<<1<<" "<<k-1<<" "<<k+2<<endl;
        }
    }
}

3、3、Trinity

Trinity 题目是看懂的，答案是写不出来的，因为对于三角的判断来说还是不够熟练，认为还是需要每一个都要满足才行，造成了当时的困扰，所以在当时的话没有写出来，赛后去补上这道题目了。这道题的话，好像按道理来说不难，就是在我知道题目怎么做之后感觉不难的，但是其中有一个地方是我在自己写的时候出现错误了。这个在讲完思路过程在去讲一下代码实现中的我遇到的问题。这道题的话，题目要求是，需要我们求的数据是最小改变次数让所有的数中的任意三个数能组成一个三角形。所以我们可以先排序一下，为什么排序呢？ 那是因为在排完之后，我就能找到最小的数和最大的数，因为我们需要保证任意三个都能组成，那就是说明我们找到的最小的两个数，能够大于最大的那个数，那我们能够改变元素的方法有哪些呢？很显然，应该是有两种，一种是在找到两个最小的数之后找到最小的超过最小的两个数之和的数，然后把这个数以及之后的所有的数都改变，变得符合题意。还有一种方法就是找到最小的两个数之后，把最小的数变的大一点，然后去比较，改变之后的序列能否满足题目的要求。这两种方法搭配着使用就能够实现计算出在任何位置为起点的数组需要操作多少次能够达到所以这两种方法的话需要我们进行比较，看每一种操作那一种是最小的，然后遍历一遍数组，看哪一次为起点的位置的数组的操作数能够最小。所以好好的理解每一次的时候都是以不同位置为最小的时候能够保证数组符合要求的操作次数。这句话是很重要的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
const int N=2e5+10;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        //for(int i=1;i<=n;i++)
        //cout<<a[i]<<" ";
        //cout<<endl;
        int i=1,j=i+2;
        int ret=n;
        for(int i=1;i<n-1;i++)
        {
            for(;j<=n;j++)
            {
                if(a[i]+a[i+1]<=a[j])
                {
                    break;
                }
            }
            ret=min(ret,i-1+n-j+1);
            
        }
        if(ret==n)
        cout<<-1<<endl;
        else
        cout<<ret<<endl;
    }
    return 0;
}