cheese_case - 个人主页动态 - 牛客网

发布(32) 评论刷题收藏

2023-11-17 22:00

清华大学 Java

题解 | #小辰的智慧树#

重点就是发现x*(hi*2-x)的最优解相当于每次取最大的hi砍x=1长度，易转化为区间加法问题 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int N = 2e6+50; int n,m,num[N]; struct node{ int h,c; }stu[N]; bool cmp(node a,node b){ if(a.h!=b.h)return a.h>b.h; else return a.c>b.c; } signe...

0 点赞评论收藏

分享

2023-08-18 23:22

清华大学 Java

题解 | #Mate in 33#F IUPC

题意: n个数 有t时间 每个时间可以选择一个合法的数（每个数只能选择一次），连续k个时间最多选m个，问有多少种方法数 思路：想到区间k状态必须要2^k表示对于t 300 ，剩余只有10+的空间给n，思考每次可以选择前缀所有，故每次可以可能可以选多个 看前一状态，若前一个状态选到j个那这个可以选到num[i]-j个 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int mod = 1e9+7; int n,t,m,k,dp[305][15]...

0 点赞评论收藏

分享

2023-08-18 23:13

清华大学 Java

题意: n个数 有t时间 每个时间可以选择一个合法的数（每个数只能选择一次），连续k个时间最多选m个，问有多少种方法数 思路：想到区间k状态必须要2^k表示对于t 300 ，剩余只有10+的空间给n，思考每次可以选择前缀所有，故每次可以可能可以选多个 看前一状态，若前一个状态选到j个那这个可以选到num[i]-j个 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int mod = 1e9+7; int n,t,m,k,dp[305][15]...

0 点赞评论收藏

分享

2023-07-30 12:20

清华大学 Java

题解 | #Qu'est-ce Que C'est?#

