Codeforces Round #531 (Div. 3)题解

A - Integer Sequence Dividing
题意：输入n,判断1-n的序列是否可以分成2个子集，并且子集的和相等。
解法：按照4分段讨论，因为容易发现每4个数字都可以构成2个子集的和相等，更简单的做法是直接判断前缀和的奇偶性。

#include <bits/stdc++.h>
using namespace std;
int n;
//1, 2, 3, 4
int main(){
    cin >> n;
    long long x = n * (long long) (n+1) / 2;
    cout << (x & 1LL) << endl;
    return 0;
}

B - Array K-Coloring
题意：给定n和k,1<=n,k<=5000，和n个数，要求用k种颜色对n个数进行涂色，要求每种颜色至少出现过一次，而且同一种颜色不能对相同的数字涂色，求是否有合法的涂色方案。
解法：贪心，如果一种数字出现的次数大于K的话显然是没有合法的方案的，否则就贪心构造答案

#include <bits/stdc++.h>
using namespace std;
int n, k, a[5010], cnt[5010], ans[5010];
int main(){
    cin >> n >> k;
    vector <int> v[5010];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        v[a[i]].push_back(i);
        if(++cnt[a[i]] > k){
            puts("NO");
            exit(0);
        }
    }
    puts("YES");
    set <int> st;
    int c = 0;
    for(int i = 0; i < n; i++){
        if(st.count(a[i])) continue;
        st.insert(a[i]);
        for(int j : v[a[i]]){
            ans[j] = c+1;
            c = (c+1)%k;
        }
    }
    for(int i = 0; i < n; i++) printf("%d ", ans[i]);
    printf("\n");
    return 0;
}

C - Doors Breaking and Repairing
题意：给一个长度为n的序列，2个人做游戏，你可以给任意一个数加x,另外一个人可以给任意一个数减y。如果一个数小于等于0，就不能被另外一个人加了。问最多有多少个数为0？
解法：规律，分x和y的情况讨论，如果x>y，无论怎么走，最后你都可以让他变成0，否则的话你只能变(ans+1)/2个，其中ans是a[i]<=x的个数

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int n, x, y;
    scanf("%d%d%d", &n,&x,&y);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    if(x > y){
        printf("%d\n", n);
    }else{
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] <= x) ans++;
        }
        ans = (ans + 1) / 2;
        printf("%d\n", ans);
    }
    return 0;
}

D - Balanced Ternary String
题意：给你一个字符串，这个字符串是由0,1,2构成的，然后让你替换字符，使得在替换的次数最少的前提下，使得新获得的字符串中0,1,2这三个字符的数目相同，并且新获得的字符串字典序要尽可能的小。
解法：分情况讨论，当2多的时候，我们就用1和0从前面进行替换。当1多的时候，我们就用2和0进行替换，为了保证字典序最小，我们将0从前面进行替换，2从后面进行替换。当0多的时候，我们就从后面开始替换，先从2开始，然后再从1开始。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n;
char s[maxn];
int num[4];

int main(){
    scanf("%d", &n);
    scanf("%s", s);
    for(int i = 0; i < n; i++){
        num[s[i]-'0']++;
    }
    int tmp = n / 3;
    //0多，从后面开始替换，先2后1
    if(num[0] > tmp){
        for(int i = n-1; i>=0; i--){
            if(s[i] == '0'){
                if(num[2] < tmp && num[0] > tmp){
                    num[2]++;
                    num[0]--;
                    s[i] = '2';
                }else if(num[1] < tmp && num[0] > tmp){
                    num[1]++;
                    num[0]--;
                    s[i] = '1';
                }
            }
        }
    }
    //1多的话，0从1前面替换，2从后面替换
    if(num[1] > tmp){
        for(int i = 0; i < n; i++){
            if(s[i] == '1'){
                if(num[0] < tmp && num[1] > tmp){
                    num[0]++;
                    num[1]--;
                    s[i] = '0';
                }
            }
        }
        for(int i = n-1; i>=0 ;i--){
            if(s[i] == '1'){
                if(num[2] < tmp && num[1] > tmp){
                    num[2]++;
                    num[1]--;
                    s[i] = '2';
                }
            }
        }
    }
    //2多，1和0从前面替换
    if(num[2] > tmp){
        for(int i = 0; i < n; i++){
            if(s[i] == '2'){
                if(num[0] < tmp && num[2] > tmp){
                    num[0]++;
                    num[2]--;
                    s[i] = '0';
                }else if(num[1] < tmp && num[2] > tmp){
                    num[1]++;
                    num[2]--;
                    s[i] = '1';
                }
            }
        }
    }
    printf("%s\n", s);
    return 0;
}

