【蓝桥杯预备营集结十一】软件类 CC++ 预备试题分析及解答

⭐️问题描述

长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

数据格式
　　第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。

接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。

要求输出1个整数，表示最后感冒蚂蚁的数目。

例如，输入：

3
5 -2 8

程序应输出：

1

再例如，输入：

5
-10 8 -20 12 25

程序应输出：

3

⭐️解题思路

黑色代表首只感冒蚂蚁

红色代表会感冒蚂蚁

蓝色代表不会感冒蚂蚁

图 1 2 为一般情况 图 3 4 为特殊情况

（两只蚂蚁相遇各自反向可以看作是两只蚂蚁分别继续前进， 然后假如感冒蚂蚁向左行，则会感染它左边所有向右行的蚂蚁，因为它继续向左行， 别感染的第一只蚂蚁继续向右行，感染所有它右边向左行的蚂蚁。）

⭐️代码

#include 
#include 
using namespace std;

const int N = 100;
int a[N + 1];
int n;
int ans;

void solve() {
    scanf("%d", &n);
    int i = 0, t = 0, h = 0;
    for (i = 0; i < n; i++) {
        scanf("%d", &t);
        if (i == 0) h = t;  //记录第一只感冒的蚂蚁
        a[abs(t)] = t;
    }

    //下面开始统计
    if (h > 0) {
        for (i = h + 1; i <= N; i++) {
            if (a[i] < 0) ans++;
        }
        if (ans > 0) {
            for (i = h - 1; i > 0; i--) {
                if (a[i] > 0) ans++;
            }
        }
    } else {
    //注意h是负数
        for (i = -h - 1; i > 0; i--) {
            if (a[i] > 0) ans++;
        }
        if (ans > 0) {
            for (i = -h + 1; i <= N; i++) {
                if (a[i] < 0) ans++;
            }
        }
    }
    printf("%d\n", ans + 1);  //最后加上第一只感冒的蚂蚁
}

int main(void) {
    solve();
    return 0;
}

#include
 int abss(int s)//取绝对值 
 { if(s<0)return -s;
    else return s;
 }
int  main()
{
  int qans=0,hans=0,n,i,gm,s;
  scanf("%d",&n); 
  scanf("%d",&gm);//gm 首个感冒蚂蚁 位值 
    for(i=1;i0)qans++;//当在首个蚂蚁左侧并且正向 必感冒 
     }
  if(gm>0&&hans!=0||gm<0&&qans!=0)printf("%d",qans+hans+1);
   else printf("1");//当首个感冒蚂蚁方向为正时 在首个蚂蚁右侧并且反向 为 0 或  
return 0; //当首个感冒蚂蚁方向为负时 在首个蚂蚁左侧并且反向 为 0 则不会被感冒除首个感冒 
}

⭐️问题描述

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

【数据格式】

输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

例如，输入：

2 2 2
1 2
2 1

程序应该输出：

2

再例如，输入：

2 3 2
1 2 3
2 1 5

程序应该输出：

14

⭐️思路分析

由题目容易知道使用动态规划来解决，设定一个四维数组 dp[55][55][15][15]，此数组用于存放当前的行动方案数量，由题目给出的数据范围可以推测出设定的数组不会使内存爆炸，dp[i][j][k][c]我们定义为到 (i,j) 这个点时，拿到了k件物品，并且当前的物品的最大价值小于c的方案数，那么可以推测出下面几种情况：

• 当mat[i][j] > 目前的最大价值（mat[i][j]表示位于(i,j)坐标的物品的价值）时，也就是说此时如果要取走(i,j)坐标的物品，那么位于(i-1,j)和(i,j-1)坐标的价值肯定小于mat[i][j]，那么此时设置一个tmp1
  tmp1 = dp[i-1][j][k-1][mat[i][j]] + dp[i][j-1][k-1][mat[i][j]]

• 不管mat[i][j]大于当前的最大价值时，也可以选择不取位于(i,j)的物品，当mat[i][j]小于当前的最大价值时，则不能取走(i,j)的物品，所以不管是大于还是小于，都存在不取的这种情况，此时设置一个tmp2
  tmp2 = dp[i-1][j][k][c] + dp[i][j-1][k][c]

最后 dp[i][j][k][c] = (tmp1%mod + tmp2%mod)%mod即可得出当前的方案数
最后输出dp[n][m][k][13]

⭐️代码

#include 
#include 
#include 
using namespace std;

const int MOD = 1e9+7;
int mat[55][55];
int dp[55][55][15][15];
int n,m,k,ans;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&mat[i][j]);
    int tmp1,tmp2;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int l=0;l<=k;++l)
                for(int c=0;c<=13;++c)
                {
                    tmp1 = 0;
                    if(i==1&&j==1)   //此处表示初始条件
                    {
                        if(l==0) dp[i][j][l][c] = 1;
                        if(l==1&&c>mat[i][j]) dp[i][j][l][c]=1;
                        continue;
                    }
                    if(c>mat[i][j]&&l) tmp1 = dp[i-1][j][l-1][mat[i][j]] + dp[i][j-1][l-1][mat[i][j]];
                    tmp2 = dp[i-1][j][l][c] + dp[i][j-1][l][c];
                    dp[i][j][l][c] = (tmp1%MOD+tmp2%MOD)%MOD;
                }
    printf("%d\n",dp[n][m][k][13]);
    return 0;
}

⭐️问题描述

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

　　输入的第一行包含一个整数n，表示小朋友的个数。
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

输出格式

　　输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3
3 2 1

样例输出

9

样例说明

　　首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

⭐️代码

#include
#include
using namespace std;
//a为原数组,b为按大小排序的数组,c为b的树状数组,d为暂存的不开心值 ,e为等差数列存储不高兴值的递增值
int a[100001],b[1000003],c[1000003],d[1000003];
long long int e[100002];
//位运算
int lowbit(int x)
{
    return x&(-x);  
}
//定义修改C数组的函数，第一个值代表数组位置，第二个代表数组值，在此题中只需默认加一
void update(int local,int num){
	int n=local,add;
	add=num-b[local];
	b[local]=num;
	while(n<1000002){
		c[n]+=add;
		n+=lowbit(n);
	}
}
//查询前多少区间的和
int read(int i){
	int n=i,sum=0;
	while(n!=0){
		sum+=c[n];
		n-=lowbit(n);
	}
	return sum;
}
//清零函数
void ini(){
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
}
int main(){
	int i,n;
	long long int sum=0;
	cin>>n;
	ini();
	for(i=0;i>a[i];//按顺序存储进来的小朋友身高
		update(a[i]+1,b[a[i]+1]+1);//修改b和c数组,
		d[i]=i-read(a[i])-b[a[i]+1]+1;//计算在第i个小朋友进来时，前面比他高的人数
	}
	ini();
	for(i=n-1;i>=0;i--){
		update(a[i]+1,b[a[i]+1]+1);//修改b和c数组,
		d[i]+=read(a[i]);//计算在第i个小朋友进来时，后面比他矮的人数
	}
	e[1]=1;
	for(i=2;i