#include<bits/stdc++.h> using namespace std; //链式前向星本质上是通过将连接的边单独存储，而用head存储对应数据的下标来实现高效的读入 //这相比邻接矩阵更节省空间，相比vector由于不用动态开内存速度更快 struct Edge{ int to,next; //to 表示当前节点相连的节点，next是指下一条以相同节点为起点的边在 edge 数组中的下标。 }edge[200005];//无向边开两倍内存因为要创建两次 int head[100005]; int cnt = 0; // u 表示当前节点 v 表示连接的点 void...

其实用二分也可以 #include<bits/stdc++.h> using namespace std; typedef long long ll; bool check(int count, int n, int limit, const vector<int>& a) { for (int i = 0; i + count - 1 < n; ++i) { if (a[i + count - 1] - a[i] <= limit) { return true; } } return false; } int main() { int n,p; c...

使用并查集进行合并，每一次的（l,r)合并从左到右更新根节点（指向r），由于不会重复拆板子，所以遍历的合并方法是可行的。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; vector<ll> sum; // ll sum[n+2]; vector<int> cnt; vector<int> fa; // int fa[n+2]; int find(int x) { if(fa[x]==x) return x; else { fa[x] = find...

很有意思的一个题，想要高效的完成这个题目我们可以关注每一次操作的本质，对于比较特殊的例如 1 2 3 4 5 这种没有0的mex为0,不管多少次操作都是无效的 0 0 0 0 0 这种不需要操作就可以分析完了特殊的我们可以来看比较一般的情况，例如 0 2026 由于数组有0才能有有效的mex本质上所有的操作最后都会来到这一步，即每次让下一个值减10 4 -> 0 3 -> 0 2 -> 01 -> 0 0(4次）0 2026 -> 0 2025 - > ... -> 0 1 -> 0 0(2026次操作)我们可以特殊化一点插入一个数字观察会有什么...

这个题目有一点表述不清，出现过的指的是现有的牌河内存在的。对于加入牌河的num 其会使得 num+3 和 num-3安全，只要这两个值合法就可以加入set(用来去重)，对于移出牌河的num如果这次操作使得它的出现次数归零显然会影响num+3 和 num-3 这就需要我们去检查num-6 num-3 num 和 num num+3 num+6 即num-6和num+6是否为0，如果为0那么num-3和num+3就不在安全，从seet移出每次操作后输出set的大小就是答案了 #include<bits/stdc++.h> using namespace std; int main() ...

不是第一次写这种输出题了，要点无非是避免硬编码和利用数学规律确认遍历时的空格和字符的个数，这次用模块化的方式实现；修改行数n可以输出目标图形。 #include<bits/stdc++.h> using namespace std; char c; void cout1() { cout << " "; } void cout2() { cout << c; } int main() { cin >> c; int n=5; int m = (n+1)/2; for(int i = 0; i < m; i++) { in...

这个题目考察的是快速幂和线性代数，看题解有多种方法，我比较认可的是用3*3矩阵来运算。当我直接拿到这个题目的时候，第一感觉是Dp但是比较明显的是在这个题目里面，如果单个dp对应的是一个元素，问题不是dp会重复计算而是计算的总次数过多，状态转移不通畅，这种大数据其实适合的是使用快速幂，思路转移到直接计算，对于这个题前三项都是1,我们可以使用线性代数，把这个题目转化成快速幂问题，即f2 = M*f1（M就是转移矩阵）每一次转移之后使得矩阵[a1,a2,a3]变成[a2,a3,a4],求得对应的转移矩阵，最后就能将数列转化成矩阵的幂的问题，用快速幂来求m的n-3次幂，最后再乘以[a1,a2,a3]，...

这个题目应该是一道数学题，对t求导可以找到最小值点，然后对应求出即可。但是我们仍然有几个需要注意的点一个是k>0,我们求导后k=log2(eln2),ln2<1,这意味着如果e比较小，我们最后得到的k是负数，但是这是不符合要求的，你只能先缩小再放大（k>0）因此需要k=max(0.0,k)另外我自己在做题时犯了一个蠢事，就是试图使用快速幂来求2**k但是double是不能对Int做数学操作的，这里的数据其实用pow()也可以实现。然后这里使用了hypot()来求距离，注意这个函数的运行时间会更长，下面的解释很精彩，感兴趣的读者可以一看https://www.zhihu.com...

和昨天的题目一样这里我们也可以使用bfs，按照题目给出的逻辑，火焰和人的移动逻辑相同，换言之人之能至者，火之可至者也。所以只需用bfs搜索联通块就行，如果所在的地点没有踩过并且是杂草，那么火就能烧到这，换言之ans++我认为这种题目其实比较模板1. 使用向量数组来限制搜索范围（在我的知识范围之内模拟移动搜索的题目都可以使用向量数组通过遍历实现搜索） 2.用queue来实现bfs 3.visit确保不重复访问  #include<bits/stdc++.h> using namespace std; int n,m; int dx[]={0,0,1,-1}; int dy[]={1,...

通过位运算状态压缩解题和bfs搜索都是可行的，这里使用bfs #include<bits/stdc++.h> using namespace std; struct State { string sa; string sb; int steps; }; bool check(string sa, string sb) { if(sa.size()!=0 && sb.size()!=0)//由于stoll,空串会异常，所以我们先检查后转换。 { long long a = stoll(sa),b= stoll(sb); return (a%b==0 || b%a==0...

最原始思路是对每一个节点进行判断然后累加，但是这样肯定会积累重复项。观察经过两个边的类型可以分为两种，子 - 父 - 子 和 孙 - 子 - 父 两种，我们可以选择中间节点作为统计的口径。对于深度为2到n-1的中间的节点作为父节点可以得到一条（子 - 父 - 子 ）作为子节点可以获得两条（孙 - 子 - 父）对于根节点，只有作为父节点的一条。对于深度为n的节点无法作为中间节点所以为0然后简单相加就可以了，也就是 S = [(2^n-1 -1)-1]*3 + 1= 3*2^n-1 - 5最后值得一提的是对于边界情况n==1我们需要特判，此时没有子节点但是仍会统计为1对于n==2 S=1正确我们可...

这个题目一开始拿到之后的思路是很明显的，就是统计连续片段的个数，但是这种思路会忽视连选数字的并行情况例如（111222这种得到的cost会是6，所以使用multiset来进行删除工作，逻辑不变，更加符合直觉。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n; cin >> n; multiset<int> nums; for(int i = 0; i < n; i++) { int a; cin >> a; nums....