首页 > 其他 > 详细

Codeforces Global Round 16

时间:2021-09-15 23:13:07      阅读:50      评论:0      收藏:0      [点我收藏+]

A. Median Maximization

思路:

因为一共有n个数,然后我们要让中位数最大,而题目定义的中位数是第(n+1)/2个数,从这个开始数,到第n个数,一共有cnt= n/2+1个数,我们只要保证后面的数都是s/cnt,这时s/cnt即为所得的最大中位数

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    while(T-- )
    {
        int n, s;
        cin >> n >> s;
        int cnt = n / 2 + 1;
        cout << s / cnt << endl;
    }
    return 0;
}

B. MIN-MEX Cut

思路:

这题暴力能过真是没想到的,记录每次接着1后面新出现0的位置,0的组数加一,(如果好几个0连续就把它们算一组),如果0的组数大于2,直接输出2

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100010;
 
int main()
{
    int T;
    cin >> T;
    getchar();
    while(T-- )
    {
        char s[N];
        cin >> s + 1;
        int res = 0;
        for(int i = 1; i <= strlen(s + 1); i ++  )
            if(s[i] == 0 && s[i - 1] != 0)
                res ++ ;
 
        cout << min(res, 2) << endl;
    }
    return 0;
}

C. MAX-MEX Cut

思路:

把每次出现的一列小矩阵分为三个类型,00,11,10或01这三个类型,出现00的时候flag0标记为true,出现11的时候flag1标记为true,然后这两种情况答案先不增加接着往下走,

flag为true表示从这开始,为false表示在这结束

1.出现的是00,如果 flag0为true,表示上次已经出现过00了,那么res++,并把这个新出现的00标记为true。如果flag1是true,表示上次出现了11,那么res+2,并把flag0和flag1都标记为false

同理

2.出现的是11,如果flag1为true,表示上次已经出现过11了,那么res不变,并把这个新出现的11标记为true。如果flag0是true,表示上次出现了00,那么res+2,并把flag0和flag1都标记为false

3.出现的是10或01,res就直接加2,然后看flag0和flag1,如果flag0为true,那让上次00的情况res++,flag1同理,然后把flag0和flag1标记为false。

最后出循环后看结尾,如果结尾的是00,那最后还要res++

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100010;
 
int main()
{
    int T;
    cin >> T;
    while(T-- )
    {
        int n;
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
 
        bool f[2];
        memset(f, 0, sizeof f);
        int res = 0;
        for(int i = 0; i < n; i ++ )
        {
            int ty = s1[i] - 0 + s2[i] - 0;
            if(ty == 0) // 00
            {
                if(f[0]) res ++ ;
                f[0] = true;
                if(f[1]) res += 2, f[0] = f[1] = false;
            }
            if(ty == 2) // 11
            {
                //if(f[1]) res += 0;
                f[1] = true;
                if(f[0]) res += 2, f[0] = f[1] = false;
            }
            if(ty == 1) // 10 01
            {
                res += 2;
                if(f[0]) res ++ ;
                //else if(f[1]) res += 0;
                f[0] = f[1] = false;
            }
        }
 
        if(f[0]) res ++ ;//最后结尾的是00
 
        cout << res << endl;
    }
    return 0;
}

D1. Seating Arrangements (easy version)

思路:

贪心,电影院仅有一行,则每个人按视力属性a就坐即可,特别地,如果有多名观众的a相同,应当让先来的观众坐里面。最后比较s

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int>PII;
typedef long long LL;
 
const int N = 310;
 
struct Seat
{
    int a, s;
    bool operator< (const Seat& t) const
    {
        if(a != t.a) return a < t.a;
        return s > t.s;//先来的坐里面
    }
}seats[N];//按a从小到大排
 
int main()
{
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> seats[i].a, seats[i].s = i;    
        sort(seats + 1, seats + 1 + m);
 
        int res = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= i; j++)
                if (seats[i].s > seats[j].s)
                    res++;
 
        cout << res << endl;
    }
    return 0;
}

以后每场都打,我要上蓝!!!!!!

Codeforces Global Round 16

原文:https://www.cnblogs.com/yctql/p/15264907.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!