希胤 - 个人主页动态 - 牛客网

发布(195) 评论刷题收藏

2021-03-24 21:55

门头沟学院 Java

dp题 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=37; ll n,ans,sum; //记得开ll ll f[N][4*N]; //f[i][j]表示前i张彩票获得j元的方案数 //这里的方案数和位置有关即类似A3取2(=2)这种，而非C3取2(=1) ll ksm(ll a,ll b){ ll res=1; while(b){ if(b&1) res*=a; a*=a; b>>=1; } return res; } int main() { ci...

0 点赞评论收藏

分享

2021-03-23 23:38

门头沟学院 Java

动态规划提高课，用此链接立减10元https://www.nowcoder.com/courses/cover/live/435?coupon=AOwWGt5图论提高课，用此链接立减10元https://www.nowcoder.com/courses/cover/live/519?coupon=Ao3wQ6j

0 点赞评论收藏

分享

2021-03-23 20:58

门头沟学院 Java

单调栈+按位置建树，数据结构就是解决问题时用的容器

单调栈 + 按位置建树 先求出每个点作为最大值的区间范围（用单调栈优化）经过证明单调栈放下标更好，以后一般都用下标单调栈：扔一次删一次，所以复杂度为O(n)数据结构就是解决问题时用的容器并查集也是容器 按位置建树求某个点左边（或右边）有多少个可选的点可以用ask求 #include<bits/stdc++.h> using namespace std; #define ll long long #define low(x) x&(-x) int const N=1e5+7; int INF=0x3f3f3f3f; int n; struct L{ int a,l,r; }b...

线段树和数状数组经典例题

0 点赞评论收藏

分享

2021-03-22 23:39

已编辑

门头沟学院 Java

最长上升子序列（模板）

话说以后看不懂自己的代码（尤其是朴素版的代码）就不要去想了，浪费时间（直接用就好了呀）（一般博客里的代码都是验证过的，百分百正确，若没过部分测试点，一般我也会注明呀，所以不要操心了）（若有模板的优化版，那就放掉以前的呗，多余的事不要管） #include<bits/stdc++.h> using namespace std; #define ll long long int n,a,pos; vector<int>ve; int main(){ cin >> n; for(int i=1;i<=n;++i){ cin >> a; pos=l...

0 点赞评论收藏

分享

2021-03-22 20:40

已编辑

门头沟学院 Java

矩阵快速幂（模板）（求通项公式的第几项通常用其求解）

题目：有规律的斐波那契求通项公式的第几项通常用矩阵快速幂求解 #include<bits/stdc++.h> using namespace std; #define ll long long int const mod=998244353; struct L{ ll a[3][3]; void init(int f=0){ //默认参数为0 memset(a,0,sizeof a); if(f==1){ //将其初始化为单位矩阵 this->a[0][0]=this->a[1][1]=this->a[2][2]=1; } if(f==2){ //将其初始化为构造...

0 点赞评论收藏

分享

2021-03-22 16:40

已编辑

门头沟学院 Java

取模的优先级和乘法的优先级一样

将d看成d个1，将两块板子插入其中（这样就可以取出3个数），统计其方案数即可（可发现其方案数为 C(n+2)取2，再判断n+1和n+2谁是偶数并将其约掉2，再计算） #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e6+7; ll const mod=998244353; ll n,a,b,ans; int main(){ cin >> n; a=n+1;b=n+2; if(a&1) b/=2; else a/=2; a%=mod;b%=mod; //这...

0 点赞评论收藏

分享

2021-03-22 16:08

门头沟学院 Java

朴实无华的签到题

