蓝桥杯备战刷题three（自用）

  1.合法日期

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{map<string,int>mp;int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};for(int i=1;i<=12;i++){for(int j=1;j<=days[i];j++){string s=to_string(i)+to_string(j);mp[s]=1;}}string m,d;cin>>m>>d;m+=d;if(mp[m])cout<<"yes"<<endl;else cout<<"no"<<endl;return 0;
}

 2.删除字符

#include <iostream>
#include <string>
using namespace std;
//使字典序最小，即删掉字典序大的
//可以删除q次
//在删除每一次时，把每一个字母删掉都试一下是不是比之前的小，如果是则贡献答案
int main()
{string s;cin>>s;string s1,s2,s3;s2=s3=s;int q;cin>>q;while(q--){for(int i=0;i<s.size();i++){s3=s;//原来的（保证每次for循环挑选出一位）s1=s3.erase(i,1);//从i开始删除1位if(s1<s2)//s2表示上一个答案{s2=s1;}}s=s2;//for循环结束后更新s}cout<<s<<endl;return 0;
}

 3.最小谈判

#include <iostream>
#include <queue>
using namespace std;
const int N=1000+10;
int n;
int ans;
priority_queue<int,vector<int>,greater<int>>q;//小根堆
int main()
{cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;q.push(x);}while(q.size()!=1){if(q.size()==1)break;//每次取出最小的两个int t1=q.top();q.pop();int t2=q.top();q.pop();ans+=(t1+t2);q.push(t1+t2);}cout<<ans<<endl;return 0;
}

 4.排列小球

#include <iostream>
using namespace std;
//有限制地枚举方案，采用dfs可以进行搜索和回溯
int sum;//三个小球的总数量
int a[3];//三个小球各自的数量
int ans;//答案即方案数
void dfs(int sum,int x,int last)
{//sum为目前还未放入进行排列的小球的数量，x为目前要放入小球的数量，//last为上次放小球的小球颜色if(sum==0){//若能够全部放完则记录一次答案ans++;return;}for(int i=0;i<3;i++)//枚举三种颜色的小球，看那种符合题意{if(i==last)//颜色相同则跳过continue;//找到不同颜色的for(int j=x+1;j<=a[i];j++)//从x+1开始枚举{a[i]-=j;dfs(sum-j,j,i);a[i]+=j;//恢复现场}}
}
int main()
{for(int i=0;i<3;i++){cin>>a[i];sum+=a[i];}dfs(sum,0,-1);cout<<ans<<endl;return 0;
}

 5.灌溉

#include <iostream>
using namespace std;
const int N=110;
int a[N][N];
int b[N][N];
int n,m,t,k,ans;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main()
{cin>>n>>m>>t;while(t--){int x,y;cin>>x>>y;a[x][y]=1;b[x][y]=2;//为出水管}cin>>k;for(int g=1;g<=k;g++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1){for(int p=0;p<4;p++){int xx=i+dx[p];int yy=j+dy[p];if(xx<1||xx>n||yy<1||yy>m)continue;b[xx][yy]=1;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[i][j]==2||b[i][j]==0)continue;a[i][j]=b[i][j];}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1)ans++;}}cout<<ans<<endl;return 0;
}

6.受伤的皇后

#include <iostream>
using namespace std;
const int N=15;
int a[N];//a[i]=j表示第i行中放在了第j列
int n;
int ans;
bool isvalid(int row,int i)
{//判断已经放好的前row-1行是否可行for(int j=1;j<row;j++){if(a[j]==i||(row+i==a[j]+j&&row-j<3)||(row-i==j-a[j]&&row-j<3))return false;}return true;
}
//注意：反对角线:x+y==定值；正对角线:x-y==定值
void dfs(int row)//代码前row-1行已经放好，现在要放第row行
{if(row==n+1)//前面n行已经放好了{ans++;return;}for(int i=1;i<=n;i++)//枚举是否可行的列{if(isvalid(row,i)){a[row]=i;dfs(row+1);a[row]=0;}}
}
int main()
{cin>>n;dfs(1);//表示前0行已经摆好了就OK//注意不能是dfs(0),表示前0-1行已经摆好了，不行!!cout<<ans<<endl;return 0;
}

7.跳跃

#include <iostream>
using namespace std;
const int N=110;
const int MIN=-1e9;
int f[N][N];
int n,m;
//注意9个方向！（特别是后三个）
int dx[]={-1,-2,-3,0,0,0,-1,-1,-2};
int dy[]={0,0,0,-1,-2,-3,-1,-2,-1};
//动态规划的思想
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>f[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//找到可以从9个方向下来中的最大值int temp=MIN;for(int k=0;k<9;k++){int xx=i+dx[k];int yy=j+dy[k];if(xx<1||xx>n||yy<1||yy>m)continue;temp=max(temp,f[xx][yy]);}if(temp!=MIN)//找到了才进行更新{f[i][j]+=temp;}}}cout<<f[n][m]<<endl;return 0;
}

8.逆序对数

#include <iostream>
using namespace std;
// 求逆序对-->归并排序
int q[]={87,39,35,1,99,10,54,1,46,24,74,62,49,13,2,80,24,58,8,14,83,23,97,85,3,2,86,10,71,15};
int temp[33];
int ans=0;
void merge_sort(int q[],int l,int r)
{if (l >= r)return ;int mid= (l + r) / 2;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r){if (q[i] <= q[j])temp[k++] = q[i++];//注意等号！！else{temp[k++] = q[j++];ans += mid - i + 1;}}while (i <= mid)temp[k++] = q[i++];while (j <= r)temp[k++] = q[j++];for (i = l, j = 0; i <= r; i++, j++)q[i] = temp[j];//注意赋值！}
int main()
{merge_sort(q,0,29);cout<<ans<<endl;return 0;
}