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

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

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

一、简答题

1. 简答题

转圈游戏

【问题描述】

n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类推。

游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n-m+1 号位置上的小伙伴走到第 1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。

【输入】

输入文件名为 circle.in。

输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。

【输出】

输出文件名为 circle.out。

输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。

【输入输出样例】

【数据说明】

对于 30%的数据,0 < k < 7;

对于 80%的数据,0 < k < 10^7;

对于 100%的数据,1 < n < 1,000,000,0 < m < n,1 ≤ x ≤ n,0 < k < 10^9。

查看答案与解析
答案:<p>import java.util.Scanner;</p><p><br/></p><p><br/></p><p>public class Main {</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>public static void main(String[] args) {</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>Scanner sc = new Scanner(System.in);</p><p><span style="white-space:pre"> </span>int n = sc.nextInt();</p><p><span style="white-space:pre"> </span>int m = sc.nextInt();</p><p><span style="white-space:pre"> </span>int k = sc.nextInt();</p><p><span style="white-space:pre"> </span>int x = sc.nextInt();</p><p><span style="white-space:pre"> </span>sc.close();</p><p><br/></p><p><span style="white-space:pre"> </span>System.out.println((x + m * f(10, k, n)) % n);</p><p><br/></p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>public static int f(int y, int k, int n) {</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>int pingfangshu = y;</p><p><span style="white-space:pre"> </span>int result = 1;</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>while (k != 0) {</p><p><span style="white-space:pre"> </span>if ((k &amp; 1) == 1) {</p><p><span style="white-space:pre"> </span>result *= pingfangshu;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>k &gt;&gt;= 1;</p><p><span style="white-space:pre"> </span>pingfangshu = (pingfangshu * pingfangshu) % n;</p><p><span style="white-space:pre"> </span>result %= n;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>return result;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span></p><p>}</p>
这道题暂未补解析。
2. 简答题

火柴排队

【问题描述】

涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:

其中 ai表示第一列火柴中第 i 个火柴的高度,bi表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。

【输入】

输入文件为 match.in。

共三行,第一行包含一个整数 n,表示每盒中火柴的数目。

第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。

第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。

【输出】

输出文件为 match.out。

输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。

【输入输出样例 1】

【输入输出样例说明】

最小距离是 0,最少需要交换 1 次,比如:交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

【输入输出样例 2】

【输入输出样例说明】

最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交

换第 2 列中后 2 根火柴的位置。

【数据范围】

对于 10%的数据, 1 ≤ n ≤ 10;

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

对于 60%的数据,1 ≤ n ≤ 1,000;

对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤

查看答案与解析
答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int mod=99999997;</p><p style="text-align: left;">const int Max=100005;</p><p style="text-align: left;">int n,m,tot,ans;</p><p style="text-align: left;">int sum[Max],c[Max&lt;&lt;1],num[Max];</p><p style="text-align: left;">struct shu{int num,id;};</p><p style="text-align: left;">shu a[Max],b[Max];</p><p> </p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0,f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();(!isdigit(c))&amp;&amp;(c!='-');c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='0') f=-1,c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x&lt;&lt;3)+(x&lt;&lt;1)+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline bool comp(const shu &amp;a,const shu &amp;b){return a.num&lt;b.num;}</p><p> </p><p style="text-align: left;">inline void pre()</p><p style="text-align: left;">{ </p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(c+1,c+tot+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>m=unique(c+1,c+tot+1)-c-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) a[i].num=lower_bound(c+1,c+m+1,a[i].num)-c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) b[i].num=lower_bound(c+1,c+m+1,b[i].num)-c;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void add(int num)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=num;i&lt;=100000;i+=i&amp;(-i)) sum[i]++;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline int Q(int num)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ans=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=num;i;i-=i&amp;(-i)) ans+=sum[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>return ans;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void solve()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) add(num[i]),ans=(ans+i-Q(num[i]))%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>cout&lt;&lt;ans&lt;&lt;"\n";</p><p style="text-align: left;">}</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>n=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) c[++tot]=a[i].num=get_int(),a[i].id=i;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) c[++tot]=b[i].num=get_int(),b[i].id=i;</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre();</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(a+1,a+n+1,comp),sort(b+1,b+n+1,comp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) num[a[i].id]=b[i].id;</p><p style="text-align: left;"><span style="white-space:pre"> </span>solve();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

货车运输

【问题描述】

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

【输入】

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。

接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。

【输出】

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。

【输入输出样例】

【数据说明】

对于 30%的数据,0 < n < 1,000,0 < m < 10,000,0 < q < 1,000;

对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q < 1,000;

