526互联

Codeforces Round 908 (Div. 2)

发布时间 2023-11-10 14:21:15作者: Howardlhhhr

比赛链接

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;
}