Problem A

從n個數(shù)的和，也就是入手。
如果和為奇數(shù)，顯然無法二等分，其最小的差只能為1。
如果和為偶數(shù)，顯然其可以二等分，故其最小的差可以為0。
具體的分割策略的話，可以求出向下取整，然后在n個數(shù)中找出部分?jǐn)?shù)湊出這個數(shù)，剩下的作為另一部分。自行dp一下可以發(fā)現(xiàn)這總能夠湊得出來的。

類比一下用不同面額的金幣湊出各種金額的問題就行了。實在不行自己寫個dp驗證一下。

時間復(fù)雜度為

#include <iostream>

using namespace std;

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

Problem B

首先，先列出會輸出NO的情況：

• 顏色太少（k太?。?/li>
• 顏色太多（k太大）

對于第二種情況的話，當(dāng)且僅當(dāng)的時候會發(fā)生。
而對于第一種情況的話，當(dāng)且僅當(dāng)k小于最少使用顏色數(shù)的時候會發(fā)生。
重點在于最少使用顏色數(shù)。這個其實就是數(shù)組a中重復(fù)次數(shù)最多的元素重復(fù)的次數(shù)。

排除掉NO的情況之后，k種顏色的涂法就是：

• 先按最少使用顏色數(shù)的方案涂（枚舉1到k，每次用該顏色涂盡可能多的元素）
• 然后看還剩多少種顏色需要涂，去找重復(fù)顏色的塊去涂即可（例如，有兩個元素都是顏色1的話，其中就有一個可以涂成別的顏色）

用最暴力的方法來做的話，時間復(fù)雜度為

#include <iostream>
#include <cstring>

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。
否則，只要無法一次踹爆的門他都能跟你耗讓那個門耐久越來越高。所以需要挑能一次踹爆的門下手。當(dāng)然他也知道這一點，所以每當(dāng)你一次踹爆一個門的時候他就會修一個【能被你一次踹爆的門】，使其成為【無法被你一次踹爆的門】。直接計算即可。
時間復(fù)雜度為

#include <iostream>

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

考慮兩種情況：

• 小的數(shù)位有多出的，大的數(shù)位有缺少的：為了讓字典序最小，我們需要盡可能的替換掉靠后的小的數(shù)位為更大的數(shù)位。
• 大的數(shù)位有多出的，小的數(shù)位有缺少的：為了讓字典序最小，我們需要盡可能的替換掉靠前的大的數(shù)位為更小的數(shù)位。

基于這個思想寫個函數(shù)然后對所有可能的數(shù)位組合（其實就三種：0和1，0和2，1和2）調(diào)用一下就行了。

時間復(fù)雜度為

#include <iostream>
#include <string>
#include <cstring>

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

一個顯然的性質(zhì)是，對于任意區(qū)間，如果，那么對于數(shù)組而言，這個區(qū)間內(nèi)的數(shù)必須相同。
于是我們便可以提出若干個這樣的區(qū)間，然后對這些區(qū)間進行合并（有相交區(qū)域的區(qū)間可以合并成一個新的大區(qū)間），最終我們可以得到若干個互不相交的區(qū)間。
設(shè)這些區(qū)間數(shù)為，那么答案顯然就是。

提取區(qū)間的話我們可以使用一個map用于記錄每種數(shù)字的最大下標(biāo)。那么合并區(qū)間的話我們便可以從左往右掃，每次通過這個map來更新區(qū)間右值，直至無法更新為止。

時間復(fù)雜度為

#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 998244353;

LL GetAns(int p)
{
    p -= 1;
    LL ans = 1;
    while(p--)
    {
        ans <<= 1;
        ans %= mod;
    }
    return ans;
}

map<int, int> mapR;
int a[200005];

int FindR(int pos)
{
    int ret = pos;
    for(int i = pos; i <= ret; i++)
    {
        ret = max(ret, mapR[a[i]]);
    }
    return ret;
}

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

        int pos = 0;
        int cnt = 0;
        while(pos < n)
        {
            pos = FindR(pos) + 1;
            cnt++;
        }

        printf("%lld\n", GetAns(cnt));
    }
    return 0;
}

Problem F

首先需要計算出對于任意兩行（第i行和第j行）：

• 如果第j行接在第i行下面的話，兩行中每列的兩個數(shù)的差的絕對值的最小值
• 如果以第i行為結(jié)尾，第j行為開頭的話，第i行中每個數(shù)與第j行中同樣位置的下一個數(shù)的差的絕對值的最小值（也就是）

對于第一個計算的量而言，將每一行看作是一個點，且每個針對有序數(shù)對計算出來的量作為從點i到點j的有向邊的權(quán)值。就可以構(gòu)成一個有向圖（我們假設(shè)該有向圖為圖A）。以同樣的方法對第二個計算出來的量建圖可以得到另一個有向圖B。
于是問題就轉(zhuǎn)換為，在有向圖A中求一條路徑使其經(jīng)過所有的點，且【所經(jīng)過的邊的權(quán)值】和【這條路徑上的終點和起點在圖B上的邊的權(quán)值】的最小值最大。
對于前者的話顯然就是一個旅行商問題的變體，照著旅行商問題的解法便可以解出來?，F(xiàn)在需要處理掉的是后者。事實上我們可以通過枚舉起點來簡化后者的問題。對于每個枚舉的起點求出【經(jīng)過所有點的權(quán)值的最小值最大】的路徑。根據(jù)終點不同會有n條不同的路徑。然后對這些路徑再去查圖B再求一遍兩兩最小，然后從中取最大即可。
不知道旅行商問題的同學(xué)可以自行學(xué)習(xí)一下狀態(tài)壓縮dp。旅行商問題算是狀態(tài)壓縮dp的一個入門題目。

總的時間復(fù)雜度為，前者為建圖過程的復(fù)雜度，后者為枚舉起點+狀壓dp的時間復(fù)雜度。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

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\n", ans);
    }
    return 0;
}