威风镰鼬

题解

/ 注册

全部文章 / 题解（共151篇）

题解 | #数据结构#

思路要维护区间和以及平方和两个线段树，同时支持加法和乘法操作。前面基本套模板就行了，那么我们重点是pushdown怎么写。（这个板子是参照oi-wiki先打出lazy的pushdown的，已经能支持加法维护区间和了）我们可以用上述式子Pushdown区间平方和。考虑乘法：一开始我们建立cheng...

线段树

2021-06-23

1 678

题解 | #[NOIP2015]信息传递#

思路这道题的大意就是要我们求最小环的长度。我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。这个是一个O(n)的做法。代码...

dfs 普及组图论环

2021-06-22

1 523

题解 | #完全平方数#

思路在l和r里面一个一个数肯定会超时的，可以采用二分先把第一个大于l的平方数找出来，然后把第一个大于等于r的平方数找出来（等于的情况可以思考一下l==r的情况）提前打好表然后就能知道中间有多少平方数啦~ 代码 #include<bits/stdc++.h> using namespac...

二分 STL

2021-06-20

1 581

题解 | #简单的数据结构#

思路 List会超！List会超！List会超！（可能是我太蒟蒻了写不出来）最后还是改成了双向链表。代码 #include<bits/stdc++.h> using namespace std; int n,m,opt,x; deque<int>a; int main(...

排序 STL

2021-06-20

1 447

题解 | #加边的无向图#

思路我们知道，要让n个点联通，就要用n-1条边。Kruskal求最小生成树用到的边数num，那么缺的边数就是n-1-num。代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005; struct E{...

并查集

2021-06-18

1 556

题解 | #序列求和#

思路本来纳闷这不就是求平方和，带公式就好了嘛？，过程中要不断取模避免出错。不过结果还是不一样……突然想到我除了一个数，要用逆元呀~因此公式应该改为就可以得到正确答案了~(可以提前算出6模1e+7意义下的逆元) 代码 #include<bits/stdc++.h> using names...

快速幂逆元

2021-06-18

2 485

题解 | #分元宵#

思路题目的参数我分别用c,v,w,q,mod代替了。想法很简单，每个碗的放法都有cv种，碗有wq个，所以是两者的全排列。这道题的主要的坑点是数据范围，如果你直接求(cv)^(wq)显然是不行的，因为c和v都有1e18大，所以要把式子分解。，w*q没有爆ll，所以用中间的式就好啦~。代码 #in...

快速幂

2021-06-18

7 548

题解 | #用来作弊的药水#

思路快速幂求出下下x^a和y^b是否相等就行了，坑点：记得取模，不然会爆。代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; ll t,x,a,y,b;...

快速幂

2021-06-18

1 434

题解 | #[NOIP2005]陶陶摘苹果#

题解求高度＜手长+30厘米的苹果树，直接数就是了。代码 #include<bits/stdc++.h> using namespace std; int main(){ int a[11],cnt=0,h; for(int i=1;i<=10;i++) cin...

2021-06-17

1 434

题解 | #最大的差#

思路可以输入的时候记下最大值和最小值，我这里比较懒就直接排序了。代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[100005]; cin>>n; for(in...

2021-06-17

2 663