【Codeforces】Codeforces Round #531

Problem A

n개수의 합, 즉 착수.만약 화(和)가 홀수라면 분명히 이등분할 수 없고, 그 최소 차이는 1일 뿐이다.만약 화(和)가 짝수라면 분명히 이등분할 수 있기 때문에 가장 작은 차는 0이 될 수 있다.구체적인 분할 전략은 아래로 정돈한 다음에 n개 수에서 부분수를 찾아 이 수를 모으고 나머지는 다른 부분으로 할 수 있다.스스로 dp를 하면 이것이 어쨌든 모을 수 있다는 것을 발견할 수 있다.
액면가가 다른 금화로 각종 금액을 모으는 문제를 비교해 보면 된다.도저히 안 되면 스스로 dp를 써서 검증해 보세요.
시간의 복잡도는

#include 

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        n = (n + 1) >> 1;
        cout << n%2 << endl;
    }
    return 0;
}

Problem B

먼저 NO가 출력되는 경우를 나열합니다.

색상이 너무 작음(k는 너무 작음)

색상이 너무 많음(k가 너무 크음)

두 번째 상황에 대해서는 당당할 때만 발생한다.첫 번째 경우 k가 최소한의 색 사용량보다 적을 때만 발생한다.최소 색상 수에 중점을 두다.이것은 사실 수조a에서 중복 횟수가 가장 많은 원소의 중복 횟수다.
NO를 제외한 k가지 색상의 바르는 방법은 다음과 같다.

최소한의 색 수를 사용하는 방안에 따라 칠한다(1부터 k까지 일일이 이 색으로 가능한 한 많은 요소를 칠한다)

그리고 몇 가지 색이 남았는지 보고 중복된 색의 블록을 찾아서 바르면 된다(예를 들어 두 요소가 모두 색 1이면 그 중 하나는 다른 색으로 칠할 수 있다)

가장 폭력적인 방법으로 하면 시간의 복잡도는

#include 
#include 

using namespace std;