迫于大佬威压来写题解，J比较明显的状态设计 发现区间加法 直接上差分即可 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int N = 5010; const int mod = 998244353; int n,m,dp[N][N*2],num[N*2]; signed main() { cin>>n>>m; for(int i=-m;i<=m;i++)dp[1][i+m]=1; for(int i=2;i&...

0 点赞评论收藏

分享

2023-04-25 16:29

清华大学 Java

题解 | #小d和送外卖#

一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 dp[i][j]：以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度 下面直接上代码，里面有过程注释 #include<bits/stdc++.h> #define int long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 2e5+8; typedef long long ll; int n,m,k,dp[N][60],cnt[N],tmp[60]; v...

0 点赞评论收藏

分享

2023-04-25 16:27

清华大学 Java

F.小d和送外卖

一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 **dp[i][j]：**以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度 下面直接上代码，里面有过程注释 #include<bits/stdc++.h> #define int long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 2e5+8; typedef long long ll; int n,m,k,dp[N][60],cnt[N],tmp[60...

0 点赞评论收藏

分享

2023-04-25 16:27

已编辑

清华大学 Java

F.小d和送外卖

链接 一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 **dp[i][j]：**以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度 下面直接上代码，里面有过程注释 #include<bits/stdc++.h> #define int long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 2e5+8; typedef long long ll; int n,m,k,dp[N][60],cnt[N],tmp...

0 点赞评论收藏

分享

2022-07-20 14:31

清华大学 Java

2022.07.20 在牛客打卡6天！

0 点赞评论收藏

分享

2022-04-12 19:45

清华大学 Java

题解 | #进制#

感觉挺不错的一道线段树题目  首先考虑区间里面存什么，因为每次修改 区间不同进制的值都会跟着改变，最大值也会改变，故要保存所有区间2-10进制所有进制的区间和，合并区间时只需要将左区间*ksm(jin,lenright)即可，思路相对清晰 线段树的题目，只需要考虑区间维护什么，且如何合并

0 点赞评论收藏

分享

2022-04-02 11:41

清华大学 Java

题解 | # [HAOI2015]树上染色#

感觉是时候总结一下树形背包的题目了，虽然都是树形背包，但是不同题目细节却有着不小的区别，这里我由两道题来分析不同点（尤其是状态是否合法的考虑以及转移循环的范围限制，对于dp 范围的限制一直都算是一个细节考虑），一题是本题，还有一题是经典树上背包 ————选课 先上选课 https://www.luogu.com.cn/problem/P2014  这题不得了，算是板子和依赖背包转化 首先由于有依赖关系，转化为树形解决该问题，定义状态，dp[i][j][k]——以i节点为根的子树中到其第j个儿子处理完后，选了k个的最大收益 转移方程dp[i][j][k]=max(dp[i][j-1][k],dp...

0 点赞评论收藏

分享

2022-03-21 12:07

清华大学 Java

题解 | #区间价值#

看到还没有题解，那就来一发 相对于说这题是dp，我觉得更像是体现了数组预处理信息的一种递推，很巧妙的运用数组储存信息  由数据范围知肯定要提前预处理，时间复杂度为O(n),那么容易想到每个区间存在关联，比如f[4]比f[3]多了一个数，贡献在于f[3]中是否有此多出的数，转化一下问题 f【4】新增的数到之前最近出现位置的距离是否>=4，若大于则有贡献1，可推广到整个区间上的所有子区间 下面转移方程f[i]=f[i-1]+cnt[i]-diff[i-1],cnt[i]代表距离>=i的满足个数，因为整个区间包含多个所要更新的子区间，而总贡献即为cnt【i】，之前我们要先处理last[i...

0 点赞评论收藏

分享

2022-03-10 18:26

清华大学 Java

题解 | #黑白树#

这题容易想到要从下向上贪心，因为从一个点开始只能染色其以及其上方的一些点，而其下方的点需要额外考虑染色，故而从叶子节点开始考虑染色，叶子节点必须染色 其范围是k[i],但是并不是最上面一个点才继续染色，而是当前染色点所包含所有点染色后这些点所能达到的最远距离，如果还需要染色，则染可以更新最远距离相对应的点，故每个点都要更新其所能达到的最远距离，（可能是其k【i】也可能是其儿子/孙子的k），每次染色后走到当前点的极限距离无法继时，将还能走的距离更新程k【cur]，也就是当前点维护的染色后能走最远距离，并且总染色数++

0 点赞评论收藏

分享

2022-03-05 10:48

清华大学 Java

题解 | #筑巢#

这题有个小坑，很荣幸踩了进去 就是ans得初始化必须是-inf ， 各位可能会习惯性初始化为0  思路就是只有子点与相连边的和>0就选择它，反之不选，一个假冒伪劣的树形dp 因为建立树时写成了v[b].push_back[b]导致查不出错误，下次直接把头剁了  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+8; ll n,dp[N],a,b,w,aa[N],ans; vector<ll>v[N]; map<pair<ll,ll&g...

0 点赞评论收藏

分享

2022-02-07 15:26

清华大学 Java

题解 | 小沙的算数

写一个极简版的，思路：保存每一个有效数区间 例如 2+432+53+2 那就有4个区间要保存，分别为2,432,53,2用一个数组保存他们对应的值，考虑到一个区间中所有元素都要能查询到这个值，可以用两种方法    运用并查集，将乘法块中的每个数都指向其第一个元素     运用一个指针数组，pos[i]=cnt,来指向;    这里我们选用方法2 ，对于最开始有效块的处理是需要注意的，想了挺久如何简化这个代码 for(int i=2;i<=n;i++){ if(s[i-1]=='*'){ pos[i]=cnt; num[cnt]=num[cnt]*a[i]%mod; } else{ num...

0 点赞评论收藏

分享

2022-02-05 13:54

清华大学 Java

这题主要就是数中分离连通块的操作 相当于切边 其次就是逆元打表啦，重要公式:  inv[i]=((mod-mod/i)*inv[mod%i])%mod;   C与A  ll C(ll x,ll y){ return f[x]*inv[x-y]%mod*inv[y]%mod; } ll A(ll x,ll y){ return f[x]*inv[x-y]%mod; }   标准的逆元打表与逆元阶乘打表   f[0]=inv[0]=f[1]=inv[1]=1; for(int i=2;i<=305;i++){ inv[i]=((mod-mod/i)*inv[mod%i])%mod; f[i]...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务