关键词:
目录
华华给月月准备礼物【二分】
https://ac.nowcoder.com/acm/problem/23049
就是一个常见的二分模板
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5+10;
LL a[N],n,k;
bool check(int x)
int cnt=0;
for(int i=0;i<n;i++) cnt+=a[i]/x;
if(cnt>=k) return true;
return false;
int main(void)
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
LL l=0,r=1e9+10;
while(l<r)
LL mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
cout<<l;
return 0;
The Biggest Water Problem【模拟】
https://ac.nowcoder.com/acm/problem/15173
#include<bits/stdc++.h>
using namespace std;
int main(void)
int n; cin>>n;
while(n>=10)
int sum=0;
while(n) sum+=n%10,n/=10;
n=sum;
cout<<n;
return 0;
Bits【递归模拟 / 未完成】
https://ac.nowcoder.com/acm/problem/201605
[NOIP2004]FBI树【树的后序遍历】
https://ac.nowcoder.com/acm/problem/16660
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
void dfs(string s)
if(s.size()>1)
dfs(s.substr(0,s.size()/2));
dfs(s.substr(s.size()/2));
int cnt0=0,cnt1=0;
for(int i=0;i<s.size();i++)
if(s[i]=='0') cnt0++;
else cnt1++;
if(cnt0&&cnt1) cout<<'F';
else if(cnt0&&!cnt1) cout<<'B';
else cout<<'I';
int main(void)
cin>>n>>s;
dfs(s);
return 0;
[USACO 2009 Dec S]Music Notes【二分+前缀和】
https://ac.nowcoder.com/acm/problem/24866
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,m;
int main(void)
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
while(m--)
int x; cin>>x;
int l=1,r=n;
while(l<r)
int mid=l+r>>1;
if(a[mid]>=(x+1)) r=mid;
else l=mid+1;
cout<<l<<endl;
[NOIP2009]分数线划定【模拟】
https://ac.nowcoder.com/acm/problem/16625
#include<cstdio>
#include<algorithm>
using namespace std;
struct student
int sum;//分数
int id;//学号
s[5005];
bool cmp(student a,student b)
if(a.sum!=b.sum)
return a.sum>b.sum;
else
return a.id<b.id;
int main(void)
int n,m;//n代表总的人数 m代表志愿者人数
int end_number;//进入面试的人数
int end_score;//面试分数线
int i;
scanf("%d %d",&n,&m);
end_number=m*1.5;
for(i=0;i<n;i++)
scanf("%d %d",&s[i].id,&s[i].sum);
sort(s,s+n,cmp);//总的排序
end_score=s[end_number-1].sum;//面试的分数线
for(i=end_number;i<n;i++)//加上重分的人
if(s[i].sum==end_score)
end_number++;
else
break;
printf("%d %d\\n",end_score,end_number);
for(i=0;i<end_number;i++)
printf("%d %d\\n",s[i].id,s[i].sum);
return 0;
逆序数【归并排序】
https://ac.nowcoder.com/acm/problem/15163
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5+10;
LL a[N],b[N],n,res;
void merge_sort(int l,int r)
if(l>=r) return;
int i=l,mid=l+r>>1,j=mid+1;
merge_sort(l,mid),merge_sort(mid+1,r);
int k=0;
while(i<=mid&&j<=r)
if(a[i]<=a[j]) b[k++]=a[i++];
else
res+=mid-i+1;
b[k++]=a[j++];
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(int i=l,j=0;i<=r;i++,j++) a[i]=b[j];
int main(void)
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
merge_sort(0,n-1);
cout<<res;
return 0;
逆序对【组合数 / 推式子】
https://ac.nowcoder.com/acm/problem/14731
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int mod=1e9+7;
LL quick_mi(LL a,LL b, LL p)
LL sum=1;
while(b)
if(b&1) sum=sum*a%p;
b>>=1;
a=(a*a)%p;
return sum%p;
int main(void)
LL n; cin>>n;
if(n==1) cout<<0;
else if(n==2) cout<<1;
else cout<<(n%mod)*((n-1)%mod)%mod*quick_mi(2,n-3,mod)%mod;
return 0;
完全平方数【二分】
https://ac.nowcoder.com/acm/problem/14733
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
vector<LL>ve;
int main(void)
for(LL i=0;i<=1e5;i++) ve.push_back(i*i);
int n; cin>>n;
while(n--)
LL a,b,l,r; cin>>a>>b;
int len1=0,len2=0;
l=0,r=ve.size()-1;
while(l<r)
int mid=l+r>>1;
if(ve[mid]>=a) r=mid;
else l=mid+1;
len1=l;
l=0,r=ve.size()-1;
while(l<r)
int mid=l+r+1>>1;
if(ve[mid]<=b) l=mid;
else r=mid-1;
len2=l;
cout<<len2-len1+1<<endl;
return 0;
2021算法竞赛入门班第四节课搜索练习题(代码片段)
目录Jelly【简单bfs】maze【建图求最短路】wyh的迷宫【BFS】Jelly【简单bfs】https://ac.nowcoder.com/acm/problem/201613#include<bits/stdc++.h>usingnamespacestd;constintN=110;structnodeintx,y,z,step;;chara[N][N][N];intst[N][N][N],n;intdx[6]=-1,0,0,1,0,0;intdy[6... 查看详情
2021算法竞赛入门班第七节课图论练习题(代码片段)
目录挖沟【最小生成树板子题】公交线路【最短路板子题】挖沟【最小生成树板子题】https://ac.nowcoder.com/acm/problem/17509#include<bits/stdc++.h>usingnamespacestd;structnodeinta,b,c;temp;boolcmp(nodea,nodeb)returna.c<b.c;constintN=1e5+10;intn... 查看详情
2021算法竞赛入门班第十节课字符串练习题(代码片段)
目录救救企鹅【KMP】救救企鹅【KMP】https://ac.nowcoder.com/acm/problem/20862KMP匹配,记录匹配的开始下标。#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;chars[N],a[N],b[N];intne[N],n,m;unordered_map<int,int>mp;intmain(void)cin>&... 查看详情
2021算法竞赛入门班第三节课堆栈队列并查集等习题(代码片段)
目录新建MicrosoftOfficeWord文档【小根堆】加边的无向图【并查集】好串【栈/括号匹配】[NOIP2004]合并果子【小根堆】DongDong认亲戚【并查集】新建MicrosoftOfficeWord文档【小根堆】https://ac.nowcoder.com/acm/problem/17889用小根堆来维护一个删... 查看详情
2021算法竞赛入门班第一节课枚举贪心习题(代码片段)
目录[USACO2007JanS]保护花朵【经典贪心】[NOIP2005]校门外的树【区间合并】[NOIP2006]明明的随机数【签到】[HNOI2003]激光炸弹【二维前缀和】铺地毯【枚举】[NOIP2007]纪念品分组【模拟】[NOIP2016]回文日期【日期模拟】[USACO2007JanS]保护花... 查看详情
递归与分治策略-第二节:分治和典型分治问题(代码片段)
...(2)大整数乘法A:大整数乘法(Karatsuba算法)B:字符串乘法 查看详情
算法竞赛入门经典第二版第二章习题及思考题(代码片段)
enmmmmmm】 大部分好像除了最后一个思考题都很简单代码如下#include<iostream>#include<cstring>#include<cstdio>#include<cmath>intmain()/*for(inti=100;i<=999;i++)inta=i/100;intc=i%10;intb=(i-a*10 查看详情
《算法竞赛入门经典(第二版)》pdf
...下载内容简介 · · · · · ·《算法竞赛入门经典(第2版)》是一本算法竞赛的入门与提高教材,把C/C++语言、算法和解题有机地结合在一起,淡化理论,注重学习方法和实践技巧。全书内容分为12章,... 查看详情
分治算法----折半查找----递归二分算法(代码片段)
//对于递归的折半查找,需要考虑找不到的情况。#include<iostream>#include<cstdio>#include<stdlib.h>#definemaxn10001usingnamespacestd;inta[maxn],key;//折半查找法---递归二分法intsearch(ints,inte)intmid;if(e>=s)mid 查看详情
c/c++分治算法(二分查找算法递归实现)(代码片段)
前段时间学习了二分查找算法,使用非递归方式实现,现在学习了分治算法,发现其实现方式就是使用二分查找的原理实现的,现在这里的分治算法就使用递归方式实现吧!分治法——见名思义,即分而治... 查看详情
《算法竞赛入门经典(第二版)》习题解答——第二章(代码片段)
文章目录一、习题2-1水仙花数(daffodil)二、习题2-2韩信点兵(hanxin)三、习题2-3倒三角形(triangle)四、习题2-4子序列的和(subsequence)五、习题2-5分数化小数(decimal)六、习题2-6排列... 查看详情
蓝桥杯dfs正确入门方式|dfs+递归与递推习题课(上)|一节课教你爆搜!——学习笔记(代码片段)
目录同系列文章——传送门【蓝桥杯】DFS深度优先练习题——基础入门模板(1)_小卢先冲的博客-CSDN博客第一题:递归实现指数型枚举、第二题:全排列问题、第三题:组合的输出https://blog.csdn.net/weixin_61082895... 查看详情
递归迭代和分治:分治与二分查找(代码片段)
...的基本思想在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的... 查看详情
二分查找算法
二分查找算法主要是解决在“一堆数中找出指定的数”这类问题。而想要应用二分查找法,这“一堆数”必须有一下特征:存储在数组中有序排列二分查找法的基本实现二分查找法在算法家族大类中属于“分治法”,分治法基本... 查看详情
算法竞赛入门经典_4.3_递归
...归头,二是递归体。我们使用gcc调试工具H:编程书籍学习算法竞赛入门经典2代码算法入门经典第四章>bf‘b‘不是内部或外部命令,也不是可运行的程 查看详情
算法第二章总结
...简单的直接求解,原问题的解即子问题的解的合并。分治算法可以分三步走:分解->解决->合并分解原问题为结构相同的子问题。分解到某个容易求解的边界之后,进行递归求解。将子问题的解合并成原问题的解。 ... 查看详情
算法设计第二章总结
...Hanoi塔问题、排列问题等学习递归的思想,通过二分搜索算法、大整数乘法等学习了分治法的思想,并学习了归并排序和快速排序两种排序方法。PTA上的问题一是找第k小的数,用到了快速排序的方法对数组进行排序,同时在寻找... 查看详情
c/c++分治算法(二分查找算法递归实现)(代码片段)
前段时间学习了二分查找算法,使用非递归方式实现,现在学习了分治算法,发现其实现方式就是使用二分查找的原理实现的,现在这里的分治算法就使用递归方式实现吧!分治法——见名思义,即分而治... 查看详情