前言
只做了 A、B、C 三题。= =，D 的 dp 没写出来，贪了好久。
A. Bad Triangle
题目大意
在给定 (n) 个数里选择出三个数，使得其不能组成三角形
分析
三角形的组成条件为任意两边和大于第三边。不妨把 (n) 个数按照升序排列（题目默认升序），然后取前面最小的两个为两个边，计算它们的和。再从第三个开始找，找到大于等于和的边就是答案。找不到就输出 (-1) 。
代码
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
using namespace std;
int arr[maxn];
int main(void){
#ifdef ljxtt
freopen("data.in", "r", stdin);
#endif
int T; scanf("%d", &T);
while(T--){
int n; scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
int sum = arr[0] + arr[1];
int inx = -1;
for(int i = 2; i < n; i++){
if(arr[i] >= sum){
inx = i;
break;
}
}
if(inx == -1)
puts("-1");
else
printf("1 2 %d
", inx + 1);
}
return 0;
}
B. Substring Removal Game
题目大意
A 和 B两个人玩游戏，A先行。
游戏规则为：给一段 01 串，每次操作都可以将一段连续相同的字符去掉，所得到的分数为去掉１的个数。当字符串为空时停止游戏。
A、B两人都按照对自己最优的策略走，问A能得到的最大的分数是多少。
分析
显然，去掉一段相同的 0 并没有什么卵用。所以，贪心地取连续最长的 1 即可。
代码
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
using namespace std;
char s[maxn];
vector<int> arr;
int main(void){
#ifdef ljxtt
freopen("data.in", "r", stdin);
#endif
int T; scanf("%d", &T);
while(T--){
scanf("%s", s);
int len = strlen(s), cnt = 0;
for(int i = 0; i < len; i++){
if(s[i] == '1'){
cnt++;
}else{
if(cnt != 0) arr.push_back(cnt);
cnt = 0;
}
}
if(cnt != 0) arr.push_back(cnt);
sort(arr.begin(), arr.end(), greater<int> ());
int ans = 0;
for(int i = 0; i < arr.size(); i += 2) ans += arr[i];
printf("%d
", ans);
arr.clear();
}
return 0;
}
C. Good Subarrays
题目大意
给定一个序列，询问有多少个区间满足：
[sum_{i = l}^{r}a_i = r - l + 1
]
分析
用前缀和表示上式为：
[egin{aligned}
S(r) - S(l - 1) &= r - l + 1 \
S(r) - r &= S(l - 1) - (l - 1)\
f(r) &= f(l - 1)
end{aligned}
]
其中 (f(x) = S(x) - x)，且 (f(0) = 0)。
所以，也就是在所有的 (f(x)) 里任意取出两个相同的数字，询问方案数。
统计一下相同数字的个数，用组合数算一下 (C_n^2) 就行了。
代码
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
using namespace std;
ll arr[maxn];
map<ll, int> ma;
int main(void){
#ifdef ljxtt
freopen("data.in", "r", stdin);
#endif
int T; scanf("%d", &T);
while(T--){
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%1lld", &arr[i]);
for(int i = 1; i <= n; i++) arr[i] += arr[i - 1];
for(int i = 1; i <= n; i++) arr[i] -= i;
for(int i = 0; i <= n; i++) ma[arr[i]]++;
ll ans = 0;
for(auto it: ma){
if(it.second > 1) ans += 1ll * it.second * (it.second - 1) / 2;
}
printf("%lld
", ans);
ma.clear();
}
return 0;
}
D. Colored Rectangles
题目大意
给定 R、G、B对的红色、绿色、蓝色的木棒，对应颜色的第 i 对的长度为 ri，gi，bi。你可以进行如下操作：
在两种不同的颜色里各选出一对，使得它们组成一个长方形，并将矩形的面积加入到答案里。
题目要求使得最后的答案最大。
分析
这种题目要么贪心，要么dp。
很显然有个贪心的想法，就是把三种木棒混合在一起，按长度排序。然后从大到小枚举木棍，再在剩下的木棍里选出颜色不同但最大的木棍组成矩形，加入到答案里。枚举一遍就是答案。但这样有一个问题就是下面这样一个样例：
1 1 2
1
1
1 1
上面这个样例就有可能使得 R 和 G 配对，然后剩下的两个 B 没办法配对。最优的答案是 R 和 B 配对，G 和 B 配对。所以上面这个贪心不成立。
所以我们考虑一下dp。先把三种不同的木棍按长度降序排列，定义 (dp[i][j][k]) 为 R、G、B分别用了 i，j，k 个木棍所取得的最大答案，那么就有转移方程为：
[egin{array}
\
dp[i][j][k] = max(&dp[i - 1][j - 1][k] + R[i] imes G[i], \ &dp[i - 1][j][k - 1] + R[i] imes B[i], \&dp[i][j - 1][k - 1] + G[i] imes B[i])
end{array}
]
初值为 (dp[0][0][0] = 0) 。
代码
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 2e2 + 7;
using namespace std;
ll dp[maxn][maxn][maxn];
int arr[3][maxn];
int main(void){
#ifdef ljxtt
freopen("data.in", "r", stdin);
#endif
int num[3]; for(int i = 0; i < 3; i++) scanf("%d", &num[i]);
for(int i = 0; i < 3; i++){
for(int j = 0; j < num[i]; j++)
scanf("%d", &arr[i][j]);
sort(arr[i], arr[i] + num[i], greater<int> ());
}
ll ans = 0;
for(int i = 0; i <= num[0]; i++)
for(int j = 0; j <= num[1]; j++)
for(int k = 0; k <= num[2]; k++){
dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + 1ll * arr[0][i] * arr[1][j]);
dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + 1ll * arr[0][i] * arr[2][k]);
dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + 1ll * arr[1][j] * arr[2][k]);
ans = max(ans, dp[i][j][k]);
}
printf("%lld
", ans);
return 0;
}