博弈论基础
概述 TonyYin学习博弈论的笔记(按学习顺序排列): P1288 取数游戏Ⅱ 【Luogu-P1288】取数游戏Ⅱ - 学习笔记 - TonyYin's Blog 巴什博奕 巴什博奕 - 学习笔记 - TonyYin's Blog 威佐夫博弈 威佐夫博弈 - 学习笔记 - TonyYin's Blog 必胜必败分析与SG函数 必胜必败分析与SG…
【ZROI-20普转提-Day1-T4】魔法师
$\rm{Description}$ 有 $m$ 次询问,每次询问给定一次操作。操作分为两种:向集合 $A$ 中添加一个物品或从集合 $A$ 中删除一个物品。对于每个物品,有两个属性: 物品的类别 $t_i$ 物品的威力 $p_i$ 现在要从集合 $A$ 中选取一个子集 $B$,使得 $B$ 中物品的威力和最大,且 $B$ 满足: 对于每个类别 $…
【Luogu-P2148】[SDOI2009]E&D
$\rm{Description}$ 有 $2n$ 堆石子,编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$,归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$. 定义分割操作: 任取一堆石子,不妨为第 $i$ 堆,将其全移走; 从和第 $i$ 堆同一组的石子中,取出若…
二分图 & 最大匹配 & 匈牙利算法
定义 二分图 对于一个无向图 $G=(V, E)$,可以将 $V$ 分为两个不相交的子集,使得任意一条边的顶点分属两个不同的点集,那么这个无向图是二分图。 匹配 对于无向图 $G=(V, E)$,取边集的子集 $E^*$,使得 $E^*$ 中任意两条边没有公共顶点,那么 $E^*$ 是图 $G$ 的一个匹配,又称边独立集。 最大匹配 边数最多的匹配…
【AT4540】Dight Sum
$\rm{Description}$ 求区间 $[1, k]$ 中有多少个整数满足:其十进制表示的数字和为 $D$ 的倍数。答案对 $1e9+7$ 取模。 $\rm{Solution}$ 观察数据范围:$1\leq k\leq 10^{10000}$. 再看题面,形如”求在数位限制下有多少满足条件的数“,想到数位 $\rm{DP}$. 如果你没有学…
【AT4846】 Max-Min Sums
$\rm{Description}$ 给定 $n$ 个数,构成集合 $A$。从 $A$ 中任取 $k$ 个数,构成 $A$ 的子集 $S$. 记 $\rm{Max}$ 为 $S$ 中的最大值,$\rm{Min}$ 为 $S$ 中的最小值,$f(S)=\rm{Max-Min}$. 题目要求:所有满足 $|S|=k$ 的 $f(S)$ 之和。(对 $1…
【AT2394】井井井 / ###
题目地址:AT2394 [ARC071B] 井井井 / ### - 洛谷 | 计算机科学教育新生态 $\rm{Description}$ 在平面直角坐标系中,给定 $n$ 条平行于 $y$ 轴的线和 $m$ 条平行于 $x$ 轴的线,求由这些线组成的矩形的面积和。 $\rm{Solution}$ $\rm{subtask}$ $\rm{1}$ 考虑…
【ZROI-19普转提-Day5-T3】 背包
题意 有 $n$ 个物品,编号为 $1$ ~ $n$,每个物品有重量 $w_i$,价值 $v_i$. 有 $m$ 个背包,编号为 $1$ ~ $m$,每个背包有容量上限 $t_i$. 物品 $i$ 能够放入背包 $j$,当且仅当 $t_j \geq w_i$。 现在选出 $n$ 个物品,使它们能够通过交换顺序满足:物品的重量和价值从左到右均单调不降…
【ZROI-19普转提-Day3-T4】DAG
原题面地址:【普转提七联测 Day 3】DAG - 题目 - Zhengrui Online Judge 题意 给出一个无向图,请你给边定向成为一个 $\rm{DAG}$,使得最长路最短。求这个最短长度。 $1\leq n\leq 8$,$1\leq m\leq 20$. 解法 $\rm{subtask}$ $\rm{1}$ 暴力? $\rm{su…
【Luogu-P1962】 斐波那契数列
P1962 斐波那契数列 题目地址:P1962 斐波那契数列 - 洛谷 | 计算机科学教育新生态 前置知识点 矩阵 定义: 一个$n\times m$矩阵是由$n\times m$个实数排列成$n$行$m$列构成的,用一对[]括起来。 下面$3\times 3$矩阵简记为$A=(a_{ij})_{3\times 3}$ $$ A=\left[ \b…