医院网站HTML5,情人节网站源码下载,网络企业网站建设方案,网站的收录率1002 - Shortest path
题目大意
对于一个数 x x x#xff0c;可以进行以下三种操作#xff1a;
1.将 x x x 变成 2 ∗ x 2*x 2∗x
2.将 x x x 变成 3 ∗ x 3*x 3∗x
3.将 x x x 变成 x 1 x1 x1
给定一个数 n n n#xff0c;问最少操作几次才能将 1 1 1 变成…1002 - Shortest path
题目大意
对于一个数 x x x可以进行以下三种操作
1.将 x x x 变成 2 ∗ x 2*x 2∗x
2.将 x x x 变成 3 ∗ x 3*x 3∗x
3.将 x x x 变成 x 1 x1 x1
给定一个数 n n n问最少操作几次才能将 1 1 1 变成 n n n
解题思路
最开始想法是建图跑最短路然后发现空间显然不够换思路
可以倒过来考虑最优操作必然是找不大于本身的最大的 2 2 2 或 3 3 3 的倍数除以 2 2 2 或 3 3 3
很容易可以想到暴力搜索但是会超时考虑记忆化优化就可以了
code
#include bits/stdc.h
using namespace std;
int t, ans;
long long n;
unordered_map long long, int v;
int dfs(long long x) {if (v.find(x) ! v.end()) return v[x];return v[x] min(dfs(x / 2) x % 2, dfs(x / 3) x % 3) 1;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cin t;v[1] 0;v[2] v[3] 1;while (t --) {cin n;cout dfs(n) \n;}return 0;
}1008 - Coins
题目大意
有 n n n 个人每个人有 a i a_i ai 个硬币每次操作可以选择任意 A , B A,\space B A, B 两个人将 A A A 的 1 1 1 枚硬币给 B B B如果这次操作后 A A A 没有硬币则 A A A 退出游戏问最后将所有硬币集中到一个人手上的期望操作次数
解题思路
先试试模拟只有两个人的时候答案是 a 1 ∗ a 2 a_1*a_2 a1∗a2再推三个人四个人发现结果刚好是 ∑ i 1 n ∑ j i 1 n a i ∗ a j \sum_{i1}^n\sum_{ji1}^na_i*a_j ∑i1n∑ji1nai∗aj
听说题解讲了鞅的停时定理咱也不会但是其实不难发现每两个人之间的游戏其实是独立事件也可以推出结论
注意卡亿下时间就好了
code
#include bits/stdc.h
using namespace std;
int t, n, a;
__int128 ans, sum;
inline void write(__int128 x) {if (x 9) write(x / 10);cout (char)(x % 10 0);
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cin t;while (t --) {cin n; sum ans 0;for (int i 1; i n; i)cin a, ans sum * a, sum a;write(ans); cout \n;}return 0;
}
