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

发布(11) 刷题

2021-02-26 12:20

数据分析师

系数题解(lucas+思维)

题目链接 题目思路 这个题目的关键就是 答案模3 要利用这个来突破 令 则 因为 显然只有 那么就可以得证 则 那么 使用lucas求解 时间复杂度 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long ll; const int maxn=3e4+5,inf=0x3f3f3f3f,mod=1e9+7; const int eps=1e...

0 点赞评论收藏

转发

2021-02-26 11:08

数据分析师

动态最小生成树题解(线段树+归并排序)

题目链接 题目思路 看到单点修改，区间查询其实很容易想到线段树 但是这个线段树有点特殊 线段树的每个节点代表这个区间的最小生成树的所有边，用vector存 那么每个节点最多n-1条边 你每次合并使用类似归并排序就是 如果暴力合并就是 那么使用归并排序总的时间复杂度就是 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long ll; con...

0 点赞评论收藏

转发

2021-02-24 22:55

数据分析师

组合数问题题解(虚数)

题目链接 题目大意 计算 题目思路 如果是计算 显然 两式相加 而下面就有点神奇要类比，想到虚数第一次真想不到 而 则 则 而 最终 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5,mod=998244353; ll n; ll qpow(ll a,ll b){ ll ans=1,base=a; while(b){ if(b&1){ ans=ans*base%mod; ...

0 点赞评论收藏

转发

2021-02-23 13:43

数据分析师

Spy Syndrome 2 题解(dp+hash)

题目链接 题目思路 这个题目算是一个经典的dp 设表示以i结尾的最后一个字符串的序列是 hash预处理 然后计算答案直接回溯即可 复杂度 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; cons...

0 点赞评论收藏

转发

2021-02-21 10:04

数据分析师

I 九峰与分割序列题解(线段树维护dp)

题目链接 题目思路 首先要想到一个dp模型 为右端点为i前一个子区间小于等于k的最大贡献 为右端点为i前一个子区间大于k的最大贡献 那么这样利用前缀和可以写出一个的dp 暴力dp #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int...

0 点赞评论收藏

转发

2021-02-18 15:39

数据分析师

Train Hard, Win Easy 题解(sort)

题目链接 题目大意 题目意思真的有点难懂 总共有个人 就是每个人都会与其余个人进行两两配对 每个人都有自己的两个权值 若配对则每个人的权值加 而有个不能配对两两的关系 求每个人最后的权值 题目思路 其实很简单就是sort一下 然后不能配对的久直接减去即可 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long ll; typedef pa...

0 点赞评论收藏

转发

2021-02-18 10:44

数据分析师

Subsequences (hard version) 题解(dp求不重复子序列)

题目链接 题目大意 给你一个长度为的字符串 要你找出个不同的子序列，使得k个不同的子序列总价值最小是多少 一个子序列的价值为删去的字符长度 空串也为子序列 题目思路 其实不难就是要明白怎么设dp方程 设 为前i个字符构造长度为j的不同子序列长度 显然 就是选和不选第i个字符的问题 但是会有重复 假设我们之前有个序列是staxya，那么如果我们现在选的是i=6,j=2的情况，如果我们直接按照上面计算我们就会选择前5个选1个字母和a组合，会出现sa,ta这种情况，还会选择直接前面5个数直接组成2个字母的情况。那么又会计算到sa,ta这种情况，那么多出来的部分是不是就是选定最近出现的位置并且保证这个...

0 点赞评论收藏

转发

2021-02-09 20:42

数据分析师

Dima and Salad 题解(01背包变形)

题目链接 题目大意 给你n个物品，每个物品有两个值一个为a，一个为b 要你拿任意的物品使得 题目思路 一个显然易见的思路设为是否有 然后最后复杂度为 显然不行 所以考虑化简 把这个问题转化为每个物品重量为 价值为 转化为变为01背包 然后由于有负数，所以把背包的初始体积平移一下即可 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef long long...

0 点赞评论收藏

转发

2021-01-31 20:54

数据分析师

济南 Tree Constructer 题解(二分图染色+构造)

题目大意 给你一颗树(n<=100) 要你给点赋权值，如果x|y= 则代表x和y有边 题目思路 只要没有回路的图都可以看作是一个二分图 把这个想成二分图染色 想成白点和黑点（白点个数<黑点个数） 白点的第59位为0，以及白点的id位为0，给每个白点赋值一个不同的id，其他位白点均为1 黑点则看与周围的白点id，所有与黑点相邻的白点id为1，其他为0 显然这样成立 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<&l...

0 点赞评论收藏

转发

2021-01-27 15:21

数据分析师

魔改森林题解(dp+容斥+组合数学)

题目链接 题目大意 给你一个n*m的方格图，中间有k个障碍，要你求从左下角到右上角有多少种方案mod 998244353 题目思路 这个题目真是很oi......首先 直接 如果方格数量很多，观察障碍物很少，则可以想到容斥的思维 然后再用组合数学预处理一下 一定要注意要预处理到2e5 wa了我一辈子 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE"<<endl; using namespace std; typedef ...

0 点赞评论收藏

转发

2021-01-25 13:28

数据分析师

均分数据题解（随机贪心）

题目链接 题目大意 把n个数分为m组 每一组相当于一个新的数，为这组所有数之和 求这m个数的均方差最小 题目思路 本来我一直是把数大的先放，然后数小的后放，疯狂贪心 结果还是只能过60% 其实可以直接随机数组，然后贪心 每次直接放在最小的那个组里面 因为显然每个数尽量接近使得均方差最少 代码 #include<bits/stdc++.h> using namespace std; const int maxn=20+5,inf=0x3f3f3f3f; const int eps=1e-6; int n,m; int a[maxn]; int zu[7]; double ans=i...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务