@Dmaxiya
2018-08-17T10:18:30.000000Z
字数 4089
阅读 906
Codeforces
Contests 链接:Codeforces Round #462 (Div. 2)
过题数:3
排名:462/9658
有一个长度为 的序列 , 有一个长度为 的序列 , 从自己的序列中除掉一个数字, 从 个数字的 序列中选择一个数字,再从自己序列中选择一个数字,将这两个数字相乘,就是得到的结果。现在 想让最终结果最小,而 想让最终结果最大,问如果两人都采取最优策略,最终的结果会是多少。
第一行为两个整数 ,第二行为 个整数 ,第三行为 个整数 ,其中 。
输出最终结果。
输入 | 输出 | 提示 |
---|---|---|
2 2 20 18 2 14 |
252 | 将会删去 ,而 将会选择 和 。 |
5 3 -1 0 1 2 3 -1 0 1 |
2 | 将会删去 , 将会选择 和 。 |
暴力枚举所有情况,对于 删除的每一个数字,枚举 所有可能的选择中的最大值,输出这些最大值中的最小值。
#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;
}
给定数字 ,构造一个不超过 的正整数 ,使得所有数位中的圈的个数和等于
一个整数 。
输出满足条件的整数 ,如果不存在满足条件的正整数,则输出 。
输入 | 输出 |
---|---|
2 | 462 |
6 | 8080 |
如果 大于 ,输出 ,否则输出 个 后,再输出 个一个环的数字(、、)。
#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;
}
给定一个长度为 的序列 ,序列中所有的数字只可能是 或者 ,现在可以从序列中选取连续的一段数字,将这段数字左右镜像颠倒,求这样颠倒之后最大的最长非递减子序列长度。
第一行为一个整数 ,第二行为 个整数 。
输出所求答案。
输入 | 输出 | 提示 |
---|---|---|
4 1 2 1 2 |
4 | 将区间 内所有的数字颠倒之后,新的序列为 ,最长非递减子序列的 长度为 。 |
10 1 1 2 2 2 1 1 2 2 1 |
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
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;
}