一衍一 - 个人主页动态 - 牛客网

发布(144) 刷题

2020-07-25 11:06

C++

用dp[i][j][k][l]表示1,2,3,4张牌各用i,j,k,l张时所走可以获得的最大分数,然后对于每次将要到达的位置有然后加上 #include<cstdio> #include<algorithm> using namespace std; const int N = 350, M = 41; int a[N], b[5] = { 0 }, maxx[M][M][M][M] = { 0 }; int main() { int n, m, temp; scanf("%d%d", &n, &m); for (int i =...

0 点赞评论收藏

转发

2020-07-24 08:54

C++

小A的柱状图

单调栈+前缀和单调栈维护区间的长度,然后用前缀和来计算最大值 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; typedef long long ll; ll a[maxn],h[maxn]; int main() { ll n,ans=0; cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; a[i]+=a[i-1]; } for(int i...

0 点赞评论收藏

转发

2020-07-20 20:39

C++

Harder Gcd Problem

题意:写出 的两个子集A,B,并且*两个子集的长度相等,且两个子集的交集为空,并且相对应位置的 *,然后第一行输出长度m,下来m行输出所构成的子集中的顺序题解:直接看样例1 2 3 4 5 6 7 8 9 10 11 12 13 14 157 145 153 69 122 48 10如果要gcd>1那么对于每一个质数,所需要的数必须为他的倍数那么对于每一个质数,比如上面出现的11和13无法利用,然后对于出现的7只有14可以利用如果提前将14利用,即和2一起使用,那么对于最终的答案,必定剩下1个2的倍数和7,不符合题意然后我们推广一下如果存在质数x的倍数有偶数个,那么就可以完美匹配然后对于...

0 点赞评论收藏

转发

2020-07-20 20:18

C++

对于第一小,排序,然后求两个的差,即数组在(1,2)(3,4)......下标的差对于第二小,还是排序,那么下来选4个数来进行(1,3)(2,4),但是可能会剩两个,所以对于每一个地方,只是4个不行,而是4个或6个来判断那个最小6个的判断是(1,3)(2,5)(3,6)然后对于第二种来写dp式子 #include<bits/stdc++.h> #define ll long long using namespace std; int t; int n; struct node { ll v,id; } a[200005]; int cmp(node & a,nod...

0 点赞评论收藏

转发

2020-07-20 20:06

C++

枚举两个点,而且还过(0,0)点,所以直接计算出所有的圆心,并用map保存 #include<bits/stdc++.h> using namespace std; const int MAXN=2005; int n,ans; double a[MAXN],b[MAXN],x,y; typedef pair<double,double> p; map<p,int> mx; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%l...

0 点赞评论收藏

转发

2020-07-20 16:51

C++

题意:求式子 的值,其中 .题解:不会做但是硬化简一下具体就是展开硬化简为然后把这个整理可以变成以3,4,5为例3为例:4为例:5为例:上面每行最后面有个"+"号然后这就是前缀和的变形 #include<iostream> using namespace std; typedef long long ll; ll a[300005],w[300005],f[300005]; ll mod=1e9+7; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin&g...

0 点赞评论收藏

转发

2020-07-16 18:55

已编辑

C++

[ZJOI2006]BOWL 碗的叠放

题意:给定n(n<=9)个碗,然后每个有r1,r2,h(r1<r2)三个属性,问所有的碗叠放在一起,的最小高度多少?如图叠放题解:n<=9???阶乘枚举9!=362880,稳过..........然后每次从下往上放,好计算,如果从上往下,像图右这种...........然后对于每次放的情况,我们假设上面的杯子为1号杯子,下面为2号杯子 第一种情况:1号杯子可以直接放到2号杯子底部(灵魂画师....凑后看,大概这意思) 红蓝代表两种极端情况 第二种情况:右图1号位置和3号位置情况 第三种情况:左图的情况 需要计算在那些位置会卡住 第四种情况:右图2号位置和3号位置情况 然后对于...

0 点赞评论收藏

转发

2020-07-03 19:29

已编辑

C++

平衡二叉树

题意:平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。这个没啥解释的,然后注意看黑体标记题解:既然要左右差值最大,那么我们可以人为的规定左子树减右子树,如果要差值最大,那么左子树要时高度为n-1的满二叉树,右子树是为了符...

0 点赞评论收藏

转发

2020-07-02 19:26

C++

题意:给定一个区间,然后再假设一个X,使得 最大题解:我们先看个样例2--0105--1013--011现在我们假设要求一个长度为3的二进制串使的 最大那么这个串就是100为什么呢,对于二进制每一位都关系到最后的结果,如果再第i位时1的数量小于0的数量那么当前位为1,反之1的数量大于等于0的数量为0所以题目转化成判断二进制相同位的0/1的数量来确定数字 #include<bits/stdc++.h> #define maxn 100010 using namespace std; int a[maxn],cnt[31][maxn],n,q; int main(){ ci...

0 点赞评论收藏

转发

2020-07-01 09:10

C++

题意:给m个计划,和每天有多少个房间,然后问计划和房间有没有冲突,如果有冲突,最早在第几天发生冲突题解: step1线段树区间更新 用每天能提供的教室数,建立线段树,然后对于每个计划进行区间更新,如果区间更新后的区间最小值小于0,结束,否则处理完之后输出0 #include<iostream> #include<cstdio> #include<cstring> #define min(a,b) (a<b?a:b) const int maxn=1000010; struct segment{ int l,r,minn,minus; }tree...

0 点赞评论收藏

转发

2020-06-29 20:49

已编辑

C++

题意:a,b两个属性,每天可以+1点a,或者+1点b,然后当a>xi并且b>yi,可以获得zi的奖励,之后的每天都可以获得zi的奖励,现在来求zi最大是多少题解:离散化dp我们先假设xi和yi,m比较小,那么先求v[i][j],表示在a=i,b=j时在剩下的天数里即(m-i-j)天里每天可以获得的zi值也就是相当于求的是从第一天起,到a加了i点,b加了j点,时可以获得的全部的zi值那么对于最后答案就是即,求a=i和b=j时状态,可以由两个状态得到,即i-1,j和i,j-1状态,然后这两个状态取最大加上v[i][j],就是到a=i,b=j时的所获得的zi值然后因为有m天,所以要再求下...

0 点赞评论收藏

转发

2020-06-27 18:13

C++

题意:找到一个包含所有小写字母的子串题解:双指针先找到一个从0开始包含所有小写字母的最短长度,并统计每个小写出现多少次,然后右指针移位,相应的字符统计++,然后对与左指针进行移位,移位到不能移位为止,即两指针中间出现有些字符不存在为止 #include<bits/stdc++.h> using namespace std; string s; int ansn=1e9,f[210]; int main(){ cin>>s; int l=0,r=-1,sum=0; while (1){ if (sum<26){ ...

0 点赞评论收藏

转发

2020-06-27 18:03

C++

Forsaken喜欢数论

题意: 表示每个数最小的质因子比如f(10)=2;f(39)=3然后求题解:素筛2 3 4 5 6 7 8 9 10 11.....2 3 2 5 2 7 2 3 2 11......如果当前数是某一个质数的倍数,那么这个数不是质数,然后素筛是从小到大筛的,所以直接符合题意另外:素筛的复杂的不是 ,大致是 级别的 #include<bits/stdc++.h> using namespace std; long long n,cnt,sum; int a[34000000]; int p[30040000]; void su() { for(int i=2;i<=n...

0 点赞评论收藏

转发

2020-06-27 17:53

已编辑

C++

之前算法周周练8写过,直接粘过来,复制完乱码......,贴的图片 #include<bits/stdc++.h> #define pb push_back #define ll long long #define mod 1e9+7 using namespace std; ll dp[31][121]={0};//表示赚的数目 ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { IOS dp[0][0]=1; int n; scanf("%d",&n); ...

0 点赞评论收藏

转发

2020-06-27 17:46

C++

吐槽下题目:不愧是cf,真的就是阅读理解,抛开复杂的题意,就是一个广搜,不过需要存三种情况.......题意:现在有三个地盘,然后要修一条可以连通三个城市的道路,并且要最短,可以穿过其他人的地盘来连通题解:记忆广搜,以每个点来广搜会超时,但是以每个地盘的数字来进行广搜就可以了先把一个地盘的所有点压入队列,然后来广搜全局,再用数组记录当前到其他剩余点所需要的时间戳,然后重复两次最后遍历全图对于每个点来进行三个时间戳求和,取最小,即答案时间复杂度: #include<bits/stdc++.h> using namespace std; struct node { int ...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务