魔法使いの秘密基地

同余方程(exgcd)题意求关于 x 的同余方程 ax = 1(mod b) 的最小正整数解。 思路ax+by = gcd , x*和y*可以用exgcd()求出 x = x* + k(b/gcd) y = y* - k(a/gcd) 因为x为最小的正数，所以 x =((x*%b)+b)%b 代码1234567891011121314151617181920212223242526272829#include<vector>#include<iostream>#include<algorithm>#include <list>using namespace std;int exgcd(int a, int b, int &x, int &y){ if (!b){ x = 1, y = 0; return a; } int d = exgcd(b, a % b, x, y); int temp = x; x = y; y =te ...

营业额统计(set)题意设第 $i$ 天的营业额为 $a_{i}$, 则第 $i$ 天 $(i \geq 2)$ 的最小波动值 $f_{i}$ 被定义为: f_{i}=\min _{1 \leq j

基础一般哈希直接用map 字符串哈希12345678910111213141516171819核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果typedef unsigned long long ULL;ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化p[0] = 1;for (int i = 1; i <= n; i ++ ){ h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P;}// 计算子串 str[l ~ r] 的哈希值ULL get(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1];} 双哈希开两个哈希，不用自然溢出，用取模，mod1=1e9+7,mod2=1e9+11; P=131 or ...

知识点应用一 :求不等式组的可行解前提条件：从源点出发，一定可以走到所有的边！！！！注意是边！！！ 步骤 先将每个不等式 xi≤xj+ck，转化成一条从 xj走到 xi，长度为 ck 的边。 找到一个超级源点，使得该源点一定可以遍历到所有边 从源点求一遍单源最短路 结果1如果存在负环，则原不等式组一定无解 结果2如果没有负环，则 dist[i]就是原不等式组的一个可行解 应用二: 求最大值或者最小值结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。 问题：如何转化 xi≤c，其中 c 是一个常数，这类的不等式。 方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 c 即可。 糖果题意给小朋友分糖果，小朋友分的糖果之间有几种关系，求最少消耗的糖果。 思路“每个小朋友都要分到糖果”，说明都大于等于1。超级原点都连权重为1的边。 几种情况对应一下建图，求最长路。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505 ...

染色时间题意 思路优先队列广搜 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <iostream>#include <cstring>#include <algorithm>#include <deque>#include <map>#include <vector>#include <time.h>#include <queue>using namespace std;typedef pair<int,int> PII;typedef long long LL;const int N=100000,MOD=1e9+7,INF=0x3f3f3f3f;int mp[510][510];int f[510][510];bool st[510][510];int dx[4]=&# ...

Rooks Defenders题意一个二维图，每次可以选择1:坐标放置车，2:移除车，3:问一个矩阵图当前是不是被攻击。 被攻击的条件：每一行都有车，或者每一列都有车。 思路方法一用一个线段树或者树状数组进行单点修改和区间求和操作即可，用两个数组记录该行/列是不是需要修改即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>#include <cstring>#include <algorithm>#include <deque>using namespace std;typedef pair<int,int> PII;typedef long long LL; LL n,q;int t,a,b,c,d;int hang[200010],lie[200010];int hh[200010],hl[200010];int lowbit(i ...

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561. 前置知识点 (1) pi = acos(-1); (2) 余弦定理 c^2 = a^2 + b^2 - 2abcos(t)2. 浮点数的比较 const double eps = 1e-8; int sign(double x) // 符号函数
...

最大子序和题意输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。 思考状态表示-集合 $f_{i}$ : 以 $i$ 为 右端点, 长度 不超过 $m$ 连续子区间状态表示-属性 $f_{i}$ : 区间的总和最大 $M a x$状态计算 $f_{i}$ : f_{i}=\max \left\{s_{i}-s_{j}\right\} \quad(1 \leq i-j \leq m)观察这个转移方程, 首先这里的 $j$ 是有范围的: $i-m \leq j \leq i-1$其次, $s_{i}$ 作为一个常量, 可以提到外面去: $f_{i}=s_{i}-\min \left\{s_{j}\right\} \quad(1 \leq i-j \leq m)$从前向后 维护一个长度不超过 $m$ 的区间的 最小值, 就想到我们最熟悉的 滑动窗口模型 了 1234567891011121314151617181920212223242526272829303132333435363738#include <iostream> ...

D - 250-like Number题意p和q是两个素数，如果k可以表示$k = p*q^3$且$q>p$，那么就称k为250-like Number。 输入n，求1到n之内有多少个250-like Number。 思考一下结论显而易见 根据算术基本定理，相当于计算满足一定条件的（p,q）数量 p < q < 1e6 素数筛。然后固定p，找到最大的q，使得$N >= p*q^3$，此时答案应该加上小于等于q的素数的个数。枚举所有p即可。 寻找q可以用二分或者双指针（随着p的增大，目标q递减） 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;#define MAXP 1000005vector<long long> prime_list;void construct_plist(){ vector<bool> fl(MAXP,false); for(int ...

[toc] 注意力机制心理学从心理学来讲，动物需要在复杂环境下有效关注值得关注的点。 在心理学上有框架：人会主动、有意识的去选择注意点。注意点可以理解为值得关注的点、引人注意的点。 以上图举例说明： 上图中，摆在眼前的有五样东西，人们往往最先注意到的是颜色鲜艳的红色杯子。 当拿起红色杯子喝了里面的咖啡后可能会想要去学习、读书。 这里理解为，人们会去有意识的关注想要的东西。 其中，红色杯子是“不随意线索”(可理解为除了想要的物品之外的其它物品们，像红色杯子和报纸都是不随意线索)，想读书是“随意线索”(可理解为想要的那个物品)。 Attention 卷积、全连接、池化层都只考虑“不随意线索”。如何理解？ 拿池化举例说明：最大池化层只考虑窗口上的最大值，只要是最大值就行。 注意力机制显示的考虑随意线索。如何理解？ 这里和之前讲的心理学内容结合起来理解。 “随意线索”就是query，就是你想查询的物品。结合之前内容，query就是想读书。 其它的物品就是key-value pair，即“不随意线索-值”对。结合之前内容，key就是红色杯子、报纸。value可以一样也可以不一样。以 ...