NOIP2014普及组初赛

深碍√TFBOYSˉ_ 2021-11-05 03:50 419阅读 0赞

二、问题求解

1. 将M个同样的球放到N个同样的袋子中，允许有的袋子空着不放，问共有多少种不同的放置方法？（用K表示）

例如：M=7，N=3时，K=8；在这里认为（5,1,1）和（1，5,1）是同一种放置方法。

问：M=8，N=5时，K=\_\_\_\_\_\_\_.

答案：18

> 解析：
> 
> 当只有一个袋子有球时，全部的球都装在一个袋子中：
> 
> 1种
> 
> 当只有2个袋子有球时：两个袋子中球的数量情况：
> 
> 1 7
> 
> 2 6
> 
> 3 5
> 
> 4 4
> 
> 当只有3个袋子有球时：
> 
> 1 1 6
> 
> 1 2 5
> 
> 1 3 4
> 
> 2 2 4
> 
> 2 3 3
> 
> 当只有4个袋子有球时：
> 
> 1 1 1 5
> 
> 1 2 1 4
> 
> 1 3 1 3
> 
> 2 2 1 3
> 
> 3 3 1 1
> 
> 当只有5个袋子有球时：
> 
> 1 1 1 1 4
> 
> 1 2 1 1 3
> 
> 2 2 1 2 1
> 
> 一共有1+4+5+5+3=18种

2. 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是\_\_\_\_\_\_\_\_.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

答案：11

> 解析：
> 
> （1）选择当前距离最短且未被宽展的点A，扩展并更新相邻点的最短距离：
> 
> ![20190808104448516.png][]
> 
> （2） 选择当前距离最短且未被宽展的点B，扩展并更新相邻点的最短距离：
> 
> ![20190808105309627.png][]
> 
> （3）选择当前距离最短且未被宽展的点C或者G（假设选C），扩展并更新相邻点的最短距离：
> 
> ![20190808105252329.png][]
> 
> （4）选择当前距离最短且未被宽展的点G，扩展并更新相邻点的最短距离：
> 
> ![20190808105446784.png][]
> 
> （5）选择当前距离最短且未被宽展的点F，扩展并更新相邻点的最短距离 ：
> 
> ![20190808105704303.png][]
> 
> （6）选择当前距离最短且未被宽展的点D，扩展并更新相邻点的最短距离：
> 
> ![20190808105814918.png][]
> 
> 表格中的数字即为A点到该点的最短距离，因此A到E的最短距离为11.
> 
> ![20190808105856271.png][]

三、阅读程序写结果

#include<iostream>
    using namespace std;
    int main()
    {
    	int a,b,c,d,ans;
    	cin >> a >> b>> c;
    	d = a-b;
    	a = d+c;
    	ans = a*b;
    	cout << "Ans="<< ans << endl;
    	return 0;
    }

输入：2 3 4

输出：\_\_\_\_\_

答案：Ans=9

> 解析：
> 
>     d = a-b;//d=a-b=2-3=-1
>     a = d+c;//a=d+c=-1+4=3
>     ans = a*b;//ans=a*b=3*3=9

#include<iostream>
    using namespace std;
    int fun(int n){
    	if(n==1) return 1;
    	if(n==2) return 2;
    	return fun(n-2)-fun(n-1);
    }
    int main()
    {
    	int n;
    	cin >> n;
    	cout << fun(n) << endl;
    	return 0;
    }

输入：7

输出：\_\_\_\_\_

答案：-11

> 解析：使用递推公式fun(n)=f(n-2)-f(n-1)画表格或者树形结构计算即可。
> 
> ![20190808111320747.png][]

#include<iostream>
    #include<string>
    using namespace std;
    int main()
    {
    	string st;
    	int i,len;
    	getline(cin,st);
    	len = st.size();
    	for(i = 0; i < len; i++){
    		if(st[i] >= 'a' && st[i] <= 'z')
    			st[i] = st[i]-'a'+'A';
    	}
    	cout << st << endl;
    	return 0;
    }

