2 3 1 这组数据不是1吗，过的代码怎么都是0？有咩有题解呀

如果你发现你的代码和标程几乎无差，思路一致，但一直有Output Limit Exceed错误，以下有我的解决方案，但对于这个错误我也无法说出所以然，故记下这篇笔记 在做模运算的时候，如果定义了long long（__INT64）a，b变量，但用了一个int对两个的乘积做模操作，在FZU2297上会出现Output Limit Exceed错误 解决方案：将mod数改成long long类型解决

题目链接 题目大意：给一个h高，w宽的广告牌，以及n条广告的宽度，每条广告的高度默认为1，问n条广告能插上的话所在的最高行数，插入不了输入-1. 解题思路：比较容易到用mlen维护区间h能够装下的最长广告的长度（未插入），n在2e5内，所以线段树最多就开8e5就足够了！之后单点更新的时候顺带返回下标。 Code: #include <bits/stdc++.h> using namespace std; const int maxn = (int)2e5+5; struct Node { int l, r; int mlen; }; Node BTree[max...

题目大意：给n个数，初始化为1，每次输入一个区间端点以及数字k，把这个区间的数全设为k。最后查询整个区间的数字和。 解题思路：线段树的裸题，区间更新区间查询，在打标记的时候直接赋值就行。 关于延迟标记 更新的时候如果发现某个区间在我们的更新区间之内，那么我们就把它的父节点更新完毕后，打个标记，表示该区间有一段任务未下放，将来用到其子区间时要完成下放的工作。然后直接结束该子树的更新任务。 Code： #include <bits/stdc++.h> using namespace std; const int maxn = (int)1e5+5; struct Node...

题目大意：一共n个数（1~n），问A[i] == i的个数大于等于k的方案数。 解题思路：其实就是大于等于k个人筛掉后剩下的人进行错排的问题。选k~n个人对应得要乘上组合数，由于n比较大，k相对较小，可以打表数组肯定mle，于是可以反过来想：总得排列数是Ann，扣除小于k的方案就能够得到答案，由于所有打表都进行取模，最后还要防止变成负数！求组合数取模的问题也可以用卢卡斯定理方法求得。 Code： #include <stdio.h> #include <string.h> const int maxn = (int)1e4+5; const int mod = (...

解题报告：问Alice的串是否能通过反转以及整除10的操作达到和Bob的串一样。相当于Bob的串只要是Alice的串的子串Alice就能赢。特别的，Bob的串为0的话Alice一定能赢！ Code： #include <stdio.h> #include <string.h> using namespace std; const int maxn = (int)1e5+5; char sa[maxn],pattern[maxn],saa[maxn]; int prefix[maxn]; void mystr(char str[], int n) { int i,...

解题报告：对于Tarjan的之前的理解的更正： 关于low数组在同一个联通分量中并不是所有的点都是标记为该搜索树的dfn！所以用book数组充当染色的角色。 关于该题的大意就是如果存在两个或以上的明星牛（不在同一个联通分支中）就等于没有！并且如果某几头牛相互关注，相当于形成一个强连通分量，然后该联通分量的出度为0，并且只有一个这样的联通分量的话，这个联通分量的所有牛都是明星！ Code： #include <bits/stdc++.h> using namespace std; const int maxn = (int)1e4+5; int n,m,tot;...

题目链接 题目大意：求给出的有向图是否为一个强联通图 解题思路：Tarjan的入门题，对于Tarjan的理解关键是low数组与dfn数组的理解，前一个是当前搜索树的第一次扫描的tot值，也就是最早的时间戳，我们整个算法就是为了更新它！而dfn是每个点被搜的时间节点，显然，每个点的dfn都不同并且dfn[i] >= low[i]。由于Tarjan是基于深度优先搜索的算法，所以被搜的点的先后次序我们可以用一个栈维护达到还原每个强连通分量的目的！特别的，筛去所有强连通分量的剩下的节点每个都是一个强连通分量！ Code： #include <bits/stdc++.h> us...

解题报告：同朴素的 O ( n 2 ) O(n^2) O(n2)写法一样，也能够记录路径，要在松弛的阶段用一个数组保存前缀节点。关于堆优化写法的注意事项： 更新的时候注意那个三角不等式的意思是：我...

解题报告：同 O ( n 2 ) O(n^2) O(n2)算法类似，不过用邻接表存图在松弛的时候优化了遍历不相邻点的复杂度，在查询当前最短径的时候直接用小根堆弹出，复杂度从 ...

解题报告：关于spfa的实现关键点： 用vector实现邻接表存图 vis数组表示某个点是否在队列中（因为一个点可能多次入队） cnt表示某个点入队的次数（如果存在负环的时候可以直接判断） dist数组同dijkstra一样表示该点与源点当前的距离，inf表示不通 spfa可以证明每个点平均入度的次数不超过两次，但判断负环的条件一定是cnt[v] > n，而不能单纯判断是否大于2，平均情况不能保证全体！ Code： #include <bits/stdc++.h> using namespace std; const int maxn = (...

解题报告：虽然没有负环，不过用spfa效率也不错。 Code： #include <stdio.h> #include <iostream> #include <queue> #include <algorithm> #include <string.h> using namespace std; const int maxn = (int)1e5+5; const int inf = 0x3f3f3f3f; struct Node{ int to; int w; Node(int to, int w) { this-...

1015 Reversible Primes (20 分) A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime. Now given any two positive integers NNN (<1...

费马小定理 假如p是质数，且gcd(a,p)=1（a和p互质），那么 a^(p-1) ≡ 1（mod p），即 ( a^(p-1) )%p = 1。 可以用这个定理快速求得一个大数的余数。例如： \(欲求：2^{100}\ \%\ 13=\ ?\) \(因为2与13互质，故根据费马小定理有：2^{13-1}\equiv1(mod\ 13)\) \(即：2^{12}\ \%\ 13 = 1\) \(又：2^{100}=(2^{12})^{8}*2^4\) \(所以，2^{100}\ \%\ 13=(2^{12})^{8}*2^4\ \%\ 13=((2^{12})^{8...