Acm

作者：Eriktse 简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……） 浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1147.htmlA. Bits Reverse题目链接：https://codeforces.com/gym/102823/problem/D 题意给定两个数字x和y，当初有一种操作：将y的二进制数的间断三位进行翻转。问起码操作多少次能够使得x = y，或输入-1示意无奈使得x = y。 剖析因为每次固定选间断三位进行翻转，咱们能够想一下间断三位翻转的一些性质。 首先两头这个数字必定是不变的，而后两边的数字swap一下。 也就是每次会抉择间隔为2的两个数字进行一次替换，那么如果某个1在奇数位上，替换后仍然在奇数位上，如果在偶数位上，替换后仍然在偶数位上。 如下图，红色区域的二进制数和蓝色区域的二进制数是互相独立的。 所以咱们能够进行奇偶分类的探讨，求出在奇数位上所需的操作次数，而后再求在偶数位上所需的操作次数即可。 咱们能够发现，如果要使得操作后x = y，那么对于奇数位（即上图中的蓝色区域），y最高位的1肯定对应x最高位的1，以此类推。而在奇数位上挪动一格须要的操作次数是1次。 具体看下图的对应关系： 代码#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 105;int a[N], b[N], pa, pb;int kase;int getabs(int x){return x < 0 ? -x : x;}void solve(){ cout << "Case " << ++ kase << ": "; int x, y;cin >> x >> y; pa = pb = 0; int ans = 0; for(int i = 0;i < 64; i += 2) { if(x >> i & 1)a[++ pa] = i; if(y >> i & 1)b[++ pb] = i; } if(pa != pb) { cout << -1 << '\n'; return; } for(int i = 1;i <= pa; ++ i)ans += getabs(a[i] - b[i]) / 2; pa = pb = 0; for(int i = 1;i < 64; i += 2) { if(x >> i & 1)a[++ pa] = i; if(y >> i & 1)b[++ pb] = i; } if(pa != pb) { cout << -1 << '\n'; return; } for(int i = 1;i <= pa; ++ i)ans += getabs(a[i] - b[i]) / 2; cout << ans << '\n';}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }B. Empty Squares题目链接：https://codeforces.com/gym/104252/problem/E ...

DAY7共2题： 约数个数的和（和式变换，整除分块）[HAOI2011]向量（扩大欧几里得剖析）难度适中。 作者：Eriktse 简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……） 原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1098.html约数个数的和题目传送门：https://ac.nowcoder.com/acm/problem/14682 剖析题意咱们能够晓得答案表达式如下： $$ans=\sum_{i=1}^{n}\sum_{d|i}1$$ 其中 $d|i$ 示意d能够整除i，这个柿子的意思是枚举每一个i，而后枚举i的所有约数，找到一个约数，就把答案+1。然而咱们发现枚举约数是一个不太不便的事儿，咱们能够思考变换求和的指标。 $$ans=\sum_{i=1}^{n}\sum_{d=1}^{n}[d|i]$$ 其中 [expression] 是一个布尔函数，当中括号外面的表达式为真时后果为1，反之为0。然而这样的柿子没有实质的扭转，咱们能够替换求和秩序。 $$ans=\sum_{d=1}^{n}\sum_{i=1}^{n}[d|i]$$ 当初咱们能够发现除了d的枚举这一层，剩下的的局部能够进行整除分块，它表白的含意是在d曾经给定的状况下，在[1, n]中有多少个d的倍数。 所以再次变换： $$ans = \sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor$$ 复杂度为$O(\sqrt{n})$。 对于整除分块的材料：https://oi-wiki.org/math/number-theory/sqrt-decomposition/ #include <bits/stdc++.h>#define int long longusing namespace std;signed main(){ int n;scanf("%lld", &n); int ans = 0; for(int l = 1, r;l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (r - l + 1); } printf("%lld\n", ans); return 0;}[HAOI2011]向量题目传送门：https://ac.nowcoder.com/acm/problem/19985 ...

