[TOC]
3.30 算法
OJ
Q1
国际象棋的棋盘上，行数是用数字1到8表示，列数是用字母a到h表示。
放置了一个皇后，返回攻击到的格子。
提示：皇后可以攻击到同一行、同一列以及同一对角线的所有棋子。
输入描述
一个字符串，代表皇后的位置。
输出描述
第一行输出一个整数，代表皇后可以攻击到的格子数量。
第二行输出2个长度为2的字符串，代表皇后能攻击到的格子。
能攻击到的格子有多个，按任意顺序输出均可。
A1
签到题。遍历8x8格子O(n^2)，判断横纵坐标是否相同，或者横纵绝对值差是否为0，注意不要重合。
Q2
一个长度为偶数的数组，每次操作可以将一个数字乘2或将一个数字除以2向下取整。
至少需要操作几次才能把这个数组变成一半是奇数，一半是偶数。
输入描述
第一行输入一个整数n（10^5）表示数组长度，保证n是偶数。
第二行输入 n个整数表示数组。
输出描述
输出一个整数表示答案。
A2
奇乘2变偶，偶除2至少一次以上变奇。
如果奇数数量大于偶数数量，选(count(odd)-count(even))//2奇数变偶数。
如果偶数..大于奇数..，选变奇次数最少的偶数变奇。
遍历一次，统计奇偶，快查一次。O(n)
Q3
给定长度为n的数组a表示每道题的难度。共有 m个考生（10^5），给出每个考生通过题目序列（10^5）。
小红定义成绩异常为以下两种情况中至少出现了一种：
- 通过了一道难度为x的题，但没通过另一道难度小于等于x-500的题。
- 存在至少k对相邻的通过题目难度之差的绝对值大于等于500。
计算有多少考生的成绩异常。
Q3
依次统计即可。
Q4
有n个城市，n个城市（10^5）之间有m条（10^5）飞机和火车的双向线路，保证 n个城市是连通的。
出发点在1号城市，目的地在 n 号城市，她可以选择坐飞机和火车，但是在第 i 个城市转换交通工具需要花费a_i的时间。特别的，小红在1号城市和 n号城市都不需要转换交通工具。
从1号城市到 n号城市最少要花费多少时间。
A4
Dijkstra秒杀，维护一个最小堆，相当于条边是重复边，全部扔堆里面没有任何影响！
Q5
众所周知，所有的无限循环小数都可以写成分数的形式
判断循环节长度为k的无限循环小数的分母是否可能是p。
共有q次询问。每次给出k，p（10^9），判断YES or NO。
循环节定义：如果无限小数的小数点后，从某一位起向右进行到某一位置的一节数字循环出现，首尾衔接，称这种小数为循环小数，这一节数字称为循环节。
A5
分子直接为1，循环节不变，模拟除法。
