排队 Problem： 牛妹在银行排队等号时，观察到以下场景。银行有m个服务窗口，假设当前有n个人等待办理业务，那么这n个人会被顺序分配一个从1到n的号码。 等待办理业务的流程如下：从第1号到第n号顺序的进行排队。假设当前第1号到第i-1号都正在办理或已经办理完业务，且某个窗口A没有客人正在办理业务，那么第i号会马上到窗口A办理他的业务。如果有多个这样的窗口，第i号会随意选择一个窗口。 在0时刻，牛妹观察到m个窗口都没有客人正在办理业务，而n个人正在等待办理业务。为了简化问题，我们假设第i号不管在哪个窗口办理业务，办理业务的时间都为​。 牛妹想知道有多少对(i,j)，满足，且第i号办理业务完...

小H和游戏 题目描述 小H正在玩一个战略类游戏，她可以操纵己方的飞机对敌国的N座城市（编号为1~N）进行轰炸 敌国的城市形成一棵树，小H会依次进行Q次轰炸，每次会选择一个城市A进行轰炸，和这座城市距离不超过2的城市都会受损（这里距离的定义是两点最短路径上的边数），轰炸结束后，小H还想知道当前城市A受损的次数 作为游戏的开发者之一，你有义务回答小H的问题 输入描述 第一行，两个整数N（\(1 \leq N \leq 750000\)）,Q(\(1\leq Q \leq 750000\)) 第2~N行，每行连个整数表示树上的一条边 第N+1~N+Q行，每行一...

牛客小白月赛24—I.求和 题目描述 已知有\(n\)个节点，有\(n-1\)条边，形成一个树的结构。 给定一个根节点\(k\)，每个节点都有一个权值，节点\(i\)的权值为\(v_i\)。 给\(m\)个操作，操作有两种类型： 1 a x : 表示将节点\(a\)的权值加上x 2 a : 表示求\(a\)节点的子树上所有节点的和（包括\(a\)节点本身） 输入描述 第一行给出三个正整数 \(n,m,k\)，表示树的节点数、操作次数、和这颗树的根节点， 第二行给出\(n\)个正整数，第\(i\)个正整数表示第\(i\)个节点的权值\(val_i\) ...

DFS序 我们在处理一些树上计数问题时，经常由于数据量过大而树形结构的统计操作又十分复杂，所以常常需要将树形结构转换成更加便于查询和修改的线性结构，再结合树状数组或者线段树等高效的查询更新结构来解决问题，这时，为了将树形结构转换成线性结构，我们经常会用到的一个东西就是DFS序。 想要得到DFS序，只需要对树做一次DFS遍历，在遍历过程中记录每个点被遍历到的时间点，这里用一个\(，Orderin，Orderout\)时间戳数组来记录，以下面的树为例： 经过DFS后得到的DFS序为： 顶点序号 1 2 3 4 5 ...

邻接表 在图的描述中，经常会用到邻接表，有时我们会用到邻接矩阵来保存图的边和权值等信息，但是这回产生\(N^2\)的空间复杂度，在数据量比较大的多数情况下，我们是无法存储的，所以这是就需要用到空间复杂度为\(N\)的邻接表来存储图。 存储 对于邻接表的存储方式，我们除了保存边的三个数组\(u,v,w\)之外还需要两个数组\(first,next\),其中\(first\)用来保存与第i号顶点相连的第1条边是第k号边（\(first[i]=k\)），\(next\)数组用来保存连在同一个顶点上的边的先后关系，\(first,next\)均初始化为-1。 例： 4 5//点数和边数 1 ...

数字游戏 题目描述 科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间\([a,b]\)，问这个区间内有多少个不降数。 输入格式 有多组测试数据。每组只含两个数字\(a,b\)，意义如题目描述。 输出格式 每行给出一个测试数据的答案，即\([a,b]\)之间有多少不降数。 样例输入 1 9 1 19 样例输出 9 18 Hint 对于全部数据，\(1\leq a \leq b \leq 2^{31}-1\)。 思路 ...

Amount of Degrees 题目描述 求给定区间\([X,Y]\)中满足下列条件的整数个数：这个数恰好等于\(K\)个互不相等的 的整数次幂之和。例如，设\(X=15, Y=20, K=2, B=2\) ，则有且仅有下列三个数满足题意： \(17 = 2^4+2^0\) \(18 = 2^4 + 2^1\) \(20 = 2^4+2^2\) 输入格式 第一行包含两个整数\(X\)和\(Y\)，接下来两行包含整数\(K\)和\(B\)。 输出格式 第一行包含两个整数 和 ，接下来两行包含整数 和 。 样例输入 15 20 2 2 ...

数位dp 简介 数位dp是一种一般用来计数的dp，常用于求解\(l-r\)之间有多少符合条件的数的问题，由于\(l,r\)一般给的很大，所以无法用直接遍历的方法求解，这时候就要用到数位dp了。 模板 long long digit[maxn]; long long dp[30][state];//二位dp数，第一维是数位，第二维是状态数 long long dfs(int pos/*数位*/, int state/*状态记录*/, bool limit/*数位上界辅助确定数组*/, bool lead/*确定数组前导0*/) { if(pos == -1) return 1;//数...

幸运数字II 题目描述： 定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。 比如说，47、744、4都是幸运数字而5、17、467都不是。 定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。 输入描述： 两个整数l和r (1 <= l <= r <= 1000,000,000)。 输出描述： 一个数字表示答案。 样例输入： 2 7 样例输出： 33 Idea 因为此类数数量不多，所以直接打表记录下所有数字，然后再求l-...

Line++ Problem Statement We have an undirected graph GG with NN vertices numbered 11 to NN and NN edges as follows: For each i=1,2,...,N−1, there is an edge between Vertex i and Vertex i+1. There is an edge between Vertex X and Vertex Y. For each k=1,2,...,N−1, solve the problem below: ...

阶乘 题目描述： 给定一个正整数 p 求一个最小的正整数 n，使得 n! 是 p 的倍数 输入描述： 第一行输入一个正整数T表示测试数据组数 接下来T行，每行一个正整数p 输出描述： 输出T行，对于每组测试数据输出满足条件的最小的n 样例输入： 4 1 2 4 8 样例输出： 1 2 4 4 备注： \(T\leq10^3,p\leq10^9\) 思路： 直接查找一个阶乘可以摸p，但是如果直接搜索一定会TLE，所以搜索过程中，我们要进行判断，如果p可以由当前值和一个不相等的素数相乘得到，那么就可以将这个素数看作可能结...

小计算器 问题描述： 模拟程序型计算器，依次输入指令，可能包含的指令有    数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数    运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余    进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)    输出指令：'EQUAL'，以当前进制输出结果    重置指令：'CLEAR'，清除当前数字 指令按照以下规则给出：    数字，运算指令不会连续给出，进制转换指令，输出指令，重置指...

分考场 问题描述： n个人参加某项特殊考试。 为了公平，要求任何两个认识的人不能分在同一个考场。 求是少需要分几个考场才能满足条件。 输入格式： 第一行，一个整数n(1<n<100)，表示参加考试的人数。 第二行，一个整数m，表示接下来有m行数据 以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。 输出格式： 一行一个整数，表示最少分几个考场。 样例输入： 5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 样例输出： 4 样例...