| NOIP201505神奇的幻方 |
|
试题描述
|
|
幻方是一种很神奇的N∗N矩阵：它由数字 1,2,3,……,N∗N构成，且每行、每列 现给定 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）正在玩一个信息传递的游戏。在游戏里每人都有一个 （注意： 可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象） |
|
输入
|
|
共 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-);
}