noip2015 提高组day1、day2

NOIP201505神奇的幻方
 
试题描述

幻方是一种很神奇的N∗N矩阵:它由数字 1,2,3,……,N∗N构成,且每行、每列
及两条对角线上的数字之和都相同。
    当N为奇数时,我们可以通过以下方法构建一个幻方:
    首先将
1 写在第一行的中间。
    之后,按如下方式从小到大依次填写每个数 K(K= 2,3,…,N∗N) :
    1. 若 (K − 1)
在第一行但不在最后一列,则将K 填在最后一行,(K − 1) 所在列
       的右一列;
    2. 若 (K − 1)
在最后一列但不在第一行,则将K 填在第一列,(K − 1) 所在行的上
       一行;
    3. 在第一行最后一列,则将K 填在(K −
1) 的正下方;
    4. 若 (K − 1) 既不在第一行,也不在最后一列,如果 (K − 1) 的右上方还未填数,
       则将 K
填在(K − 1)的右上方,否则将K 填在 (K − 1) 的正下方。

现给定 N,请按上述方法构造 N ∗ N 的幻方。

输入
输入文件名为 magic.in 。
输入文件只有一行,包含一个整数 N,即幻方的大小。
输出
输出文件名为 magic.out 。
输出文件包含N 行,每行N 个整数,即按上述方法构造出的 N ∗ N 的幻方。
相邻两个整数之间用单个空格隔
输入示例
magic.in 
3
输出示例
magic.out
8 1 6
3 5 7
4 9 2
其他说明
对于 100% 的数据,1 ≤ N ≤ 39 且 N 为奇数。
 #include<iostream>
using namespace std;
int n;
int a[][];
int k1[],k2[];
int main()
{
scanf("%d",&n);
a[][n/+]=;
k1[]=;k2[]=n/+;
for(int i=;i<=n*n;i++)
{
if(k1[i-]==&&k2[i-]!=n)
{
a[n][k2[i-]+]=i;
k1[i]=n;k2[i]=k2[i-]+;
}
else if(k2[i-]==n&&k1[i-]!=)
{
a[k1[i-]-][]=i;
k1[i]=k1[i-]-;k2[i]=;
}
else if(k1[i-]==&&k2[i-]==n)
{
a[][n]=i;
k1[i]=;k2[i]=n;
}
else
{
if(!a[k1[i-]-][k2[i-]+])
{
a[k1[i-]-][k2[i-]+]=i;
k1[i]=k1[i-]-;k2[i]=k2[i-]+;
}
else
{
a[k1[i-]+][k2[i-]]=i;
k1[i]=k1[i-]+;k2[i]=k2[i-];
}
}
}
for(int i=;i<=n;i++)
{
printf("%d",a[i][]);
for(int j=;j<=n;j++) printf(" %d",a[i][j]);
printf("\n");
}
}
NOIP201506信息传递
 
试题描述

有N 个同学(编号为 1 到 N)正在玩一个信息传递的游戏。在游戏里每人都有一个
固定的信息传递对象,其中,编号为 i
的同学的信息传递对象是编号为 Ti
的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前
所知的生日信息告诉各自的信息传递对象

(注意: 可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)
。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入
共 2 行。第 1 行包含 1 个正整数 N,表示 N 个人。
第 2 行包含 N 个用空格隔开的正整数 T1 ,T2 ,……,Tn , 其中第 i 个整数Ti 表示编号为 i
的同学的信息传递对象是编号为 Ti 的同学,
Ti ≤ N 且 Ti ≠ i。
数据保证游戏一定会结束。
输出
共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮 。
输入示例
5
2 4 2 3 1
输出示例
3
其他说明
数据范围:对于 100% 的数据,N ≤ 200000。
 #include<iostream>
using namespace std;
int read()
{
char x;
int f=;
x=getchar();
while(x<''&&x>'') x=getchar();
while(x>=''&&x<='')
{
f=f*+x-'';
x=getchar();
}
return f;
} int n,minn=,temp=,s1=,s2=;
int a[],b[];
int dfs(int i)
{
if(b[i])
{
s1=i;
s2=;
temp=;
return ;
}
b[i]=;
int hh=dfs(a[i]);
if(s2) hh++;
if(i==s1) s2=,temp=;
return hh;
}
int main()
{
n=read();
for(int i=;i<=n;i++) a[i]=read();
for(int i=;i<=n;i++)
{
int ls;
if(!b[i]) ls=dfs(i);
if(ls<minn&&temp) minn=ls;
}
printf("%d",minn);
}
NOIP201508跳石头
 
试题描述

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石) 。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石) 。

输入
第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。接下来 N 行,每行一个整数,第 i 行的整数 Di( 0 < Di < L )表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出
只包含一个整数,即最短跳跃距离的最大值。
输入示例
25 5 2
2
11
14
17
21
输出示例
4
其他说明
【样例说明】将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点) 。
【数据范围】100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。
 #include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
#define re(i) i=read()
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int read()
{
int f=;
char x;
x=getchar();
while(x<''||x>'') x=getchar();
while(x>=''&&x<='')
{
f=f*+x-'';
x=getchar();
}
return f;
}
int l,n,m;
int a[],b,c;
bool pd(int mid)
{
int last=;
int ans=;
rep(i,,n)
if(a[i]-last<mid) ans++;
else last=a[i];
if(ans>m) return ;
return ;
}
int main()
{
re(l),re(n),re(m);
rep(i,,n) re(a[i]);
a[n+]=l;n++;
int L=,R=l;
while(L<=R)
{
int mid=(L+R)/;
if(pd(mid)) L=mid+;
else R=mid-;
}
printf("%d",L-);
}
上一篇:NOIP2015 提高组 Day T3 斗地主


下一篇:os.path.md