工大最菜 - 个人主页动态 - 牛客网

发布(575) 评论刷题

2020-03-26 20:43

已编辑

河南工业大学 C++

ZOJ-2112 整体二分单点修改-区间第k小

题目链接：https://vjudge.net/problem/ZOJ-2112多样例：输入一个样例数t。输入一个n和m。数组长度和操作数Q l r k：查询区间[l, r]的第k小的数C x y：修改a[x]=y Sample Input25 33 2 1 4 7Q 1 4 3C 2 6Q 2 5 35 33 2 1 4 7Q 1 4 3C 2 6Q 2 5 3Sample Output3636 思路：整体二分的模板题 #include <bits/stdc++.h> using namespace std; #define LL long long const...

0 点赞评论收藏

分享

2020-03-26 13:48

河南工业大学 C++

每日一题 3月27日数学考试线性DP

思路：很容易可以看出来是一个线性DP。 #include <bits/stdc++.h> using namespace std; #define LL long long LL a[200005], f[200005]; int main(){ int t; scanf("%d", &t); while(t--){ int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++){ scanf("%lld", &a[i...

0 点赞评论收藏

分享

2020-03-25 16:20

已编辑

河南工业大学 C++

每日一题 3月26日合并回文子串区间DP

思路：我们用f[l1][r1][l2][r2]:表示A[l1] ~ A[r1]和B[l2] ~ B[r2]是否能合并成一个回文串。考虑转移：因为顺序是不能改变的。所以只有这4个可能的转移。 #include <bits/stdc++.h> using namespace std; #define LL long long int f[55][55][55][55]; char s1[55], s2[55]; int main(){ int t; scanf("%d", &t); while(t--){ memset(f, 0, size...

0 点赞评论收藏

分享

2020-03-24 22:16

河南工业大学 C++

每日一题 3月25日 tokitsukaze and Soldier 优先队列

思路：我们考虑按s[i]存入vectoc,从大到小枚举s[i]的值。那么就是在所有>=s[i]的士兵中选v最大的s[i]个。我们可以优先队列维护。因为s[i]是减小的。所以删除的士兵一定在后面用不到。 #include <bits/stdc++.h> using namespace std; #define LL long long priority_queue<LL, vector<LL>, greater<LL> > q; vector<LL> ve[100005]; int main(){ int n; sc...

0 点赞评论收藏

分享

2020-03-24 22:22

已编辑

河南工业大学 C++

POJ 1390 Blocks - 颜色段消除的最大分数三维DP

题目链接：http://poj.org/problem?id=1390&tdsourcetag=s_pctim_aiomsg 题目大意：一个积木游戏，有连续的n个方块。相同颜色的方块连续方块可以消除。如果该段由k个积木组成。得分为k*k。 <mstyle displaystyle="false" scriptlevel="0"> 我 ...

0 点赞评论收藏

分享

2020-03-31 21:30

已编辑

河南工业大学 C++

洛谷P3147 DP-倍增

题目链接：https://www.luogu.com.cn/problem/P3147题目大意： #include<bits/stdc++.h> #define LL long long using namespace std; int f[60][300000]; int main(){ int n, x; scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d", &x); f[x][i]=i+1; } ...

0 点赞评论收藏

分享

2020-03-24 22:22

已编辑

河南工业大学 C++

Codeforces Round 83 E. Array Shrinking DP-相同的元素可合并求剩余的最少元素

题目链接：https://codeforces.ml/contest/1312/problem/E 题目大意：给你一个数组，两个相邻的相同元素X可以合并成一个元素X+1。可以无限次合并。问最后数组剩余的最少元素。 <mstyle displaystyle="false" scriptlevel="0"> 我 ...

0 点赞评论收藏

分享

2020-03-24 22:23

已编辑

河南工业大学 C++

Codeforces Round 83 D.Count the Arrays 单峰数组数量-组合计数

题目链接：https://codeforces.ml/contest/1312/problem/D 题目大意：问你一个满足下列条件的数组数量。 <mstyle displaystyle="false" scriptlevel="0"> 1. 有 ...

0 点赞评论收藏

分享

2020-10-10 21:31

已编辑

河南工业大学 C++

洛谷P3224 永无乡 - 连通块合并查询第k小权值并查集+线段树合并

