算法刷题(一)-爱代码爱编程
算法刷题(一)
以下题部分来自于AcWing,蓝桥杯等地。
二分
机器人跳跃问题
输入样例1:
5
3 4 3 2 4
输出样例1:
4
输入样例2:
3
4 4 4
输出样例2:
4
输入样例3:
3
1 6 4
输出样例3:
3
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=100010;
int a[N];
bool check(int e)
{
for(int i=0;i<n;i++)
{
e=e*2-a[i];
if(e>=1e5) return true;
if(e<0) return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int l=0,r=1e5;
while(l<r)
{
int mid=l+(r-l)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}
带分数
资源限制
内存限制:256.0MB
C/C++时间限制:1.0s
Java时间限制:3.0s
Python时间限制:5.0s
100 可以表示为带分数的形式:100 = 3 + 69258 / 714
还可以表示为:100 = 82 + 3546 / 197
注意特征:带分数中,数字1~9分别出现且只出现一次(不包含0)。
类似这样的带分数,100 有 11 种表示法。
题目要求:
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意:不要求输出每个表示,只统计有多少表示法!
例如:
用户输入:
100
程序输出:
11
用户输入:
105
程序输出:
6
资源约定:
峰值内存消耗 < 64M
CPU消耗 < 3000ms
#include <bits/stdc++.h>
using namespace std;
const int N=20;
int ans=0;
int n;
bool st[N],backup[N];
bool check(int a,int c)
{
int b=n*c-a*c;
if(!a||!b||!c)
return false;
memcpy(backup,st,sizeof st);
while(b)
{
int x=b%10; //娶个位数
b/=10;//删掉个位数
if(!x||backup[x])
return false;
backup[x]=true;
}
for(int i=1;i<=9;i++)
{
if(!backup[i])
return false;
}
return true;
}
void dfsc(int u,int a,int c)
{
if(u==n) return;
if(check(a,c))
ans++;
for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i]=true;
dfsc(u+1,a,c*10+i);
st[i]=false;
}
}
}
void dfsa(int u,int a)
{
if(a>=n) return;
dfsc(u,a,0);
for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i]=true;
dfsa(u+1,a*10+i);
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfsa(0,0);
cout <<ans<<endl;
return 0;
}
递归
递归求斐波那契数列
输入样例:
4
输出样例:
3
#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
if(n==1||n==2)
{
return 1;
}
if(n>2)
{
return f(n-1)+f(n-2);
}
}
int main()
{
int n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}
递归实现组合型枚举
输入样例:
5 3
输出样例:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
#include <bits/stdc++.h>
using namespace std;
const int N=30;
int m,n;
int st[N];//位置
void dfs(int x,int y )
{
if(x==m+1)
{
for(int i=1;i<=m;i++)
{
cout<<st[i]<<" ";
}
puts(" ");
return;
}
for(int i=y;i<=n;i++)
{
st[x]=i;
dfs(x+1,i+1);
st[x]=0;
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
return 0;
}
递归实现排列型枚举
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n;
bool s[N];
int st[N]; //记录每个位置当前的状态 ,0没考虑,1选,2不选
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
{
printf("%d ",st[i]);
}
puts("");
return ;
}
for(int i=1;i<=n;i++)
{
if(!s[i])
{
st[u]=i;
s[i]=true;
dfs(u+1);
st[u]=0;
s[i]=false;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
翻硬币
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:* * o o * * * o o o o
如果同时翻转左边的两个硬币,则变为:o o o o * * * o o o o
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作。
程序输入:
两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度<1000
程序输出:
一个整数,表示最小操作步数
用户输入:
**********
o****o****
程序输出:
5
用户输入:
*o**o***o***
*o***o**o***
程序输出:
1
资源约定:
峰值内存消耗 < 64M
CPU消耗 < 1000ms
#include <bits/stdc++.h>
using namespace std;
const int N=110;
char st[N],en[N];
int n;
void turn(int i)
{
if(st[i]=='o')
{
st[i]='*';
}
else
{
st[i]='o';
}
}
int main()
{
cin>>st>>en;
n=strlen(st);
int s=0;
for(int i=0;i<n-1;i++)
{
if(st[i]!=en[i])
{
turn(i),turn(i+1);
s++;
}
}
cout<<s;
return 0;
}