Sasha and the Casino
算法本质
思维
题目大意
玩家初始有a个硬币，可以选择进行任意回合游戏，每回合游戏规则如下：
- 玩家选择
y个硬币作为门票 - 主办方直接决定玩家的胜负，如果玩家胜利会获得
ky个硬币，反之什么得不到
同时也有一条对主办方的限制：无法使得玩家连续失败x+1次。
已知k x a，询问玩家是否可以赢得$100^{100^{100}}$个硬币。
思路推演
联想到“倍投法”。显然这个游戏规则十分适合倍投，因为在x+1回合里必然有胜利。但不同的是，玩家胜利获得的硬币数是ky而不一定是2y。这引导我们深入一些思考倍投的内涵。
显然我们以每次胜利作为一个阶段，我们仅需保证每个阶段都不亏钱即可——保证每次的收益都可以覆盖之前的损失，同时保证投的钱最少即可。
检查复杂度，可行。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
int k, x, a;
cin>>k>>x>>a;
int pre=0;
flag = 1;
for (int i=1; i<=x+1; i++)
{
int y = (pre + k-2) / (k-1);
y += (pre % (k-1) == 0);
pre += y;
if (pre > a)
{
flag = 0;
break;
}
}
cout<<(flag?"YES":"NO")<<endl;
return;
}Sasha and a Walk in the City
算法本质
思维、dp
题目大意
给定树结构，节点初始全白，玩家可以给任意节点涂黑，如果涂色后树结构满足任意一条简单路径上黑点数目<=2则称之为美丽。
输出玩家可以创造的美丽树结构数目。
思路推演
很显然的树形dp题目，所以从树形dp的角度去思考，可以缩小方法。
如果要记录中途点u状态，我们仅能记录点u到其子树的任意一条简单路径上的最多黑点数目。
构建dp[u][i]表示：点u到其子树的任意一条简单路径上的最多黑点数目为i个的方法数。
dp[u][0]显然只能为1。dp[u][1]，考虑两种情况：u是黑色和u非黑色。dp[u][2]，考虑两种情况：u是黑色和u非黑色。
具体的公式看代码
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void dfs(int u, int fr, vector<vector<int>> &g, vector<int> &dp1, vector<int> &dp2)
{
for (int v:g[u])
{
if (v==fr) continue;
dfs(v, u, g, dp1, dp2);
dp1[u] = dp1[u] * (dp1[v]+1) % mod;
dp2[u] += dp1[v] + dp2[v];
dp2[u] %= mod;
}
}
inline void solve()
{
cin>>n;
vector<vector<int>> g(n+5);
vector<int> dp1(n+5, 1), dp2(n+5);
for (int i=1; i<n; i++)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0, g, dp1, dp2);
int ans = 1 + dp1[1] + dp2[1];
ans %= mod;
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)