A 神奇天平 一道热身题， 每次把物品尽可能平均的分成 m+1m+1m+1 堆， 把其中 mmm​ 堆放到天平上，如果平衡，重球在不在天平的那一堆里，否则在最重的那一堆里。所以最劣情况下每次 nnn 至少被缩小为 ⌈nm+1⌉\lceil\frac{n}{m+1}\rceil⌈m+1n​⌉ code B 魔法学院(easy version) 裸的线段树题，题意实际上是区间取 maxmaxmax​ , 最后求区间和, 用线段树可以 O((n+m)log⁡n)O((n + m) \log n)O((n+m)logn)​​ 解决. code C 魔法学院(hard version) 数据加强了，刚...

所有点对最短路径问题(S2oj337) 标签： 线性筛，欧拉函数 对于 gcdgcdgcd 不为 111 的点对，距离显然为 111 否则考虑寻找过渡点。这里设 pxp_xpx​ 表示 xxx 的最小质因子，可以通过线性筛得到 只有一个过渡点(距离为 222）： ​ 那这个过渡点和两点的 gcdgcdgcd 都不为 111，显然 pxpyp_xp_ypx​py​ 是 xxx 和 yyy 之间的最小过渡点， 所以两点距离为 222 当且仅当 pxpy≤n∧gcd⁡(x,y)=1p_xp_y \leq n \land \gcd(x,y) = 1px​py​≤n∧gcd(x,y)=1 有两个...

思路： 因为每个数都是k的正整数次幂，所以可以直接以正整数次幂的形式存起来，是k的几次幂就存几，然后根据，求最大的指数和，最后求就行了. Code: #include <iostream> #include <cstdio> #include <map> #define ll long long using namespace std; const int N = 2020; map<ll, ll> sq; ll n, m, k, a[N][N], mod, ans; ll qpow(ll a, ll b) { ll res = ...

思路： 毫无疑问，先把小的数加起来再依次乘最优，证明： Code: #include <iostream> #include <cstdio> #include <algorithm> #define ll long long using namespace std; const ll mod = 998244353; const int N = 5e5 + 10; ll a[N], n; ll ans; int main() { scanf("%lld", &n); for (int i = 1; i <= n...

牛客练习赛65题解： A题: 思路： 毫无疑问，先把小的数加起来再依次乘最优，证明： Code: #include <iostream> #include <cstdio> #include <algorithm> #define ll long long using namespace std; const ll mod = 998244353; const int N = 5e5 + 10; ll a[N], n; ll ans; int main() { scanf("%lld", &n); for (int i...