首页 > 其他分享 >Codeforces Round 908 (Div. 2)

Codeforces Round 908 (Div. 2)

时间:2023-11-10 14:23:05浏览次数:43  
标签:数字 int 题解 908 Codeforces solve 数组 序列 Div

比赛链接

A. Secret Sport

题解 O(1 * T)

对于一场比赛,结束前谁最后赢就是谁赢

#include <bits/stdc++.h>
using namespace std;
string s;
void solve()
{
    int n;
    cin >> n >> s;
    cout << s[n-1] << endl;
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

B. Two Out of Three

题解 O(n * T)

在此处为了方便解释定义一个如果一个数组某个数字出现大于等于两次,那么我们把这个数字成为可处理数字。当一组中有两组以上的可处理数字那么这个数组处理出合理的b数组,将可处理数字满足1 2,后面的可处理数字满足1 3,其余置1即可

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
struct Node
{
    int a,b;
}nd[N];
bool st[N];
int last[N];
void solve()
{
    memset(st,0,sizeof st);
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++) scanf("%d",&nd[i].a);
    bool flag = false;
    bool a[4] = {false};
    for(int i = 0;i<n;i++)
    {
        if(!st[nd[i].a]) nd[i].b = 1,st[nd[i].a] = true,last[nd[i].a] = 1;
        else
        {
            if(last[nd[i].a]==1)
            {
                if(!flag) nd[i].b = 2,flag = true;
                else nd[i].b = 3;
                last[nd[i].a] = nd[i].b;
            } 
            else nd[i].b = last[nd[i].a];
        }
        a[nd[i].b] = true; 
    }
    int cnt = 0;
    for(int i = 1;i<=3;i++) if(a[i]) cnt ++;
    if(cnt<=2)
    {
        puts("-1");
        return;
    } 
    else
    {
        for(int i = 0;i<n;i++)
        {
            cout << nd[i].b << ' ';
        }
    }
    puts("");
    
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

C. Anonymous Informant

题解 O(n*T)

假设有a数组可以满足题意,那么对于$a_x = x$向左移动x位后,必定会移动到数组的末尾。换句话来说,如果已经知道b数组,数组末尾的数就是上一次的不定点,只需要维护最后一个值的下标是多少即可
** 注意两个问题,第一个,如果枚举到的数字大于n,那么这个数字无法作为不定点,可以直接退出。第二个,如果已经做完min(n,k)个操作,可以直接判断Yes,理由如下,如果n>k,那么我们直接枚举完k次操作即可,对于k>n ,最坏的情况是每一个数字最后的数字在数组中都不一样,那么n次操作讲每一个数字(下标相同)都枚举了一遍,是一个周期满足。在n次之内如果数组中某个数字(下标相同)出现了两次,那么说明这两次之间会形成一个周期,因为当这个数字出现第二次的时候还是会按照第一次的方式执行下去**

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N];
void solve()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 0;i<n;i++) scanf("%d",&a[i]);
    int last = n-1;
    k = min(n,k);
    while(k--)
    {
        if(a[last]>n)
        {
            puts("No");
            return;
        }
        else
        {
            last = (last+n-a[last])%n;
        }
    }
    puts("Yes");
    return;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

D. Neutral Tonality

题解 O(T*(n+m)):

对于a序列,最长上升子序列的长度是不变的(a的顺序是不变),因此想要LIS(c)最小化,就是要b数组插入之后尽量不增加或者说让LIS(c) = LIS(a),注意一个点就是对于b数组,第一我们不能让b数组有上升子序列,第二我们不能让b数组跟a数组形成额外的上升子序列。对于第一个点,我们可以将b数组从大到小排序,这个时候b数组的最长上升子序列的长度LIS(b) = 1,这个时候我们考虑怎么插的时候我们考虑第二点,对于每一个a数组的数字$a_i$,我们将大于$a_i$的数放在前面,小于$a_i$的数放在后面让这个数前后形成一个不严格单调下降序列即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    vector<int>a(n),b(m),c(n+m);
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
    sort(b.rbegin(),b.rend());
    merge(a.begin(),a.end(),b.begin(),b.end(),c.begin(),greater<int>());
    for(int i = 0;i<n+m;i++)
    {
        printf("%d ",c[i]);
    }
    puts("");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

标签:数字,int,题解,908,Codeforces,solve,数组,序列,Div
From: https://www.cnblogs.com/howardsblog/p/17824011.html

