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

发布(419) 评论刷题

2020-12-17 17:01

已编辑

南开大学 Java

min25筛前n项素数个数的板子

ll s[320010]; ll a[320010]; ll b[320010]; double inv[320010]; inline ll Prime(ll N) { ll S = sqrt(N); for (int i = 1; i <= S; ++i) a[i] = i, s[i] = i, b[i] = N / i, inv[i] = 1.0 / i; s[S + 1] = S + 1, s[S + 2] = S + 2; for (int p = 2; p <= S; ++p) if (a[p] != a[p - ...

0 点赞评论收藏

分享

2020-12-17 16:59

已编辑

南开大学 Java

题目链接：http://codeforces.com/contest/1421/problem/D D. Hexagons time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Lindsey Buckingham told Stevie Nicks “Go your own way”. Nicks is now sad and wants to go away as quickly as possible, but she lives ...

0 点赞评论收藏

分享

2020-12-17 16:59

已编辑

南开大学 Java

E. Carrots for Rabbits（贪心）

题意： 有n个萝卜 ，每根萝卜长度不一样，现在将这些萝卜分为k段 这k根萝卜每根萝卜的花费是长度的平方，求最小的花费。 思路： 原本想的是放进将萝卜放进大根堆，然后取最大的对半分，其实这样是不正确的，hack数据：3 5 10 3 1 如果按照对半分的思路来 就是分为 2 3 5 3 1 ，然而最优解是 3 3 4 3 1，那就是不正确的，那么我们换一种思路，如果知道每一根萝卜分为z段 ，那么每根萝卜的最优解就是均分，那么有个大胆的想法就是将每个萝卜的当前最小花费和多分一段的最小花费的差值放进大根堆里面，然后执行k-n次，每次就减去最大值，不得不说太优秀了这个想法。 ac代码： #inclu...

0 点赞评论收藏

分享

2020-12-17 16:58

南开大学 Java

E - Two Round Dances

题意：给定n个人 ，n为偶数 ，让它平均分为两组，然后如果两个序列他们的圆排列相同那他们就等价，例如 4,1,2,3 和 3,4，1,2是等价的，问有多少种分法。 思路：好多人都是查oeis，太赖皮了，我还是偷偷摸摸的看题解慢慢懂吧QAQ，那么正确的解法是啥呢，给定了一个长度为n的序列与它等价的序列（包括它自己）有n种，那么将N分成两份，一个序列重复的次数有N*N/4种，那么我们将N全排列，记得除以二，因为两组之间是没有次序的，然后去重，答案就是N!2/(NN) #include<bits/stdc++.h> using namespace std; int main() { ...

0 点赞评论收藏

分享

2020-12-17 16:58

已编辑

南开大学 Java

题意：给定一棵树，求出每个点到树上所有点的最大距离。 思路： 先dfs预处理出来 考虑u这颗子树，往下走的最大值和次大值，然后每个点的最大值，来源一下面的最大值和它根节点往上走的最大值再取max，那么往上走的情况有两种例如下图： p代表u的父节点，根节点往上走的途径有两条，一条是继续往他的父节点走，就是up[j]+w[i]，还有一条就是它往下走，往下走就要判断一下往下走的最大值是否经过u这个点，如果经过了就只能用次打值来更新了，否则可以用最大值。 #include<bits/stdc++.h> using namespace std; const int N=20010; in...

0 点赞评论收藏

分享

2020-12-17 16:58

已编辑

南开大学 Java

I - Tree with Maximum Cost

题意：选择一个点作为根节点，然后每个顶点到它的花费为距离那个顶点的值。求最大值。 思路：也是树形dp，dp[i]代表考虑以i为根节点，他的子树对他的花费，sum[i]代表i整颗子树的节点个数和，那么dfs两次就行了，第一次dfs预处理出来sum和dp数组，第二次处理出每个点的答案。u节点的答案就是ans[u]=dp[u]+(all-sum[u])+ans[p]-sum[u]-dp[u]=all+ans[p]-2sum[u]; AC代码： #include<bits/stdc++.h> using namespace std; #define int long long int ...

0 点赞评论收藏

分享

2020-12-17 16:57

已编辑

南开大学 Java

题意：每次可以将包含1的节点的子树加1或者减1，问最小的操作数让整棵树变成0； 解题思路： 由于每次操作都要带上1，那么我们把1当做根节点，然后我们发现他的操作数与子树有关，先不考虑u这个节点，仅考虑他的子树，那么操作数有上升的也有下降的，那就是启发我们开两个数组，up，down记录上升的次数和下降的次数，状态方程转移：up[u]=max(up[j]),down[u]=max(down[j]),然后再考虑u这个点，先把down和up都计算到val中，如果val大于零down+=val，否则up-=val 最后把up和down加起来就是答案了。 AC代码： #include<bits/...

0 点赞评论收藏

分享

2020-12-17 16:57

南开大学 Java

A - Distance in Tree

题意：给你一棵树，让你记录树上两点距离为k的点对数。 思路： dp[i][j]代表考虑i这颗子树，与它距离为j的点数量，dp[i][0]就是1了，然后dfs处理一下就可以，那么它就是答案的一部分，还有一部分就是把i当做中转节点，从u开始递归，枚举它的每个子树，ans+=(dp[u][tt]-dp[j][tt-1])*(dp[j][k-tt-1])，最后别忘记除以二，最后有点小疑惑，为什么这样就是答案了呢，会不会重复或者漏算呢，首先dp[i][k]加起来肯定是不重复的，然后画画图发现把u当做中转的也不会有重复。 #include<bits/stdc++.h> using names...

0 点赞评论收藏

分享

2020-12-17 16:57

南开大学 Java

K - Appleman and Tree

题意： 给定一棵树，将树分成k个连通块，并且每个连通块内只有一个节点的方案数。 思路： 这个实在是想不出来啊，标解是开个dp[u][2]数组，表示只考虑u这颗子树并且u这个节点是否在有黑棋子的连通块中的方案数。 初始化就是如果黑色dp[u][1]=1,否则dp[u][0]=1; 转移也很骚： 枚举每个子树，由于乘法原理我们发现子树之间是相互独立的， dp[u][1]=dp[u][1](dp[j][0]+dp[j][1])+dp[u][0](dp[j][1]) dp[u][0]=dp[u][0]*(dp[j][0]+dp[j][1]) 为何这么转移？如果这个点已经被包括在有黑点的连通块中了，那么...

0 点赞评论收藏

分享

2020-12-17 16:56

南开大学 Java

D - Timofey and a tree

题意： 给定一棵树，每个点带有各自的颜色，问是否能找出一个点当做根节点，并且它的子树颜色都是相同的。 思路：每颗子树之间的边的两端都是相同的颜色，对不同颜色的答案和是没有贡献的，那么如果找到两端颜色不同的就让不同边数++，两端点都++，如果有个点他的val值等于不同边的总数，那么它一定可以当做根节点了，因为子树中没有点对对答案造成影响。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=100010; int h[N]; int c[N]; int kind; vector<pair<int,...

0 点赞评论收藏

分享

2020-12-17 16:56

南开大学 Java

tokitsukaze and Soldier

题意： 选择k个士兵，在满足总共的mins>=k的情况下，让他们的值和最大 思路： 是真的菜，这么简单的贪心都想不到，假设我们已经知道了最后选取k个士兵，那么我们可以优先选择s>=k最大的k个士兵，然后我们将士兵们排序嘛，然后按照值放进堆中，如果堆的大小大于限制，把最垃圾的t出来！ ac代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100010; struct node{ ll x; ll y; bool operator <(c...

0 点赞评论收藏

分享

2020-12-17 16:55

已编辑

南开大学 Java

题意：找一个点作为源点，问能往周围流的最多的水流。树形dp，dp数组代表以i为根的能流的所有水流，转移很简单，看代码，然后我们要处理一下从父节点流下来的值。如图。 之前wa了三十分钟，是因为转移的时候忘记考虑了父节点子树给他的贡献，从上面留下来的水流包括父节点父节点流下来的水流+子树的水流，然后别忘记特判一下当两个端点的时候，两端都可以流。 #include<bits/stdc++.h> using namespace std; const int N=200010; typedef long long ll; ll dp[N]; ll up[N]; ll ans[N]; in...

0 点赞评论收藏

分享

2020-12-17 16:55

南开大学 Java

题意：给你一个字符串，问你有多少个树形结构。 思路：有dfs序那味道了，哈哈哈哈，然而是个区间dp，f[l][r]代表字符串从l到r中有多少种树形结构，状态转移不太好想，为了达到不重不漏的目的，我们通过枚举k来枚举第一个子树出现的大小，然后，只有在两端点相等的时候才能执行，因为最后要回到该点。其实k枚举到r-2或者r-3都是可以的，因为区间长度如果为2是不合法的。 ac代码： #include<bits/stdc++.h> using namespace std; const int mod=1e9; typedef long long ll; ll dp[310][310]; ...

0 点赞评论收藏

分享

2020-12-17 16:55

南开大学 Java

扑克牌概率dp

题意： 从54张牌中抽牌，问抽到a张红，b张黑，c张方，d张梅的概率，当抽取到大王和小王的时候，会固定抽期望步数最少的牌。求最小的期望步数。 思路：期望dp ，dp(a,b,c,d,e,f）,a,b,c,d,代表前4种牌的数量，e，f代表大王和小王的状态，要注意判断不合法的情况，即所有牌都抽完了，还是没有得到想要的局面。然后我做的时候理解错题意了，把题意理解炒成期望步数了，其实抽到小王大王的时候选择是固定的，而没有四个分支。 #include<bits/stdc++.h> using namespace std; const double inf=1e20; double dp[...

0 点赞评论收藏

分享

2020-12-17 16:54

南开大学 Java

题意：某个课只有它父节点选的时候他才能选，问n个点构成的树，选m个课的最大学分数。 思路：构建一个虚拟节点0，那么0就是必选了，把选的课数量+1，对问题造成的影响是等价的，然后就是熟悉的分组背包问题了，早上卡了很久，因为要空出一格来放父亲的节点，然后对于背包dp的顺序是不能改变的，1物品组2体积最后是决策，里面只能选m-1个点，因为要留一个给自己放。 ac代码： #include<bits/stdc++.h> using namespace std; const int N=310; int f[N][N]; int w[N]; int e[N*2],ne[N*2],h[N],i...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务