- 博客(236)
- 收藏
- 关注
RSS订阅原创 CodeForces 1475G Strange Beauty （dp）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列，让你删除一些元素使得剩余的元素满足 i∣ji|ji∣j 或 j∣ij|ij∣i ，求最小的删除元素个数题目分析：我们知道整除具有传递性，即若 i∣j,j∣ki|j,j|ki∣j,j∣k 则有 i∣ki|ki∣k所以我们可以设 dp[i]dp[i]dp[i] 表示以 iii 结尾的满足条件的序列的最长长度故有转移方程：dp[i]=max(dp[j])+cnt[i]dp[i]=max(dp[j])+cnt[i]dp[i]=max(dp[j]
2022-05-07 18:53:01
388
原创 CodeForces 1661D Progressions Covering（思维，线段树）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列 aia_iai ，你可以执行一个操作：选定一个区间 [l,r]（长度小于等于k）[l,r]（长度小于等于 k）[l,r]（长度小于等于k） ，然后让 a[l]−=1,a[l+1]−=2,...,a[r]−=(r−l+1)a[l]-=1,a[l+1]-=2,...,a[r]-=(r-l+1)a[l]−=1,a[l+1]−=2,...,a[r]−=(r−l+1) ，即区间减去一个首项为 111 公差为 111 的等差数列求最小操作次数使得所有
2022-04-10 19:50:16
569
2
原创 P1438 无聊的数列（线段树维护等差数列）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列 aia_iai ，有两种操作：1 l r K D1\ l\ r\ K\ D1 l r K D：给出一个长度等于 r−l+1r-l+1r−l+1 的等差数列，首项为 KKK，公差为 DDD，并将它对应加到 [l,r][l,r][l,r] 范围中的每一个数上。2pos2 pos2pos 询问 aposa_{pos}apos 的值题目分析：不难发现等差数列相邻
2022-04-10 19:40:10
359
原创 CodeForces - 615D Multipliers （欧拉降幂）
题目链接：点击这里题目大意：给定一个正整数 nnn ，求其所有约数的乘积，即求 ∏d∣ndmod 1e9+7\prod\limits_{d|n}d \mod 1e9+7d∣n∏dmod1e9+7题目分析：将 nnn 用唯一分解定理展开 n=∏i=1xpiain=\prod_{i=1}^xp_i^{a_i}n=∏i=1xpiai ，逐个质数考虑贡献：对于 piaip_i^{a_i}piai 来说，自己有 1+2+...+ai=ai⋅(ai+1)21+2+...+a_i=\frac{a_
2022-03-21 22:06:29
244
原创 CodeForces 1382D Unmerge （思维，背包）
题目链接：点击这里题目大意：题目分析：发现，对于每一个 xxx 若后面是 y,zy,zy,z 且 x>y,x>zx>y,x>zx>y,x>z 那么 xxx 和 y,zy,zy,z 一定是同一组的，然后利用这个性质将序列划分，再对划分好的数组长度跑一下背包看其是否可以恰好组成两个长度为 nnn 的序列即可具体细节见代码：// Problem: B - Unmerge// Contest: Virtual Judge - 康复训练01// URL: https
2022-03-21 22:05:23
228
原创 CodeForces - 433C Ryouko‘s Memory Note（思维，结论）
题目链接：点击这里题目大意：给出 222 个正整数 n,m(1≤n,m≤105)n,m(1\le n,m \le 10^5)n,m(1≤n,m≤105) ，接下去给出 a1,a2,⋯am(1≤ai≤n)a_1,a_2,\cdots a_m(1\le a_i\le n)a1,a2,⋯am(1≤ai≤n) 你可以把这个序列里所有值为 aia_iai 的元素改成 aj(1≤i,j≤m)a_j (1\le i,j\le m)aj(1≤i,j≤m) ，注意 iii 可以等于 jjj ，只可以改一次。
2022-03-21 22:02:13
429
原创 CodeForces - 1634F Fibonacci Additions （思维）
题目链接：点击这里题目大意：已知两个长度相同的数组 AAA ，BBB ，给出若干次操作，每次操作后你需要求出取模过后的数组 AAA，BBB 是否相等。有两个长度都为 nnn 的数列 A,BA,BA,B，同时他会进行 qqq 次操作。对于每一次操作，他会先选择其中一个数列 (A/B)(A/B)(A/B)，再选择一个区间 [l,r](1≤l≤r≤n)[l,r](1≤l≤r≤n)[l,r](1≤l≤r≤n)，将选定的序列 [l,r][l,r][l,r] 中的数对位加上 Fibonacci\t
2022-03-19 19:33:38
174
原创 P2852 [USACO06DEC]Milk Patterns G（后缀数组+二分+单调队列）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列 a[i]a[i]a[i] ，求至少重复 kkk 次的重复子串的最长长度题目分析：我们知道 lcpi,j=min(lcpi,i+1,lcpi+1,i+2,...,lcpj−1,j)lcp_{i,j}=min(lcp_{i,i+1},lcp_{i+1,i+2},...,lcp_{j-1,j})lcpi,j=min(lcpi,i+1,lcpi+1,i+2,...,lcpj−1,j)所以要找至少重复 kkk 次的重复子串的最长长度，只需要
2022-03-18 08:17:39
182
原创 P2870 [USACO07DEC]Best Cow Line G（后缀数组）
题目链接：点击这里题目大意：给定一个长度为 nnn 的字符串，每次只能从两边取字符，加入到答案字符串中，求字典序最小的答案字符串题目分析：不难想到一个贪心策略，每次把两端中字典序小的字符加到答案字符串中去，但是这只限于字母不同。考虑如何处理两端字符相同的情况：我们设此时的左右端点为 l,rl,rl,r ，那么就看 lll 从左往右看的字符串和 rrr 从右往左看的字符串谁的字典序大即可为了实现这个效果，只需要把原字符串反转后接到原串上，然后对新串处理个后缀数组，用 rkrkrk 数组比大小即可
2022-03-18 08:17:21
204
原创 P4051 [JSOI2007]字符加密（后缀数组）
题目链接：点击这里题目大意：题目分析：不难想到把字符串再复制一遍贴到原串末尾来达到破环为链的效果。这样题目所需要排序的这 nnn 个串都以后缀的前缀的形式出现了。接下来只需要给这 2∗n2*n2∗n 个后缀排序即可，此由于串很长，所以采用后缀数组对后缀进行排序。得出 sasasa 数组后，只需要遍历前 nnn 个后缀的排名即可，然后让其按排名输出其对应串的最后一个字符。对于如何找这 nnn 个后缀的排名，只需要遍历 sasasa 数组，这样就保证了查找的后缀一定是按排名遍历的，然后找到 sa[
2022-03-15 14:27:42
164
原创 P3809 【模板】后缀排序（后缀数组模板）
题目链接：点击这里题目大意：读入一个长度为 nnn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII\text{ASCII}ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 111 到 nnn。题目分析：本题求的是字符串的 sasasa 数组下面记录一下后缀数组的各个变量的含义：x[i],y[i]x[i],y[i]x[i],y[i] 分别为基数排序的两个关键字c[i]c[i]c[i] 是基数排序的桶sa[i
2022-03-15 14:26:24
230
原创 CodeForces - 1646E Power Board （思维，数学）
题目链接：点击这里题目大意：给定一个 n×mn\times mn×m 的矩阵，其中 a[i][j]=ija[i][j]=i^ja[i][j]=ij ，求这个 n×mn\times mn×m 的矩阵有多少个不同的元素一个 3×33\times 33×3 的矩阵如下图所示：题目分析：不难想到，如果两行有相同的元素，那么两行中必然分别存在一个 aba^bab 和 aca^cac例如第 2,4,82,4,82,4,8 行其元素分别为：21,22,...,2m2^1,2^2,...,2^m21,22,
2022-03-05 13:24:52
606
1
原创 P5502 [JSOI2015]最大公约数（结论，ST表）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列 aia_iai ，你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。即求： maxl≤r(r−l+1)⋅gcd(al,al+1,...,ar)max_{l\le r}(r-l+1)·\gcd(a_l,a_{l+1},...,a_r)maxl≤r(r−l+1)⋅gcd(al,al+1,...,ar)题目分析：一个经典结论：长度 nnn 的序列的所有子序列的最大公
2022-02-19 17:04:00
310
原创 AtCoder - arc083_b Restoring Road Network（思维，最短路）
题目链接：点击这里题目大意：已知任意两点间的最短路长度，求原图边权和的最小值题目分析：nnn 很小，多元最短路考虑 floydfloydfloyd ，我们对当前图做一次 floydfloydfloyd ，如果存在 a[i][j]>a[i][k]+a[k][j]a[i][j]>a[i][k]+a[k][j]a[i][j]>a[i][k]+a[k][j] 就说明原图中的 a[i][j]a[i][j]a[i][j] 不是最短距离，属于无解情况我们先令答案 res=∑a[i][j]res
2022-02-18 13:56:41
120
原创 P4931 [MtOI2018]情侣？给我烧了（加强版） （错位排列）
题目链接：点击这里题目大意：一个电影院有 nnn 排座椅，每排座椅有两个座位，现在有 nnn 对情侣（每对情侣是一男一女两人），求有 kkk 对情侣坐在一起的方案数题目分析：有 kkk 对情侣坐在一起，就说明有 n−kn-kn−k 对情侣没有坐在一起，我们可以先将 kkk 对情侣安排入座，然后再对剩下的 n−kn-kn−k 对情侣进行一个错位排列首先考虑将 kkk 对情侣安排入座，其贡献为：Cnk⋅Ank⋅2kC_n^k·A_n^k·2^kCnk⋅Ank⋅2k其意义为先在 nnn 排座椅中
2022-02-16 11:01:16
590
原创 P3402 可持久化并查集
题目链接：点击这里题目大意：给定 nnn 个集合，第 iii 个集合内初始状态下只有一个数，为 iii。有 mmm 次操作。操作分为 333 种：1 a b1\ a\ b1 a b 合并 a,ba,ba,b 所在集合；2 k2\ k2 k 回到第 kkk 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；3 a b3\ a\ b3 a b 询问 a,ba,ba,b 是否属于同一集合，如果
2022-02-14 20:30:23
254
原创 P1891 疯狂 LCM（欧拉函数）
题目链接：点击这里题目大意：求 ∑i=1nlcm(i,n)\sum_{i=1}^nlcm(i,n)∑i=1nlcm(i,n)题目分析：思路同 月月给华华出题我们知道 lcm(i,n)=i⋅ngcd(i,n)lcm(i,n)=\frac{i·n}{\gcd(i,n)}lcm(i,n)=gcd(i,n)i⋅n所以题目所求就转化成了∑i=1ni⋅ngcd(i,n)=n⋅∑i=1nigcd(i,n)\sum_{i=1}^n\frac{i·n}{\gcd(i,n)}=n·\sum_{i=1}^n
2022-02-14 17:38:35
246
原创 P7884 【模板】Meissel–Lehmer 算法（亚线性求素数个数）
题目链接：点击这里题目大意：给定整数 nnn ，求出 π(n)\pi(n)π(n) 的值。其中 π(n)\pi(n)π(n) 表示 1∼n1 \sim n1∼n 的整数中质数的个数。题目分析：min25min25min25 在求素数个数上被此算法完爆（此题 min25min25min25 求 101310^{13}1013 的数据会 ttt 飞）Meissel–Lehmer\text{Meissel–Lehmer}Meissel–Lehmer 算法时间复杂度 101310^131013 以内为
2022-02-13 14:26:27
594
原创 POJ - 3090 Visible Lattice Points （数学，四种做法）
题目链接：点击这里题目大意：题目分析：本题需要一个重要的转化：仔细观察上图，我们会发现：当一个点的横坐标和纵坐标的 gcd\gcdgcd 大于 111 时就会被遮挡，即 gcd(x,y)≠1\gcd(x,y)≠1gcd(x,y)=1 的点会被遮住所以题目所求就是：2+∑i=1n∑j=1n[gcd(i,j)=1]2+\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]2+∑i=1n∑j=1n[gcd(i,j)=1]（其中2是x=0 || y=0的贡献）所以便有
2022-02-11 20:03:26
563
3
原创 POJ - 2480 Longge‘s problem （欧拉函数）
题目链接：点击这里题目大意：给定正整数 n(1<n<231−1)n(1<n<2^{31}-1)n(1<n<231−1) ，求：∑i=1ngcd(i,n)\sum_{i=1}^n\gcd(i,n)i=1∑ngcd(i,n)题目分析：∑i=1ngcd(i,n)\sum_{i=1}^n\gcd(i,n)i=1∑ngcd(i,n)=∑d∣n∑i=1n[gcd(i,n)=d]⋅d=\sum_{d|n}\sum_{i=1}^n[\gcd(i,n)=d]·d=d∣
2022-02-11 15:13:03
349
转载 kuangbin几何模板
转自：https://kuangbin.github.io/2019/04/28/20190428/#more二维几何：// `计算几何模板`const double eps = 1e-8;const double pi = acos(-1.0);const int maxp = 1010;//`Compares a double to zero`int sgn(double x){ if(fabs(x) < eps)return 0; if(x < 0)return -1;
2022-02-10 22:07:02
174
原创 2022牛客寒假第二场 小沙的remake （排序+树状数组优化dp）
题目链接：点击这里题目大意：给定两个长度为 nnn 的序列 a[i],b[i]a[i],b[i]a[i],b[i]对于 a[i]a[i]a[i] 序列，我们按顺序选择，对于每个 a[i]a[i]a[i] 有选与不选两种选择，当且仅当 a[i]a[i]a[i] 比前面的选择的元素大 时才可被选择，选择还有一个位置限制：只有在 [i−bi,i)[i-b_i,i)[i−bi,i) 下标内有元素被选择时 a[i]a[i]a[i] 才可被选择对于选择方案来说，如果有一个选择不同即认为是一种不同的方案，求总方
2022-02-04 22:00:12
711
原创 2022牛客寒假第二场 小沙的魔法（思维，并查集）
题目链接：点击这里题目大意：你有 nnn 个点，和 mmm 条边，每个点初始值 xi=0x_i=0xi=0。初始的时候图上没边，你可以进行两种操作：1：在 mmm 条边里面选择一条没有被选过的边加入图中2：将图中的一个极大连通子图中的每个点权值 +1+1+1 .你需要使得对于任意的 iii ，都有想 xi=aix_i =a_ixi=ai 。你可以最多可以执行 min(5∗n,m)min(5*n,m)min(5∗n,m) 次操作 111 。请问你最少进行多少次操作 222 。给定边可能出现重
2022-02-04 19:39:12
244
原创 2022牛客寒假第二场 小沙的身法 （思维，树上两点距离）
题目链接：点击这里题目大意：题目分析：不难发现，此题是求树上两点的最近距离，此问题一般可以使用 dep[x]+dep[y]−2⋅dep[lca(x,y)]dep[x]+dep[y]-2·dep[lca(x,y)]dep[x]+dep[y]−2⋅dep[lca(x,y)] 来解决但是此题 xxx 到 yyy 的距离和 yyy 到 xxx 的距离不一定一样，所以此公式会有所限制，我们需要做出如下优化：因为我们发现从高到低和从低到高的，所以我们可以建立两个高度为 000 的虚拟节点，一个连 xxx ，
2022-02-03 21:51:12
775
原创 2022牛客寒假第二场 小沙的炉石（思维）
题目链接：点击这里题目大意：初始时，你有 111 点体力；有 nnn 张攻击牌，每张攻击牌可以消耗 111 点体力并造成 111 点基础伤害；有 mmm 张法术牌，每张牌恢复 111 点体力（体力 无上限）；每次使用一张牌后会使之后的攻击牌增加 111 点伤害，求是否可以使用这些牌恰好造成 kkk 点伤害题目分析：我们不妨设 n≤m+1n\le m+1n≤m+1 （若 n>m+1n>m+1n>m+1 时可以看作 n=m+1n=m+1n=m+1 ，因为多余的攻击牌会因缺少体力而无法使
2022-02-03 21:36:40
458
原创 2022牛客寒假第一场 炸鸡块君与FIFA22 （线段树）
题目链接：点击这里题目大意：给定一个长度为 nnn 的字符串，mmm 次询问，每次询问 [l,r][l,r][l,r] 区间以起始 sss 分的最终得分得分规则为遇到 WWW 加一分，遇到 DDD 分数不变，遇到 LLL 若此时分数不是 333 的倍数则减一分题目分析：我们可以用线段树维护区间 [l,r][l,r][l,r] 以 xmod 3x\mod 3xmod3 分为起始的得分对于 pushup\text{pushup}pushup 来说根节点的值可以用左区间的值-对 333 的余数，再用
2022-01-24 22:13:45
446
原创 2022牛客寒假第一场 B站与各唱各的 （期望）
题目链接：点击这里题目大意：有 nnn 个人和一个长度为 mmm 的序列。每个人对序列的每个元素都可以选或不选，如果某个元素被 000 或 nnn 个人选中就算该元素被删除掉，在人们不互相沟通且做出最优选择的前提下，求该序列剩余元素个数的期望题目分析：我们可以发现，对于序列的不同位置，是相互独立的，因此期望就是单个元素的期望乘上 mmm 。因为每个都是在不能互相交流的情况下做出最优选择，所以他们对于同一个元素的选取概率是相同的不妨设第 iii 个人选该元素的概率为 ppp ，因此该元素被删掉的期
2022-01-24 20:06:16
249
3
原创 CodeForces - 1200E Compress Words （KMP）
题目链接：点击这里题目大意：给定 nnn 个字符串，求 nnn 个字符串按序拼接好后的字符串，拼接规则为找到最大的 i(i≥0)i(i\ge 0)i(i≥0) ，满足第一个单词的长度为ii的后缀和第二个单词长度为 iii 的前缀相等，然后把第二个单词第ii位以后的部分接到第一个单词后面。输出最后那个单词题目分析：最长公共前后缀不难想到 KMPKMPKMP ，我们发现如果想合并 aaa 串和 bbb 串，只需要构造一个 b,ab,ab,a 的串即可，对这个串求一下 nextnextnext 数组，然后
2022-01-24 19:04:19
342
1
原创 P3375 【模板】KMP字符串匹配（KMP模板）
题目链接：点击这里题目大意：题目分析：KMP\text{KMP}KMP 模板，nxt[i]$ 表示前 iii 个字符构成的非本身的最长公共前后缀长度，可通过自己匹配自己获得具体细节见代码：// Problem: P3375 【模板】KMP字符串匹配// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3375// Memory Limit: 512 MB// Time Limit: 1000 ms// // Power
2022-01-24 19:04:04
284
原创 upc 数字游戏 （质因子分解）
题目大意：Alice的父亲是一个伟大的数学家，他很喜欢和Alice一起玩数学游戏，这次他写下一系列的数，告诉Alice可以进行以下操作：选择序列中的任意两个数A和B，再选择一个能整除A的素数X，然后用A/X替代A，用B*X替代B。上述操作可以进行任意次，最终得分为数列中所有数的最大公约数。请你帮助Alice获得最大得分。题目分析：不难发现这个操作就是把质因子的指数进行了均分，所以可以把这 nnn 个数都质因子分解一下，然后再遍历一遍存指数的桶，把值均分给这 nnn 个数即可具体细节见代码：
2022-01-21 23:05:30
2243
原创 vijos1204 CoVH之柯南开锁（最小点覆盖）
题目链接：点击这里题目大意：给定一个 m×nm\times nm×n 的矩阵，矩阵有 0/10/10/1 两种取值，每次操作可以把一行或者一列的元素全变成 000 ，求最少需要几次操作可以把矩阵所有元素全变成 000题目分析：我们可以把矩阵的行列看成二分图的两个集合，如果 a[i][j]=1a[i][j]=1a[i][j]=1 就表明第 iii 行和第 jjj 列有一条边，题目就相当于变成了删除最少的点使得删除该图上的所有边，即求该图的最小点覆盖König定理：二分图的最大匹配等于这个图的最小点覆
2022-01-20 15:30:10
245
原创 P1129 [ZJOI2007] 矩阵游戏（二分图匹配）
题目链接：点击这里题目大意：给定一个 n×nn\times nn×n 的矩阵，每个元素有 0/10/10/1 两种可能 ，可以交换两行或两列，问是否可以通过若干次交换使得矩阵的主对角线上元素都是 111题目分析：可以将行和列抽象成二分图的两个集合，每行每列都是对应集合的一个元素，然后认识 a[i][j]=1a[i][j]=1a[i][j]=1 就是 i,ji,ji,j 有一条边仔细分析后我们会发现，交换行只是相当于给行重命名了，并不改变原图的形状。即我们可以在保持当前二分图结构不变的情况下，把一侧
2022-01-20 14:52:32
344
原创 P3386 【模板】二分图最大匹配（匈牙利算法模板）
题目链接：点击这里题目大意：给定一个二分图，其左部点的个数为 nnn ，右部点的个数为 mmm ，边数为 eee ，求其最大匹配的边数。题目分析：本题使用的匈牙利算法完成的二分图最大匹配具体细节见代码：// Problem: P3386 【模板】二分图最大匹配// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3386// Memory Limit: 512 MB// Time Limit: 1000 ms// //
2022-01-20 14:27:28
259
原创 P2216 [HAOI2007]理想的正方形（二维st表）
题目链接：点击这里题目大意：有一个 n×mn \times mn×m 的整数组成的矩阵，现请你从中找出一个 k×kk \times kk×k 的正方形区域，使得该区域所有数中的最大值和最小值的差最小，求改最小值题目分析：二维 rmqrmqrmq 问题，可以使用二维 ststst 表解决，本题可以通过 O(n⋅mlog(k))O(n·m\log(k))O(n⋅mlog(k)) 预处理 O(n2)O(n^2)O(n2) 遍历所有可能来获取答案具体细节见代码：// Problem: P2216 [H
2022-01-18 23:19:47
242
原创 POJ - 2019 Cornfields（二维rmq）
题目链接：点击这里题目大意：给定一个 n×n(n≤250)n\times n(n\le 250)n×n(n≤250) 的方阵，以及 k(k≤105)k(k\le 10^5)k(k≤105) 个询问。每次询问以 (xi,yi)(x_i,y_i)(xi,yi) 为左上角，边长为 bbb 的子方阵中，最大值和最小值的差题目分析：设 dp[i][j][k][o]dp[i][j][k][o]dp[i][j][k][o] 表示以 (i,j)(i,j)(i,j) 为左下角的点，横纵坐标跨度分别为 2k,2o
2022-01-18 22:49:56
208
原创 P2852 [USACO06DEC]Milk Patterns G（二分答案+哈希）
题目链接：点击这里题目大意：给定一个长度为 nnn 的序列 a[i]a[i]a[i] ，求至少重复 kkk 次的重复子串的最长长度题目分析：答案具有单调性是显然的，考虑如何写 check(x)\text{check(x)}check(x) ，我们可以先对序列哈希一下，然后对于每一个长度为 xxx 的字串的哈希值都存到一个计数桶里（这里用的 mapmapmap 当桶），最后扫一遍桶，看是否有次数大于等于 kkk 次的哈希值即可判段当前长度是否合法时间复杂度为 O(nlog2n)O(nlog^2n)O
2022-01-14 23:46:15
454
原创 等差数列（dp）
题目大意：给定一个长度为 nnn 的序列，现在希望修改最少的元素数量，使得修改之后的序列仍是一个等差数列题目分析：不难想到，希望修改次数最小，只需要找到一个原序列的最长等差数列，然后把不是该等差数列的元素修改成是该等差数列的元素。设 dp[i][d]dp[i][d]dp[i][d] 表示以 a[i]a[i]a[i] 结尾为的公差为 ddd 的最长等差数列长度转移方程为 dp[i][d]=max(dp[j][d]+1)dp[i][d]=max(dp[j][d]+1)dp[i][d]=max(dp[.
2022-01-14 16:00:01
711
1
原创 CodeForces - 182E Wooden Fence（计数dp）
题目链接：点击这里题目大意：给定 nnn 种长为 aaa ，宽为 bbb 的矩形，每种矩形可以使用任意次。现在要用这些矩形拼成一个长为 mmm 的大区域，这个区域满足如下条件：1.上一个使用的矩形必须于当前使用的矩形不同2.上一个使用的矩形的宽(b\text{b}b) 等于当前使用矩形的长(a\text{a}a)求能摆成长度为 mmm 的区域的方法有几种题目分析：不难想到是计数 dpdpdp 的问题，考虑如何设计状态：dp[i][j]dp[i][j]dp[i][j] 表示长度为 iii 的
2022-01-12 20:23:52
140
原创 CodeForces - 1624G MinOr Tree（贪心）
题目链接：点击这里题目大意：给定 nnn 个点， mmm 条边的一个图，求该条的最小或运算（or\text{or}or）生成树，即求其生成树中，所有边权或运算之最小的那个生成树题目分析：二进制逐位考虑，我们从高位向低位考虑，我们肯定希望高位尽可能为 000 ，那么我们就可以看这一位为 000 的那些边是否可以构成一颗生成树，如果可以，那么就把这一位是 111 的边标记上永不再用（因为选择这条边会使或运算的结果这一位为 111），往复此过程即可具体细节见代码：// Problem: G. MinO
2022-01-11 22:01:15
625
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人