考试读错题了导致没有\(\text{AK}\)。 题目描述 \(\text{GISPZJZ}\)有一个长度为\(n\)的序列\(a_1,a_2,\dots ,a_n\)。序列的所有元素都是\(1\)或者\(2\)。我们称一序列是该序列的不下降...
解题报告
幻魔皇 题解【数列】【递推】【斐波那契树】
这个题暴力分倒是挺多的……正解也不是很难想 问题描述 幻魔皇拉比艾尔很喜欢斐波那契树,他想找到神奇的节点对。 所谓斐波那契树,根是一个白色节点,每个白色节点都有一个黑色节点儿子...
神炎皇 题解【数学】【gcd】【欧拉函数】
怎么才能想到可以这样推啊……数学题做少了orz。 问题描述 神炎皇乌利亚很喜欢数对,他想找到神奇的数对。 对于一个整数对\((a,b)\),若满足\(a+b\le n\)且\(a+b\)是\(ab\)的因子,则成为...
洛谷 P1039 NOIp2003提高组 侦探推理 题解【模拟】【字符串】【枚举】
细节比较多的一道题。疯狂stl…… 题目描述 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中...
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
洛谷 P3959 NOIp2017提高组 宝藏 题解【状态压缩】【DP】【生成树】【贪心】
还是在NOIp2018前写出了这道2017谜之状压。 问题描述 参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了\(n\)个深埋在地下的宝藏屋,也给出了这\(n\)个宝藏屋之间可供开发的 \(m\)条...
最近公共祖先 题解【dfs序】【线段树】
煞笔题考场上没看出来……打了跟正解很接近的暴力… 题目描述 给定一棵\(n\)个节点的有根树,节点编号为\(1\sim n\),其中根节点为\(1\)号节点。每个节点都对应着一种颜色(黑/白)和一个固...
锦标赛游戏 题解【竞赛图】【递推】【排列组合】【构造】
解决竞赛图问题是需要一些技巧的。 问题描述 \(\text{YJC}\)很喜欢玩游戏,今天他决定和朋友们玩锦标赛游戏。 锦标赛游戏的规则是这样的:一共有\(i(1\le i\le n)\)个人参与游戏,每个...
密码游戏 题解【构造】【哈希】
转化比较多的一道题,还需要一定构造技巧。 问题描述 \(\text{YJC}\)很喜欢玩游戏, 今天他决定和朋友们玩密码游戏。 密码游戏的规则是这样的:初始时有两个大小为\(m\)的数组\(a\)和\(...
Tenka1 Programmer Contest 2018 D – Crossing 题解【构造】【模拟】
一道比较基础的构造题,需要正确的思路方向。 Problem Statement You are given an integer \(N\). Determine if there exists a tuple of subsets of \(\{1,2,\dots ,N\}, (S_1,S_2,…,S...