威风镰鼬

题解

/ 注册

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

题解 | #Biorhythms#

思路在信息学奥赛数论一本通里面我愣是没搞懂题解的5544、14421、1288这些数是怎么来的，在网上找了很多博客才搞懂中国剩余定理的原理。总结一下步骤：（方程组形式为mod m意义下与a同余）求大模数M->对每个小模数M/m，求模m意义下的逆元i，那么M/mia就是满足方程的一个最小数，然...

数论中国剩余定理

2021-08-05

1 392

题解 | #Sumdiv#

代码读懂代码前需要掌握的芝士：唯一分解定理任意正整数都有且只有一种方式写出其素因子的乘积表达式。约数和方程对于已经分解的整数有A的所有因子之和为我们先记录素因子，然后利用约数和方程求解。这里有一个二分加速的过程，推导在代码里面。牛客上面有三道Sumdiv大家可以顺便A了。思路 #i...

数论二分

2021-08-04

3 497

题解 | #加分二叉树#

思路大概就是区间DP，先枚举区间长度，长度为1时就是这个节点的分数。对于每一个区间枚举根节点，同时计算得分，那么[l,r]的最高得分是可以确定的，数据量很小，f[1,n]就是我们要求得的最高得分。我们记录了每个区间的根节点，要求输出前序遍历正常求就好了。注释给的很详细了应该。代码 #inclu...

dp 二叉树区间dp

2021-08-04

1 491

题解 | #wyh的天鹅#

思路学艺不精，交splay结果WA了，还找不到问题。所以我还是用了vector写。保持vector是有序的，插入和删除的时候二分，复杂度很优。记得要清空vector。代码 #include<bits/stdc++.h> //#define int long long using na...

vector 平衡树数据结构

2021-08-03

1 699

题解 | #青蛙的约会#

思路根据题目列出式子：(x+mt)-(y+nt)=pL其中：t是跳的次数，p是圈数差转化为：(n-m)t+Lp=x-y令a=n-m,b=L,c=GCD(a,b),d=x-y 有at+b*p=d要求的是t的最小整数解，转化为扩展欧几里得，求解同余方程就能得出答案。代码 #include<bi...

数论同余方程

2021-07-30

1 492

题解 | #[SCOI2005]繁忙的都市#

思路最小生成树的板子题，前置知识：并查集以及Kruskal算法；答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。代码 #include<bits/stdc++.h> using n...

最小生成树 Kruskal 并查集

2021-07-29

1 489

题解 | #[SDOI2009]ELAXIA的路线#

思路通过求出dis的交集来得到公共路径。然后重新建一个图。对x1，y1,x2,y2分别进行一次求最短路，交集部分（点的dis相同）进行rebuild，生成一个可拓扑排序求最长路径的DAG.因为做了课件，代码的注释写得很详细，这里就不细讲了。题解 #include <bits/stdc++....

最短路图论拓扑排序

2021-07-28

1 563

题解 | #[HAOI2016]食物链#

思路记忆化搜索、拓扑排序的题目。对于一个已经走过一次的点，后面能走的情况都是确定的，只要能把情况数记录下来，后面的结点就不需要再走一遍了，就可以很大程度上节省时间。代码 #include <bits/stdc++.h> using namespace std; const int...

搜索记忆化图论 dfs 拓扑排序

2021-07-16

1 493

题解 | #栗酱和火柴#

思路求最小公倍数，怕他越界所以用了int128。代码 #include<bits/stdc++.h> #define int __int128 using namespace std; int t,x,y; inline void read(int &data){ ...

2021-07-13

0 692

题解 | #[NOIP2004]合并果子#

思路贪心正解。用优先队列，每次把最小的两个果子合并了，得到的是最优解。代码 #include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int> , greater<int&g...

贪心 NOIP

2021-07-06

2 516