题目1:日期差值
输入日期格式:YYYYMMDD,求与20190205相隔天数
输入样例20190208,输出样例3
类似题目
原题链接
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
//month[2][0]平年, month[2][1]闰年
int month[13][2] = {{0,0}, {31, 31}, {28,29}, {31,31}, {30,30}, {31, 31}, {30,30},{31, 31}, {31, 31}, {30,30}, {31, 31},{30,30},{31, 31}} ;
bool isLeapYear(int year){
if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)){
return true;
}
return false;
}
int main(){
int time1, time2 = 20190205;
scanf("%d", &time1);
if(time1 > time2){
swap(time1, time2);
}
int y1, m1, d1, y2, m2, d2;
y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
int num = 0;
while(y1 < y2 || m1 < m2 || d1 < d2){
d1++;
num++;
if(d1 == month[m1][isLeapYear(y1)] + 1){
m1++;
d1 = 1;
}
if(m1 == 13){
y1++;
m1 = 1;
}
}
cout << num << endl;
return 0;
}
题目2:最大连续子序列
给定一个数字序列A1,A2…An,求i,j(1<=i<=j<=n),使得Ai+…+Aj最大,输出这个最大和。
第一行输入一个整数n,表示数列大小
第二行输入n个整数
输入样例:6
-2 11 -4 13 -5 -2
输出样例:20
类似题目
复旦只要输出最大连续子列的值
原题链接
#include <cstdio>
#include <vector>
using namespace std;
vector<int> data, dp;
// 最大连续子序列 复旦2019年真题
/**
* 这里很明显是一个动态规划的题
* 设dp[i]是以第i个结尾的序列的最大值
* 1. 状态转移方程
* dp[i] = { dp[i-1] + data[i], dp[i-1] + data[i] >= 0
* 0 , dp[i-1] + data[i] < 0
* 2. 边界条件
* dp[0] = 0;
*/
int main(){
int n, tmp, max=0;
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &tmp);
data.push_back(tmp);
}
// 初始化
for (int i=0; i<=n; i++){
dp.push_back(0);
}
for (int i=1; i<=n; i++){
int pivot = dp[i-1] + data[i-1];
if (pivot >= 0){
dp[i] = pivot;
}else{
dp[i] = 0;
}
}
for (int i=0; i<=n; i++){
if (dp[i] > max){
max = dp[i];
}
}
printf("%d\n", max);
return 0;
}
题目3:有向树的行态
求N个结点能够组成的二叉树的个数。 1<=n<=20
输入样例3,输出样例5
原题链接
#include <cstdio>
// 2019年真题 有向树形态
int main(){
int n;
scanf("%d", &n);
long long data[n+1];
data[0] = 1;
data[1] = 1;
for (int i=2; i<=n; i++){
long long sum = 0, left;
for (int j=0; j<= i-1; j++){
left = i - j - 1;
if (left==j){
sum += data[j]*data[j];
}else{
sum += data[j]*data[left];
}
data[i] = sum;
}
}
printf("%lld\n", data[n]);
return 0;
}
第三题可以这样写,ACwing上面AC了
第三题可以用dp写,lc上有原题,https://leetcode.cn/problems/unique-binary-search-trees/
给一个dfs的思路hh
也可以这样写:
第三题,卡特兰数,
以下写法只能通过较小的N