相关文章

  • CodeForces 852C Property
    洛谷传送门CF传送门NOIP模拟赛T1,小清新几何题。要让选出的点组成的多边形面积最大,就要让正多边形的面积减去选出的点组成的多边形面积最小。而这个面积差可以表示成\(2n\)个三角形的面积,即\(\sum\limits_{i=0}^{2n-1}S_{\triangleA_iA_{(i+1)\bmodn}B_{(i+......
  • Educational Codeforces Round 126 (Rated for Div. 2)
    https://codeforces.com/contest/1661/B题数据很小,直接bfs预处理就行C题随便猜了一下,设mx=\(max\{a_i\}\)最后的值应该是mx,mx+1,mx+2,mx+3之类的吧D题刚开始从前面考虑,陷入僵局,一度非常的困,学习凯库勒睡了一会,就突然想到了,前面不行,就从后面考虑,可以发现,从后面考虑的话,就非常......
  • 11月9月字体的属性2以及div模块的另一种用法
    目录字体的属性2文字对齐文字的装饰首行缩进文字的距离设置块级标签的另一个作用字体的属性2文字对齐、文字装饰、首行缩进、文字之间的距离文字对齐需要用到属性text-align,该属性是用于规定元素中的文本水平对齐方式。然后就是text-align的属性值:值描述left左边......
  • cf908(div2)题解(补题)
    纪念这次div2让我上绿名,但还是有点遗憾,差一点就可以过三题超神了比赛链接cf908div2A这题是个骗人题,整个比赛会停下来就是一个人赢够了回合数,那么在谁这停下来就是谁赢了整个比赛,不用管每回合赢得规则。#include<iostream>usingnamespacestd;#include<string>intmain(){......
  • Codeforces Round 908 (Div. 2)
    A.SecretSport题意:A与B选手在下棋,规定下赢X把看作赢一局,一共赢Y把的那个是最后的赢家。思路:因为不知道x,y到底是多少,n的范围是到20,所以只需要枚举x即可,时间复杂度不高,注意的是,如果枚举结果是A赢,那么给定字符串的最后一个值一定是A,反之也是。#include<bits/stdc++.h>usingnam......
  • 相对熵/KL散度(Kullback–Leibler divergence,KLD)
    相对熵(relativeentropy)又称为KL散度(Kullback–Leiblerdivergence,简称KLD),信息散度(informationdivergence),信息增益(informationgain)。KL散度是两个概率分布P和Q差别的非对称性的度量。     KL散度是用来度量使用基于Q的编码来编码来自P的样本平均所需的额外的比特个......
  • Codeforces Visit
    CodeforcesVisit记录一下自己大概vis了那几场??随机补题大法好!CF632Div.2飞速模拟出ABC。优势在我!CF1333D发现就是把字符串变成LLRR此类形状。所以开头必然是L啊,然后我们考虑先把L换到第一个。发现必然是LLLLLLLLLLLRRRRRRRR啊,很快啊,不会了。CF1333E你妈妈con......
  • CSS让子元素div的高度填满父容器的剩余空间的方法
    原帖:https://pythonjishu.com/unbayyjtzdjeewe/以下是详细讲解CSS让子元素div的高度填满父容器的剩余空间的方法的完整攻略。方法一:FlexboxFlexbox是一种强大的布局方式,使用起来非常方便。可以通过设置父元素的display属性为flex来开启flexbox布局,然后设置子元素的......
  • Educational Codeforces Round 157 (Rated for Div. 2)
    A.TreasureChest题目大意:人在0处,宝藏在x,钥匙在y,人最多拿宝箱z秒,问你最快多久开宝箱?思路:如果说钥匙在宝箱的左边,那么人只需要往右走就是最佳答案,如果钥匙在宝箱的右边,那么人只需要拿的宝箱到最佳地点就行#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intx,y......
  • Educational Codeforces Round 157 (Rated for Div. 2)
    F.FancyArrays第一眼感觉是去容斥掉条件1,因为条件2其实挺紧的。不妨用\(f(l,r)\)表示\(a\)值域在\([l,r]\)的方案(满足条件2)。那么答案为\(f(0,+\infty)-f(0,x-1)-f(x+k,+\infty)\),因为如果选了\([0,x-1]\)的数,那么还要更大的话,一定会选到\([x,x+k-1]\),所以你要......