카탈로그

A - Remove Smallest

B - Gifts Fixing

C - Boats Competition

D - Binary String To Subsequences

A - Remove Smallest

아이디어:

작은 순서에서 큰 순서로 인접한 두 개의 비교를 보면 인접한 두 개의 수의 차이가 1을 초과하면 하나만 남을 수 없다

코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 5010
using namespace std;

int a[N];

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        bool flag = 0;
        for(int i = 1; i < n; i++)
        {
            if(a[i] - a[i - 1] > 1)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            printf("NO
");
        else
            printf("YES
");
    }
    return 0;
}

B - Gifts Fixing

아이디어:

a, b 수조에서 가장 작은 수인 아미노와 bmin을 찾았다. 수조에서 모든 숫자를 아미노와 bmin을 빼면 먹을 사탕과 귤이 많이 나온다.첫 번째 선물을 계산하는 데 몇 번을 먹어야 하는지는 바로 이때ai와bi의 비교적 큰 숫자이다.

의문: 귤 한 개로 배불리 먹을 수 없나요?잘 몰라

코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 5010
using namespace std;

typedef long long ll;

ll a[N], b[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        int amin = INF, bmin = INF;
        for(int i = 0; i < n; i++)
        {
            scanf("%lld", &a[i]);
            if(a[i] < amin)
                amin = a[i];
        }
        for(int i = 0; i < n; i++)
        {
            a[i] -= amin;
        }
        for(int i = 0; i < n; i++)
        {
            scanf("%lld", &b[i]);
            if(b[i] < bmin)
                bmin = b[i];
        }
        for(int i = 0; i < n; i++)
        {
            b[i] -= bmin;
        }
        ll ans = 0;
        for(int i = 0; i < n; i++)
        {
            if(a[i] < b[i])
                ans += b[i];
            else
                ans += a[i];
        }
        printf("%lld
", ans);
    }
}

C - Boats Competition

처음에는 C문제 WA가 멍청해져서 아무리 해도 문제를 찾지 못하고 완전히 폭력적인 과오를 다시 썼다.마지막으로 앞부분을 검사했을 때 첫 번째 문장의 초기화 범위가 for(int i = 0; i <= n; i++) num[i] = 0폭력용memset이었기 때문이라는 것을 발견했다.문제를 다시 한 번 보고 n을 2*n으로 고쳐 넘겼다.만약 경기장에서 C문제 WA 8발이었다면, 결과는 상상조차 할 수 없었을 것이다...
아이디어:

폭력: 본 문제는 데이터 범위가 좁아서 2부터 2*n까지 매거와 상황을 직접 계산하고 각 상황에 모을 수 있는 대수를 계산하여 최대치

를 얻을 수 있다.

최적화: 두 수의 합은 반드시 모든 수 중 가장 작은 수보다 크면min*2부터 매거할 수 있다

코드(최적화 버전):

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1100
using namespace std;

typedef long long ll;

int a[N];
int num[N];
bool vis[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        int minn = INF;
        int maxx = -1;
        int cnt = 0;
        scanf("%d", &n);
        for(int i = 0; i <= 2 * n; i++)
            num[i] = 0;
        for(int i = 0; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            if(minn > x)
                minn = x;
            if(maxx < x)
                maxx = x;
            if(num[x] == 0)
                a[cnt++] = x;
            num[x]++;
        }
        int ans = 0;
        for(int sum = minn * 2; sum <= maxx * 2; sum++)
        {
            int tmp = 0;
            for(int i = 0; i < cnt; i++)
            {
                if(sum - a[i] == a[i])
                {
                    tmp += num[a[i]];
                    continue;
                }
                tmp += num[sum - a[i]] < num[a[i]] ? num[sum - a[i]] : num[a[i]];
            }
            ans = tmp / 2 > ans ? tmp / 2 : ans;
        }
        printf("%d
", ans);
    }
    return 0;
}

코드(최적화되지 않은 버전):

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1100
using namespace std;

typedef long long ll;

int a[N];
int num[N];
bool vis[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i <= 2 * n; i++)
            num[i] = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            num[a[i]]++;
        }
        ll ans = -1;
        for(int sum = 2; sum <= 2 * n; sum++)
        {
            ll tmp = 0;
            for(int i = 1; i <= sum; i++)
                tmp += min(num[i], num[sum - i]);
            ans = max(tmp / 2, ans);
        }
        printf("%lld
", ans);
    }
    return 0;
}

D - Binary String To Subsequences

아직 경기장에 안 썼어...아이디어:

참조: CF1399-Codeforces Round #661(Div.3)-D. Binary String To Subsequences(구성, 시뮬레이션)

두 개의 대기열q1, q0으로 현재 01열의 정보를 기록하고 끝은 0으로 q0열에 기록하고 끝은 1로 q1열에 기록한다

vector로 각 요소가 있는 01열 번호

를 기록한다.

str[i]를 선택하고 0이면 대기열q1에 원소가 있는지 확인하기;원소가 없으면 체인을 새로 만들고 원소가 있으면 이 체인의 끝에 연결한다.1의 경우

코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1000100
using namespace std;

typedef long long ll;
char str[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        scanf("%s", str);
        ll cnt = 0;
        queue <ll> q0, q1;
        vector <ll> ans;
        for(int i = 0; i < n; i++)
        {
            if(str[i] == '0')
            {
                if(q1.empty())
                    ans.push_back(cnt++);
                else
                {
                    ans.push_back(ans[q1.front()]);
                    q1.pop();
                }
                q0.push(i);
            }
            else
            {
                if(q0.empty())
                    ans.push_back(cnt++);
                else
                {
                    ans.push_back(ans[q0.front()]);
                    q0.pop();
                }
                q1.push(i);
            }
        }
        printf("%lld
", cnt);
        for(auto i : ans)
        {
            printf("%lld ", i + 1);
        }
        printf("
");
    }
    return 0;
}

경기 후 소결:

다행히 어제 밤새 안 쳤어요(bushi

D문제는 또 이루어지지 않을 거라고 생각했다

C문제는 막다른 골목에 이르렀다. 간단한 초기화 문제는 마지막에 전체 코드를 바꾸었고 다음에는 범위를 주의해야 한다

널리 양해해 주시고, 열심히 진보하십시오.