「CF1264X」Codeforces Round #604 (Div. 1)

2019年12月24日4,1530

A. Beautiful Regional Contest
排序后，按照题数划分成若干块，找到 m / 2 所在的块，只考虑前面的块。找出和最大题数相同的给金牌，之后选尽量少的满足要求的块给银牌，剩下的人给金牌。

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int a[400005];
int g, s, b;
bool check(int x)
{
    if(x == 1)return 0;
    int snum = 0;
    for(int i = 1; i <= x; i++)
        if(a[i] == a[1])g++;
        else
        {
            if(s <= g || a[i] == snum)
            {
                snum = a[i];
                s++;
            }
            else b++;
        }
    if(g >= s || g >= b)return 0;
    return 1;
}
int main()
{
    int T = read();
    while(T--)
    {
        n = read();
        for(int i = 1; i <= n; i++)
            a[i] = read();
        m = n / 2;
        while(m > 1 && a[m] == a[m + 1])
            m--;
        g = s = b = 0;
        if(check(m))cout << g <<' '<< s <<' '<< b << endl;
        else puts("0 0 0");
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m;

int a[400005];

int g, s, b;

bool check(int x)

{

if(x == 1)return 0;

int snum = 0;

for(int i = 1; i <= x; i++)

if(a[i] == a[1])g++;

else

{

if(s <= g || a[i] == snum)

{

snum = a[i];

s++;

}

else b++;

}

if(g >= s || g >= b)return 0;

return 1;

}

int main()

{

int T = read();

while(T--)

{

n = read();

for(int i = 1; i <= n; i++)

a[i] = read();

m = n / 2;

while(m > 1 && a[m] == a[m + 1])

m--;

g = s = b = 0;

if(check(m))cout << g <<' '<< s <<' '<< b << endl;

else puts("0 0 0");

}

return 0;

}

B. Beautiful Sequence

我用了比较复杂的分类讨论来构造，其实可以通过枚举 + 构造解决

比如可以枚举起始数字，然后贪心地先排小的再排大的

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a, b, c, d;
int ans[1000005], cnt, first = 1;
bool check()
{
    for(int i = first + 1; i <= cnt; i++)
        if(ans[i] != ans[i - 1] + 1 && ans[i] != ans[i - 1] - 1)
            return 0;
    if(a || b || c || d)return 0;
    return 1;
}
int main()
{
    a = read(); b = read(); c = read(); d = read();
    while(a > 0)
    {
        if(a > 0){a--; ans[++cnt] = 0;}
        if(b > 0){b--; ans[++cnt] = 1;}
    }
    while(c > 1)
    {
        if(c > 0){c--; ans[++cnt] = 2;}
        if(b > 0)
        {
            if(c < d && first == 1)
            {
                first--;
                ans[first] = 1;
                b--;
                break;
            }
            else {b--; ans[++cnt] = 1;}
        }
        else break;
    }
    if(c > 0 && ans[cnt] != 2){c--; ans[++cnt] = 2;}
    if(b > 0 && first == 1)
    {
        first--;
        ans[first] = 1;
        b--;
    }
    if(b > 0){b--; ans[++cnt] = 1;}
    while(d > 0)
    {
        if(d > 0){ans[++cnt] = 3; d--;}
        if(c > 0){ans[++cnt] = 2; c--;}
        else break;
    }
    if(d > 0 && first == 1)
    {
        first--;
        ans[first] = 3;
        d--;
    }
    if(check())
        puts("YES");
    else
    {
        puts("NO");
        return 0;
    }
    for(int i = first; i <= cnt; i++)
         cout << ans[i] <<' ';
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int a, b, c, d;

int ans[1000005], cnt, first = 1;

bool check()

{

for(int i = first + 1; i <= cnt; i++)

if(ans[i] != ans[i - 1] + 1 && ans[i] != ans[i - 1] - 1)

return 0;

if(a || b || c || d)return 0;

return 1;

}

int main()

{

a = read(); b = read(); c = read(); d = read();

while(a > 0)

{

if(a > 0){a--; ans[++cnt] = 0;}

if(b > 0){b--; ans[++cnt] = 1;}

}

while(c > 1)

{

if(c > 0){c--; ans[++cnt] = 2;}

if(b > 0)

{

if(c < d && first == 1)

{

first--;

ans[first] = 1;

b--;

break;

}

else {b--; ans[++cnt] = 1;}

}

else break;

}

if(c > 0 && ans[cnt] != 2){c--; ans[++cnt] = 2;}

if(b > 0 && first == 1)

{

first--;

ans[first] = 1;

b--;

}

if(b > 0){b--; ans[++cnt] = 1;}

while(d > 0)

{

if(d > 0){ans[++cnt] = 3; d--;}

if(c > 0){ans[++cnt] = 2; c--;}

else break;

}

if(d > 0 && first == 1)

{

first--;

ans[first] = 3;

d--;

}

if(check())

puts("YES");

else

{

puts("NO");

return 0;

}

for(int i = first; i <= cnt; i++)

cout << ans[i] <<' ';

return 0;

}

« 「CF1246X」Codeforces Round #596 (Div. 1) 「CF1276X」Codeforces Round #606 (Div. 1) »

hzwer.com _ Home | http://hzwer.com

「CF1264X」Codeforces Round #604 (Div. 1)

分类目录

热门文章

Myfriends

近期评论