1001 收集金币
题目链接
//dp[i][0]表示前i个事件都没有选择使用技能
//dp[i][1]表示前i个事件已经选择使用技能了
int dp[N][2];
void solve()
{
memset(dp, 0, sizeof dp);
int n; cin >> n;
for (int i = 1; i <= n; i ++ )
{
string op; int val;
cin >> op >> val;
if (op[0] == 'G')//对于get不管有没有使用技能， 金币数都要增加
{
dp[i][0] = dp[i - 1][0] + val;
dp[i][1] = dp[i - 1][1] + val;
}
else
{
//如果前i个事件都没有选择使用技能
dp[i][0] = max(dp[i - 1][0] - val, 0);
//前i-1个事件没有选择使用技能，但是当前选择使用
//前i-1个事件已经使用过技能，当前不可用
//比较两种情况哪一种金币数最多
dp[i][1] = max(dp[i - 1][0], max(dp[i - 1][1] - val, 0));
}
}
cout << max(dp[n][0], dp[n][1]) << "\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
IOS;
int T; cin >> T;
while (T -- )
{
solve();
}
return 0;
}
1002 使用技能
题目链接
本题是一个组合数学和期望问题
首先得知道期望如何来求，
期
望
=
所
有
情
况
的
伤
害
和
所
有
情
况
数
期望=\frac{所有情况的伤害和}{所有情况数}
期望=所有情况数所有情况的伤害和
所有情况不难求出，就是n个位置从m个中选，每一个位置有m中选法，那么就有
m
n
m^{n}
mn 次
关键就是求所有情况的伤害和
枚举每一种技能释放的次数x，n个技能栏有x个是这一种技能，即
C
n
x
C_{n}^{x}
Cnx，那么其他技能栏放的技能可能情况为
(
m
−
1
)
n
−
x
(m-1)^{n-x}
(m−1)n−x
根据题意这一种技能造成的伤害为
x
2
x^{2}
x2，而且选择每一种技能的概率是一样的，所以m种技能选择x次所造成的伤害就是
C
n
x
⋅
m
⋅
(
m
−
1
)
n
−
x
⋅
x
2
C_{n}^{x}\cdot m\cdot (m-1)^{n-x}\cdot x^{2}
Cnx⋅m⋅(m−1)n−x⋅x2
那么所有的伤害综合就是
∑
x
=
1
n
C
n
x
⋅
m
⋅
(
m
−
1
)
n
−
x
⋅
x
2
\sum_{x=1}^{n}C_{n}^{x}\cdot m\cdot (m-1)^{n-x}\cdot x^{2}
∑x=1nCnx⋅m⋅(m−1)n−x⋅x2
int n, m;
LL f[N], inf[N];
LL ksm(LL a, LL p)
{
LL res = 1;
while (p)
{
if (p & 1) res = res * a % mod;
p >>= 1;
a = a * a % mod;
}
return res;
}
void init()
{
f[0] = inf[0] = 1;
for (int i = 1; i <= N; i ++ )
f[i] = f[i - 1] * i % mod;
inf[N] = ksm(f[N], mod - 2);
for (int i = N - 1; i >= 1; i -- )
inf[i] = inf[i + 1] * (i + 1) % mod;
}
LL C(int a, int b)
{
return f[a] * inf[b] % mod * inf[a - b] % mod;
}
void solve()
{
scanf("%d%d", &n, &m);
LL ans = 0;
for (int i = 1; i <= n; i ++ )
ans = (ans + m * C(n, i) % mod * ksm(m - 1, n - i) % mod * i % mod * i % mod) % mod;
ans = ans * ksm(ksm(m, n), mod - 2) % mod;
cout << ans << "\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
int T; scanf("%d", &T);
while (T -- ) solve();
return 0;
}
1003 欢度佳节
题目链接
枚举
2
17
2^{17}
217种占领状态， 然后dfs判断是否是联通块
int val[18], cnt[18], n, ans, sum;
int g[6][6];
PII p[18];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
void dfs(int x, int y)
{
sum ++;
for (int i = 0; i < 4; i ++ )
{
int nx = dx[i] + x, ny = dy[i] + y;
if (nx < 1 || nx > 5 || ny < 1 || ny > 5 || g[nx][ny] == -1) continue;
g[nx][ny] = -1;
dfs(nx, ny);
}
}
void init()
{
p[0] = {1, 1}, p[1] = {1, 2}, p[2] = {1, 4}, p[3] = {1, 5};
p[4] = {2, 2}, p[5] = {2, 3}, p[6] = {2, 4}, p[7] = {3, 2};
p[8] = {3, 3}, p[9] = {3, 4}, p[10] = {4, 2}, p[11] = {4, 3};
p[12] = {4, 4}, p[13] = {5, 1}, p[14] = {5, 2}, p[15] = {5, 4}, p[16] = {5, 5};
}
void solve()
{
for (int i = 0; i < 17; i ++)
{
scanf("%d", &val[i]);
cnt[i] = (val[i] - 1) / 6 + 1;
}
scanf("%d", &n);
ans = 0;
for (int i = 0; i < 1 << 17; i ++ )
{
sum = 0;
bool flag = true;
if (!(i >> 13 & 1))
{
flag = false;
continue;
}
vector<int> v;
memset(g, -1, sizeof g);
for (int j = 0; j < 17; j ++ )
{
if (i >> j & 1)
{
g[p[j].fi][p[j].se] = j;
v.push_back(j);
}
}
if (flag)
{
g[p[13].fi][p[13].se] = -1;
dfs(p[13].fi, p[13].se);
if (sum == v.size())
{
int tmp = 0;
for (auto it : v)
tmp += cnt[it];
if (tmp <= n) ans = max(ans, sum);
}
}
}
printf("%d\n", ans);
}
int main()
{
init();
int T; scanf("%d", &T);
while (T -- ) solve();
return 0;
}
1005 闯关游戏
题目链接
初看是分组背包问题，但实际上是由限制的
每一关必须选择一个物品，否则就结束游戏
所以每次背包容量的下界就是前几关选择的过的物品容量
int dp[N];
void solve()
{
memset(dp, 0 , sizeof dp);
int n, h; scanf("%d%d", &n, &h);
int sum = 0, ans = 0;
bool f = false;
//每一关必须选一个，要么就结束
for (int i = 1; i <= n; i ++ )
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (f) continue;
int last = sum;
sum += min(a, c);
if (sum > h)
{
f = true;
continue;
}
for (int j = h; j >= sum; j -- )
{
bool flag = false;
if (j - a >= last)
{
dp[j] = dp[j - a] + b;
ans = max(ans, dp[j]);
flag = true;
}
if (j - c >= last)
{
if (!flag) dp[j] = dp[j - c] + d;
else dp[j] = max(dp[j], dp[j - c] + d);
ans = max(ans, dp[j]);
}
}
}
printf("%d\n", ans);
}
int main()
{
int T; scanf("%d", &T);
while (T -- ) solve();
return 0;
}
1010 小凯的书架
题目链接
题目说数据随机生成，直接暴力即可，暴力代码就不写了。如果数据不是随机生成的貌似要用主席树+二分（不会）。