题目链接：https://www.luogu.com.cn/problem/P3224 题目大意： 思路：直接给每个岛建立一棵线段树。然后用并查集合并岛，线段树合并一下两个岛的权值。 #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5+5; int w[N], p[N], lc[N*20], rc[N*2...

0 点赞评论收藏

分享

2020-03-24 22:23

已编辑

河南工业大学 C++

洛谷P3605 线段树合并

题目链接：https://www.luogu.com.cn/problem/P3605 题目大意：给出一颗树，每个点都有一个权值，最后对于每个点，输出在它的子树中，有多少个点的权值比它大。 把权值取负，就是p[j]<p[i]的节点个数。直接线段树合并。 #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5+5; int w[N], p[N], lc[N*20], rc[N*20], rt[N*20], tot=0, n; vector<int>...

0 点赞评论收藏

分享

2020-03-24 22:24

已编辑

河南工业大学 C++

调度问题-完成事件需要时间:a[i]，截止时间：t[i]

问题一：https://nanti.jisuanke.com/t/43373 水灾了。有n个城市。抢救每个城市需要时间a[i]。每个城市会在t[i]时被销毁。 必须在<=t[i]（小于等于）才能抢救这个城市。问你最多能够抢救多少城市，时间从0开始。 in: 5 5 10 6 15 2 7 3 3 4 11 out: 4 #include <bits/stdc++.h> #define LL long long using namespace std; struct node{ LL t, h; }a[200005]; struct rule{ ...

0 点赞评论收藏

分享

2020-03-24 22:24

已编辑

河南工业大学 C++

ICPC North Central NA Contest 2017 - D. Smooth Array 分组背包+前缀最大值转移

题目链接：https://nanti.jisuanke.com/t/43371 题目大意：有n个数。给你一个k和s。每个数字可以改变成0-s。让你以相邻的k个为一组[a[1]…a[k]], [a[2]…a[k+1]]…。问使每一组的和为s。至少需要改变多少个数。 根据题目的条件这个数组最后的样子一定是以k为循环节。a[1]=a[k+1],a[2]=a[k+2]… 那么就是有k组数。我们把每组数出现的次数计为：size。那么就可以变成一个容量为S的分组背包。出现的数组体积为数字。贡献为size（如果把这组都变成这个数字，那么这组可以不用改变的数字个数）。 最后n-f[n][s]就是答案。 ...

0 点赞评论收藏

分享

2020-03-24 22:24

已编辑

河南工业大学 C++

Codeforces Round #625 E - World of Darkraft: Battle for Azathoth - 线段树

题目链接：https://codeforces.com/contest/1321/problem/E 题目大意： 有n个武器。每个有属性攻击力：a[i]，价格：ca[i]。 有m个盾牌。每个有属性防御力：b[i]，价格：bc[i]。 有k个怪物。每个有防御力xk, 攻击力yk，价值zk。 现在你必须并且只能买一个武器和一个盾牌。如果你的攻击力>怪物的防御力并且你的防御力>怪物的攻击力。那么你就可以打败这只怪物并且得到这只怪物价值的钱。所以你的收益为所有击败怪物的价值和-购买武器和盾牌的钱。现在让你最大化收益。 思路：我们枚举武器攻击力a[i]。那么我们可以打败的怪物只可能是x[i...

0 点赞评论收藏

分享

2020-03-24 22:25

已编辑

河南工业大学 C++

牛客练习赛58 E-最大GCD 离线-区间与X的最大gcd

题目链接：https://ac.nowcoder.com/acm/contest/4090/E 题目大意： 思路：我们可以证明一定是一个区间里面的a[i]与X。你们问题就转化成给你一个区间[L, R]找到一个L<=i<=R。最大化gcd(a[i], X)。因为最大GCD一定是X的因数。可以直接莫队维护一个区间%P的个数。 题解思路： //莫队 #include<bits/stdc++.h> #define LL long long using namespace std; int a[100005], f[100005], ans[100005]; int ...

0 点赞评论收藏

分享

2020-03-24 22:25

已编辑

河南工业大学 C++

poj1947 Rebuilding Roads - 树上背包-删除最少边得到一个大小为p的连通块

题目链接：http://poj.org/problem?id=1947 题目大意：一棵节点数为n的树。让你删除最少的边。得到一个大小为p的子树。 p<=n<150。 我 们 考 虑 用 f ...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务