E. Monotonic Renumeration
题意：有一个长度为n的原始序列a,你需要构造一个长度为n的目标序列b，使得对于所有位置i,j有a[i]==a[j]的也必有b[i]==b[j]，并且对于任意的i，必有 $b [i] = = b [i + 1]$ 和 $b [i] + 1 = = b [i + 1]$ ，现在问b的方案数。
解法：观察一下序列，会发现对于任意一个数，它的左右端点不一样的话，那么这段序列只有一种可能，相反，如果是单个的数并且不包含在其他相等数的最前和最后位置确定的区间中，就有2种可能，所以这个问题就变成了统计不包含在任意相等数确实的区间中的单个数的个数，记作cnt,答案就是 $2^{c n t}$ 。为了统计，直接维护一个每个数相等的数向后延伸的最远位置。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n;
int main(){
    scanf("%d", &n);
    vector <int> a(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    map <int, int> last;
    vector <int> last_pos(n);
    for(int i = n-1; i>=0; i--){
        if(!last.count(a[i])){
            last[a[i]] = i;
        }
        last_pos[i] = last[a[i]];
    }
    int ans = 1;
    int mx = -1;
    for(int i = 0; i < n-1; i++){
        mx = max(mx, last_pos[i]);
        if(mx == i) ans = ans * 2 % mod;
    }
    printf("%d\n", ans);
    return 0;
}

F - Elongated Matrix
题意：一个nm的矩阵，可以任意排列矩阵的行，然后按列展开为nm的序列，统计序列中a[i+1]-a[i]的绝对值最小的值，作为当前序列的特征值，问这个特征值最大为多少？
解法：状态压缩DP。把n个行当成一个个点，点之间的距离就是相同位置差值的最大值。枚举起点，以这个起点出发求状压dp，dp[S][i] 代表最后到达的点是i，状态是S，再枚举终点，如果直接DP的话是会T的，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 18;
const int maxm = 10003;
//以这个起点出发求状压dp，dp[S][i] 代表最后到达的点是i，状态是S
int a[maxn][maxm], mi[maxn][maxn], dp[1<<maxn][maxn];
int n, m;
int main(){
    scanf("%d%d", &n,&m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            int minn = 0x3f3f3f3f;
            for(int k = 0; k < m; k++){
                minn = min(minn, abs(a[i][k] - a[j][k]));
            }
            mi[i][j] = minn;
            mi[j][i] = minn;
        }
    }
    //dp
    int ans = 0;
    for(int st = 0; st < n; st++){
        for(int mask = 0; mask < 1 << n; mask++)
            fill_n(dp[mask], n, 0);
        dp[1 << st][st] = 0x3f3f3f3f;
        for(int mask = 0; mask < 1 << n; mask++){
            for(int en = 0; en < n; en++){
                if(dp[mask][en])
                for(int i = 0; i < n; i++){
                    if(!(mask & 1 << i))
                        dp[mask | 1 << i][i] = max(dp[mask | 1 << i][i], min(dp[mask][en], mi[en][i]));
                }
            }
            for(int en = 0; en < n; en++){
                int minn = dp[(1 << n) - 1][en];
                for(int j = 0; j+1 < m; j++){
                    minn = min(minn, abs(a[en][j] - a[st][j+1]));
                }
                ans = max(ans, minn);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

所以，可以将上面的代码改成记忆化搜索的形式，就可以通过了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 18;
const int maxm = 100 * 100 + 13;
const int INF = 1e9;
int dp[1<<maxn][maxn];
int a[maxn][maxm];
int n, m, mn1[maxn][maxn], mn2[maxn][maxn];
int cal(int mask, int en){
    if(dp[mask][en] != -1) return dp[mask][en];
    dp[mask][en] = 0;
    for(int st = 0; st < n; st++){
        if(st != en && ((mask >> st) & 1))
            dp[mask][en] = max(dp[mask][en], min(mn1[st][en], cal(mask ^ (1<<en), st)));
    }
    return dp[mask][en];
}
int main(){
    scanf("%d%d", &n,&m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int val = INF;
            for(int k = 0; k < m; k++){
                val = min(val, abs(a[i][k] - a[j][k]));
            }
            mn1[i][j] = val;
            val = INF;
            for(int k = 0; k < m-1; k++){
                val = min(val, abs(a[i][k] - a[j][k+1]));
            }
            mn2[i][j] = val;
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        memset(dp, -1, sizeof(dp));
        for(int j = 0; j < n; j++){
            dp[1<<j][j] = (j == i ? INF : 0);
        }
        for(int j = 0; j < n; j++){
            ans = max(ans, min(mn2[j][i], cal((1<<n)-1, j)));
        }
    }
    printf("%d\n", ans);
}