首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2

全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 VIP

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

一、简答题

1. 简答题

无线网络发射器选址

【问题描述】

随着智能手机的日益普及,人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。

东西向街道和南北向街道相交形成路口,规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是(x, y)。在某些路口存在一定数量的公共场所。

由于政府财政问题,只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心,边长为 2*d 的正方形。传播范围包括正方形边界。

例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器,希望你帮助他们在城市内找出合适的安装地点,使得覆盖的公共场所最多。

【输入】

输入文件名为 wireless.in。

第一行包含一个整数 d,表示无线网络发射器的传播距离。

第二行包含一个整数 n,表示有公共场所的路口数目。

接下来 n 行,每行给出三个整数 x, y, k, 中间用一个空格隔开,分别代表路口的坐标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。

【输出】

输出文件名为 wireless.out。

输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点方案数,以及能覆盖的最多公共场所的数量。

【输入输出样例】

【数据说明】

对于 100%的数据,1 ≤ d ≤ 20,1 ≤ n ≤ 20, 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤1,000,000。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;cstdlib&gt;</p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    int ans=0,d,n,x,y,k[129][129],jc=0,sum=0,m1,m2,n1,n2;</p><p style="text-align: left;">    bool city[129][129];</p><p style="text-align: left;">    scanf("%d",&amp;d);</p><p style="text-align: left;">    scanf("%d",&amp;n);</p><p style="text-align: left;">    for (int i=1;i&lt;=n;i++) {</p><p style="text-align: left;">                            scanf("%d%d",&amp;x,&amp;y);</p><p style="text-align: left;">                            scanf("%d",&amp;k[x][y]);</p><p style="text-align: left;">                            city[x][y]=true;</p><p style="text-align: left;">                            }          </p><p style="text-align: left;">    for (int i=0;i&lt;=128;i++)</p><p style="text-align: left;">        for (int j=0;j&lt;=128;j++){</p><p style="text-align: left;">            n1=i-d;n2=i+d;m1=j-d;m2=j+d;</p><p style="text-align: left;">                     if (n1&lt;0) n1=0;if (n2&gt;128) n2=128;</p><p style="text-align: left;">                     if (m1&lt;0) m1=0;if (m2&gt;128) m2=128;</p><p style="text-align: left;">            for (int q=n1;q&lt;=n2;q++)</p><p style="text-align: left;">                 for (int p=m1;p&lt;=m2;p++)</p><p style="text-align: left;">                             if (city[q][p]) ans=ans+k[q][p];  </p><p style="text-align: left;">            if (ans&gt;jc) {jc=ans;</p><p style="text-align: left;">                         sum=1;}</p><p style="text-align: left;">            else if (ans==jc) sum++;</p><p style="text-align: left;">            ans=0;</p><p style="text-align: left;">                                 }</p><p style="text-align: left;">    printf("%d %d\n",sum,jc);</p><p style="text-align: left;">    //system("pause");                           </p><p style="text-align: left;">    return 0;   </p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

寻找道路

【问题描述】

在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:

1.路径上的所有点的出边所指向的点都直接或间接与终点连通。

2.在满足条件 1 的情况下使路径最短。

注意:图 G 中可能存在重边和自环,题目保证终点没有出边。

请你输出符合条件的路径的长度。

【输入】

输入文件名为 road.in。

第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。

接下来的 m 行每行 2 个整数 x、y,之间用一个空格隔开,表示有一条边从点 x 指向点y。

最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。

【输出】

输出文件名为 road.out。

输出只有一行,包含一个整数,表示满足题目᧿述的最短路径的长度。如果这样的路径不存在,输出-1。

【输入输出样例 1】

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题目描述的路径不存在,故输出-1。

【输入输出样例 2】

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2连了一条边到点 6,而点 6 不与终点 5 连通。

