dilingtian

分类

题解(18)

/ 注册

全部文章（共17篇）

题解 | #[NOIP2007]守望者的逃离#

dpdpdp做法，先全用魔法更新一遍动态数组，然后再加入常规走法更新 AC代码 #include <bits/stdc++.h> using namespace std; const int N = 1e6; int dp[N]; int main(void) { int m, s, ...

动态规划贪心

2022-11-29

1 379

题解 | #被3整除的子序列#

如果一个数可以被333整除，那么这个数的每一位之和一定是333的倍数证明:题解 | 3的倍数定义：数组dp[i][j]dp[i][j]dp[i][j]表示以iii为结尾组成的子序列，数位之和对333取余为jjj的方案数动态转换方程： num=(s[i]−′0′)%3num=(s[i]-'0')...

动态规划

2022-11-28

1 423

题解 | #[NOIP2014]联合权值#

本题不能使用常规做法树形dp，因为相互之间没有联系，无法找到动态转换方程。所以我们换个思路，我们尝试遍历每个节点作为中转点，也可以称为根，那么它的两边的节点两两配对就可以符合题目的要求。我们将两边的节点的权值存入一个数组中，先排序，将数组的最后两个节点相乘就是本次最大的答案，不断更新就行。而且，...

前缀和树

2022-11-25

1 376

题解 | #小A与欧拉路#

树的直径题解树的直径树的直径的定义:图中两个叶子节点的最长距离定义d1[i]d1[i]d1[i]表示以iii为根节点到叶子节点的最长距离定义d2[i]d2[i]d2[i]表示以iii为根节点到叶子节点的次最长距离定义mp[i][j]mp[i][j]mp[i][j]表示从iii到jjj的...

欧拉路树的直径

2022-11-24

1 498

题解 | #兔子的区间密码#

结论：从高位计算，第一个不相同的之后全部为111 假设lll,rrr在第iii位开始不相同，iii位之前的异或之后全为000，之后的我们可以保证凑成不一样的，异或之后全部位111。这样我们的结果就是从iii开始往后全为111的二进制，将二进制转换位十进制输出即可。 AC代码 #include <...

二进制思维

2022-11-23

2 397

题解 | #求和#

玄学做法：打表找规律：名称缩写 a0a_0a0 1 a1a_1a1 3 a2a_2a2 8 a3a_3a3 20 a4a_4a4 48 ... ... ana_nan 2∗an−1+2n−12*a_{n-1}+2^{n-1}2∗an−1+2n...

快速幂数学

2022-11-19

1 404

小喵觅食

错误版本本题可以理解为矩阵上的单源最短路径，因为数据不是很大，我们可以使用BFS进行搜索PLMM和猫到达图中所有点的最短路径。但是题目加上了附属条件，PLMM走的步数是有限的，而且猫的嗅觉也是有限的。所以我们可以求完最短路径之后，找到一个可以同时满足两个要求的点，如果可以找到，则更新答案。不能则输...

BFS 最短路

2022-11-18

5 516

题解 | #乘积#

异或规则：只有同时出现1才结果为1，其他的全为0。即：1&1=1 1&0=0 0&0=0 ∏i=1n∏j=1nAi\prod_{i=1}^n\prod_{j=1}^nA_i∏i=1n∏j=1nAi&AjA_jAj 式中AiA_iAi&AjA_jAj...

数学暴力

2022-11-18

2 484

题解 | #3的倍数#

三的倍数判断条件：数位相加的和是否为三的倍数证明： abcabcabc =a∗100+b∗10+c=a*100+b*10+c=a∗100+b∗10+c =a∗99+b∗9+a+b+c=a*99+b*9+a+b+c=a∗99+b∗9+a+b+c 显然，a∗99+b∗9a*99+b*9a∗99+b∗9...

数论

2022-11-17

3 552

题解 | #[USACO 2007 Jan S]Protecting the Flowers#

贪心：假设如果有两头牛，往返的时间分别是tit_iti，每分钟摧毁的花是did_idi。那么我们可以得出： 1.先牵第一头牛，消耗的总数为t1∗d2t_1*d_2t1∗d2 2.先牵第二头牛，消耗的总数为t2∗d1t_2*d_1t2∗d1 我们使第一种情况消耗总数最小，可以列出t1∗...

贪心排序

2022-11-16

1 372