参考博客：https://www.cnblogs.com/wuanran/p/13907357.html题目链接：https://ac.nowcoder.com/acm/contest/7502/D #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h> #include <cmath> #include <bitset> #inc...

D-涛涛和策策的游戏：博弈论(sg) 思路：游戏输的一方是找不到一个大于1的数，那么就是说每个人都想最先让所有数变为1。所有如果双方都会考虑让对方把这个数变成素数，所以我们就去找每个数有多少个素因子，这就类似于尼姆游戏了，每个数相当于每堆石子，素因子个数相当于每堆石子的个数，然后异或一下便可得到答案。 #include <iostream> #include <cstdio> #include <algorithm> #include <time.h> #include <stac...

https://ac.nowcoder.com/acm/problem/14600 #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h> #include <cmath> #include <bitset> #include <set> #include <map> #define ll long long...

一些内置函数 可以弹出对话框的有，警示对话框：alert(),确认对话框：confirm(),提示对话框：prompt(). prompt(): 用于输入内容，也可以在括号内写上输出内容。 var t = parseFloat(prompt("input：\nsss")); document.write(t); 显示结果为： parseFloat(): 对字符串进行解析，并返回一个浮点数。 该函数首先对字符串的首位进行判断，如果是数字则进行解析，直至最后一个数字，最后返回该子串组成的数字。一般用在输入当中。 var t = parseFloat(pro...

必胜点与必败点： p：必败点，即谁在这个点，只要双方正确操作，在这个点的一方必输。 N：必胜点，即谁在这个点，只要双方正确操作，在这个点的一方必胜。 一般博弈题可以通过画PN图找规律来解题。 例题：http://acm.hdu.edu.cn/showproblem.php?pid=1847 从图中可以看出规律，只要牌的数量是3的倍数Kiki必输。 代码戳我可看 再来看说明是sg函数： 这里引入一个集合mex{x}表示不属于这个集合的最小整数。 **小性质：**如果mex的集合都大于零，那么最小的一定为零，如果有一个数等于零，那么最小的一定大于零。 对于任意状态sg(x) = mex{s},s...

N皇后问题是给定一个N*N的棋盘，要将N个棋子放入这个棋盘中，但要规定每个皇后不能放在同一行，同一列，也不能放在同一对角线上，问总共有多少中放法。 对于N皇后问题，我们大多数采用的是DFS+剪枝求解。 思路如下： 1）考虑一个棋子能否放在(i,j),那么第i行，第j列不能放有其他棋子容易判断的，而对角线怎么判断呢，设某个点(r,c)放有一个棋子，那么只要|i-r| != |j-c|就行。 2）我们定义一个数组a，a[i] = j表示第i行的第j列放了一个皇后。 3）我们从第一行往最后一行放，对于每一行的点，我们去判断这个是否能放，注意一定是判断前面已经放过皇后的行。如果不能放，那么判断这一行的...

思路： 1）因为要求最小的改变次数，那么就是要从这个序列中找出最长符合a[i+1]-a[i] = i的序列，它们之间可以是不相邻的，也就是说把其他不符合这个最长的序列的元素改变使得它们满足这个序就可以了，而这个最长序列中的元素不用改变。 2）现在是要如何找到这个最长序列呢。 那我们就先找到一个符合a[i+1]-a[i]=i的一个序列，长度和题目给的序列的长度相等，我们只需要看这个序列的元素和题目给的序列对应下标的元素相差多少，假设是x，用mp[x]保存x出现的次数，也就是能组成符合序列的长度。 3）为什么这样可以呢？比如下标为i和j的元素a[i],a[j],题目给出的数...

割点 定义：在一个连通分量中存在一些关键点，如果删除它，会把这个连通分量分成两个或多个，这种点称为割点。 在一个连通分量G中，对任意一点，做DFS，能够访问到所有点，产生一棵“深搜优先生成树”T。 定理1：T的根节点s是割点，当且仅当s有两个或两个以上的孩子节点。 定理2：T中非根节点u是割点，当且仅当u存在一个孩子节点v，v及其后代都没有回退边连回u的祖先。 编程实现定理2： 设u的一个直接后代是v 1) num[u], 记录DFS对每个节点的访问顺序。 2) low[v], 记录v和v的后代能够连回的祖先num。 3) 如果low[v]...

多组输入/一行读多个数 当输入的是string型时，可不用int，否则要用int或者float while True:     n,m = map(int,input().split())     print(n,m) 输入时只能在一行输入，换行直接退出 while True:     try:         n,m =&nb...

http://acm.hdu.edu.cn/diy/contest_show.php?cid=36899 1010-我！是！签！到！题！：BFS http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1010&cid=36899 思路：bfs，普通的用bfs求最短路是先到终点的路径最短，而这里又是最短里面的字典序最小，那么就不能上下左右的顺序任意选择了，而是优先选择小的字母去走，因为D<L<R<U,那么就按照下左右上的顺序去走。 #include <iostream>...

小白月赛30 https://ac.nowcoder.com/acm/contest/9667#question A-黑白边：并查集 思路： 1）先把所有黑白连起来，用并查集来维护连通块 2）然后看白边的两个点是否在一个联通块内，如果不在则连起来，白边个数+1 3）最后如何来判断所有点是否联通呢？只需要判断f[i] == i是否成立，是一个联通快的话，只有一个点的f[i]=i，其余的都不会，如果有多个，说明有多个连通块，也就是所有点不连通。这也是判断连通块个数的好方法。 #include <iostream> #include&nb...

技巧：要判断一遍dfs能否走完所有节点，可以判断这些节点的父亲是否相同，如果相同则可以走完所有节点，否则不能。 链式前向星存图 struct edge{ int val,v,next; }edge[2005]; int head[2005],cnt; void init() { for(int i = 0; i <= n; i++) head[i] = -1; } void add(int u,int v,int val) { edge[cnt].v = v; edge[cnt].val = val; edge[cnt].next = ...

树上倍增 利用二进制的思想，二进制的数可以表示出所有十进制的数，令f[i][j]表示i的第 个祖先，i = f[i][j]表示i跳到第j个祖先上去，假如我们要求i的第k个祖先，我们不需要一步一步的往上走，利用二进制的思想，我们可以一次条多步的往上走，例如要求i的第5个祖先，5的二进制形式是101，即 那么我们先跳到i的第一个祖先t，然后t跳到t的第4个祖先，也就求到了i的第五个祖先。树上倍增的应用： 1) 求某个节点的第k个祖先2) 求a，b的最近公共祖先LCA......如何求f[i][j]呢，对树根节点跑一边dfs即可 void dfs(int so,int fa) { f[so]...

表达式计算4 https://ac.nowcoder.com/acm/problem/50999 #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h> #include <cmath> #include <bitset> #define&n...