首页 › 试卷 › 信息学奥赛 › 信息学奥赛-入门级 › 全国信息学(计算机)奥林匹克联赛(NOIP2014)复赛 普及组

全国信息学(计算机)奥林匹克联赛(NOIP2014)复赛 普及组 VIP

信息学奥赛-入门级 共 4 题 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

珠心算测验

【问题描述】

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

【输入】

输入文件名为 count.in。

输入共两行,第一行包含一个整数 n,表示测试题中给出的正整数个数。

第二行有 n 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。

【输出】

输出文件名为 count.out。

输出共一行,包含一个整数,表示测验题答案。

【输入输出样例】

【样例说明】

由 1+2=3,1+3=4,故满足测试要求的答案为 2。注意,加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 100%的数据,3 ≤ n ≤ 100,测验题给出的正整数大小不超过 10,000。

查看答案与解析
答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define MAXN 1e6+2</p><p style="text-align: left;">#define inf 0x3f3f3f3f</p><p style="text-align: left;">#define rep(x, a, b) for(int x=a; x&lt;=b; x++)</p><p style="text-align: left;">#define per(x, a, b) for(int x=a; x&gt;=b; x--)</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int NC = 1e5+2;</p><p style="text-align: left;">//queue&lt;int&gt; que;</p><p style="text-align: left;">int num[200];</p><p style="text-align: left;">int cot;</p><p style="text-align: left;">int n;</p><p style="text-align: left;">bool visit[200];</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;">    cin&gt;&gt;n;</p><p style="text-align: left;">  rep(i, 1, n)</p><p style="text-align: left;">  {</p><p style="text-align: left;">    cin&gt;&gt;num[i];</p><p style="text-align: left;">  }</p><p style="text-align: left;">  sort(num+1, num+1+n);</p><p style="text-align: left;">  rep(i, 1, n)</p><p style="text-align: left;">  {</p><p style="text-align: left;">      rep(j, i+1, n)</p><p style="text-align: left;">      {</p><p style="text-align: left;">          if(num[i] != num[j])</p><p style="text-align: left;">          {</p><p style="text-align: left;">              rep(k, j+1, n)</p><p style="text-align: left;">              {</p><p style="text-align: left;">                  if(num[i]+num[j] == num[k] &amp;&amp; !visit[k])</p><p style="text-align: left;">                  {</p><p style="text-align: left;">                      cot++;</p><p style="text-align: left;">                      visit[k] = true;</p><p style="text-align: left;">                  }</p><p style="text-align: left;">              }</p><p style="text-align: left;">          }</p><p style="text-align: left;">      }</p><p style="text-align: left;">  }</p><p style="text-align: left;">  cout&lt;&lt;cot;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

比例简化

【问题描述】

在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有 1498 人,反对的有 902 人,那么赞同与反对的比例可以简单的记为1498:902。

不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。因为这个比例的数值太大,难以一眼看出它们的关系。对于上面这个例子,如果把比例记为 5:3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。

现给出支持人数 A,反对人数 B,以及一个上限 L,请你将 A 比 B 化简为 A’比 B’,要求在 A’和 B’均不大于 L 且 A’和 B’互质(两个整数的最大公约数是 1)的前ᨀ下,A’/B’ ≥ A/B且 A’/B’ - A/B 的值尽可能小。

【输入】

输入文件名为 ratio.in。

输入共一行,包含三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。

【输出】

输出文件名为 ratio.out。

输出共一行,包含两个整数 A’,B’,中间用一个空格隔开,表示化简后的比例。

【输入输出样例】

【数据说明】

对于 100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤ L。