int main()
{
    int a[5005], n, k;
    int ans[5005];
    while(cin >> n >> k)
    {
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        memset(ans, -1, sizeof(ans));

        if(n < k)
        {
            cout << "NO" << endl;
            continue;
        }

        int cnt = 0;
        for(int i = 1; i <= k; i++)
        {
            bool vis[5005] = {0};
            if(cnt == n)
            {
                for(int j = 0; j < n; j++)
                {
                    if(vis[ans[j]])
                    {
                        ans[j] = i;
                        i++;
                        if(i > k)
                        {
                            break;
                        }
                    }
                    else
                    {
                        vis[ans[j]] = true;
                    }
                }
            }
            else
            {
                for(int j = 0; j < n; j++)
                {
                    if(ans[j] == -1)
                    {
                        if(vis[a[j]])
                        {
                            continue;
                        }
                        vis[a[j]] = true;
                        ans[j] = i;
                        cnt++;
                    }
                }
            }
        }

        if(cnt == n)
        {
            cout << "YES" << endl;
            for(int i = 0; i < n; i++)
            {
                if(i)
                {
                    cout << " ";
                }
                cout << ans[i];
            }
            cout << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Problem C

상황별 토론: 만약, 분명히 그와 천천히 소모하면 모든 문을 깨뜨릴 수 있다. 답은 n이다.그렇지 않으면, 한 번에 터뜨릴 수 없는 문만 있으면 그는 너와 함께 그 문의 내구성을 더욱 높일 수 있다.그래서 한 번에 터뜨릴 수 있는 문짝을 골라야 돼.물론 그도 이 점을 알고 있기 때문에 네가 한 번 문을 차서 터뜨릴 때마다 그는 [너에게 한 번 차일 수 있는 문]을 고쳐서 [너에게 한 번 차일 수 없는 문]이 되도록 한다.직접 계산하면 된다.시간의 복잡도는

#include 

using namespace std;

int a[1005];

int main()
{
    int n, x, y;
    while(cin >> n >> x >> y)
    {
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        if(x > y)
        {
            cout << n << endl;
        }
        else
        {
            int cnt = 0;
            for(int i = 0; i < n; i++)
            {
                if(a[i] <= x)
                {
                    cnt++;
                }
            }
            cout << (cnt + 1) / 2 << endl;
        }
    }
    return 0;
}

Problem D

두 가지 시나리오를 고려하십시오.

작은 숫자는 많고 큰 숫자는 부족하다. 사전의 순서를 최소화하기 위해 우리는 가능한 한 뒤에 있는 작은 숫자를 더 큰 숫자로 교체해야 한다.

큰 숫자는 많고 작은 숫자는 부족하다. 사전의 순서를 최소화하기 위해 우리는 가능한 한 앞에 있는 큰 숫자를 더 작은 숫자로 교체해야 한다.

이 사상을 바탕으로 함수를 써서 모든 가능한 디지털 조합(사실 세 가지: 0과 1, 0과 2, 1과 2)을 호출하면 된다.
시간의 복잡도는

#include 
#include 
#include 

using namespace std;

string s;
int cnt[5], n;

void Fix(int a, int b)
{
    int pos = 0;
    while((cnt[a] < 0) && (cnt[b] > 0))
    {
        if(s[pos] == b + '0')
        {
            s[pos] = a + '0';
            cnt[a]++;
            cnt[b]--;
        }
        pos++;
    }

    pos = n - 1;
    while((cnt[b] < 0) && (cnt[a] > 0))
    {
        if(s[pos] == a + '0')
        {
            s[pos] = b + '0';
            cnt[b]++;
            cnt[a]--;
        }
        pos--;
    }
}

int main()
{
    while(cin >> n)
    {
        cin >> s;
        for(int i = 0; i < 3; i++)
        {
            cnt[i] = -1 * (n / 3);
        }
        for(int i = 0; i < n; i++)
        {
            cnt[s[i] - '0']++;
        }

        Fix(0, 2);
        Fix(0, 1);
        Fix(1, 2);
        
        cout << s << endl;
    }
    return 0;
}

Problem E

하나의 명백한 성질은 임의의 구간에 대해, 만약, 수조에 대해 말하자면, 이 구간 내의 수는 반드시 같아야 한다는 것이다.그래서 우리는 몇 개의 이런 구간을 제기한 다음에 이 구간을 합병할 수 있다(교차구역이 있는 구간은 하나의 새로운 큰 구간으로 합병할 수 있다). 결국 우리는 서로 교차하지 않는 몇 개의 구간을 얻을 수 있다.이 구간수를 예로 들면, 답은 분명히 그렇다.
추출 구간은 각각 숫자의 최대 하표를 기록하는 데 사용할 수 있습니다.그러면 구간을 합치면 왼쪽에서 오른쪽으로 훑어볼 수 있습니다. 매번 이 map 를 통해 구간의 오른쪽 값을 갱신할 수 없습니다. 갱신할 수 없을 때까지.
시간의 복잡도는

#include 
#include 

Problem F

먼저 두 행의 경우(i 행과 j 행)를 계산해야 합니다.

j줄이 i행 아래에 연결되면 두 줄 중 열마다 두 수의 차이의 절대값의 최소값

제i행위로 끝나고 제j행위로 시작하면 제i줄의 각 수와 제j줄의 같은 위치의 다음 수의 차이의 절대값의 최소값(즉)

첫 번째 계산의 양에 대해 말하자면 모든 줄을 하나의 점으로 간주하고 모든 순서에 따라 계산된 양을 점 i에서 점 j까지의 유방향적인 값으로 한다.유방향도를 구성할 수 있다. (우리는 유방향도를 그림 A로 가정한다.)같은 방법으로 두 번째 계산된 양에 대해 도면을 만들면 또 다른 유방향도 B를 얻을 수 있다.그래서 문제는 그림 A에 모든 점을 통과할 수 있는 경로를 구하고 [이 경로의 끝점과 시작점이 그림 B에 있는 끝의 값]의 최소값이 가장 크다는 것으로 바뀌었다.전자의 말은 분명히 여행사 문제의 변체로 여행사 문제의 해법에 따라 풀 수 있다.지금 처리해야 할 것은 후자다.사실 우리는 일괄적인 출발점을 통해 후자의 문제를 간소화할 수 있다.모든 매거진의 기점에서 [모든 점을 통과하는 권한의 최소값이 가장 크다]의 경로를 구한다.종점에 따라 n개의 경로가 다릅니다.그리고 이 경로에 대해 다시 그림 B를 찾아서 두 냥의 최소를 구하고 그 중에서 최대를 찾으면 된다.여행사 문제를 모르는 학생은 스스로 상태 압축 dp를 배울 수 있다.여행사 문제는 상태 압축 dp의 입문 문제라고 할 수 있다.
전체적인 시간 복잡도는 전자는 도면을 만드는 과정의 복잡도이고 후자는 매거점 + 상압 dp의 시간 복잡도이다.

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INF = 1.5e9;

int e[25][25], nxt[25][25];
int a[25][10005];

void Build(int &n, int &m)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int w = INF;
            for(int k = 0; k < m; k++)
            {
                w = min(w, abs(a[i][k] - a[j][k]));
            }
            e[i][j] = w;

            w = INF;
            for(int k = 1; k < m; k++)
            {
                w = min(w, abs(a[i][k-1] - a[j][k]));
            }
            nxt[i][j] = w;
        }
    }
}

int dp[70000][25];

int GetAns(int &src, int &n)
{
    memset(dp, -1, sizeof(dp));
    dp[1 << src][src] = INF;
    for(int bitm = 1; bitm < (1 << n); bitm++)
    {
        for(int i = 0; i < n; i++)
        {
            if(!(bitm & (1 << i)))continue;
            for(int j = 0; j < n; j++)
            {
                if(i == j)continue;
                if(!(bitm & (1 << j)))continue;
                if(bitm == (1 << j))continue;
                dp[bitm][i] = max(dp[bitm][i], min(dp[bitm - (1 << i)][j], e[j][i]));
            }
        }
    }

    int ret = -1;
    for(int i = 0; i < n; i++)
    {
        ret = max(ret, min(dp[(1 << n) - 1][i], nxt[i][src]));
    }
    return ret;
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }

        Build(n, m);
        int ans = -1;
        for(int i = 0; i < n; i++)
        {
            ans = max(ans, GetAns(i, n));
        }
        printf("%d
", ans);
    }
    return 0;
}