DAY3共2题： 游览tokitsukaze and Soldier 作者：Eriktse 简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……） 原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1093.html游览题目传送门：https://ac.nowcoder.com/acm/problem/15748 该题次要考查对树的了解，以及简略的树上dp和贪婪算法。 咱们将会住的节点标记为1，其余不住的节点标记为0。 咱们能够发现，根节点（s）是肯定会标记为1的，那么剩下的节点该怎么调配能够使得标记为1的节点数最多呢？ 当咱们在某个点x标记时，咱们能够发现它的父亲、儿子们都不能再被标记了。然而点x的兄弟却不受影响，接下来考虑一下哪些节点的兄弟多呢？应该是叶子节点。 所以咱们能够想到首先将根节点和叶子结点全副都标记为1，而后遍历整棵树，如果某个点的父亲和儿子们都没被标记，那么他也能够被标记为1。 留神思考非凡状况，比方只有一个点的树，只有两个点的树....#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 5e5 + 9, inf = 8e18;bitset<maxn> sel;vector<int> g[maxn];int n, s;void dfs(int x, int pre){ //如果到了叶子节点，就间接标记并返回 //这里sel[x] = !sel[pre]是思考到叶子的深度可能为2（即叶子的父亲就是根） //此时根肯定被标记，那么叶子就不能被标记 //如果是个别状况，那么父亲必定不会被标记（因为父亲的标记须要儿子解决实现之后再决定） //本人就打上标记 if(g[x].size() == 1 and x != s)return sel[x] = !sel[pre], void(); bool tag = true;//tag == true示意以后点能够被标记 if(x == s)sel[x] = true;//根肯定被标记 else if(sel[pre])tag = false;//如果父亲被标记了，那么以后点肯定不能被标记 //看看儿子们是否被标记 for(auto &y : g[x]) { if(y == pre)continue; dfs(y, x); if(sel[y])tag = false; } sel[x] = tag;}signed main(){ scanf("%lld %lld", &n, &s); for(int i = 1;i < n; ++ i) { int x, y;scanf("%lld %lld", &x, &y); g[x].push_back(y), g[y].push_back(x); } dfs(s, 0); int ans = 0; for(int i = 1;i <= n; ++ i) if(sel[i])ans ++;//统计标记的点的个数 printf("%lld\n", ans); return 0;}做完这道题，咱们能够总结一点点对于树上dp这一类题的教训技巧： ...

较量传送门：https://ac.nowcoder.com/acm/contest/52441 感觉整体难度有点偏大。 作者：Eriktse 简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……） 集体博客：www.eriktse.comA-蛋挞签到题。 只需比拟a / b和a % b的大小即可。留神开longlong。 #include <bits/stdc++.h>#define int long longusing namespace std;signed main(){ int a, b;scanf("%lld %lld", &a, &b); if(a / b < a % b)printf("niuniu eats more than others"); else if(a / b > a % b)printf("niuniu eats less than others"); else printf("same"); return 0;}B-玩具排序贪婪。 因为咱们要将n个玩具全副买下，所以咱们免单的玩具价格越高越好，咱们将整个数组排升序后从后往前两个两个拿，且只付更高价格的玩具的钱。 #include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e6 + 9;int a[maxn];signed main(){ int n;scanf("%lld", &n); for(int i = 1;i <= n; ++ i)scanf("%lld", a + i); sort(a + 1,a + 1 + n); int ans = 0; for(int i = n;i >= 1; -- i) { ans += a[i]; i --; } printf("%lld\n", ans); return 0;}C-开题程序dfs。 ...

DAY2共三题： 较量（概率）数学考试（前缀和与思维）简略瞎搞题（dp）视频解说：https://www.bilibili.com/video/BV1hP411o7RD/ 作者：Eriktse 简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……） 集体博客：www.eriktse.com较量tag: 概率传送门：https://ac.nowcoder.com/acm/problem/14734 咱们设对于每一道题： 事件A：本人做对了事件B：听右边的，做对了事件C：听左边的，做对了三个事件的概率都曾经给出了，别离是$P(A), P(B), P(C)$。 设事件Y：该题做对了 咱们能够晓得事件$Y=A \cup B \cup C$，如果要正向求解$Y$是有肯定难度的，因为这里的$Y$实际上由7个最小项形成，而事件$\overline{Y}$仅有一个最小项形成（这里就不开展说了）。 容易失去表达式： $$P(Y) = 1 - (1-P(A))(1-P(B))(1-P(C))$$ 而后咱们能够枚举所有的序列，而后算一下以后这个情景对答案的奉献。 枚举序列能够用二进制数枚举，也能够用dfs，用dfs的话有个益处就是能够剪枝。 二进制枚举可能常数小点。 #include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 20;double a[maxn], b[maxn], c[maxn];double ans[maxn];double getp(int k){ return max(0.0, 1.0 - (1 - a[k]) * (1 - b[k]) * (1 - c[k]));}void dfs(int dep, int cnt, double p){ if(p == 0)return; if(dep == 13) { ans[cnt] += p; return; } //没对第i题 dfs(dep + 1, cnt, p * (1.0 - getp(dep))); //对了第i题 dfs(dep + 1, cnt + 1, p * getp(dep));}signed main(){ for(int i = 1;i <= 12; ++ i)scanf("%lf", a + i); for(int i = 1;i <= 12; ++ i)scanf("%lf", b + i); for(int i = 1;i <= 12; ++ i)scanf("%lf", c + i); //for(int i = 1;i <= 12; ++ i)printf("p[%lld] = %.2lf\n", i, getp(i)); dfs(1, 0, 1); for(int i = 0;i <= 12; ++ i)printf("%.6f\n", ans[i]); return 0;}数学考试tag: 前缀和，思维传送门：https://ac.nowcoder.com/acm/problem/15553 ...