查看答案与解析
答案:<p>#include &lt;iostream&gt;</p><p>#include &lt;cstdio&gt;</p><p>#include &lt;string&gt;</p><p>#include &lt;queue&gt;</p><p>#include &lt;cstring&gt;</p><p>#include &lt;cmath&gt;</p><p>#include &lt;cctype&gt;</p><p>#include &lt;vector&gt;</p><p>#include &lt;algorithm&gt;</p><p>#include &lt;map&gt;</p><p>#include &lt;stack&gt;</p><p><br/></p><p>using namespace std;</p><p>typedef long long ll;</p><p>typedef pair&lt;int,int&gt; pa;</p><p>const int N=100005;</p><p>const int mod=99999997;</p><p>int x,y,l;</p><p>int a,b;</p><p>int gcd(int x,int y)</p><p>{</p><p>    if(x&lt;y) return gcd(y,x);</p><p>    if(y==0) return x;</p><p>    return gcd(y,x%y);</p><p>}</p><p>int main()</p><p>{</p><p>    scanf("%d%d%d",&amp;x,&amp;y,&amp;l);</p><p>    double t1,t2,t3;</p><p>    t1=x*1.0/y;</p><p>    t3=l*1.0;</p><p>    for(int i=1;i&lt;=l;i++)</p><p>    {</p><p>        for(int k=1;k&lt;=l;k++)</p><p>        {</p><p>            t2=i*1.0/k;</p><p>            if(t2&gt;=t1 &amp;&amp;gcd(i,k)==1 &amp;&amp; t2-t1&lt;t3)</p><p>            {</p><p>                a=i;</p><p>                b=k;</p><p>                t3=t2-t1;</p><p>            }</p><p>        }</p><p>    }</p><p>    printf("%d %d\n",a,b);</p><p>    return 0;</p><p>}</p>
这道题暂未补解析。
3. 简答题

螺旋矩阵

【问题描述】

一个 n 行 n 列的螺旋矩阵可由如下方法生成:

从矩阵的左上角(第 1 行第 1 列)出发,初始时向右移动;如果前方是未曾经过的格子,则继续前进,否则右转;重复上述操作直至经过矩阵中所有格子。根据经过顺序,在格子中依次填入 1, 2, 3, ... ,,便构成了一个螺旋矩阵。

下图是一个 n = 4 时的螺旋矩阵。

现给出矩阵大小 n 以及 i 和 j,请你求出该矩阵中第 i 行第 j 列的数是多少。

【输入】

输入文件名为 matrix.in。

输入共一行,包含三个整数 n,i,j,每两个整数之间用一个空格隔开,分别表示矩阵大小、待求的数所在的行号和列号。

【输出】

输出文件名为 matrix.out。

输出共一行,包含一个整数,表示相应矩阵中第 i 行第 j 列的数。

【输入输出样例】

【数据说明】

对于 50%的数据,1 ≤ n ≤ 100;

对于 100%的数据,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;stdio.h&gt;</p><p style="text-align: left;">#include&lt;stdlib.h&gt;</p><p style="text-align: left;">#include&lt;string.h&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("matrix.in","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("matrix.out","w",stdout);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int n,i,j;</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d %d %d",&amp;n,&amp;i,&amp;j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=j,y=i;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a=n/2;</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(n%2==0)//判断该数属于第几行 </p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x&gt;a)</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=1+(n-x);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(y&gt;a)</p><p style="text-align: left;"><span style="white-space:pre"> </span>y=1+(n-y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x&gt;a+1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=1+(n-x);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(y&gt;a+1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>y=1+(n-y);<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>int ceng=x&lt;y?x:y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=1;y=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int p=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int m=1;m&lt;ceng;m++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=4*(n-1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>n-=2;</p><p style="text-align: left;"><span style="white-space:pre"> </span>x++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>y++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(y==i)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=j-x;</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%d",p);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>x+=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x==j)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=i-y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%d",p);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>y+=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(y==i)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=x-j;</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%d",p);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>x-=n-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x==j)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>p+=y-i;</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%d",p);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
4. 简答题

 子矩阵

【问题描述】

给出如下定义:

1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

例如,下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如右图所示。

2. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。

3. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个 n 行 m 列的正整数矩阵,请你从这个矩阵中选出一个 r 行 c 列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

【输入】

输入文件名为 submatrix.in。

第一行包含用空格隔开的四个整数 n,m,r,c,意义如问题᧿述中所述,每两个整数之间用一个空格隔开。

接下来的 n 行,每行包含 m 个用空格隔开的整数,用来表示问题᧿述中那个 n 行 m 列的矩阵。

【输出】

输出文件名为 submatrix.out。

输出共 1 行,包含 1 个整数,表示满足题目描述的子矩阵的最小分值。

【输入输出样例 1】

【输入输出样例 1 说明】

该矩阵中分值最小的 2 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、

【输入输出样例 2】

【输入输出样例 2 说明】

该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成,选取的分值最小的子矩阵为