输入：Hello, my name is Lostmonkey.

输出：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

答案：HELLO, MY NAME IS LOSTMONKEY.

> 解析：该代码实现的是将字符串中的所有小写字母转成大写字母。

#include<iostream>
    using namespace std;
    const int SIZE=100;
    int main()
    {
    	int p[SIZE];
    	int n,tot,i,cn;
    	tot=0;
    	cin >> n;
    	for(i = 1; i <= n; i++) p[i]=1;
    	for(i=2;i <= n; i++){
    		if(p[i] == 1) tot++;
    		cn = i*2;
    		while(cn <= n){
    			p[cn] = 0;
    			cn += i;
    		}
    	}
    	cout << tot << endl;
    	return 0;
    }

输入：30

输出：\_\_\_\_\_\_\_\_\_

答案：10

> 解析：该代码是筛选法就质数的代码，将2、3、4、5、6等的倍数筛掉，剩下的就是质数。
> 
> 30以内的质数就有：2、3、5、7、11、13、17、19、23、29.

四、完善程序

1. （数字删除）下面程序的功能是将字符串中的数字字符删除后输出。请填空。

![20190808122817402.png][]

> 解析：
> 
>     #include<iostream>
>     using namespace std;
>     int delnum(char *s){//统计删除数字后的字符串长度
>     	int i,j;
>     	j = 0;
>     	for(i = 0; s[i] != '\0'; i++)
>     		if(s[i] < '0' || s[i] > '9')
>     		{
>     			s[j] = s[i];//s[j]存储非数字字符 
>     			j++; //统计非数字字符的个数 
>     		}
>     	return j;
>     } 
>     
>     const int SIZE = 30;
>     int main(){
>     	char s[SIZE];
>     	int len,i;
>     	cin.getline(s,sizeof(s));
>     	len = delnum(s);
>     	for(i = 0; i < len; i++) cout << s[i];//经过delnum(s)后，s中存储的是删除数字字符后的结果 
>     	cout << endl;
>     	return 0;
>     }

2. （最大子矩阵和）给出m行n列的整数矩阵，求最大的子矩阵和（子矩阵不能为空）。

输入第一行包含两个整数m和n，即矩阵的行数和列数。之后m行，每行n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]

> 解析：
> 
>     #include<iostream>
>     using namespace std;
>     const int SIZE=100;
>     int matrix[SIZE+1][SIZE+1];
>     int rowsum[SIZE+1][SIZE+1];
>     //rowsum[i][j]记录第i行前j个数的和 
>     int m, n, i, j, first, last, area, ans; 
>     int main()
>     {
>     	cin >> m >> n;
>     	for(i = 1; i <= m; i++)
>     		for(j = 1; j <= n; j++)
>     			cin >> matrix[i][j];
>     	ans = matrix[1][1];
>     	for(i = 1; i <= m; i++)//边界 
>     		rowsum[i][0] = 0;
>     	for(i = 1; i <= m; i++)//计算每一行上的连续子段和 
>     		for(j = 1; j <= n; j++)
>     			rowsum[i][j] = rowsum[i][j-1]+matrix[i][j];
>     	for(first = 1; first <= n; first++)//把状态压缩到一列中，相当于求一列中的最大连续子段和 
>     		for(last = first; last <= n; last++){
>     			area = 0;
>     		for(i = 1; i <= m; i++){
>     			area+=rowsum[i][last]-rowsum[i][first-1];
>     			if(area > ans) ans = area;
>     			if(area < 0) area = 0; 
>     		}
>     		}
>     	cout << ans << endl;
>     	return 0;
>     }

## **思路可参考：[https://www.jianshu.com/p/cd257dcb389e][https_www.jianshu.com_p_cd257dcb389e]** ##

之前学过最大子序列的求法：  
要求一个序列中和最大的连续的子序列，那么需要满足一下几步：  
1，子序列的第一个数大于1。  
2，从第一个大于0的数开始累加，不断记录最大的和。  
3，如果出现和小于0，那么说明负数值已经足够多，该记录不再继续，重新开始累加。  
总结成代码函数实现：

