到里面去看 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好吧，他叫你找一个number，有个数列，和也是n，最小公倍数也是n。 这个数列必须是他的因数集，且和是这个数。 废话！ 这个数列最好是他的质因数的次方的集，剩下的全是1！ 那只要判断这个number有没有至少两个质因数就行了！

不会

这一篇是算法的网3的下一篇。 观前须知： 1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。 2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。 —————————————————————————————————————————— 这是我们的网现在的样子： 我们接着上一篇提到的，来讲一讲旅游巴士的第二种做法。 喔喔喔喔喔喔喔。我有点恍然大悟了。 分层图本身可能比不是一定要把每个点都以在图上添加k个来实现的。（比如说P4568飞行路线） 它也可以是：一个点有k个状态。 而dis[i][j]就是表示第i个点的j个状态。 这是我上一篇写的： 它的第二维就是状态。虽然是n个点，但实际上是k*n个点的分层图。 哦。所以没有第二种做法。 原来如此。 好的，那我们看下一题吧。 陌路寻诗礼 唔。我好像没见过这种要求。好神奇啊。 这道题目的要求是：给出n（节点数）,m（边数）,k（边权取值范围）和m条边。 问：如何安排m条边的边权，使得从点1到其他城市的最短路径为1. 我的初步思路是跑BFS，然后在跑的过程中给边加边权。 那么如何赋值边权呢。 我不会。 啊啊啊啊。怎么构造啊。 想太久了没想出来又去看题解了。我觉得我好**。但关键是不看也做不出来。 怎么办啊。 那我多做一点最短路绿好了。我觉得只练十题太少了。练二十题好了。 牛的旅行 社交网络 道路选择 最长距离 黑暗城堡 (上面的这些是前面的十多题遗留的，下面的十题是新选择的） 团 图上交互题 car的旅行路线 最优贸易 灾后重建 房间最短路问题 跑路 Cleaning Shifts S 电话 采蘑菇 好的，题挑完了，我们接着看陌路寻诗礼。 好的，我看完题解了。 其实这个题解让我感觉很诡异：就是我觉得，这个思路似乎是不难想的，或者说理所应当的。但是同时我认为，这个做法像是从天上掉下来的一样。（也就是我当时在想题的时候，从来没有想过这个方面） 它居然是可以直接加的嘛……好震惊。 我再看完之后的感觉是很奇怪，因为在我的大脑里潜意识认为这种做法行不通的。（如果有大佬知道这是怎么回事，欢迎指点qwq）。 而且，这道题目的代码实现也非常非常地简单！ 只要在原有的模板上做一点点更改就好了： 我不会告诉你我调了半个小时就因为 并且，可喜可贺的是在我调错的时候，我重新搞懂了这个思路，我明天来分析它！ 好吧。我突然奋发图强了。所以我今天晚上就来分析它。 这个题解的楼主给你的感觉是：四两拨千斤。 但是实际上它很复杂。接下来我会从两个角度去分析： 一.文字本身 这句话看似普通又平常，但是想到它其实并不容易哦。 当你一开始做的时候，需要给每条边去赋值。你可能就得想：欸，我是要赋值最大值还是要赋值最小值，或者是中间值？（甚至如果你想的偏一点，你甚至可能根本想不出要赋值，可能回去想一些乱七八糟的方法，构造题本身就很容易很容易跑偏） 有一个突破口可以（更容易）想到它： 当k只能等于1，那么就直接赋值为1，然后融入一部分最短路计数的代码，去看有没有相同值。 这部分做完之后，你再去看接下来怎么做，就会更容易联想到。 接下来的部分我会从代码的角度去分析： 我上面的那版代码，是我已经更具这份题解提供的代码修改过的。 我现在将两份代码（我原来的和我现在的）进行对比。 现在的： 原来的： 接下来，我们一处对比一处对比地分析一下： 1.我将len变量删除了 并且把要加的len改成了"+1"。 这是因为，在dijkstra中，每条边能够对它所连接的点进行更新的机会永远都只有一次。 (因为每个点在Dijkstra里面也只会被遍历一次） 而第一次被遍历时，这条边的初始值也只能是1。 2.直接填写2 这边的逻辑和上面的逻辑是一样的。直接增加1就好了。 虽然我前面那些都写得很简单很轻松，但是其实头脑风暴了很久。 所以在这里得建议是：大家做完一道题之后可以去看看题解写的代码。有一些代码写的简短漂亮，那么它背后的思路可能也更好。 我当时发现后面可以直接填2得时候我都惊呆了。好妙得构造啊。 这道题我一直没有注意道德是：在dijkstra中，每条边只会进行一次遍历（单向边哦）。 不过这个也是只在模板上进行更改，并没有与算法进行美妙的联动。但是思想上有提升。 所以网没办法更新qwq。 好吧，我们看下一题吧。 采蘑菇 五一新学了最小生成树。八级要考。先过一点最小生成树。 二.最小生成树 例题：买礼物 先说做法，再说想法。 做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。 由于在熟悉，所以prim和kruskal都会拿出来弄一遍。 prim: 在写prim的时候，我发现了一点比较有意思的事情。 我将vis[k]=1改动成了： 如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。 当时居然没注意，随意改了一下酿成大错qwq。 接下来是kruskal的版本。 分析： 1.如何分析这道题目需要用到最小生成树 分析这个问题，先需要想到，这是一道和图论相关的问题。 如何将一个实际问题转化成为图。或者说如何识别有“图”。 它有点之间的关系。点i和点j之间的联系就是k[i][j]。 那么这个联系就可以变成边。 想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。 然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。 最后分析复杂度：一共有n*n条边。大约2e5。可以支撑的起O(mlogn)的时间复杂度。 2.使用prim更好还是使用kruskal更好。 稠密图。推荐使用prim。 营救 找最小生成树。再计算出点s到点t的最大值即可。 天空 灌溉

下面面的用的枚举，上面的用的递归，体会一下（没法用二分）

#include <iostream> using namespace std; int main(){ int n; cin>>n; if (n1) cout<<"AC"; if (n2) cout<<"WA"; if (n3) cout<<"TLE"; if (n4) cout<<"RE"; if (n5) cout<<"MLE"; if (n6) cout<<"PE"; if (n==7) cout<<"OLE"; }

很简单也很难

前置知识点：倍增lca 树上倍增 最小为生成树 如果你对此并不了解，请移步： 1.倍增lca短篇讲解 （这篇帖子是我专门为了次小生成树写的，所以可能会合适一点） 2.最小生成树一篇通（未完成） （虽然没有完成，但也只是某一道例题没有弄完。基础的东西都已经弄好了。） —————————————————————————————————————————— 然后就可以开始我们的旅行了。 （先说做法。不过这个做法是我从洛谷书上学的会相似。后面就全部都是我自己的思考） 首先，它的名字叫次小生成树。所以自然而然，我们会去思考它和最小生成树之间是否有关系。 其次，它是严格次小生成树。是排第二的，所以我们可以进行一些猜测。比如：它是否是在最小生成树的基础上进行修改而成的。（比如：对几条边进行替换） 不过事实上，我们可以证明：次小生成树是在最小生成树上的基础上替换一条边建成的。 以下是证明过程： 采用反证法。我们可以假设某颗”严格次小生成树“与最小生成树有k(k≥2k\ge2k≥2)条。断开这些边，发现原树被分成了k+1k+1k+1个连通块。选择其中的kkk个，并用最小生成树的边将它们变成一个连通块。再将最后一个点和这个连通块用次小生成树的边连在一起。 发现此时，这颗新的树的边权之和小于”严格次小生成树“。 以此我们证明出：次小生成树是在最小生成树上的基础上替换一条边建成的。 大致的做法应该也差不多出来了。 我们先处理出最小生成树。枚举每一条不在最小生成树中的边，将它们依次加入最小生成树。此时，最小生成树中会形成一个环。我们在环中（寻找除了这条加入的边）其它边中边权最大的边，然后把它去掉。算树的边权之和。 这样算完后，最小的那个数就是次小生成树。 值得一提的是，如果这个环中最后筛选出来的边的边权与新加入的这条边的边权相等，那么就去找次大。（注意有可能存在次大值=最大值的情况，即不存在次小生成树）（不过这条边没有不代表其他便没有） 注意到x≤105x\le10^5x≤105如果是普通枚举的话会超时。用在树中比较常见的优化技巧：树上倍增。 用树上倍增预处理出每一个点往上走2j2^j2j个点的路径中边权最大和次大。 m≤3∗105m\le3*10^5m≤3∗105适合用kruskal。 接下来就是代码分析环节： 这个代码有点点复杂。不过大多都是重复和模板的拼凑。 我们一点点分析。 1.输入 注意到需要处理自环。注意到普通的最小生成树不需要处理自环。 why。 因为自环的边肯定不会出现在最小生成树中。所以意味着后期遍历边会轮到它。 那么树中就没有环了，操作也进行不了。 开局把它请出去是比较明智的选择。 不过这个点有点刁钻了。如何想到? 1.被相似题目坑过一把 2.仔细读题 2.kruskal 额这个没什么好分析的。不过注意到有加边操作。 因为后期的倍增预处理是在最小生成树中去做的。所以需要提前把最小生成树建出来。 3.树上倍增初始化 额。这个就有点麻烦了。 因为lca是前置知识点，所以这边我主要是想提对于最大值和次大值的预处理。 mx[x][i]mx[x][i]mx[x][i]的定义是：在第xxx个点到这个点往上2j2^j2j个点的路径中边权最大者。 mx2[x][i]mx2[x][i]mx2[x][i]的定义是：在第xxx个点到这个点往上2j2^j2j个点的路径中边权次大者。 接下来我来分析一下判断： 这个判断的意思是:如果点xxx往上2i−12^{i-1}2i−1个点 到 点xxx往上2i2^i2i个点 的路径中（即红色路段）中的边权最大值 >>> 点xxx到点xxx往上2i−12^{i-1}2i−1个点的路径中（即绿色路段）中的边权最大值 这句话的意思是：将点xxx到点xxx往上2i2^i2i个点的路径中（即红色+绿色路段）中的边权最大值 赋值为 点xxx往上2i−12^{i-1}2i−1个点 到 点xxx往上2i2^i2i个点 的路径中（即红色路段）中的边权最大值 这句话的意思是什么我就不解释了。感觉前两行的解释过于冗长了。 我主要想解释一下原理。理论上而言，能够构成mx2[x][i]mx2[x][i]mx2[x][i]的应该只有红色段和绿色段的次大值。 但是由于绿色路段的最大值并不是（红+绿）路段的最大值。所以次大值就可以在绿色最大值和红色次大值之间选择。 后面两个大同小异。 4.寻找次大生成树 1. 我们找l的目的是在以它为最小深度点的环中去寻找边权最大值和次大值。 后面for循环中的内容和刚刚分析的判断本质相同，所以我要偷懒。 不过要注意的是，最后的结果需要用 long long存储。 好了。差不多分析完了。下一篇学习笔记见。

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; while (n--) { unsigned long long s; cin >> s; vector<unsigned long long> powers; for (int i = 0; i < 64; ++i) { if (s >> i & 1) { powers.push_back(1ULL << i); } } int cnt = powers.size(); if (cnt == 0 || cnt > 4) { cout << "-1" << endl; } else { for (auto x : powers) { cout << x << " "; } cout << endl; } } return 0; }

耶！

#include <bits/stdc++.h> using namespace std; int a[110],m[110],g[110]; bool cmp(int x,int y){ return x>y; } int main(){ int n; cin>>n; int ms=0,gs=0; for(int i=0;i<n;i++){ cin>>a[i]; if(a[i]>0){ m[ms]=a[i]; ms++; }

错了一个样例，逻辑分析了，AI求助了，找不到反例。有大佬来给指导一下吗？ 已找到反例： 5 1 1 3 3 4 错误原因：应该优先使用比need 编号小的 以及 重复出现的卷轴。

只输出数字

提示：这题变量要用char类型

康拓表？

明明这题比a1048简单

#include<bits/stdc++.h> main(){printf("%s","Hello World");} //我哭死，你再给1/4m呢？

#include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; cout<<a+b; return 0; }

把int改成string试试，对了的话能点个赞吗？