第五周提前写完了。把博客也放出来然后可以干别的了。

从总体来说第五周题目质量还可以，难度也还行，比第四周的啥多项式（没错我又要吐槽了）好了不少。

最简分数排序-2

【问题描述】 从标准输入上读入正整数N(N<5000)，以及一个表示排序区间的字符串。找出所有分母不大于N、且数值在0和1之间的最简真分数，以值的升序方式对这些分数进行排序，输出排序后指定区间的分数。区间字符串的格式为a-b，其中a和b均为正整数，表示排序后从1起算的第a个到第b个(含)分数。当a被省略时，表示从1开始，当b被省略或b大于所有分数的数量时，表示直到排序后的最后一个分数，当a和b都被省略时，表示输出全部分数。各分数之间使用一个空格分隔，分子、斜线及分母之间不留空格。例如，当输入数据为5 - 时，满足条件的最简真分数有1/2，1/3，2/3，1/4，3/4，1/5，2/5，3/5，4/5，则输出内容及格式如下：  1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 当输入数据为5 3-6，则输出内容及格式如下： 1/3 2/5 1/2 3/5 【输入形式】 从标准输入上读入正整数N(N<5000)，以及一个表示排序区间的字符串。 【输出形式】 标准输出上输出结果。行末输出回车。 【输入样例1】 5 - 【输出样例1】 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 【输入样例2】 5 3-6 【输出样例2】 1/3 2/5 1/2 3/5 【时间限制】 1s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为fraction.c。

