c++ 算法开发语言蓝桥杯备战刷题one（自用）

1.被污染的支票

#include

using namespace std;

int main()

{

int n;

cin>>n;

vectorL;

mapmp;

bool ok=0;

int num;

for(int i=1;i<=n;i++)

{

cin>>num;

if(mp[num]==1)ok=1;

else

{

mp[num]=1;

L.push_back(num);

}

sort(L.begin(),L.end());

int x=L.back()*2;//?????

vectorL2;

for(int i=2;i

{

if(x%i==0)L2.push_back(i);

}

if(L!=L2)ok=1;

if(ok)

{

cout<<-1<

}

else

{

cout<

}

return 0;

}

2.日期统计

#include

using namespace std;

int main()

{

int ans=0;

int num[100]={5, 6, 8, 6, 9, 1, 6, 1, 2, 4,

9, 1, 9, 8, 2, 3, 6, 4, 7, 7,

5, 9, 5, 0, 3, 8, 7, 5, 8, 1,

5, 8, 6, 1, 8, 3, 0, 3, 7, 9,

2, 7, 0, 5, 8, 8, 5, 7, 0, 9,

9, 1, 9, 4, 4, 6, 8, 6, 3, 3,

8, 5, 1, 6, 3, 4, 6, 7, 0, 7,

8, 2, 7, 6, 8, 9, 5, 6, 5, 6,

1, 4, 0, 1, 0, 0, 9, 4, 8, 0,

9, 1, 2, 8, 5, 0, 2, 5, 3, 3};

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

for(int mon=1;mon<=12;mon++)

{

for(int day=1;day<=days[mon];day++)

{

int temp[8]={2,0,2,3,mon/10,mon%10,day/10,day%10};

int k=0;

for(int i=0;i<100;i++)

{

if(num[i]==temp[k])

{

k++;

}

if(k==8)

{

ans++;

break;

}

cout<

return 0;

}

3.01串的熵

#include

using namespace std;

int main()

{

int n=23333333;

for(int i=0;i<=n/2;i++)//0的次数

{

double a=(i*1.0)/n;

double b=((n-i)*1.0)/n;

double ans=0;

ans-=(a*log2(a)*i+b*log2(b)*(n-i));

if(fabs(ans-11625907.5798)<0.0001)

{

cout<

break;

}

return 0;

}

（注意浮点数，double，以及比较大小时使用1e-4）

4.冶炼金属

#include

using namespace std;

#define ll long long

int main()

{

ll n,a,b,minn,maxx;

maxx=1e9;//要满足最小的

minn=0;//要满足最大的

cin>>n;

for(ll i=0;i

{

cin>>a>>b;

minn=max(minn,a/(b+1)+1);

maxx=min(maxx,a/b);

}

cout<

return 0;

}

//二分

#include

using namespace std;

int a[10000+5];

int v[10000+5];

int n;

bool check_min(int x)

{

for(int i=1;i<=n;i++)

{

if(a[i]/x>v[i])return false;

}

return true;

}

bool check_max(int x)

{

for(int i=1;i<=n;i++)

{

if(a[i]/x

}

return true;

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i]>>v[i];

}

int L=1,R=1000000000,minn=0;

while(L<=R)

{

int mid=(L+R)>>1;

if(check_min(mid))

{

minn=mid;

R=mid-1;

}

else L=mid+1;

}

int maxx=0;

L=1,R=1000000000;

while(L<=R)

{

int mid=(L+R)>>1;

if(check_max(mid))

{

maxx=mid;

L=mid+1;

}

else R=mid-1;

}

cout<

return 0;

}

5.飞机降落

#include

using namespace std;

struct node

{

int t,d,l;

};

bool ok=0;

vectorv;

vectorvis;

int n;

void dfs(int cnt,int last)

{

if(cnt==n)

{

ok=1;

return;

}

for(int i=0;i

{

if(!vis[i]&&v[i].t+v[i].d>=last)//可以降落

{

vis[i]=1;

dfs(cnt+1,max(last,v[i].t)+v[i].l);

vis[i]=0;//恢复

}

int main()

{

int t;

cin>>t;

while(t--)

{

cin>>n;

v.clear();

vis.clear();

for(int i=1;i<=n;i++)

{

//t d l (t/t+d -- l)

int x,y,z;

cin>>x>>y>>z;

v.push_back({x,y,z});

vis.push_back(0);

}

ok=0;

dfs(0,0);//0架飞机，0需要时间

if(!ok)cout<<"NO"<

else cout<<"YES"<

}

return 0;

}

6.接龙数列

这道题其实本质就是求解出数列中最长的接龙数列，计算出最长的接龙数列长度，数列总长度-最长接龙数列长度等于最少删除次数。这就是一个求最优解的问题，然而看到这道题的数据量可以发现，暴力求解一定会超时，因此考虑动态规划。动态规划最重要的就是状态转移方程，而这个题目就可以定义状态为当前最长接龙数列长度，则dp[i]就是以i为数字最后一位的最长接龙数列长度，设x为当前数字的第一位(如果为接龙数列，也就是前一位数的最后一位)，y为当前数字的最后一位，则转移方程可以写为dp[y]=max(dp[x]+1,dp[y])

#include

using namespace std;

int f[10];//表示在i=0-9中,f[i]为以i数字为连接的最长接龙数列的长度

int main()

{

int n;

cin>>n;

int ans=0;

string s;

for(int i=0;i

{

cin>>s;

int pre=s[0]-'0',nex=s[s.size()-1]-'0';

f[nex]=max(f[nex],f[pre]+1);

ans=max(ans,f[nex]);

}

cout<

return 0;

}

7.岛屿个数

搜索出所有岛屿，这个不难做到。由于岛屿之间互相隔离，则如果岛屿的一个格子在一个环内，那么整个岛屿也都在环内。遍历所有的岛屿，选中当前岛屿的第一个格子，搜索周围海洋，若能搜索到地图的边界外，则此岛屿不在任何一个环内；否则，此岛屿在某个环内，岛屿数量减一。

#include

using namespace std;

#define pii pair

const int N=100;

int n,m,ans;

vector>vis;

string s[N];

int dx[8]={-1,1,0,0,-1,1,-1,1};

int dy[8]={0,0,-1,1,-1,1,1,-1};

bool inmap(int x,int y)

{

if(x<1||x>n||y<1||y>m)return 0;

return 1;

}

//bfs统计岛屿的情况

void bfs(int x,int y)

{

vis[x][y]=1;

queueq;

q.push({x,y});

while(!q.empty())

{

auto t=q.front();

q.pop();

for(int i=0;i<4;i++)

{

int xx=t.first+dx[i];

int yy=t.second+dy[i];

if(!inmap(xx,yy)||vis[xx][yy]||s[xx][yy]!='1')continue;

vis[xx][yy]=1;

q.push({xx,yy});

}

bool check(int x,int y)//是否不在环内，即周围是海洋（用是否到边界判断）

{

vector>fin(n+1,vector(m+1,0));

fin[x][y]=1;

queueq;

q.push({x,y});

while(!q.empty())

{

auto t=q.front();

q.pop();

//到达边界，证明不在环中

if(t.first==1||t.first==n||t.second==1||t.second==m)return 1;

for(int i=0;i<8;i++)

{

int xx=t.first+dx[i];

int yy=t.second+dy[i];

if(!inmap[xx][yy]||fin[xx][yy]||s[xx][yy]!='0')continue;

fin[xx][yy]=1;

q.push({xx,yy});

}

return 0;

}

int main()

{

int t;

cin>>t;

while(t--)

{

ans=0;

cin>>n>>m;

for(int i=1;i<=n;i++)

{

cin>>s[i];

s[i]='2'+s[i];

}

vis=vector>(n+1,vector(m+1,0));

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

if(!vis[i][j]&&s[i][j]=='1')

{

bfs(i,j);

if(check(i,j))ans++;

}

cout<

}

return 0;

}

8.子串简写

#include

using namespace std;

int main()

{

int k;

//最小可以简写的长度

cin>>k;

string s;

char st,ed;

cin>>s>>st>>ed;

long long ans=0;

int st_num=0;

for(int i=0,j=k-1;j

{

if(s[i]==st)st_num++;

if(s[j]==ed)ans+=st_num;

}

cout<

return 0;

}

//4

//abababdb a b

（注意规律，开long long）

9.整数删除

#include

using namespace std;

//优先队列+双向链表

const int N=5e5+10;

#define ll long long

#define val first

#define pos second

#define pli pair

int n,k;

ll a[N],pre[N],nxt[N];

priority_queue,greater>q;//小根堆

int main()

{

cin>>n>>k;

for(int i=1;i<=n;i++)

{

cin>>a[i];

q.push({a[i],i});

pre[i]=i-1;

nxt[i]=i+1;

}

pre[1]=-1;

nxt[n]=-1;

while(k--)

{

pli now;

do{

now=q.top();

q.pop();

}while(a[now.pos]!=now.val);//保证弹出同一个

int PRE=pre[now.pos];

int NXT=nxt[now.pos];

if(PRE!=-1)

{

a[PRE]+=now.val;

q.push({a[PRE],PRE});

nxt[PRE]=NXT;

}

if(NXT!=-1)

{

a[NXT]+=now.val;

q.push({a[NXT],NXT});

pre[NXT]=PRE;

}

a[now.pos]=-1;

}

for(int i=1;i<=n;i++)

{

if(a[i]!=-1)cout<

}

return 0;

}

10.景区导游

//最近公共祖先。倍增做法 (深搜)

#include

#define ll long long

using namespace std;

const int N=1e5+10;

vectore[N],w[N];

int n,k;

ll dep[N],fa[N][20],dist[N],b[N];

void dfs(int u,int father){

fa[u][0]=father;

dep[u]=dep[father]+1;

for(int i=1;i<20;i++){

fa[u][i]=fa[fa[u][i-1]][i-1];

}

for(int i=0;i

int v=e[u][i];

int t=w[u][i];

if(v!=father){

dist[v]=dist[u]+t;

dfs(v,u);

}

int lca(int u,int v){

if(dep[u]

for(int i=19;i>=0;i--){

if(dep[fa[u][i]]>=dep[v])

u=fa[u][i];

}

if(u==v) return v;

for(int i=19;i>=0;i--){

if(fa[u][i]!=fa[v][i]){

u=fa[u][i],v=fa[v][i];

}

return fa[u][0];

}

ll sol(int x,int y){

if(!x||!y) return 0;

return dist[x]+dist[y]-2*dist[lca(x,y)];

}

int main(){

cin>>n>>k;

for(int i=1;i

int x,y,t;

cin>>x>>y>>t;

e[x].push_back(y);

e[y].push_back(x);

w[x].push_back(t);

w[y].push_back(t);

}

dfs(1,0);

ll Dis=0;

for(int i=1;i<=k;i++){

cin>>b[i];

Dis+=sol(b[i],b[i-1]);

}

for(int i=1;i<=k;i++){

cout<

}

return 0;

}

11.砍树

#include

using namespace std;

const int N=1e5+10;

vectore[N],num[N];

int n,m,dep[N],fa[N][21],s[N],ans;

void dfs(int u,int Fa)

{

dep[u]=dep[Fa]+1;

fa[u][0]=Fa;

for(int i=1;i<=20;i++)

{

fa[u][i]=fa[fa[u][i-1]][i-1];

}

for(auto &v:e[u])

{

if(v==Fa)continue;

dfs(v,u);

}

int LCA(int u,int v)

{

if(dep[u]

for(int i=20;i>=0;i--)

{

if(dep[fa[u][i]]>=dep[v])

{

u=fa[u][i];

}

if(u==v)return u;

for(int i=20;i>=0;i--)

{

if(fa[u][i]!=fa[v][i])

{

u=fa[u][i];

v=fa[v][i];

}

return fa[u][0];

}

void dfs2(int u,int Fa)

{

for(int i=0;i

{

int v=e[u][i],p=num[u][i];

if(v==Fa)continue;

dfs2(v,u);

s[u]+=s[v];

if(s[v]==m)ans=max(ans,p);

}

int main()

{

cin>>n>>m;

for(int i=1;i

{

int x,y;

cin>>x>>y;

e[x].push_back(y);

e[y].push_back(x);

num[x].push_back(i);

num[y].push_back(i);

}

dfs(1,0);

for(int i=1;i<=m;i++)

{

int a,b;

cin>>a>>b;

s[a]++;s[b]++;s[LCA(a,b)]-=2;

}

dfs2(1,0);

cout<

return 0;

}

金钥匙

c++ 算法开发语言蓝桥杯备战刷题one（自用）

服务器 ssh 运维树莓派4b连接手机热点wifi及远程桌面连接

scratch蓝桥杯真题蓝桥杯scratch真题中小学scratch scratch蓝桥杯省赛真题蓝桥杯scratch省赛真题 scratch比赛题目【蓝桥杯省赛真题51】Scratch消除字母蓝桥杯scratch图形化编程中小学生蓝桥杯省赛真题讲解

发表评论取消回复

金钥匙

c++ 算法 开发语言 蓝桥杯备战刷题one（自用）

服务器 ssh 运维 树莓派4b连接手机热点wifi及远程桌面连接

scratch蓝桥杯真题 蓝桥杯scratch真题 中小学scratch scratch蓝桥杯省赛真题 蓝桥杯scratch省赛真题 scratch比赛题目 【蓝桥杯省赛真题51】Scratch消除字母 蓝桥杯scratch图形化编程 中小学生蓝桥杯省赛真题讲解

相关文章

发表评论取消回复

c++ 算法开发语言蓝桥杯备战刷题one（自用）

服务器 ssh 运维树莓派4b连接手机热点wifi及远程桌面连接

scratch蓝桥杯真题蓝桥杯scratch真题中小学scratch scratch蓝桥杯省赛真题蓝桥杯scratch省赛真题 scratch比赛题目【蓝桥杯省赛真题51】Scratch消除字母蓝桥杯scratch图形化编程中小学生蓝桥杯省赛真题讲解