分类-题解

题意一个有向图,求:至少选多少个起点才可以遍历整个图至少加几条边,能满足从任意一个点出发都能遍历整张图其中点数 $N\le 100$ 。题解显然可以先缩点,然后对题意进行转化:入度为 $0$ 的点的个数加最少的边,让整张图成一个环问题 $1$ 很显然,对于问题 $2$ ,可以把所有入度为 $0$ 和出度为 $0$ 的节点相连,所以答案即为两者的较大值。#include<bits/std...
   题解    0 条评论
提高+/省选-
题意有 $N$ 个长度相同的字符串,问恰好与其中 $K$ 个匹配的字符串有多少个。定义满足如下条件的字符串 $x$ 和 $y$ 为匹配的:$len_x=len_y$$\forall 1\le i\le len_x \ , \ x[i]='?' \ or \ x[i]=y[i]$其中 $N\le 15$ ,字符串长度 $len\le 50$ 。题解看数据范围,可以对 $N$ 进行状压。先预处理...
   题解    0 条评论
省选/NOI-
题意学生排队去食堂吃饭,每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间,之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。为了节省总等待时间,食堂有时会不按排队顺序做,但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。其中人数 $N\le 1000$ ,$\text{...
   题解    0 条评论
省选/NOI-
题意在 $N\times M$ 的棋盘上放若干个炮,要求不能互相攻击,求方案个数。其中 $N,M\le 100$ 。题解将题意转化一下就是每行每列都不能放超过 $2$ 个棋子,那么可以用 $f[i][j][k]$ 表示前 $i$ 行,有 $j$ 列是有 $1$ 个棋子,有 $k$ 列是有 $2$ 个棋子的合法方案数。那么没有棋子的列数即为 $M-j-k$ 。然后分类讨论。不放继承上一步的状态...
   题解    0 条评论
省选/NOI-
题意动物园的笼子环形排列,每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物,每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。定义每个小朋友是开心的,当且仅当下列条件之一满足:在视线范围内至少有一个喜欢的动物没被移走。在视线范围内至少有一个害怕的动物被移走。求最优方案,使得开心的小朋友尽可能多。其中动物数 $N\le 10000$ ,小朋友个数 $C\le 50000$ 。题解动...
   题解    0 条评论
省选/NOI-
题意在 $N\times M$ 的图中部署炮兵,只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格,求方案数。其中 $N\le 100,M\le 10$ 。题解跟 玉米田 差不多,但是因为前两行都对当前状态有影响,所以需要多一维。如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了,所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种,所...
   题解    0 条评论
提高+/省选-
题意在一个 $N\times M$ 的田地里种草,有的地方不能种,要求不能有两块相邻的。求方案数。其中 $N,M\le 12$ 。题解状压dp。把图存下来,每次枚举时判断状态合不合法即可。$$\text{f}[i][j]+=\text{f}[i-1][k]$$#include<bits/stdc++.h> #define ha 100000000 using namespace...
   题解    0 条评论
提高+/省选-
题意在 $N\times N$ 的棋盘里摆 $k$ 个国王,每个国王可以攻击周围 $8$ 个格子,求国王互不侵犯的摆法有多少种。其中 $N\le 9$ 。题解显然状压dp。可以预处理每一行的合法方案存在 $\text{s}[]$ ,合法方案即没有两个相邻的。用 $\text{f}[i][j][k]$ 表示在第 $i$ 行,合法方案编号为 $j$ ,放了 $k$ 个棋子的方案数。枚举上一行的状...
   题解    2 条评论
提高+/省选-
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问,求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ,询问数 $M\le 50000$ 。...
   题解    2 条评论
NOI/NOI+/CTSC
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问,求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ,询问数 $M\l...
   题解    0 条评论
NOI/NOI+/CTSC
题意一棵树,每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留,并获得权值。有如下操作:单点修改信仰值单点修改权值查询 $(x,y)$ 路径上权值和查询 $(x,y)$ 路径上权值最大值其中节点数 $N\le 100000$ ,操作数 $M\le 100000$ ,宗教个数 $C\le 100000$ 。题解显然每个宗教需要单独维护,但每个宗教开个线段树空间要爆,所以用动态开点线段树...
   题解    0 条评论
省选/NOI-
咕咕咕。
   题解    0 条评论
提高+/省选-
题意有 $N$ 个正整数,每次可以选相邻的相同的数合并,合并后得到的值为原数 $+1$ 。求合并后最大数的最大值。其中 $N\le 262144$ 。题解用 $f[i][j]$ 表示左端点为 $j$ ,能合并出 $i$ 这个数字的右端点的位置。显然 $i$ 是由 $i-1$ 转移过来的,所以我们要构造 $f[i-1][?]$ 。不妨考虑 $i+1$ ,在 $f[i][j]$ 这个右端点基础上...
   题解    0 条评论
提高+/省选-
题意一棵无根树,要求根节点到每个叶子的路径上都至少有一个有色节点。给出根节点到每个叶子节点路径上最后一个有色节点的颜色,求有色节点个数最小值。其中点数 $N\le 1000$ ,叶子节点个数 $M\le 5021$ 。(我按个人习惯反过来了)题解树形dp,用 $f[x][0/1]$ 表示以 $x$ 为根的子树,最后一个有色节点颜色为黑/白的最优情况。考虑状态转移,如果子节点和自己要求一样,则...
   题解    0 条评论
提高+/省选-
时隔半年再来做发现还是不会,于是乎还是写个总结吧。题意一棵二叉树,只能保留 $Q$ 条边,求剩下的边最大边权和。其中点数 $N\le 100$ ,$Q\le 100$ 。题解用 $f[x][j]$ 表示在以 $x$ 为根的子树上保留 $j$ 条边的最优情况。搜索时枚举 $x$ 的子节点 $y$ ,然后类比背包枚举以 $y$ 为根的子树保留的边数 $k$ ,得到状态转移如下:$f[x][j]=...
   题解    0 条评论
提高+/省选-