Codeforces Round #462 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #462 (Div. 2)
过题数：3
排名：462/9658

A. A Compatible Pair

题意

$Tommy$ 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，$Banban$ 有一个长度为 $m$ 的序列 $b_1,b_2,\cdots,b_n$，$Tommy$ 从自己的序列中除掉一个数字，$Banban$ 从 $n-1$ 个数字的 $a$ 序列中选择一个数字，再从自己序列中选择一个数字，将这两个数字相乘，就是得到的结果。现在 $Tommy$ 想让最终结果最小，而 $Banban$ 想让最终结果最大，问如果两人都采取最优策略，最终的结果会是多少。

输入

第一行为两个整数 $n,m~(2\leq n,m\leq50)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n$，第三行为 $m$ 个整数 $b_1,b_2,\cdots,b_m$，其中 $-10^9\leq a_i,b_i\leq10^9$。

输出

输出最终结果。

样例

题解

暴力枚举所有情况，对于 $Tommy$ 删除的每一个数字，枚举 $Banban$ 所有可能的选择中的最大值，输出这些最大值中的最小值。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100;
int n, m;
LL a[maxn], b[maxn];
LL solve(int Index) {
    LL ret = -(1LL << 60);
    for(int i = 0; i < n; ++i) {
        if(i == Index) {
            continue;
        }
        for(int j = 0; j < m; ++j) {
            ret = max(ret, a[i] * b[j]);
        }
    }
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        LL ans = (1LL << 60);
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &a[i]);
        }
        for(int j = 0; j < m; ++j) {
            scanf("%I64d", &b[j]);
        }
        for(int i = 0; i < n; ++i) {
            ans = min(ans, solve(i));
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

B. A Prosperous Lot

题意

给定数字 $k$，构造一个不超过 $10^{18}$ 的正整数 $n$，使得所有数位中的圈的个数和等于 $k。$

输入

一个整数 $k~(1\leq k\leq10^6)$。

输出

输出满足条件的整数 $n$，如果不存在满足条件的正整数，则输出 $-1$。

样例

题解

如果 $k$ 大于 $36$，输出 $-1$，否则输出 $\lfloor\frac{k}{2}\rfloor$ 个 $8$ 后，再输出 $k\%2$ 个一个环的数字（$4$、$6$、$9$）。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
int k;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &k) != EOF) {
        if(k > 36) {
            printf("-1\n");
            continue;
        }
        while(k - 2 >= 0) {
            printf("8");
            k -= 2;
        }
        if(k != 0) {
            printf("6");
        }
        printf("\n");
    }
    return 0;
}

C. A Twisty Movement

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，序列中所有的数字只可能是 $1$ 或者 $2$，现在可以从序列中选取连续的一段数字，将这段数字左右镜像颠倒，求这样颠倒之后最大的最长非递减子序列长度。

输入

第一行为一个整数 $n~(1\leq n\leq2000)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(a\in\{1,2\})$。

输出

输出所求答案。

样例

题解

先预处理从第 $1$ 个数字到第 $i$ 个数字最大值为 $x$ 的最长非递减子序列长度 $dpL[i][x]$，以及从第 $i$ 个数字到第 $n$ 个数字最小值为 $x$ 的最长非递减子序列长度 $dpR[i][x]$，以及 $cnt_1$ 和 $cnt_2$ 的前缀和 $sum_1,sum_2$，接着 $O(n^2)$ 枚举所有区间，对于每个区间求出区间内以 $i$ 开头以 $j$ 结尾最小值为 $x$ 的最长非递增子序列的长度 $dp[j][x]$，对每一个区间 $[i,j]$ 取

$$\max \begin{cases} dpL[i-1][1]+dpR[j+1][1]+sum[j][1]-sum[i-1][1]\\ dpL[i-1][2]+dpR[j+1][2]+sum[j][2]-sum[i-1][2]\\ dpL[i-1][1]+dpR[j+1][2]+dp[j][1] \end{cases}$$ 就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int n, ans;
int num[maxn];
int dpL[maxn][3], dpR[maxn][3];
int dp[maxn][3], sum[maxn][3];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            sum[i][1] = sum[i - 1][1];
            sum[i][2] = sum[i - 1][2];
            ++sum[i][num[i]];
        }
        for(int i = 1; i <= n; ++i) {
            if(num[i] == 1) {
                dpL[i][1] = dpL[i - 1][1] + 1;
                dpL[i][2] = max(dpL[i][1], dpL[i - 1][2]);
            } else {
                dpL[i][1] = dpL[i - 1][1];
                dpL[i][2] = max(dpL[i - 1][1], dpL[i - 1][2]) + 1;
            }
        }
        dpR[n + 1][1] = dp[n + 1][2] = 0;
        for(int i = n; i > 0; --i) {
            if(num[i] == 1) {
                dpR[i][1] = max(dpR[i + 1][1], dpR[i + 1][2]) + 1;
                dpR[i][2] = dpR[i + 1][2];
            } else {
                dpR[i][2] = dpR[i + 1][2] + 1;
                dpR[i][1] = max(dpR[i + 1][1], dpR[i][2]);
            }
        }
        for(int i = 1; i <= n; ++i) {
            dp[i - 1][1] = dp[i - 1][2] = 0;
            for(int j = i; j <= n; ++j) {
                if(num[j] == 1) {
                    dp[j][1] = max(dp[j - 1][1], dp[j - 1][2]) + 1;
                    dp[j][2] = dp[j - 1][2];
                } else {
                    dp[j][2] = dp[j - 1][2] + 1;
                    dp[j][1] = max(dp[j - 1][1], dp[j][2]);
                }
                ans = max(ans, dpL[i - 1][1] + dpR[j + 1][1] + sum[j][1] - sum[i - 1][1]);
                ans = max(ans, dpL[i - 1][2] + dpR[j + 1][2] + sum[j][2] - sum[i - 1][2]);
                ans = max(ans, dpL[i - 1][1] + dpR[j + 1][2] + dp[j][1]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}