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

  1.合法日期

#include 
#include 
#include 
using namespace std;
int main()
{
  mapint>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"<
  else cout<<"no"<
  return 0;
}

 2.删除字符

#include 
#include 
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;isize();i++)
    {
      s3=s;//原来的（保证每次for循环挑选出一位）
      s1=s3.erase(i,1);//从i开始删除1位
      if(s1//s2表示上一个答案
      {
        s2=s1;
      }
    }
    s=s2;//for循环结束后更新s
  }
  cout<
  return 0;
}

 3.最小谈判

#include 
#include 
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<
  return 0;
}

 4.排列小球

#include 
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<
  return 0;
}

 5.灌溉

#include 
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<
  return 0;
}

6.受伤的皇后

#include 
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
  {
    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<
  return 0;
}

7.跳跃

#include 
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<
  return 0;
}

8.逆序对数

#include 
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<
  return 0;
}