Jason Fan.

📕NOIP 数论笔记，素数筛法、欧几里得、扩展欧几里得、欧拉函数、欧拉定理、费马小定理、逆元、求解同余方程（中国剩余定理） 素数筛法 对于少量的判断一个 n 是不是素数，我们可以通过暴力 O(n)O(\sqrt{n})O(n​) 的复杂度解决，而当题目需要判断大量素数时便引入了筛法求素数。 朴素的筛法 遇到一个数把它的所有倍数标记掉，依次筛，没有标记的就是素数。复杂度 O(nlog⁡n)O(n\log n)O(nlogn) 123456789void init(int n) { int up = (int)sqrt(n) + 1; for (int i = 2; i <= up; i++) for (int j = i * i; j <= n; j += i) flag[j] = true; for (int i = 2; i <= n; i++) { if (!flag[i]) p[tot++] = i; }} 线性筛素数 O(n)O(n)O(n) ...

📒 关于 dfs 树的笔记、用 tarjan 求割点、割边、双连通分量、强连通分量、缩点…… 边的分类 对于有向图 树边、前向边、后向边（返祖边）、横叉边 树边dfs 形成的边 前向边指向子孙方向的边 后向边（返祖边） 指向祖先方向的边 横叉边指向另一子树的边 对于无向图 树边，后向边（返祖边），前向边 树边dfs 形成的边 后向边（返祖边） 指向祖先方向的边 无向图的双连通分量 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用 Tarjan 算法。 ————百度百科 其中边双连通分量一定是点双连通分量，而点双连通分量不一定是边双连通分量（反例：两点一边） 割点 对于一个无向联通图，去掉一个点，这个图不联通，则该点为割点，下图中 u，v 即为割点 做法 （后文会用到）考虑对图进行 dfs，记录时间戳dfn[u]dfn[u]dfn[u],还有low[u]low[u]low[u ...

求所有子树的重心，利用重心性质合并子树重心 Kay and Snowflake After the piece of a devilish mirror hit the Kay’s eye, he is no longer interested in the beauty of the roses. Now he likes to watch snowflakes. Once upon a time, he found a huge snowflake that has a form of the tree (connected acyclic graph) consisting of n nodes. The root of tree has index 1. Kay is very interested in the structure of this tree. After doing some research he formed q queries he is interested in. The i-th query asks to find a centroid of ...

树形dp，分组背包 Find Metal Mineral Humans have discovered a kind of new metal mineral on Mars which are distributed in point‐like with paths connecting each of them which formed a tree. Now Humans launches k robots on Mars to collect them, and due to the unknown reasons, the landing site S of all robots is identified in advanced, in other word, all robot should start their job at point S. Each robot can return to Earth anywhere, and of course they cannot go back to Mars. We have research the informat ...

通过求直径解决 Anton and Tree Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph. There are n vertices in the tree, each of them is painted black or white. Anton doesn’t like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white). To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of ...

求树的直径解决 Computer A school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information. Hint: the example input is corresponding ...

树形dp，背包问题 Apple Tree Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at one node. She can eat up all the apples in the nodes she reaches. HX is a kind guy. He knows that eating too many can make the lovely girl become fat. So he doesn’t allow Wshxzt to go more than K steps in the tree. It costs one step when she goes from one node to another adjacent node. Ws ...

最大权独立集，树形dp HDU - 1520 There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number ...

c++实现，控制台小游戏 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#include <windows.h>#include <conio.h>#include <cstdio>#include <ctime>#include <cstdlib>const int fig[4][2]={{-1,0},{1,0},{0,-1} ...

c++实现，控制台游戏。 调用了 windows.h 库，其中 system(char) 函数用于发出一个DOS命令，相当于在CMD中直接写命令。MessageBox() 是调用对话框。通过_getch()函数可以直接获取输入字符而不会显示。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#include <windows.h>#include <bits/stdc++.h>#include<conio.h>const int n=19;int map[30][30];int x,y,sx=0,sy=2;const int fig[9][2]={{ ...