福建省长乐一中 冲刺Noip2011
冲刺NOIP2011长乐一中day1
题目名称 存盘文件名 输入文件名 输出文件名 时限 内存限制 骑士守卫 knights knights.in knights.out 1s 64M 信任链 chain chain.in chain.out 1s 64M 树形图计数 count count.in count.out 1s 64M 【注意事项】：请自行完成题目，切勿讨论。
题1 骑士守卫
【问题描述】
你现在负责管理骑士，也就是负责城堡的守卫工作。
现在告诉你一个N*M的矩阵，上面有若干位置有骑士，有若干位置有入侵者，还有一个位置是城堡的入口。
骑士每一个单位时间，都会扩展一格视野。假设骑士在x,y，那么在时间t，任意格子i,j，只要满足|x-i|+|y-j|<=t，那么这些格子上的入侵者都是可以发现的。
入侵者每一个单位时间最多可以走一步（可以不走，方向为上下左右中的一个）。一旦入侵者被骑士发现就会消灭，如果在城堡入口被发现了，也会被消灭。 你只需要回答最多有多少入侵者可能通过城堡入口进入城堡。 【输入格式】
第一行2个整数N，M
下面N行M列的整数描述题中的矩阵，表示城堡外的区域，0表示空地，1表示骑士，2表示入侵者，3表示城堡入口。 【输出格式】
输出一行一个整数， 表示最多有多少入侵者可能进入城堡。 【输入样例】 6 5
0 0 3 0 0 0 2 0 0 0 0 0 2 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 2 0 【输出样例】 2
【数据规模】
40%：N，M不超过100，入侵者和骑士都不超过10
100%：所有数字不超过1000，包括骑士数量，入侵者数量什么的。
第 1 页 共 3 页
福建省长乐一中 冲刺Noip2011
题2 信任链
【问题描述】
现在有一排人站成一列，然后开始玩游戏。
现在告诉你有N个人（编号成1到N，排成一列），每个人有一个唯一的数字P。如果有俩个人A和B， 如果B的P是A的编号的约数并且B的编号小于A，那么A就相信B。 现在要找出最长的信任链，即一系列人，每个人都信任他前面的一个人，序列可以不连续。
【输入格式】
第一行一个数N。
下面一行N个数，表示每个人的唯一数字P。 【输出格式】
输出最长的信任链的长度。 【输入样例】 6
1 1 2 1 4 3 【输出样例】 5
【数据规模】 30%：N<1000
100%：N<100000 并且0 题3 树形图计数 【问题描述】 小k同学最近正在研究最小树形图问题。所谓树形图，是指有向图的一棵有根的生成树，其中树的每一条边的指向恰好都是从根指向叶结点的方向。现在小k在纸上画了一个图，他想让你帮忙数一下这个图有多少棵树形图，树形图包括所有点。 【输入格式】count.in 第1行输入1个正整数：n，表示图中点的个数 第2~n+1行每行输入n个字符，描述了这个图的邻接矩阵。第i+1行第j个字符如果是0则表示没有从i连向j的有向边，1表示有一条从i到j的有向边。 【输出格式】count.out 输出1行1个整数，表示这个有向图的树形图个数。 【样例输入】 4 0100 0010 0001 1000 【样例输出】 4 【数据规模和约定】 对于100%的数据，n<=8。 第 2 页 共 3 页 福建省长乐一中 冲刺Noip2011 第 3 页 共 3 页