int sub_sum(int *b)
    {
        int s,max;
        s = max = b[1];
        int i;
        for(i=2;i<=n;i++)
        {
            s += b[i];
            if(s > max)
                max = s;
            if(s < 0)
                s = 0;
        }
        return max;
    }

而当最大子序列扩展为最大矩阵时，暴力破解必定是超时的，这时需要用到该知识点进行扩展从而求解。  
思路如下：  
1，所求的子矩阵必须是每一行数字个数都相等，每一列的数字个数也相等。  
2，假设都是固定的列数，可以将每一列都加和存入数组，那么得到的就是一个一维的数组，把这个数组求最大子序列即可。  
3，既然是在一个矩阵中求解的，所以子矩阵的列数范围在原矩阵的列数范围之内，用列举方法即可。  
具体图解如下：

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xODI1MDc3LTA3YWEyMWFmYzYzY2RhNjAucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy8xMDAwL2Zvcm1hdC93ZWJw][]

表示，从第一行，第一，二行，到从第一行到最后一行，每次都取各列的和存入数组，求解最大子序列。  
从第二行，第二，三行，到从第二行到最后一行，每次都取各列和存入数组，求最大子序列。  
一直到最后一行，求最大子序列。  
最大子序列中求解最大值，即是所求的解。

整理成代码求解：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 501
    int a[N][N];
    int n,m;
    int sub_sum(int *b)//求最大子序列
    {
        int s,max;
        s = max = b[1];
        int i;
        for(i=2;i<=n;i++)
        {
            s += b[i];
            if(s > max)
                max = s;
            if(s < 0)
                s = 0;
        }
        return max;
    }
    int main()
    {
        int i,j,t,maxsum,s;
        int *b;
        scanf("%d%d",&n,&m);
        b = (int *)malloc(sizeof(int)*(n+1));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        maxsum = a[1][1];
        for(i=1;i<=m;i++)
        {
            memset(b,0,(n+1)*sizeof(int));
            for(j=i;j<=m;j++)
            {
                //固定i,j列
                for(t=1;t<=n;t++)
                    b[t] += a[t][j];//自底向上(固定列m,m,n(固定行n,n,m))
                s = sub_sum(b);
                if(s > maxsum)
                    maxsum = s;
            }
        }
        printf("%d\n",maxsum);
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20211104/33ce83a7e47243dba3b6f03ac2391619.png
[20190808104448516.png]: /images/20211104/c9b85d9aad874d9bb63990b674f0cb35.png
[20190808105309627.png]: /images/20211104/20d351d15b3a45758b8b2b44d6543db2.png
[20190808105252329.png]: /images/20211104/4fb8e3b87dea4c08aa12481819028738.png
[20190808105446784.png]: /images/20211104/aafdfa57d3b949b8b9e41c840ed4f58b.png
[20190808105704303.png]: /images/20211104/7e21ccc2ab5640609f5165add71c7163.png
[20190808105814918.png]: /images/20211104/0d60735216b6497589547e09a3b630a2.png
[20190808105856271.png]: /images/20211104/b88bf8daef3b4d95a425b72aa9efd0f2.png
[20190808111320747.png]: /images/20211104/e0583dad55e1427ba5d3a4662b2877ba.png
[20190808122817402.png]: /images/20211104/c0b972ae9a8b449aa57d3271e8850c75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20211104/032ec2f3c50945ae947831e6a04c8f1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20211104/a4b5310e77794959ac78015e6f559be0.png
[https_www.jianshu.com_p_cd257dcb389e]: https://www.jianshu.com/p/cd257dcb389e
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xODI1MDc3LTA3YWEyMWFmYzYzY2RhNjAucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy8xMDAwL2Zvcm1hdC93ZWJw]: /images/20211104/3da01b74748443408efa3c860d2e270a.png