机试Day2

博主： Xherlock
发布时间：2023 年 05 月 24 日
295 次浏览
暂无评论
1379字数
分类： C/C++&机试

# 机试Day2

一些算法题目需要设置主循环体来接收变量输入，如下代码

~~~c++
while(scanf("%d", &h)!=EOF){
    xxx
}
~~~

原因如下：（EOF=-1）

1. scanf有返回值，返回被输入函数成功赋值的变量个数，上述代码中，如果完成输入并给h赋值，则返回1；**可以通过scanf的返回值来判断循环条件是否成立**。
2. 题目未说明数据只有单组，因此输入数据可能有多组，可以这个循环测试条件对输入是否结束进行判断。

## Hello World for U

[Hello World for U_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/c6e414fddd7c401887c350c9cc41f01b?tpId=40&tqId=21478&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

Given any string of N (>=5) characters, you are asked to form the characters into the shape of U. For example, "helloworld" can be printed as: h d e  l l r lowo That is, the characters must be printed in the original order, starting top-down from the left vertical line with n1 characters, then left to right along the bottom line with n2 characters, and finally bottom-up along the vertical line with n3 characters. And more, we would like U to be as squared as possible -- that is, it must be satisfied that n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 - 2 = N.

**输入描述**：

There are multiple test cases.Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

**输出描述**：

For each test case, print the input string in the shape of U as specified in the description.

~~~
输入：
helloworld!
www.nowcoder.com

输出：
h   !
e   d
l   l
lowor
w    m
w    o
w    c
.    .
n    r
owcode
~~~

### 法1：计算n1、n2较简单，但是遍历赋值是按照输入字符串顺序

思路：

1. **N+2三等分，取小值为n1、n3，n2=N-n1-n2**；
2. 接着定义一个n1\*n2大小的矩阵，全赋值为空格；
3. 按照输入字符串的顺序找对应位置填进去（有些麻烦）；
4. 遍历打印矩阵

~~~c++
#include <iostream>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        int n1, n2;
        int len = str.size();
        n1 = (len + 2) / 3;
        n2 = len + 2 - 2 * n1;
        char u[n1][n2];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                u[i][j] = ' ';
            }
        }
        for (int i = 0; i < len; i++) {
            if (i < n1) {
                u[i][0] = str[i];
            } else if (n1 <= i && i < (n1 + n2 - 1)) {
                u[n1 - 1][i - n1 + 1] = str[i];
            } else {
                u[len - i - 1][n2 - 1] = str[i];
            }
        }
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                printf("%c", u[i][j]);
            }
            printf("\n");
        }
    }
}
~~~

### 法2：一行行直接打印（改进他人）

思路：

1. n1、n2同上法；
2. 不再定义矩阵，直接一行行输出（思路简洁）：**第i行第一个字符就是输入字符串的第i个字符，最后一个字符就是输入字符串的倒数第i个字符**（除了最后一行单独打印）
3. 最后一行采用字符串函数substr直接截取输出

~~~c++
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int main() {
	string str;
	while (cin >> str) {
		int len = str.size();
		int n1 = (len + 2) / 3;
        int n2 = len + 2 - 2 * n1;
		int i = 0;
		while (i < n1-1) {
			cout << str[i];
			for(int j = 0; j < n2 - 2; j++) {
				cout << ' ';
			}
			cout << str[len-i-1] << endl;
			i++;
		}
		cout << str.substr(n1-1, n2) << endl;
	}
	return 0;
}
~~~

## 今年的第几天？

[今年的第几天？_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ae7e58fe24b14d1386e13e7d70eaf04d?tpId=40&tqId=21350&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

输入年、月、日，计算该天是本年的第几天。

**输入描述**：

包括三个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)。

**输出描述**：

输入可能有多组测试数据，对于每一组测试数据， 输出一个整数，代表Input中的年、月、日对应本年的第几天。

~~~
输入：
1990 9 20
2000 5 1
输出：
263
122
~~~

