BNDSBilly

分类

题解(15)

/ 注册

全部文章（共15篇）

【每日一题】12月28日 Topforces Strikes Back

枚举第一个数为x去除x的所有倍数找到最大的数z去除z的所有约数找到最大的y答案为max(x+y+z) 代码如下： #include<bits/stdc++.h> #define ll long long #define pa pair<int,int> using names...

2020-12-28

0 799

【每日一题】12月18日 Necklace C++ 题解

如果有两种颜色的珠子个数是奇数个，那么魅力值就是0，任意输出一个串就可以。否则，魅力值一定是颜色个数的最大公约数。代码如下： #include<bits/stdc++.h> #define lalala printf("lalala\n"); #define N 35 using na...

2020-12-17

0 894

【每日一题】12月17日老瞎眼 pk 小鲜肉 C++ 题解

根据题意，我们可以使用复杂度求出以为右边界的左边界在哪，然后把所有的询问离线，按照右端点从小到大排序，维护一个棵线段树，结点代表以为右边界的最小区间长度，对于每个询问，只要把所有的右端点前的值更新到线段树中，再查询一次最小值即可知道答案。 #pragma comment(linker, ...

2020-12-16

0 791

【每日一题】12月16日 Superhero Battle C++ 题解

首先,回合数越少越好。我们发现,让boss剩下最多(但是在一个回合内能够击杀)的血量时回合数最少把boss的血量状态压缩，然后进行枚举，代码如下： #include <bits/stdc++.h> #define R register #define ll long long #def...

2020-12-15

0 838

【每日一题】树形dp专题消耗战 C++ 题解

对于每次询问，我们建一棵“虚树”这棵虚树只包括询问点以及相应的lca这样在虚树上dp复杂度为总复杂度为代码如下： #include <bits/stdc++.h> typedef long long ll; const int N = 250010; using namespace s...

2020-12-14

0 705

【每日一题】树形dp专题 Jimi Hendrix C++ 题解

每个节点记录四个量，从左到右最多匹配到第几个字符，以及初始的端点。从右到左最多匹配到第几个字符，以及初始的端点。 #include<bits/stdc++.h> using namespace std; const int N=5e5+7; int n,m; struct Edge{ ...

2020-12-14

0 607

【每日一题】树形dp专题 Betrayed C++ 题解

对于每一棵树，我们要统计以每个点为根的树的最长深度。树形DP统计最长链和次长链+换根就可以。现在得到统计每棵树的概率p[i]和不能通过的概率q[i]=(1-p[i])。dp[i]:从第1棵树到第i棵树的期望时间。dp[i]=dp[i−1]+q[i]∗(1)+pi我们在第i-1棵树的时候。尝试一次。p...

2020-12-14

0 698

【每日一题】树形dp专题 Minimax Tree C++ 题解

因为最大值和最小值求法对称，以求最小值为例。要让尽量小的上来，可以贪心选择一条路前面都是min不够了后面就用max。因为如果min上面有max，max换到下面不会更差。但是这条前面都是min的路选哪一条呢？显然是最后一个min节点的子节点里max取最小的。共k个min，所以取第k+1层所有节点的...

2020-12-14

0 850

【每日一题】树形dp专题 [JLOI2016]侦察守卫 C++ 题解

我们设计状态 g[i][j]表示当前在i节点，处理到了第k棵子树时，还能向外扩展j层的最小花费。 f[i][j]表示当前在i节点，处理到了第k棵子树时，在i节点的子树中向下还有j层没有被覆盖时的最小花费。那么状态转移(现在在点u,v为新子树)： g[u][j]=min(g[u][j]+f[v][j...

2020-12-14

0 751

【每日一题】树形dp专题 [SHOI2014]概率充电器 C++ 题解

首先我们考虑一个点连上它子树的不通电概率(这里转化为"不"是为了方便算,不转化也能做)有:f[u]=∏i(f[vi]+(1−f[vi])∗(1−wi))注意到v不通电和v通电但边不通电是互斥事件,故我们可以把概率直接加起来对于子树以外的部分,直接换根dp就行,详见代码: #include <...

2020-12-14

0 689