对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q < 30,000,0 ≤ z ≤ 100,000。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;iostream&gt;</p><p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;cstring&gt;</p><p style="text-align: left;">#include&lt;cmath&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</p><p style="text-align: left;">#define _for(i,a,b) for (int i=a;i&lt;=b;i++)</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N=1e4+5,M=5e4+5;//g[u][j]表示u到f[u][j]这条链上边权的最大值。</p><p style="text-align: left;">int n,m,fa[N],h[N],e[M],ne[M],w[M],idx,d[N],f[N][20],g[N][20];</p><p style="text-align: left;">struct node{</p><p style="text-align: left;">    int a,b,w;</p><p style="text-align: left;">    bool operator &lt;(const node&amp; rhs) const{</p><p style="text-align: left;">        return w&gt;rhs.w;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}a[M];</p><p style="text-align: left;">inline void c_plus(){//可以忽略</p><p style="text-align: left;">    ios::sync_with_stdio(false);</p><p style="text-align: left;">    cin.tie(0);</p><p style="text-align: left;">    cout.tie(0);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_list(){//单链表</p><p style="text-align: left;">    idx=0;</p><p style="text-align: left;">    memset(h,-1,sizeof(h));</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void add(int a,int b,int c){//同上</p><p style="text-align: left;">    e[idx]=b;</p><p style="text-align: left;">    w[idx]=c;</p><p style="text-align: left;">    ne[idx]=h[a];</p><p style="text-align: left;">    h[a]=idx++;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_set(){//并查集</p><p style="text-align: left;">    _for(i,1,n){</p><p style="text-align: left;">        fa[i]=i;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">int get(int x){//同上</p><p style="text-align: left;">    if (x==fa[x]){</p><p style="text-align: left;">        return x;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return fa[x]=get(fa[x]);</p><p style="text-align: left;">}</p><p style="text-align: left;">void kruskal(){//kruskal算法</p><p style="text-align: left;">    sort(a+1,a+m+1);</p><p style="text-align: left;">    _for(i,1,m){</p><p style="text-align: left;">        int x=get(a[i].a);</p><p style="text-align: left;">        int y=get(a[i].b);</p><p style="text-align: left;">        if (x!=y){</p><p style="text-align: left;">            fa[y]=x;</p><p style="text-align: left;">            add(a[i].a,a[i].b,a[i].w);</p><p style="text-align: left;">            add(a[i].b,a[i].a,a[i].w);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">void dfs(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>d[u]=d[f[u][0]]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int i=h[u];i!=-1;i=ne[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int j=e[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (j==f[u][0]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;">        }</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[j][0]=u;</p><p style="text-align: left;">        g[j][0]=w[i];//我们需要在dfs函数里给g[v][0]赋初值,为每个结点v上面那条边的权值。</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">int lca(int x,int y){//LCA算法</p><p style="text-align: left;">    if (get(x)!=get(y)){//判断是否合法,在不在一个连通块内</p><p style="text-align: left;">        return -1;</p><p style="text-align: left;">    }</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[x]&lt;d[y]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>swap(x,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>int k=(int)(log2(d[x])),ans=0x7fffffff;//ans存答案</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j&gt;=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[f[x][j]]&gt;=d[y]){</p><p style="text-align: left;">            ans=min(ans,g[x][j]);//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[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><p style="text-align: left;"><span style="white-space:pre"> </span>if (x==y){/</p><p style="text-align: left;"><span style="white-space:pre"> </span>goto output;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>k=(int)(log2(d[x]));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j&gt;=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (f[x][j]!=f[y][j]){</p><p style="text-align: left;">            ans=min(ans,min(g[x][j],g[y][j]));//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[x][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>y=f[y][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><p style="text-align: left;">    ans=min(ans,min(g[x][0],g[y][0]));//最后还差一步才到达lca,因此还要算上最后两条边的最大值</p><p style="text-align: left;">    output:</p><p style="text-align: left;"><span style="white-space:pre"> </span>return ans;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    freopen("truck.in","r",stdin);</p><p style="text-align: left;">    freopen("truck.out","w",stdout);</p><p style="text-align: left;">    c_plus();</p><p style="text-align: left;">    int q,x,y;</p><p style="text-align: left;">    cin&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;">    init_list();</p><p style="text-align: left;">    init_set();</p><p style="text-align: left;">    _for(i,1,m){</p><p style="text-align: left;">        cin&gt;&gt;a[i].a&gt;&gt;a[i].b&gt;&gt;a[i].w;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    kruskal();</p><p style="text-align: left;">    _for(i,1,n){</p><p style="text-align: left;">        if (d[i]==0){//每个连通块都要遍历</p><p style="text-align: left;">            dfs(i);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for (int j=1;(1&lt;&lt;j)&lt;=n;j++){</p><p style="text-align: left;">        _for(i,1,n){</p><p style="text-align: left;">            f[i][j]=f[f[i][j-1]][j-1];</p><p style="text-align: left;">            g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);//通过动态规划计算g数组剩余的值。</p><p style="text-align: left;">//转移方程很显然,就是把从i到f[i][j]这条链,拆成i到f[i][j-1]和f[i][j-1]到f[i][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;">    cin&gt;&gt;q;</p><p style="text-align: left;">    while (q--){</p><p style="text-align: left;">        cin&gt;&gt;x&gt;&gt;y;</p><p style="text-align: left;">        cout&lt;&lt;lca(x,y)&lt;&lt;endl;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。