空间换时间，预定义一个int数组存储每个月份的天数（只需定义一年即可），然后每个月循环+天数，若为闰年，在二月时额外+1【闰年定义：4的倍数且不为100的倍数，400的倍数除外】

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int y, m, d;
    while (scanf("%d %d %d", &y, &m, &d) != EOF) {
        int number = 0;
        m -= 1;
        while (m > 0) {
            number += day[--m];
            if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && m == 1) {
                number += 1;
            }
        }
        number += d;
        printf("%d\n", number);
    }
}
~~~

## 打印日期

[打印日期_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/b1f7a77416194fd3abd63737cdfcf82b?tpId=69&tqId=29669&tPage=1&ru=/kaoyan/retest/11002&qru=/ta/hust-kaoyan/question-ranking)

**描述**

给出年分m和一年中的第n天，算出第n天是几月几号。

**输入描述**：

输入包括两个整数y(1<=y<=3000)，n(1<=n<=366)。

**输出描述**：

可能有多组测试数据，对于每组数据， 按 yyyy-mm-dd的格式将输入中对应的日期打印出来。

~~~
输入：
2000 3
2000 31
2000 40
2000 60
2000 61
2001 60
输出：
2000-01-03
2000-01-31
2000-02-09
2000-02-29
2000-03-01
2001-03-01
~~~

同第一题，逆向思维而已

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int y, m, d, number;
    int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    while (scanf("%d %d", &y, &number) != EOF) {
        m = 0, d = 0;
        if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
            day[1] = 29;
        } else {
            day[1] = 28;
        }
        while (number - day[m] > 0) {
            number -= day[m++];
        }
        m++;
        d = number;
        printf("%04d-%02d-%02d\n", y, m, d);
    }
}
~~~

## 日期累加

