总的来说，题目还是比较简单的。照顾了全国平均水平。
①图像旋转
问题描述
旋转是图像处理的基本操作，在这个问题中，你需要将一个图像逆时针旋转90度。
计算机中的图像表示可以用一个矩阵来表示，为了旋转一个图像，只需要将对应的矩阵旋转即可。
输入格式
输入的第一行包含两个整数n, m，分别表示图像矩阵的行数和列数。
接下来n行每行包含m个整数，表示输入的图像。
输出格式
输出m行，每行包含n个整数，表示原始矩阵逆时针旋转90度后的矩阵。
样例输入
2 3
1 5 3
3 2 4
样例输出
3 4
5 2
1 3
评测用例规模与约定
1 ≤ n, m ≤ 1,000，矩阵中的数都是不超过1000的非负整数。
代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int n, m;
int a[1005][1005];
int b[1005][1005];
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
scanf("%d", &a[i][j]);
}
}
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
b[i][j] = a[j][m - 1 - i];
}
}
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n - 1; j ++) {
printf("%d ", b[i][j]);
}
printf("%d\n", b[i][n-1]);
}
}
return 0;
}
②数字排序
问题描述
给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。
输入格式
输入的第一行包含一个整数n，表示给定数字的个数。
第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。
输出格式
输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。
样例输入
12
5 2 3 3 1 3 4 2 5 2 3 5
样例输出
3 4
2 3
5 3
1 1
4 1
评测用例规模与约定
1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。
代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
struct node {
int num;
int ci;
}a[1005];
int n;
bool cmp(node a, node b) {
if(a.ci == b.ci) return a.num < b.num;
else return a.ci > b.ci;
}
int main() {
while(scanf("%d", &n) != EOF) {
for(int i = 0; i < 1005; i ++) {
a[i].num = i;
a[i].ci = 0;
}
for(int i = 0; i < n; i ++) {
int x;
scanf("%d", &x);
a[x].ci ++;
}
sort(a, a + 1005, cmp);
for(int i = 0; i < 1005; i ++) {
if(a[i].ci == 0) break;
printf("%d %d\n", a[i].num, a[i].ci);
}
}
return 0;
}
③节日
问题描述
有一类节日的日期并不是固定的，而是以“a月的第b个星期c”的形式定下来的，比如说母亲节就定为每年的五月的第二个星期日。
现在，给你a，b，c和y1, y2(1850 ≤ y1, y2 ≤ 2050)，希望你输出从公元y1年到公元y2年间的每年的a月的第b个星期c的日期。
提示：关于闰年的规则：年份是400的整数倍时是闰年，否则年份是4的倍数并且不是100的倍数时是闰年，其他年份都不是闰年。例如1900年就不是闰年，而2000年是闰年。
为了方便你推算，已知1850年1月1日是星期二。
输入格式
输入包含恰好一行，有五个整数a, b, c, y1, y2。其中c=1, 2, ……, 6, 7分别表示星期一、二、……、六、日。
输出格式
对于y1和y2之间的每一个年份，包括y1和y2，按照年份从小到大的顺序输出一行。
如果该年的a月第b个星期c确实存在，则以”yyyy/mm/dd”的格式输出，即输出四位数的年份，两位数的月份，两位数的日期，中间用斜杠“/”分隔，位数不足时前补零。
如果该年的a月第b个星期c并不存在，则输出”none”（不包含双引号)。
样例输入
5 2 7 2014 2015
样例输出
2014/05/11
2015/05/10
评测用例规模与约定
所有评测用例都满足：1 ≤ a ≤ 12，1 ≤ b ≤ 5，1 ≤ c ≤ 7，1850 ≤ y1, y2 ≤ 2050。
代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool judge(int y) {
if((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)) return true;
return false;
}
int a, b, c, ye1, ye2;
int xingqi[3005][13];//第i年第j个月的第一天为星期几
void init() {
xingqi[1850][1] = 2;
for(int i = 1851; i <= 2050; i ++) {
if(judge(i - 1)) xingqi[i][1] = (xingqi[i - 1][1] + 366 - 1) % 7 + 1;
else xingqi[i][1] = (xingqi[i - 1][1] + 365 - 1) % 7 + 1;
}
for(int i = 1850; i <= 2050; i ++) {
for(int j = 2; j <= 12; j ++) {
xingqi[i][j] = (xingqi[i][j - 1] + month[j - 1] - 1) % 7 + 1;
if(j == 3 && judge(i)) xingqi[i][j] = (xingqi[i][j] + 1 - 1) % 7 + 1;
}
}
//for(int i = 1; i <= 12; i ++) cout << xingqi[2015][i] << " ";
}
int main() {
init();
while(scanf("%d %d %d %d %d", &a, &b, &c, &ye1, &ye2) != EOF) {
for(int y = ye1; y <= ye2; y ++) {
int cha = c < xingqi[y][a] ? 7 + c - xingqi[y][a] : c - xingqi[y][a];
//cout << cha << " ";
int day = (b - 1) * 7 + cha + 1;
month[2] = 28;
if(judge(y)) month[2] = 29;
if(day > month[a]) printf("none\n");
else printf("%4d/%02d/%02d\n", y, a, day);
}
}
return 0;
}
④网络延时
树中的最长路。。
问题描述
给定一个公司的网络，由n台交换机和m台终端电脑组成，交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置，编号为1的交换机为根交换机，层级为1。其他的交换机都连接到一台比自己上一层的交换机上，其层级为对应交换机的层级加1。所有的终端电脑都直接连接到交换机上。
当信息在电脑、交换机之间传递时，每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问，电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。
输入格式
输入的第一行包含两个整数n, m，分别表示交换机的台数和终端电脑的台数。
第二行包含n - 1个整数，分别表示第2、3、……、n台交换机所连接的比自己上一层的交换机的编号。第i台交换机所连接的上一层的交换机编号一定比自己的编号小。
第三行包含m个整数，分别表示第1、2、……、m台终端电脑所连接的交换机的编号。
输出格式
输出一个整数，表示消息传递最多需要的步数。
样例输入
4 2
1 1 3
2 1
样例输出
4
样例说明
其中电脑1与交换机4之间的消息传递花费的时间最长，为4个单位时间。
样例输入
4 4
1 2 2
3 4 4 4
样例输出
4
样例说明
其中电脑1与电脑4之间的消息传递花费的时间最长，为4个单位时间。
评测用例规模与约定
前30%的评测用例满足：n ≤ 5, m ≤ 5。
前50%的评测用例满足：n ≤ 20, m ≤ 20。
前70%的评测用例满足：n ≤ 100, m ≤ 100。
所有评测用例都满足：1 ≤ n ≤ 10000，1 ≤ m ≤ 10000。
代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
const int maxn = 20005;
vector<int> G[maxn];
int vis[maxn];
int first[maxn];
int second[maxn];
int n, m;
int ans;
void dfs(int u) {
int d = G[u].size();
vis[u] = 1;
priority_queue<int> que;
for(int i = 0; i < d; i ++) {
int v = G[u][i];
if(!vis[v]) {
dfs(v);
que.push(first[v]);
}
}
first[u] = second[u] = 0;
if(!que.empty()) {
first[u] = max(first[u], que.top() + 1);
que.pop();
}
if(!que.empty()) second[u] = max(second[u], que.top() + 1);
ans = max(ans, first[u] + second[u]);
return;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 2; i <= n + m; i ++) {
int v;
scanf("%d", &v);
G[i].push_back(v);
G[v].push_back(i);
}
memset(vis, 0, sizeof(vis));
ans = 0;
dfs(1);
printf("%d\n", ans);
return 0;
}
⑤最小花费
待补。。