【数据说明】

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N = 20;</p><p style="text-align: left;">int n, m, r, c;</p><p style="text-align: left;">int num[N][N], ch[N], gs = 1;</p><p style="text-align: left;">int lc[N], hc[N][N];</p><p style="text-align: left;">int f[N][N];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">/*</p><p style="text-align: left;">具体思路:</p><p style="text-align: left;">首先想到暴力方法</p><p style="text-align: left;">枚举每个rc大小的矩阵,然后计算差值和,但复杂度过高</p><p style="text-align: left;">需要优化:</p><p style="text-align: left;">首先枚举n行中的r行</p><p style="text-align: left;">利用dfs()枚举每种可能,当dfs()进行到已经不能完成r行时停止</p><p style="text-align: left;">预处理选出来的r行每一列之间的行与行的差值和即lc[i]</p><p style="text-align: left;">在预处理c列中任意两列之间的差值和即hc[i][j] 第i列和第j列的差值和</p><p style="text-align: left;">利用线性dp处理即可</p><p style="text-align: left;">f[i][j]表示前i列中选j列的最小值(选第j列)</p><p style="text-align: left;">f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k])</p><p style="text-align: left;">*/</p><p style="text-align: left;">void Init()</p><p style="text-align: left;">{</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        lc[i] = 0;</p><p style="text-align: left;">        for(int j = 1; j &lt; r; j++)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            lc[i] += abs(num[ch[j]][i] - num[ch[j + 1]][i]);//</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for(int i = 2; i &lt;= m; i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        for(int j = 1; j &lt; i; j++)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            hc[i][j] = 0; //第i列减第j列的中r行的差值差值</p><p style="text-align: left;">            for(int k = 1; k &lt;= r; k++)</p><p style="text-align: left;">            {</p><p style="text-align: left;">                hc[i][j] += abs(num[ch[k]][i] - num[ch[k]][j]);</p><p style="text-align: left;">            }</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">int minn = 2e9;</p><p style="text-align: left;">int cmin;</p><p style="text-align: left;">void dp()</p><p style="text-align: left;">{</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; i++) //前i行</p><p style="text-align: left;">    {</p><p style="text-align: left;">        cmin = min(i, c);</p><p style="text-align: left;">        for(int j = 1; j &lt;= cmin; j++)//选j行</p><p style="text-align: left;">        {</p><p style="text-align: left;">            if(j == 1)</p><p style="text-align: left;">                f[i][j] = lc[i];</p><p style="text-align: left;">            else</p><p style="text-align: left;">            {</p><p style="text-align: left;">                if(i == j)</p><p style="text-align: left;">                {</p><p style="text-align: left;">                    f[i][j] = f[i - 1][j - 1] + lc[i] + hc[i][j - 1];</p><p style="text-align: left;">                }</p><p style="text-align: left;">                else</p><p style="text-align: left;">                {</p><p style="text-align: left;">                    f[i][j] = 2e8;</p><p style="text-align: left;">                    for(int k = j - 1; k &lt; i; k++)</p><p style="text-align: left;">                    {</p><p style="text-align: left;">                        f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k]);</p><p style="text-align: left;">                    }</p><p style="text-align: left;">                }</p><p style="text-align: left;">            }</p><p style="text-align: left;">            if(j == c) minn = min(minn, f[i][c]);//前i列选c列</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void dfs(int node)</p><p style="text-align: left;">{</p><p style="text-align: left;">    if(node &gt; n)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        Init();</p><p style="text-align: left;">        dp();</p><p style="text-align: left;">        return;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    if(r - gs + 1 == n - node + 1)//已经取地行数还没取得行数 优化剪枝</p><p style="text-align: left;">    {</p><p style="text-align: left;">        ch[gs ++] = node;</p><p style="text-align: left;">        dfs(node + 1);</p><p style="text-align: left;">        ch[gs --] = 0;</p><p style="text-align: left;">        return;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    dfs(node + 1);</p><p style="text-align: left;">    if(gs &lt;= r)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        ch[gs ++] = node;</p><p style="text-align: left;">        dfs(node + 1);</p><p style="text-align: left;">        ch[gs --];</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;">    cout &lt;&lt; 2&lt;&lt;20 &lt;&lt; e</p><p style="text-align: left;">    scanf("%d%d%d%d", &amp;n, &amp;m, &amp;r, &amp;c);</p><p style="text-align: left;">    for(int i = 1; i &lt;= n; i++)</p><p style="text-align: left;">        for(int j = 1; j &lt;= m; j++)</p><p style="text-align: left;">            scanf("%d", &amp;num[i][j]);</p><p style="text-align: left;">    dfs(1);</p><p style="text-align: left;">    printf("%d", minn);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。