【数据说明】

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">#define ll long long</p><p style="text-align: left;">#define MAXN 500010</p><p style="text-align: left;">#define N 201</p><p style="text-align: left;">#define INF 0x7f7f7f7f</p><p style="text-align: left;">#define gtc() getchar()</p><p><br style="text-align: left;"/></p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">template &lt;class T&gt;</p><p style="text-align: left;">inline void read(T &amp;s){</p><p style="text-align: left;"><span style="white-space:pre"> </span>s = 0; T w = 1, ch = gtc();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>s *= w;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">template &lt;class T&gt;</p><p style="text-align: left;">inline void write(T x){</p><p style="text-align: left;">    if(x &lt; 0) putchar('-'), x = -x;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x &gt; 9) write(x/10);</p><p style="text-align: left;">    putchar(x % 10 + '0');</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">struct node{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y, ne, z;</p><p style="text-align: left;">}e[MAXN];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int lin[MAXN], len = 0;</p><p style="text-align: left;">inline void add(int x, int y, int z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++len].y = y, e[len].ne = lin[x], lin[x] = len;</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[len].z = z;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int n, m;</p><p style="text-align: left;">int st, ed;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int col[MAXN], vis[MAXN];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void bfs(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue&lt;int&gt; q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[u] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = q.front(); q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[x]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y; </p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 1) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(vis[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[y] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(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>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void bfs2(int u){//这个不是bfs,之前写错写成bfs,后来直接在这个函数里改了。</p><p style="text-align: left;"><span style="white-space:pre"> </span>col[u] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[u]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 1) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(col[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>col[y] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int dis[MAXN];</p><p style="text-align: left;">void bfs3(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(dis, INF, sizeof(dis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[u] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue&lt;int&gt; q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = q.front(); q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[x]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 2) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(col[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[y] != INF) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[y] = dis[x] + 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(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>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></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>read(n), read(m);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x, y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= m; ++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>read(x), read(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>add(x, y, 1); add(y, x, 2);//1为正边,2为负边</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>read(st), read(ed);</p><p style="text-align: left;"><span style="white-space:pre"> </span>bfs(ed);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= n; ++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>bfs2(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><p style="text-align: left;"><span style="white-space:pre"> </span>bfs3(st);<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[ed] == INF) puts("-1");</p><p style="text-align: left;"><span style="white-space:pre"> </span>else printf("%d\n", dis[ed]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

解方程

【问题描述】

已知多项式方程:

【输入】

输入文件名为 equation.in。

输入共 n+2 行。

第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。

接下来的 n+1 行每行包含一个整数,依次为

【输出】

输出文件名为 equation.out。

第一行输出方程在[1, m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【数据说明】

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define LL long long</p><p style="text-align: left;">#define mod 1000000007</p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">inline LL read() {</p><p style="text-align: left;">    LL x = 0; int t = 1; char ch = getchar();</p><p style="text-align: left;">    while(ch &gt; '9' || ch &lt; '0')    { if(ch == '-') t = -1; ch = getchar(); }</p><p style="text-align: left;">    while(ch &gt;= '0' &amp;&amp; ch &lt;= '9') { x = ((x &lt;&lt; 1) % mod + (x &lt;&lt; 3) % mod + ch - '0') % mod;    ch = getchar(); }</p><p style="text-align: left;">    return x * t;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">LL a[105];</p><p style="text-align: left;">int n, m, ans[1000005], tot;</p><p style="text-align: left;">inline bool cal(int x) {</p><p style="text-align: left;">    LL res = a[n];</p><p style="text-align: left;">    for(int i = n - 1; i &gt;= 0; i --)</p><p style="text-align: left;">        res = (res * x % mod + a[i]);</p><p style="text-align: left;">    return res == 0;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main() {</p><p style="text-align: left;">    n = read(); m = read();</p><p style="text-align: left;">    for(int i = 0; i &lt;= n; i ++)    a[i] = read();</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; i ++)</p><p style="text-align: left;">        if(cal(i))    ans[++tot] = i;</p><p style="text-align: left;">    printf("%d\n", tot);</p><p style="text-align: left;">    for(int i = 1; i &lt;= tot; i ++)</p><p style="text-align: left;">        printf("%d\n", ans[i]);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。