23.8.15 杭电暑期多校9部分题解

1002 - Shortest path

题目大意

对于一个数 $x$，可以进行以下三种操作：

1.将 $x$ 变成 $2\ast x$

2.将 $x$ 变成 $3\ast x$

3.将 $x$ 变成 $x+1$

给定一个数 $n$，问最少操作几次才能将 $1$ 变成 $n$

解题思路

最开始想法是建图跑最短路，然后发现空间显然不够，换思路

可以倒过来考虑，最优操作必然是找不大于本身的最大的 $2$ 或 $3$ 的倍数除以 $2$ 或 $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$ 个人，每个人有 $a_i$ 个硬币，每次操作可以选择任意 $A,B$ 两个人，将 $A$ 的 $1$ 枚硬币给 $B$，如果这次操作后 $A$ 没有硬币，则 $A$ 退出游戏，问最后将所有硬币集中到一个人手上的期望操作次数

解题思路

先试试模拟，只有两个人的时候答案是 $a_1\ast a_2$，再推三个人，四个人，发现结果刚好是 ${\sum }_{i=1}^n{\sum }_{j=i+1}^n{a}_i\ast a_j$

听说题解讲了鞅的停时定理，咱也不会，但是其实不难发现每两个人之间的游戏其实是独立事件，也可以推出结论

注意卡亿下时间就好了

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;
}