记忆化搜索 bzoj1026 找出区间内满足相邻两位数差大于等于2的数的个数 数位dp的过程就是先分解记录数位，然后从最高位开始dfs，注意前导零和limit的限制，然后一般带上的还有pos当前位置和pre上一个数，然后根据具体题目再带上其他状态，dp[i][j]在这里表示高一位为j的i位数满足条件的个数，第二维也要根据具体题目设计状态 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll l,r; int a[20]; //dp[i][j]表示高一位为j的i位数满足条件的个数 ll dp[20...

import java.io.*; import java.util.Arrays; import java.util.Scanner; import java.util.StringTokenizer; public class Main {  static long[][] dp=new long[20][20]; static int[] a=new int[20]; static long dfs(int pos,int pre,boolean status,boolean limit){  if(pos<0){  return 1; } //status true表示没有前导零...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+50; int p[N],phi[N]; bool check[N]; //同时筛出素数和欧拉函数 void init(){  int t; check[1]=true; phi[1]=1; for(int i=2;i<=N;i++){  if(!check[i]){  p[++p[0]]=i; phi[i]=i-1; } for(int j=1;j<=p[0];j++){  t=i*p[j]; if(t...

#include <bits/stdc++.h> using namespace std; const int N=1e7+50; //同时筛出素数和莫比乌斯函数 int p[N],miu[N]; bool check[N]; int pre[N]; void init(){  int t; miu[1]=1; check[1]=true; for(int i=2;i<=N;i++){  if(!check[i]){  p[++p[0]]=i; miu[i]=-1; } for(int j=1;j<=p[0];j++){  t=i*p[j]; if(t>N){  ...

若 x = p 1 a 1 p 2 a 2 . . . p n a n x=p_1^{a_1}p_2^{a_2}...p_n^{a_n} x=p1a1​​p2a2​​...pnan​​，那 x x x的约数个数 σ ( x ) = ( a 1 + 1 ) ( a 2 + 1 ) . . . ( a n + 1 ) \sigma(x)=(a_1+1)(a_2+1)...(a_n+1) σ(x)=(a1​+1)(a2​+1)...(an​+1) 证明就是对于 p i a i p_i^{a_i} piai​​来说，他的因子有 p i 0 , p i 1 , . . . , p i a i p_i^0...

分别是线性筛素数，欧拉函数，莫比乌斯函数，约数个数，约数和，其中有些都是可以一起筛的 这里给出分别的模板 1. 素数 最基本的，后面基本都要用到素数的筛法 const int N=1e7+50; int p[N]; //true表示被筛，即不是素数 bool check[N]; int n,m,a; void init(){  int t; check[1]=true; for(int i=2;i<=n;i++){  //素数，直接记录 if(!check[i]){  p[++p[0]]=i; } //p[0]记录的是素数个数 //枚举现在已知的所有素数 for(int j=1;j&lt...

绝对路径导入格式为import a.b或者from a import b，相对路径导入格式为from . import b或者from ..a import b。 python2默认为相对路径导入，python3默认为绝对路径导入。 为使python2，3通用，建议采用相对路径导入from .a import b

Description   如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：    给出n, d，编程数出深度为d的n元树数目。 Input   仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16) Output   仅包含一个数，即深度为d的n元树的数目。 Sample Input 【样例输入1】 2 2 【样例输入2】 2 3 【样例输入3】 3 5 Sample Output 【样例...

Description 折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’，则AB  A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B)  AAACBB，而2(3(A)C)2(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。 Input 仅一行，即字符串S，长度保证不超过100。 Output 仅一行，即最短...

Description   FGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的 电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FG D希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联 系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码。 Input   第一行包含两个整数N（2<=N<=100000）和M（1<=M<=2000000）。职员被依次编号为1,2,……,N.以下M行，每 行...

给一个带权树,求出树中异或值最大的一个路径的异或值 异或的性质使得可以用类似前缀和那种思想 我们先求出每个节点到根的异或值,然后插入字典树中,然后就变成01字典树的模板题了,枚举所有异或值,查询与这个异或值(节点到根的异或值)异或最大的值 代码: #include <bits/stdc++.h> using namespace std; const int N=1e5+50; const int M=2e5+50; int n,u,v,w; struct Edge{  int v,w,next; }edge[M]; int cnt,head[N]; void init(){  cn...

据说是模板题… 求最大权闭合子图 最大权闭合子图参考这里 然后把题目的边看成原模板中的正权点,原先的点就看成原模板中的负权点,跑最大流求出最小割,然后用总的边权减去最小割即可 代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+50; const int M=2e6+50; const ll INF=1e18; int n,m; ll val[N]; struct Edge{  int v; ll cap,flow; int next; }edge[M]; i...

链接：https://ac.nowcoder.com/acm/contest/272/B 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 给定一棵n个点的树，每个点有权值。定义表示 到 的最短路径上，所有点的点权异或和。 对于，求所有的异或和。 输入描述: 第一行一个整数n。 接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。 第n+1行有n个整数，表示每个点的权值。 输出描述: 输出一个整数，表示所有的异或和，其中。 示例1 输入 复制 4 1 2 1 3 1...

好难的题,队友解释半天才搞懂… 给一棵树,能给叶子染不同的颜色,定义一个节点为happy当且仅当该子树叶子节点(可包括本身)的颜色各不相同,然后求分别有1到n个happy节点的情况下的最小颜色数 反过来想,先考虑n的情况,要n个happy节点,那就是所有叶子都染不同颜色,然后考虑n-1的情况,就去掉一个根节点,那么就变成两棵独立的子树,那只要保证那个叶子节点多的那个子树的叶子染不同的颜色即可,另外的兄弟子树的叶子不管染什么色肯定不会超过这一棵的颜色数,所以其实就是第二大的叶子数的子树,所以答案就是dfs一遍预处理出每个节点对应的子树的叶子节点数,排序输出即可 代码: #include <...