男可以用1表示，女用0表示01的数量一样，比较谁在奇数位更优01的数量不一样，多的一定在奇数位注：题目并没有说，给出的n个学号一定是在[1,n]的范围内 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e6+7; int n,cntj,x,y,ans; int a; int main(){ cin >> n; for(int i=1;i<=n;++i){ cin >> a; if(a&1){ cntj++; if(i&1) x+...

0 点赞评论收藏

分享

2021-03-22 15:34

门头沟学院 Java

将每个点依次作为边界，对每个点操作：要么全删左边，要么全删右边，寻最大值，以此求解（具体见代码） #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e6+7; int n; ll a[N],b[N],c[N]; //b是前缀和 //c是后缀和 double ans,z1,z2; int main(){ cin >> n; for(int i=1;i<=n;++i){ cin >> a[i]; b[i]=a[i]+b[i-1]; } for(int...

0 点赞评论收藏

分享

2021-03-21 23:17

门头沟学院 Java

n*m的方格，对角线共有gcd(n,m)+1个点在格点上

1、n*m的方格，对角线共有gcd(n,m)+1个点在格点上，即有gcd(n,m)个子正方形被大正方形的对角线穿过（这里的穿过指：子正方形的对角线与大正方形的对角线重合）2、系统自带__gcd(n,m)函数 #include<bits/stdc++.h> using namespace std; #define ll long long ll n,m; /*ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }*/ int main(){ cin >> n >> m; ll z= __gcd(n,m); //ll z=g...

0 点赞评论收藏

分享

2023-03-27 22:55

已编辑

门头沟学院 Java

序列自动机（模板）

题目：Summer Trip #include<bits/stdc++.h> using namespace std; #define ll long long string s; vector<int>ve[30]; //v[i][j]表示记录序列中第j个i字母的位置 ll fun(int a,int b){ ll res=0; int lena=ve[a].size(); int lenb=ve[b].size(); int j=0; for(int i=0;i<lena;i++){ while(j<lenb && ve[b][j]&lt...

0 点赞评论收藏

分享

2021-03-18 19:48

已编辑

门头沟学院 Java

树状数组模型之逆序对，离散化

此题为什么是树状数组： 此题就是问在p点前面比a[p]大的数有多少个，类似求区间和，但要进过一些处理（处理下面解法中会提到） 此题就是树状数组的经典运用模型，以后直接运用即可（作为模型或板子记下） 区间修改题（前缀和、树状数组和线段树）经常要用到离散化 离散化的建法： 若对相邻关系有要求：46 47 100 ==> 1 2 4 //保留其相对大小的关系 若对相邻关系无要求：46 47 100 ==> 1 2 3 此题（代码是解法一）： 解法一：按值排序（为了离散化），按其起始位置的顺序输入（add），再按值建树，此时的 逆序对=当前值（在树中的位置）后面有几个数 按值建树：值变成了...

0 点赞评论收藏

分享

2021-03-16 22:03

门头沟学院 Java

分组背包例题

题目：此题总费用固定，同种疾病的费用只能选择一种方案（每种疾病有四种方案）（方案：花多少钱救多少人），求最多挽救人数分组背包经典例题 #include<bits/stdc++.h> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int const N=1e4+7; int const M=1e5+7; int t,n,m; int v[N],w[N]; int f[M]; int main(){ cin >> t; for(int p=1;p&lt...

0 点赞评论收藏

分享

2021-03-16 21:42

已编辑

门头沟学院 Java

用dfs判连通块和环

题目：给出一张图，判断有几个连通块（单点不算），有几个有环的连通块 判断连通块： 方法一：dfs，若点在同一个连通块里，就标记一下 方法二：并查集，判断有几个祖先 判断有无环（以后用方法一或三）： 方法一：如果一个点除了走到它的父亲，还走到了一个被访问的点，说明有环 （被访问的点说明一定存在一个已走过的路径到达该点）（以下代码是方法一） 方法二：dfs或记度数，再判断是否是树（树的度数是n-1） 方法三：并查集，如果一条边的两个点已经在同一个集合里，说明有环（类似kruskal）// #include<bits/stdc++.h> using namespace std; int ...

0 点赞评论收藏

分享

2021-03-13 18:06

已编辑

门头沟学院 Java

2021牛客寒假算法基础集训营2

D-牛牛与整除分块 规律题临界点是sqrt(n)令b=n/x （此题分析从此以下的规律即结论都是举例找出来的）当x<=sqrt(n)时：b大且分布得比较稀疏（每个b相差好几个数），所以x分别对应一个b,所以此时b是第几大的数？第x大的数。当x>sqrt(n)时：b小且分别得比较稠密，所以可能几个x对应着同一个b（每个b是在整数意义上连续的）,所以此时b是第几大数？第 sqrt(n)+(n/(sqrt(n)+1)-n/x+1) 大的数以n=25,x=9为例，临界点a=sqrt(25)=5 当x<=5时 #include<bits/stdc++.h> using na...

0 点赞评论收藏

分享

2021-03-10 23:47

已编辑

门头沟学院 Java

2021牛客寒假算法基础集训营1

A—串 #include<bits/stdc++.h> using namespace std; #define ll long long #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int const mod=1e9+7; int const N=1e6+7; ll f[N][3]; //f[i][0]表示前i字符串中没有u的 //f[i][1]表示有u没有us的 //f[i][2]表示有us的 int n; int main(){ fio; cin >> n; f[0][0]=1; ...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

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