#积性函数 #线性筛 #快速幂 题意  给定n，求解 n<=1.3e7  思路   满足积性函数 需要找到n以下每个数的n次方，可以用筛法，质数的用快速幂计算，合数的用质数递推 因为空间限制，无法记录每个数的最小质因子，但其实可以直接暴力的乘上每一个质因子，同时开一个bool的vis数组保证每一个数只计算一遍  代码 #include<iostream> using namespace std; using ll=long long ; const int N=13e6+10; const int p=1e9+7; ll qpow(ll a,ll b){ a%=p; ll r...

100多个AK的佬，牛逼  A 题解的token计算 题意  输入一个数 ，输出  误差不超过1e-3  思路  直接硬搞，用printf格式化输出更方便  代码 #include<bits/stdc++.h> using namespace std; int main(){ double a; scanf("%lf",&a); printf("%lf",150*log(a)); }  B 76修地铁 题意  从第5列开始，每5列需要2个a 从第5列开始，每10列需要1个b 从第20列开始，每20列需要3个c 从第1列开始，除了放置普通铁轨的那列，每列需要2个d   示意图...

赛时EG，补KLIH  G 题意  给定一个字符串S，处理q次询问 每次询问给出另一字符串T和数字a 回答T和S有多少相同的区间满足   思路  签到题，将T和S直接按位对比有多少连续且相同的字母 每个连续区间对总答案的贡献是  总复杂度：   代码 #include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n,q; cin >> n >> q; string s; cin >> s; for(int i=0;i<q;i++){...

多起点多终点问题  设置一个超级起点和超级终点，然后正常做  多层次问题  不同的问题有不同的设计方法，最重要的是不要出现只之前不存在的边  每一层内设置一个平台点，去平台点花费，出平台点不花费，平台之间代价为0 设计两个点，一个点接受下一层点的进入，并指向上一层点，经过的代价为t，另一个点接受上一层点的进入并指向下一层点，代价也为t

题意  n个数，确定了m对关系(a>b) 求还需要多少对关系就能确定任意两个数之间的大小  思路  把大小关系视为一条有向边 这个题就变成了任意两个点是否联通 考虑使用FLoyd，但是n是1000量级的，刚好爆炸 使用bitset优化  足够 floyd算法可以传递闭包关系 bitset错误赋值，1是int超过32位就无效了   cin >> n >> m ; for(int i=1;i<=m;i++){ int x,y; cin >> x >> y; f[x]|=(1<<(y-1)); }  代码 #include&lt...

题意  n个点，m个集合，在i-th集合内相互移动的代价为t-th 两个人从1和n开始移动，求碰面最短时间和碰面的点  思路  强行给每个集合之间的点互相连边复杂度会到  不可以 对于这种集合/平台类的问题，我们通常选择给每个集合/平台单开一个点，集合中所有点到这个单开点建双向边，过去的代价为t，回来的代价为0,这样就建完了图 建完图后，从1和n跑两遍dijkstra 最终答案遍历每一个点，取   代码 #include<bits/stdc++.h> using namespace std; struct ty{ int t,l,nxt; }edge[2020220]; int h...

题意  给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点 特别的，两个点一样高，就认为是双向边 求出最多能到达的点的个数，以及到达这些点需要的最小距离  思路  先dfs一遍，确定哪些点能到 类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两个点之间能联通 到这个题，由任意点都只能向下访问各个点，所以，Prim的排序就不再只按照长度排序，而是先按照高度(保证尽可能访问更多点)，再按照长度 而如果使用Kruskal，给边排序的时候也是按照边中较低的点进行排序，使得终点最高，然后再按长度排序，拿到一条边的时候从高的地方走向矮的地方，那就要保...

#反向建边 #拓扑排序 题意  有n个菜，m个条件约束条件(a,b)，表a必须在b之前 除了约束条件外，要保证序号小的的尽可能先做 在满足所有限制的前提下，1 号菜肴”尽量“优先制作； 在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作； 以此类推。 例：共4 道菜肴，两条限制<3,1>、<4,1>，那么制作顺序是 3,4,1,2。  思路  正向描述这个拓扑序不好描述，因为每做一个菜都可能影响当前的“最优先做的菜” 考虑反向描述 先做序号最小的->最后做序号最大的 通过反向建边，变为在拓扑序中寻找字典序最大的  代码 #include&l...

题意  n*n的正方形地图，从起点走到终点，图中有一些障碍物不能走 求最小转弯次数  思路  图不大，迷宫问题，考虑搜索，不再记录步长，而是在走每一步的时候考虑和走过来的方向是否相同，如果不同就给转弯次数+1 用一个优先队列避免重复走 不开vis，否则部分优势可能掩盖全局劣势 也可以最短路做，每个点转化成四个点，和其它点建边  代码 #include<bits/stdc++.h> using namespace std; //太痛了，01bfs用vis可能会劣势路抢占优势路 char mp[120][120]; int dis[120][120][4]; int mv[4][2] ...

特殊最短路  树：直接起点dfs搜索到终点即可 有向无环图：拓扑排序，删掉每一个点时更新后继的最短距离 边权全部为相等：bfs  单源最短路  从一个点出发到其它顶点的最短路径长度 基本操作：松弛  这样的(u,v)称为紧的，可以对它进行松弛  dijkstra  不能存在负边，每个边会被访问一次，每个边都有可能进一次优先队列   dis数组初值赋为极大 起点dis为0 计算与s相邻的所有点的dis—— 取还没算出最短路的点中dis最小的点u，它的最短路就是 对于u相连的所有点v如果能松弛，更新 重复4,5直到所有点求完  #include<bits/stdc++.h> using...

Prim  从单一顶点开始 不断加入最小的边，且边的一个顶点在树中一个顶点不在  #include<bits/stdc++.h> using namespace std; typedef struct{ int t,l,nxt; }E; E edge[1010110]; int head[101010]; int cnt; int n,m; void insert(int a,int b,int v){ edge[++cnt].t=b; edge[cnt].l=v; edge[cnt].nxt=head[a]; head[a]=cnt; } struct ty{ int x,len...

关键路径  AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应，它通常表示一个工程的计划或进度。 AOE网是一个带权的有向无环图，图中的：  边：表示活动(子工程)， 边上的权：表示该活动的持续时间，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。   其中有两个特殊的顶点(事件)  一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边； 另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余...

引入  一个工程有许多子工程，称为活动，在有向图中用顶点表示活动，有向边表示活动的先后顺序，这样的图称为AOV网，在AOV网中为了更好的完成工程，需要满序先后关系，将各活动排一个先后次序，就称为拓扑排序  问题  对一个AOV图，判断能否排序，并进行排序  解决方法  从有向图中选一个没有前驱的结点，输出 从图中删除这个点以及所有出边 重复上述两步直至图为空，或者无法删除 注意，拓扑排序存在多解，可能同时存在两个没有前驱的结点  实现  开一个队列，把入度为0的点弹入，弹出队首，给邻接点入读减一，如果减成0,入队 对于每个点每个边都访问一次，O(nm)  #include<bits/st...

1.邻接矩阵  二维数组，如果有重边就按题意考虑是否可以合并成一条边，或者只取一条边  2.邻接表  链表结构，头插法  3.vector  开一个vector数组来简化邻接表，但有时不够块  4.链式前向星  开一个结构体存边信息，开一个数组存每一条边，开一个head记录连接着这个点的下一个点是谁,head初值赋值成-1  typedef struct{ int t,val,nxt; }E; E edge[N]; int head[N]; int cnt; void insert(int x,int y,int l){ edge[++cnt].t=y; edge[cnt].val=l; ed...