[日期累加_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/eebb2983b7bf40408a1360efb33f9e5d?tpId=40&tqId=31013&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

设计一个程序能计算一个日期加上若干天后是什么日期。

**输入描述**：

输入第一行表示样例个数m，接下来m行每行四个整数分别表示年月日和累加的天数。

**输出描述**：

输出m行，每行按yyyy-mm-dd的个数输出。

思路就是前两题合并！这里为了简化主函数，单独分出了两个数组（非闰年和闰年）和判断闰年的函数

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

int main() {
    int examples;
    scanf("%d\n", &examples);
    int y, m, d, number;
    int leap;
    while (examples--) {
        scanf("%d %d %d %d", &y, &m, &d, &number);
        leap = is_leap(y);
        m -= 1;
        while (m > 0) {
            number += day[leap][--m];
        }
        number += d;
        if (number > year_day[leap]) {
            number -= year_day[leap];
            y += 1;
        }
        leap = is_leap(y);
        while (number - day[leap][m] > 0) {
            number -= day[leap][m++];
        }
        m++;
        d = number;
        printf("%04d-%02d-%02d\n", y, m, d);
    }
}
~~~

## 日期差值

[日期差值_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ccb7383c76fc48d2bbc27a2a6319631c?tpId=40&tqId=21442&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天

**输入描述**：

有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD

**输出描述**：

每组数据输出一行，即日期差值

~~~
输入：
20110412
20110422
输出：
11
~~~

### 法1：自己的，比较复杂，采用了输入一个int值，拆分为年月日

~~~c++
#include <cstdio>
#include <iostream>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

int main() {
    int day1, day2, leap;
    while (scanf("%d%d", &day1, &day2) != EOF) {
        int y1 = day1 / 10000, m1 = day1 / 100 % 100, d1 = day1 % 100, number1 = 0;
        int y2 = day2 / 10000, m2 = day2 / 100 % 100, d2 = day2 % 100, number2 = 0;
        leap = is_leap(y1);
        m1 -= 1;
        while (m1 > 0) {
            number1 += day[leap][--m1];
        }
        number1 += d1;
        leap = is_leap(y2);
        m2 -= 1;
        while (m2 > 0) {
            number2 += day[leap][--m2];
        }
        number2 += d2;
        for (int i = y1; i < y2; i++) {
            number2 += year_day[is_leap(y1)];
        }
        int diff = number2 - number1 + 1;
        printf("%d\n", diff);
    }
}
~~~

### 法2：结构体表示一个日期，省空间

~~~c++
#include <cstdio>
#include <iostream>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

int main() {
    int leap;
    int y1, m1, d1, number1 = 0;
    int y2, m2, d2, number2 = 0;
    while (scanf("%4d%2d%2d", &y1, &m1, &d1) != EOF) {
        scanf("%4d%2d%2d", &y2, &m2, &d2);
        leap = is_leap(y1);
        m1 -= 1;
        while (m1 > 0) {
            number1 += day[leap][--m1];
        }
        number1 += d1;
        leap = is_leap(y2);
        m2 -= 1;
        while (m2 > 0) {
            number2 += day[leap][--m2];
        }
        number2 += d2;
        for (int i = y1; i < y2; i++) {
            number2 += year_day[is_leap(y1)];
        }
        int diff = number2 - number1 + 1;
        printf("%d\n", diff);
    }
    return 0;
}
~~~

## Day of Week

[Day of Week_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/a3417270d1c0421587a60b93cdacbca0?tpId=40&tqId=21439&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

We now use the Gregorian style of dating in Russia. The leap years are years with number divisible by 4 but not divisible by 100, or divisible by 400. For example, years 2004, 2180 and 2400 are leap. Years 2005, 2181 and 2300 are not leap. Your task is to write a program which will compute the day of week corresponding to a given date in the nearest past or in the future using today’s agreement about dating.

**输入描述**：

There is one single line contains the day number d, month name M and year number y(1000≤y≤3000). The month name is the corresponding English name starting from the capital letter.

**输出描述**：

Output a single line with the English name of the day of week corresponding to the date, starting from the capital letter. All other letters must be in lower case. Month and Week name in Input/Output: January, February, March, April, May, June, July, August, September, October, November, December Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday

### 法1

思路：查看了下题解发现有个计算周几的蔡勒公式，直接记住吧，省得算时间差

$$
W=[\frac{c}{4}-2c+y-1+\frac{y}{4}+[\frac{13(m+1)}{5}]+d]\\W=(W\%7+7)\%7

[蔡勒(Zeller)公式及其推导：快速将任意日期转换为星期数 - faterazer - 博客园 (cnblogs.com)](https://www.cnblogs.com/faterazer/p/11393521.html)

c是世纪数-1，年份前两位；y是年份后两位；m是月份（3-14，1、2月看为上一年的13、14月）；d是日数；[]是向下取整；W是星期【至于什么国外1582年罗马教皇决定啥时候用啥历法，鬼知道他们闲的干啥的，不用管】

需要注意 在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算【记得减年份】

~~~c++
#include <iostream>
using namespace std;

string months[12] = {"March", "April", "May", "June", "July", "August", "September", "October", "November", "December", "January", "February"};
string day_of_week[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

int main() {
    int d, m, y;
    string month;
    while (cin >> d >> month >> y) {
        for (int i = 0; i < 12; i++) {
            if (month == months[i]) {
                m = i + 1 + 2;
                break;
            }
        }
        if (m >= 13) {
            y--;
        }
        int c = y / 100;
        y = y - (y / 100) * 100;
        int w = int(c / 4) - c * 2 + y - 1 + int(y / 4) + int(26 * (m + 1) / 10) + d;
        w = (w % 7 + 7) % 7;
        cout << day_of_week[w] << endl;
    }
}
~~~

【其实这样下来也不简单了】

### 法2：老实按今天周几算当时周几

略。。。

最后修改：2023 年 05 月 24 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

Sqli-labs学习6
浏览次数: 550
C++数据结构1
浏览次数: 343
Vue（二）
浏览次数: 843
pytorch tensor处理
浏览次数: 422
C语言~结构回顾
浏览次数: 522

机试Day2

Xherlock • 2023 年 05 月 24 日

# 机试Day2

一些算法题目需要设置主循环体来接收变量输入，如下代码

~~~c++
while(scanf("%d", &h)!=EOF){
    xxx
}
~~~

原因如下：（EOF=-1）

## Hello World for U

**描述**

**输入描述**：

There are multiple test cases.Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

**输出描述**：

For each test case, print the input string in the shape of U as specified in the description.

~~~
输入：
helloworld!
www.nowcoder.com

输出：
h   !
e   d
l   l
lowor
w    m
w    o
w    c
.    .
n    r
owcode
~~~

### 法1：计算n1、n2较简单，但是遍历赋值是按照输入字符串顺序

思路：

~~~c++
#include <iostream>
using namespace std;

### 法2：一行行直接打印（改进他人）

思路：

~~~c++
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

## 今年的第几天？

**描述**

输入年、月、日，计算该天是本年的第几天。

**输入描述**：

包括三个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)。

**输出描述**：

输入可能有多组测试数据，对于每一组测试数据， 输出一个整数，代表Input中的年、月、日对应本年的第几天。

~~~
输入：
1990 9 20
2000 5 1
输出：
263
122
~~~

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

## 打印日期

**描述**

给出年分m和一年中的第n天，算出第n天是几月几号。

**输入描述**：

输入包括两个整数y(1<=y<=3000)，n(1<=n<=366)。

**输出描述**：

可能有多组测试数据，对于每组数据， 按 yyyy-mm-dd的格式将输入中对应的日期打印出来。

~~~
输入：
2000 3
2000 31
2000 40
2000 60
2000 61
2001 60
输出：
2000-01-03
2000-01-31
2000-02-09
2000-02-29
2000-03-01
2001-03-01
~~~

同第一题，逆向思维而已

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

## 日期累加

[日期累加_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/eebb2983b7bf40408a1360efb33f9e5d?tpId=40&tqId=31013&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

设计一个程序能计算一个日期加上若干天后是什么日期。

**输入描述**：

输入第一行表示样例个数m，接下来m行每行四个整数分别表示年月日和累加的天数。

**输出描述**：

输出m行，每行按yyyy-mm-dd的个数输出。

思路就是前两题合并！这里为了简化主函数，单独分出了两个数组（非闰年和闰年）和判断闰年的函数

~~~c++
#include <iostream>
#include <cstdio>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

## 日期差值

[日期差值_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ccb7383c76fc48d2bbc27a2a6319631c?tpId=40&tqId=21442&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天

**输入描述**：

有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD

**输出描述**：

每组数据输出一行，即日期差值

~~~
输入：
20110412
20110422
输出：
11
~~~

### 法1：自己的，比较复杂，采用了输入一个int值，拆分为年月日

~~~c++
#include <cstdio>
#include <iostream>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

### 法2：结构体表示一个日期，省空间

~~~c++
#include <cstdio>
#include <iostream>
using namespace std;

int day[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
int year_day[2] = {365, 366};

int is_leap(int y) {
    int leap = 0;
    if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) {
        leap = 1;
    }
    return leap;
}

## Day of Week

[Day of Week_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/a3417270d1c0421587a60b93cdacbca0?tpId=40&tqId=21439&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

**输入描述**：

There is one single line contains the day number d, month name M and year number y(1000≤y≤3000). The month name is the corresponding English name starting from the capital letter.

**输出描述**：

### 法1

思路：查看了下题解发现有个计算周几的蔡勒公式，直接记住吧，省得算时间差

$$
W=[\frac{c}{4}-2c+y-1+\frac{y}{4}+[\frac{13(m+1)}{5}]+d]\\W=(W\%7+7)\%7

[蔡勒(Zeller)公式及其推导：快速将任意日期转换为星期数 - faterazer - 博客园 (cnblogs.com)](https://www.cnblogs.com/faterazer/p/11393521.html)

需要注意 在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算【记得减年份】

~~~c++
#include <iostream>
using namespace std;

【其实这样下来也不简单了】

### 法2：老实按今天周几算当时周几

略。。。

发表评论 取消回复

机试Day2

发表评论取消回复