zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15838986.html 题目链接 题目 魔术师的桌子上有 nnn 个杯子排成一行，编号为 1,2,…,n1,2,…,n1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。 花费 cijc_{ij}cij​ 元，魔术师就会告诉你杯子 i,i+1,…,ji,i+1,…,ji,i+1,…,j 底下藏有球的总数的奇偶性。 采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？ 思路 前缀和建图...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/diary/15836742.html 六中集训Day3 又是痛苦的一天 上午讲dp 这dp还是人学的吗 掉线时间：上课开始的时候 好痛苦啊 上来就讲斜率 =最可恶的是，那个老师还把完成情况写到白板上，叫我们自己上来填 吐血 上午最欢乐的时光就是和hjh和cjl玩捉迷藏的时候了 呜呜呜呜呜呜 中午吃饭，喝了两碗汤 下午想去做上午的题，做不动 然后vp了一场cfdiv.3，然后D题就做不动了 然后听了一下lgl讲导数和对数，没太听懂 平淡的一天

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/diary/15834366.html 六中集训Day2 吐血的一天 啊啊啊！！！ 早上一个姓麦的人过来讲计数，然后… 几乎什么都听不懂，一开始讲简单容斥还好，后面就… min-max容斥勉强听懂一点 洛必达法则完全没听懂 然后旁边的人看到我写日记就过来和我勉强把洛必达法则讲懂了 他讲题的时候，基本上也听不懂 那些题目，一道比一道恶心 没错，就像吕欣讲课一样 到了后期，我全程在看ppt背景 话说，ppt背景还真好看 一直在鼓励自己，撑下去！ 然后就去吃...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/diary/15830975.html 六中集训day1 鹭江站下地铁，旁边就是六中了。 早上一来打模拟赛 T1感觉是个数位dp，打了打，然后就拍上了 T2感觉是个dp+组合数学，就是组合数学那里卡了一下，10点就过了样例 T3推了推，想不出正解，跳过 T4想了一下 n⩽20n\leqslant20n⩽20 的部分分，就是一个 O(2n)O(2^n)O(2n)，很快打出来 然后又发现 R≤2R\le2R≤2 的情况只能横着放，然后也打了一下 回去看T3...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15826957.html 题目 Gildong owns a bulgogi restaurant. The restaurant has a lot of customers, so many of them like to make a reservation before visiting it. Gildong tries so hard to satisfy the customers that he even memorized al...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：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×...