https://ac.nowcoder.com/acm/contest/72041#question
签到
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
int A, B, C, D;
cin >> A >> B >> C >> D;
if (a * A + b * B + c * C - d * D > e)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
贪心，很显然，我们应该尽可能将更大的魔法1用于更大的魔法2。
所以先将两个数组从大到小排序。
一个小细节是：如果当前直接使用魔法2就能击败，那么就直接使用魔法2，没必要先使用魔法1。以及如果当前魔法1是1，那么也没必要使用。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
int a[maxn], b[maxn];
void solve() {
int n, m, x;
cin >> n >> m >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
sort(a + 1, a + 1 + n, greater<int>());
sort(b + 1, b + 1 + n, greater<int>());
int cnt = 0, i = 1, j = 1;
while(j <= n) {
int f1 = a[i] * b[j];
int f2 = b[j];
if (f1 > f2 && x > f2) {
cnt += 2;
x -= f1;
i++;
j++;
} else {
cnt++;
x -= f2;
j++;
}
if (x <= 0)
break;
}
if (x <= 0)
cout << cnt << "\n";
else
cout << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(18);
solve();
return 0;
}
看见题面是Minecraft MITE直接肃然起敬。
根据题意很容易分析出，只有三种方案可以做出铜镐：
1、16个铜粒。
2、12个铜粒+4个银粒。
3、12个铜粒+4个金粒。
将三种方案的概率相加即可。
公式如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
//double PJIN[20], PYIN[20], PTONG[20];
double pow(double b, int e) {
if (e == 0)return 1;
if (e == 1)return b;
double res = pow(b, e / 2);
if (e % 2 == 0) {
return res * res;
}
else {
return res * res * b;
}
}
double Power(double base, int exponent) {
if (exponent == 0)return 1;
if (exponent == 1)return base;
if (exponent < 0) {
return pow(1 / base, -exponent);
}
else {
return pow(base, exponent);
}
}
void solve() {
double a, b, c;
cin >> a >> b >> c;
double pTong = a / 16;
double pYin = b / 16;
double pJin = c / 16;
double tongGao = Power(pTong, 12);
// 方案一：4铜粒（工作台） + 12铜粒（一个铜稿子）
double f1 = Power(pTong, 4) * tongGao;
// 方案二：4银粒（工作台) + 12
double f2 = Power(pYin, 4) * tongGao * 1820; // C(16, 4) = 1820
// 方案三：4金粒 + 12
double f3 = Power(pJin, 4) * tongGao * 1820;
cout << (f1 + f2 + f3) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(18);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
n <= 500，所以O(n^3)也是能过的。
考虑找出左端点为ch1，右端点为ch2，长度为k的子序列数量，假设有si == ch1，sj == ch2，那么[i, j]这段子串对于答案的贡献为C(j - i - 1, k - 2)。
因为这相当于在固定了si和sj的情况下，在中间j - i - 1个字符（[i + 1, j - 1]这个子串）中选择k - 2个字符。
我们可以考虑先预处理出答案，暴力枚举，第一层循环枚举左端点，第二层循环枚举右端点，第三层循环枚举子序列长度，统计出数量。对于组合数我们可以先用杨辉三角预处理出来。
详见代码和注释。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e2 + 10;
const int INF = 0x3fffffff;
const ll mod = 998244353;
ll c[maxn][maxn];
string s;
int n;
ll ans[300][maxn][maxn]; // 预处理答案，ans[ch1][ch2][k]代表在字符串s中左端点为ch1，右端点为ch2，长度为k的子序列的数量
void initC() {
for (int i = 0; i <= n; i++) {
c[i][i] = 1;
c[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
}
void init() {
// 用杨辉三角预处理组合数
initC();
// 预处理
for (int i = 0; i < n; i++) { // 枚举左端点
for (int j = i + 1; j < n; j++) { // 枚举右端点
for (int k = 2; k <= j - i + 1; k++) { // 枚举序列长度
char ch1 = s[i];
char ch2 = s[j];
// 当左端点为i右端点为j，能贡献出C(j - i - 1, k - 2)个长度为k的左端点si，左端点sj的子序列
ans[ch1][ch2][k] += c[j - i - 1][k - 2]; // 将贡献数量加到对应的答案记录
ans[ch1][ch2][k] %= mod;
}
}
}
}
void solve() {
cin >> n;
cin >> s;
// 预处理
init();
// 询问查询
int m;
cin >> m;
while (m--) {
char ch1, ch2;
cin >> ch1 >> ch2;
int len;
cin >> len;
cout << ans[ch1][ch2][len] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(18);
solve();
return 0;
}