我们可以先自然想到一个朴素的做法，就是直接通过枚举n个点所以的序列，然后求出每条路的权值和，最后取最小的即可。但是，我们看一下数据范围，发现如果这样算的话时间复杂度为n（n!）。所以我们要想一下用什么办法进行优化，我们发现，对于最多n个点的状态，我们可以用一个二进制进行表示，比如，我们遍历了1,3,4这三个点，那么他们的状态就是1011,去他对应的十进制进行存储即可，我们发现最大也就是2^20-1,这是可以接受的，时间复杂度为O(n^2*2^n)。我们可以用状态压缩的方法进行存储，比如，我们此时要求遍历到了第j个点的时候，对应的状态i的最小值，我们这里用f[i][j]进行表示，我们假设这中间的...

我们可以发现，如果将a和b直接进行相乘的话，那肯定会爆long long。当然，python选手自动忽略。那么，我们可以这样思考，对于任意一个整数，我们都可以用二进制进行表示，也就是用二进制进行拆分，比如：b=2^n+2^(n-1)+...+2^3+2^0.所以我们就可以把ab=a2^n+a2^(n-1)+...+a2^3+a2^0,这样，我们就是分别进行一个快速幂，然后累加到答案即可。其实可以把b想象成一个01二进制串，然后，我们可以通过将b不断进行向右进行移位的方式进行求解，其实就是和快速幂非递归的思路差不多。 #include<iostream> using namespac...

对于这个题目，我们可以知道，其实就是一个快速幂的写法。 //非递归的写法 #include<iostream> using namespace std; typedef long long ll; int main(){ ll a,b,mod; cin>>a>>b>>mod; ll ans=1; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } cout<<ans%mod<<endl; return 0; } //递归的写法 #include&lt...

之前一直在写洛谷的题目，但是感觉光一直写没啥印象，效果也不是很好，所以，决定接下来的时间把自己每一天刷的题目以表格的形式分享出来，也算是加深印象了。2021.01.28 UPD:今天写完了60题普及组的了，感觉不能继续这样写下去了，明天开始刷提高组题目了。    日期 题目平台及编号 题目难度 算法类型 题目思路    1月28日 洛谷P1288 普及/提高- 博弈论 可以往两边走，直到遇到0停止，看一下是否走了几步，存在奇数步的话说明可以先手赢，否则是后手赢   1月28日 洛谷P1290 普及/提高- 博弈论 看谁有多余选择的可能，没有多余选择的可能就按照正常的进行下去，如果到了谁操作的时...

A题 面试 思路：直接进行一个处理，先根据输入计算出四次机会下来获得的评级A,B,C,D的个数，然后根据题目的要求进行一个相应的处理即可。代码： #include<iostream> #include<queue> #include<algorithm> #include<cstring> #include<stack> using namespace std; void solve(){ int a=0,b=0,c=0,d=0; char ch; for(int i=0;i<4;i++){ cin>>ch; if(...

小y的考试 思路：我们先对四个选项进行一个排序，同时我们将排好序后的要能够保留到原始的选项号，根据“三长一短选最短”，我们判断有没有最短的那个选项，有就选对应的选项，然后根据“三短一长选最长”，我们可以找出是否有最长的，同理，如果两者都没有，那么直接输出C即可。 #include<bits/stdc++.h> using namespace std; string s[4]; struct node{ int len; char ch; }Node[4]; bool cmp(node a,node b){ return a.len>b.len; } int main(){ i...

最大生成树是通过先对边权进行一个排序，然后对排序后的边权进行提取，看两端的点是否联通，也就是利用并查集进行一个优化，如果两点还未在同一个集合里面，则累加边权到最后的答案，合并两个点即可。 #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<queue> #include<cmath> #include<set> using namespace std; typ...

时间复杂度 题意：给出一个t，表示分钟数，要你计算出t分钟后时钟上面时针和分针的更小的那个夹角的大小。思路：一个简单模拟，看似简单，实际上要注意的是四舍五入，我们习惯上分别计算时针和分针走的角度，然后进行一个做差，问题就很可能出在做差的时候，做差下来小于180度没话说，但是一旦超过一百八十度的时候我们肯定想到的是做差，然而做差下来之后进行四舍五入的话很可能把改进位的改为舍去了，两者相差了1，所以要进行一个分情况来讨论。注意用double类型的变量即可。代码： #include<bits/stdc++.h> using namespace std; int main(){ int n...

#include<iostream> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<queue> #include<cmath> #include<set> using namespace std; typedef long long ll; const int N=1e5; const int maxn=1e7+10; int n,m; int head[N],ver[N],nxt[N],...

一、向上标记法 比如求x，y的lca，我们先从x向上走到根节点，中途标记每个被走过的点，然后从y向上标记，直到遇到第一个被标记的点就是他们的lca了。(不适用于多次查询操作）时间复杂度：O(n) 二、树上倍增法 这种方法主要是利用了倍增的思想，不断地向上试探，同时利用dp不断转移到上面，然后即可求出lca， /* 树上倍增法求最近公共祖先 时间复杂度： O ((n+m)log(n)) 1、d[x]表示x的深度，不妨设d[x]>=d[y](否则x，y交换） 2、用二进制拆分的思想，把x向上调整到和y同一深度 3、若此时x=y，则说明找到了LCA，LCA就是y 4、用二进制拆分的思想，把x，...

A、U131732 Woft6c看两任摸鱼王抢咸鱼 思路：逻辑思维题，首先可以自己进行模拟，找到规律。但是要注意开long long。代码： #include<stdio.h> int main(){ int t; scanf("%d",&t); while(t--){ long long n; scanf("%lld",&n); long long ans=(n-1)/2; printf("%lld\n",ans); } return 0; }B、U130186 Peterliang学习杨氏矩阵 思路：考...

主要介绍两种方法，一种是进行两次dfs进行求解，我们先任选一个点，然后对这个点进行dfs求出离这个点最远的那个点，我们记为p，然后，我们再以p为起点，进行dfs求出离p点最远的那个点，我们记为q，pq长度就是我们要求的这颗树的直径了。 代码： #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N=100010; int head[N],nxt[N],ver[N],edge[N]; int n...

B、 乐***对 题意：给出n个人，将这些人分为若干个组，每个人对应的一个值a[i]，表示这个人所在队伍的人数只要有a[i]个人才可以，问最多可以组成多少个队伍？若不能组成队伍，则输出-1.思路：我们考虑贪心的算法，我们令dp[i]表示当前到i的时候我们可以组成的最多的队伍数量。那么，我们可以直到，当我们到达i的时候，我们要考虑将i分到哪个组里面，我们可以将它们与i-1组成一组，如果i>=a[i]的话，我们也可以让[i-a[i]+1,i]这些组成一组，所以我们可以得到状态转移方程： 所以我们直接进行一个dp即可。代码： #include<bits/stdc++.h> usin...

数字计数 题意：求最大的数字与次大的数字之差,最大的数字与次小的数字之差,次大的数字与次小的数字之差,次大的数字与最小的数字之差。思路：题目的数据量比较小，直接用一个sort排好序后进行求解即可，注意去重即可。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; int a[1000]; int main(){ int n; cin>>n; map<int,int> mp; int k=0; for(int i=0;i<...