zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15825535.html 状压dp的引入 状压DP，是用二进制的性质来描述状态的一种DP。 对于状压dp，我们要先了解一下位运算。 位运算 x&y 与运算，101&110=100 x|y 或运算，100|101=101 x^y 异或运算，101^100=001 x<<1 左移运算 x>>1 右移运算 状压dp 先看一道题： 在 n×nn\times nn×n 的棋盘上放 kkk 个国王，国王可攻击相邻...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15818532.html 数位dp的引入 首先假设有一天，我们遇见一道题： 求在 [a,b][a,b][a,b] 的区间里，满足条件的数有多少个。 如果我们没学过数位dp，我们会打出这样一个暴力： 12for(i=a; i<=b; ++i) if(check(i)) ++ans; 这样的时间复杂度是 O(n×check的时间复杂度)O(n\times \text{check的时间复杂度})O(n×check的时间复杂度) 当 a,b...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15818062.html 题目 在 n×nn×nn×n 的棋盘上放 kkk 个国王，国王可攻击相邻的 888 个格子，求使它们无法互相攻击的方案总数。 对于全部数据，1≤n≤10,0≤k≤n21≤n≤10,0≤k≤n^21≤n≤10,0≤k≤n2 思路 方法一：爆搜 方法二：状压dp 每行很大，不可能开个十几维数组，怎么办？ 把每行压成一个二进制！ 设 dp(i,j,x)dp(i, j, x)dp(i,j,x) 表示第 iii 行放置状态为 xx...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15817918.html 求： {S≡b1(moda1)S≡b2(moda2)⋯S≡bi(modai)⋯S≡bn(modan)\Large\begin{cases}S\equiv b_1\pmod {a_1}\\ S\equiv b_2\pmod {a_2}\\ \cdots\\ S\equiv b_i\pmod {a_i}\\ \cdots\\ S\equiv b_n\pmod {a_n}\\ \end{cases}⎩⎨⎧​S≡b1​(mo...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15817137.html 题目 原题来自：Romania OI 2002 求 ABA^BAB 的所有约数之和  mod 9901\bmod 9901mod9901。 思路 首先按照算术基本定理: A=p1k1×p2k2×⋯×pnkn\Large A=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_n^{k_n} A=p1k1​​×p2k2​​×⋯×pnkn​​ 所以： AB=p1k1×B×p2k2×B×...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15816368.html 上课记的，有点乱 「一本通 6.4 例 1」青蛙的约会 式子推倒 x+mt≡y+nt(modL)\Large x+mt\equiv y+nt\pmod L x+mt≡y+nt(modL) mt−nt≡y−x(modL)\Large mt-nt\equiv y-x \pmod L mt−nt≡y−x(modL) (m−n)t≡y−x(modL)\Large (m-n)t\equiv y-x \pmod L (m−n)t≡y...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15813525.html 题目链接 题目 设一个 nnn 个节点的二叉树 tree\text{tree}tree 的中序遍历为(1,2,3,…,n)(1,2,3,\ldots,n)(1,2,3,…,n)，其中数字 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 iii 个节点的分数为 did_idi​，tree\text{tree}tree 及它的每个子树都有一个加分，任一棵...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15812840.html 题目 原题来自：2014 年湖北省队互测 Week2 「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，Madoka 与 QB 签订了契约。 这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的 H...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15812544.html 题目 Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJ不愿让他的奶牛们看到这些内容。 FJ已经根据杂志的所有文字，创建了一个字符串 SSS ( SSS 的长度保证不超过 10610^6106 )，他想删除其中的子串 TTT ,他将删去 SSS 中第...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目 原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 思路 首先，我们如果有三点： 一个字符串的循环节必然是字符串长度的约数 循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节 如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...