往前期末考试题系列。期末题一般还是比较和善的，从思路难度到编码实现难度上都不大。

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXNUM 10000007 struct _fraction { int numer; //分子 int denom; //分母 }fraction[MAXNUM]; int cmp(const void *p1, const void *p2); int construct(int n); int gcd(int a, int b); void analyse(char s[], int cnt, int *left, int *right); void print(int left, int right); int main() { int n, cnt; int left, right; char s[10]; scanf("%d", &n); scanf("%s", s); cnt = construct(n); analyse(s, cnt, &left, &right); print(left, right); } int construct(int n) { int i, j; int cnt = 0; for (i = 2; i <= n; i++) { for (j = 1; j < i; j++) { if (gcd(i, j) == 1) { fraction[cnt].denom = i; fraction[cnt].numer = j; cnt++; } } } qsort(fraction, cnt, sizeof(fraction[0]), cmp); return cnt; } void analyse(char s[], int cnt, int *left, int *right) { int i = 0; int temp = 0; if (s[0] == '-') *left = 1; else { for (i = 0; s[i] != '-'; i++) temp = 10 * temp + s[i] - '0'; *left = temp; } i++; temp = 0; if (s[i] == '\0') { *right = cnt; } else { for (; s[i] != '\0'; i++) temp = 10 * temp + s[i] - '0'; *right = temp > cnt ? cnt : temp; } } void print(int left, int right) { int i; for (i = left - 1; i <= right - 1; i++) { printf("%d/%d ", fraction[i].numer, fraction[i].denom); } } int cmp(const void *p1, const void *p2) { struct _fraction *a = (struct fraction *)p1; struct _fraction *b = (struct fraction *)p2; return a->numer * b->denom - a->denom * b->numer; } int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); }

思路就是对于小于n的每一组数判断是不是最简分数（最大公约数是否为1），是的话就构造。然后对分数排序（我这里是表示通分后比大小），然后分析左边界和右边界，输出左边界和右边界中间的所有分数。很直观的题。

放置正方形

【问题描述】 将一个矩形划分成N*M个格子，每个格子有被占用和未被占用两种情况，将一个边长为i的正方形放入矩形中，要求正方形区域中不包含被占用的格子，问共有多少种合适的放置方案。 【输入形式】 输入文件为当前目录下的squares.in。 该文件第一行是一个整数i (1<i<=min(M,N))，表示正方形的边长。之后有N(1<=N <=2000)行，每行有M(1<=M<=2000)个0或1（1表示该格未被占用，0表示该格被占用）。输入以EOF结束。 【输出形式】 输出文件为当前目录下的squares.out。 该文件只有一个整数输出，表示边长为i的正方形在矩形中合适的放置方案数。 【输入样例】 2  1011  1111  1110  1110 【输出样例】 5 【时间限制】 2s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为squares.c。

输入还是比较奇怪，问题不大。

这题一眼望去就是用暴力做了（不是），但是暴力的话会超时。（不过用暴力可以拿到大半分数，只有一个超时）。所以得另找思路。

其实也还好，每次我们判断能否放下的时候，其实是在判断一个i*i的矩阵中是否有0，换句话说该矩阵如果全都是1才能放下。这时矩阵的“面积”应该为i*i。所以我们只需要判断一个矩阵的各个元素之和即可。

比较快一点的方法是二维前缀和，即开始时记录每个点到（0，0）这个矩阵中有多少个1。可以用类似DP的思路，sum(右下)=左下+右上-左上+a(i,j)。如果有图会很好理解，类似于排列组合的问题。

然后判断矩阵面积时，如果要(i,j)到(i+N,j+N)这一段的面积，其实是右下+左上-左下-右上。不过这个左上左下右上都不包括(i,j)这个点，而是在其外层一圈的。有图也会好理解一点。

#include<stdio.h> #include<string.h> #include<stdbool.h> #define MAXNUM 2002 void read(int a[][MAXNUM], int *n, int *m); void add(int a[][MAXNUM], int sum[][MAXNUM], int n, int m); int count(int sum[][MAXNUM], int n, int m, int N); int a[MAXNUM][MAXNUM] = { 0 }; int sum[MAXNUM][MAXNUM] = { 0 }; int main() { freopen("squares.in", "r", stdin); freopen("squares.out", "w", stdout); int N; int n, m; int cnt; scanf("%d", &N); read(a, &n, &m); add(a, sum, n, m); cnt = count(sum, n, m, N); printf("%d", cnt); } void read(int a[][MAXNUM], int *n, int *m) { char s[MAXNUM]; int row = 1, col = 1; int i; fgets(s, MAXNUM, stdin); while (fgets(s, MAXNUM, stdin) != NULL) { for (i = 0; s[i] == '0' || s[i] == '1'; i++) { a[row][col++] = s[i] - '0'; } *m = col - 1; row++; col = 1; } *n = row - 1; } void add(int a[][MAXNUM], int sum[][MAXNUM], int n, int m) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; } } } int count(int sum[][MAXNUM], int n, int m, int N) { int i, j; int cnt = 0; for (i = 0; i <= n - N; i++) { for (j = 0; j <= m - N; j++) { if (sum[i + N][j + N] + sum[i][j] - sum[i + N][j] - sum[i][j + N] == N * N) cnt++; } } return cnt; }

选排列

【问题描述】 求从n个自然数(1-n)中选取m个数的所有的排列形式，即求P（n，m）的所有的排列形式，且按升序排列。 【输入形式】 标准输入。输入只有一行，包括两个整数n和m，其中0<n,m<=9，二者之间以一个空白符分隔。 【输出形式】 在标准输出上输出有若干行，每一行都是符合题意的一种排列形式，每个元素间用一个空格分隔，并按升序排列。 【输入样例】 3 2 【输出样例】 1 2  1 3  2 1  2 3  3 1  3 2 【时间限制】 2s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为pailie.c。

和全排列差不多，DFS，有了思路的话毫无难度的一题。

矩阵乘法B

【问题描述】 从文件arr.in中读入一个m行k列的整数矩阵a和一个k行n列的整数矩阵b(1 < m, k, n < 200)，在标准输出上输出这两个矩阵的乘积。 【输入形式】 输入文件arr.in中有m+k行，前m行是矩阵a的元素aij，后k行是矩阵b的元素bij (-3000 < aij, bij < 3000)。 【输出形式】 输出结果为m行，每行n个元素，按整数左对齐方式输出，每个元素占相同的位数，且各个元素之间空格的最少数量应等于1。 【输入样例】 1 0  0 1  1 1  1 1 【输出样例】 1 1  1 1 【时间限制】 1s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为arr.c。

。。。啥玩意，不知道从何吐槽起了。

先读一下总行数然后读了一行确定k，那m就是总行数-k了。除此之外和A基本一模一样。无聊的题。

单词连接

【问题描述】 对N(2≤N≤100000)个由M(2≤M≤1000)个小写字母组成的英文单词排序, 使得相邻的两个单词中前一个单词的末字母等于后一个单词的首字母。 【输入形式】 从标准输入上读入。 输入文件有N(2≤N≤100000)行，每行只含一个单词，单词之间以换行符分隔，以EOF结束。 【输出形式】 输出到标准输出。 输出内容占一行，以换行符结束。对于可以按上述规则排列的输入，输出yes；否则输出no。 【输入样例】 mouse  acm  malform 【输出样例】 yes 【时间限制】 1s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为words.c。

这次最有意思的一题了，也是蛮老的题目。好在上课有讲过思路，所以很顺利写出来了。总的来说是解题思路>编程难度的一题。这题需要用图的模型来解决。然而连我这种不怎么会写图的人也过了= =

首先是解题思路，我们需要构造图的模型。如果以单词作为节点，以单词尾字母的有向边连接，那么我们需要遍历所有的顶点才行，这就是哈密顿回路的问题。按照这个规模，肯定是无法完成的。

正确思路是以26个字母作为顶点，以单词作为弧，即从尾字母指向另一个首字母的有向边。这样我们只需要经过所有边即可，这就是欧拉通路问题（即一笔画问题），可以说容易解决很多。判定条件：

1、图为连通的。这里的连通是弱连通（即其对应的无向图为连通的），因为只要弱连通都有可能用一笔画画出来。接下来的判断由条件2来判断。

2、所有顶点入度=出度。或有一个点入度-出度=1，这个点称为终点，以及一个点出度-入度=1，这个点称为起点。

基于这两个条件应该很容易能写出来了。首先数据结构直接用邻接矩阵来存储即可，因为只需要知道一个顶点到另一个顶点有几条边就够了。另外需要两个数组分别存入度与出度。写完才发现这里甚至原始的有向图都没必要存，存个无向图即可。

首先判断一下无向图连通性，这里我直接DFS了。如果有顶点入度出度都为0说明没出现过，跳过这个点即可。接下来是判断出入度，代码也很简单。

#include<stdio.h> #include<string.h> #include<stdbool.h> #define MAX_VERTEX_NUM 26 #define MAX_WORDS_LENGTH 1001 int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = { 0 }; //邻接矩阵存图 int temp[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = { 0 }; //无向图，判断弱连通 int inner[MAX_VERTEX_NUM] = { 0 }; //入度 int outer[MAX_VERTEX_NUM] = { 0 }; //出度 int visited[MAX_VERTEX_NUM] = { 0 }; //DFS void DFS(int v); bool connect(int v); bool judge(); int main() { char s[MAX_WORDS_LENGTH]; int v1, v2; while ((scanf("%s", s)) != EOF) { v1 = s[0] - 'a'; v2 = s[strlen(s) - 1] - 'a'; graph[v1][v2] ++; temp[v1][v2] ++; temp[v2][v1] ++; inner[v2] ++; outer[v1] ++; } if (!connect(v1)) printf("no\n"); else if (!judge()) printf("no\n"); else printf("yes\n"); } void DFS(int v) { visited[v] = 1; int i; for (i = 0; i < MAX_VERTEX_NUM; i++) if (temp[v][i] != 0 && visited[i] == 0) DFS(i); } bool connect(int v) { int i; DFS(v); for (i = 0; i < MAX_VERTEX_NUM; i++) if (visited[i] == 0 && (inner[i] != 0 || outer[i] != 0)) return false; return true; } bool judge() { int one = 0, mone = 0; int i; for (i = 0; i < MAX_VERTEX_NUM; i++) { if (inner[i] - outer[i] == 0) continue; else if (inner[i] - outer[i] == 1) one++; else if (inner[i] - outer[i] == -1) mone++; else return false; } if (one == 1 && mone == 1) return true; else if (one == 0 && mone == 0) return true; return false; }

C2可以放一下先干别的了= =