题意给出一个连成树的有向图，求拓扑序数量数据范围：$1 \le n \le 1000$题解树形$dp$，用$f[i][j]$表示以$i$为根的子树中，节点$i$的排名为$j$的方案数考虑转移，对于$u$为$v$的父节点，$x$在原序列中排名为$p_1$，新序列中排名为$p_3$；$y$在原序列中排名为$p_2$，新序列中排名为$p_4$，从$f[u][p_1]$与$f[v][p_2]$转移到...

题意一个$n \times m$的方格，初始时每个格子有一个整数权值接下来每次有$2$种操作改变一个格子的权值求一个子矩阵中某种特定权值出现的个数数据范围：$n,m \le 300,1 \le c \le 100$题解$n,m,c$较小，对于每个$c$开一个二维树状数组维护代码：#include<iostream> #include<cstdio> using nam...

题意求长度$\le$最短路$+k$的路径数数据范围：$n \le 100000,m \le 200000$题解首先需要跑一边最短路找到这个最短路；虽然保证存在$1 \rightarrow n$的路径，但并不是所有的点都能到$n$，所以应跑反向图用$f[u][i]$表示从$u$到$n$的路径中$\le dis[u][n]+i$的路径数，则答案为$f[1][k]$对于转移，考虑一条边$u \ri...

题意略数据范围：$1 \le n \le 100$题解数据范围较小，可直接$dfs$越过连续$1$为int nx=x+v[i][0],ny=y+v[i][1],cnt=1; for(;nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny];nx+=v[i][0],ny+...

题意对于一个数列，有$2$种操作：$1 \ x$ 询问$\ge x$的连续段的个数$2 \ i \ x$ 将$a_i$的值修改为$x$数据范围：$1 \le n,m \le 200000,1 \le a_i,x \le 10^9$题解首先对于一个询问考虑：将$\ge x$的数定义为$1$，$< x$的数定义为$0$；那么一个段的构成应为$$011 \dots 110$$即一个$01$+...

题意给定一个长度为$n$的序列，你有一次机会选中一段连续的长度不超过$d$的区间，将里面所有数字全部修改为$0$。请找到最长的一段连续区间，使得该区间内所有数字之和不超过$p$数据范围：$1 \le d \le n \le 2000000,0 \le p \le 10^{16}$题解首先能够想到枚举区间左右端点$l,r$，再减去区间内和最大的一段，用前缀和表示为$$s[r]-s[l-1]-\...

题意维护一个长度为$n$的序列，一开始都是$0$，支持以下两种操作：$U \ k \ a$ 将序列中第$k$个数修改为$a$$Z \ c \ s$ 在这个序列上，每次选出$c$个正数，并将它们都减去$1$，询问能否进行$s$次操作每次询问独立，即每次询问不会对序列进行修改数据范围：$1 \le n,m \le 1000000$题解对于一个询问，记$\ge s$的数有$x$个，$< s$...