题目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;
}
第三题可以用dp写，lc上有原题，https://leetcode.cn/problems/unique-binary-search-trees/
#include <iostream> using namespace std; const int N = 25; long long numTrees(int n) { long long dp[N]; dp[0] = 1; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { long long sum = 0; for (int j = 0; j < i; j++) { sum += dp[j] * dp[i - 1 - j]; } dp[i] = sum; } return dp[n]; } int main() { int n; cin >> n; cout << numTrees(n); }第三题可以这样写，ACwing上面AC了
#include<bits/stdc++.h> using namespace std; int n; int main() { cin>>n; long long ans=1; for(int i=n+1,j=1;i<=2*n;i++,j++) { ans=ans*i/j; } cout<<ans/(n+1)<<endl; }完成mark
第二题，如果全是负数的话，按照这样的写法会输出0，但是按照题意似乎必须至少选择一个数，这样写是不是有点问题呀？
给一个dfs的思路hh
#include<bits/stdc++.h> using namespace std; const int N=2e2+10,INF=1e9; int n; int dp[N]; long long dfs(int u){ if(u==0) return 1; if(dp[u]!=0) return dp[u]; for(int i=0;i<=u-1;i++){ dp[u]+=dfs(i)*dfs(u-i-1); } return dp[u]; } int main(){ cin>>n; cout<<dfs(n); }也可以这样写：
///卡特兰数 #include <iostream> using namespace std; const int N = 22; int n; int main() { cin >> n; long long a = 1, b = 1; for(int i = 2 * n; i > n; i--) { a *= i; b *= (i - n); //防止最后的数过大 if(a % b == 0) { a = a / b; b = 1; } } cout << a / b / (n + 1) << endl; }第三题，卡特兰数，
以下写法只能通过较小的N
#include <iostream> using namespace std; long long Cmn(long long n) { long long fengzi = 1, fengmu = 1; for (int i = 2 * n; i > n; i--) { fengzi *= i; } for (int i = n; i > 1; i--) { fengmu *= i; } return fengzi / fengmu; } int main() { long long N; cin >> N; cout << Cmn(N) / (N + 1) << endl; return 0; }