计院
A 相隔天数
输入一个 yyyymmdd 格式的时间，如 20190318，计算与 20190205 相差的天数，
取绝对值，所有输入在 19000101 和 21000101 之间。
样例输入：20190208
输出：3
#include<iostream>using namespace std;int month_day[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}};int Isrunyear(int year){if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) return 1;return 0;
}
int main(){int y1,y2 = 19001001;cin >> y1;if(y1 < y2) swap(y1,y2);int year1 = y1 /10000,month1 = (y1/100) % 100,day1 = y1 % 100;int year2 = y2 /10000,month2 = (y2/100) % 100,day2 = y2 % 100;int num = 0;while(year1 > year2 || month1 > month2 || day1 > day2){num++;day2++;if(day2 == month_day[month2][Isrunyear(year2)] + 1) { //这里没考虑好二维矩阵下标问题。全局变量越界访问等于访问0day2 = 1;month2++;}if(month2 == 13) {month2 = 1; //这里=写成==year2++;}}cout << num;return 0;
}
// 出现问题耐心调试！备注写了些写的过程中的错误。一道并不难的题写了很久。。。细节问题要注意。继续加油吧~
B 最大连续子序列
//10.24
#include<iostream>
#include<vector>
using namespace std;vector<int> a,dp;
int main(){int n;cin >> n;a.push_back(0);for(int i = 1;i <= n;i++) {int x;cin >> x;a.push_back(x);}int max1 = 0;for(int i = 0;i <= n;i++)dp.push_back(0);for(int i = 1;i <= n;i++){int sum = dp[i - 1] + a[i];if(sum < 0 ) dp[i] = 0;else {dp[i] = sum;max1 = max(max1,sum);}} cout << max1;return 0;
}DP问题
状态定义：dp[i]表示以第i个数结尾的序列集合中的最大值
状态划分：以sum = dp[i - 1] + a[i]是否大于0划分（因为本题答案一定为正数，所以可以这么划分）
C 二叉树形态
#include<iostream>
#include<vector>
using namespace std;const int N = 21;
long long dp[N];
int main(){int n ;cin >> n;dp[0] = 1;dp[1] = 1;for(int i = 2;i <= n;i++){long long sum = 0;for(int j = 0;j <= i - 1;j++)sum += dp[j] * dp[i - j - 1];dp[i] = sum;}cout << dp[n];return 0;
}状态定义：dp[i]表示节点数为i的二叉树形态有几个
状态划分：根据根节点的左右子树有0 、 1、 2...i-1个来划分
都是很简单的dp问题，可是自己就是想不出来。。。吐了。。。
工研院
A 九键输入
//11.58
#include<iostream>
#include<vector>
#include<map>using namespace std;
char input[100];
const int N = 21;
map<int,char> g;int main(){int num = 0;for(int i = 2;i <= 7;i++){int k = i;for(int j = 1;j <= 3;j++, k = k* 10 + i){g.insert({k,'a' + num});num++;}}g.insert({0,' '});g.insert({7777,' S'});g.insert({8,' T'});g.insert({88,' U'});g.insert({888,' V'});g.insert({9,' W'});g.insert({99,' X'});g.insert({999,' Y'});g.insert({9999,' Z'});int length = 0;while(cin >> input[length++]); //字符串输入for(int i = 0;i < length - 1;i++){if(input[i] == '-') continue;if(input[i] == '0') {cout << ' ';continue;}char output = input[i];int num = output - '0';int j = 1;while(input[i + 1] == output) i++,j++;if(j == 1) cout << g[num];if(j == 2) cout << g[num * 10 + num];if(j == 3) cout << g[num * 100 + num * 10 + num];}return 0;
}其实可以用二维数组存的，会更加方便一些。
B 服务器维护
假设有编号从1-N的服务器，首先给出服务器个数，再给出一组服务器状态。
然后给出一次数字，表示修改状态次数，接下来输入为i，j，x，意思是使用x修改从i到j的服务器。
最后输出所有服务器状态
例：
输入：
5
1 2 2 3 1
2
1 2 5
2 5 -1
输出：
6 6 1 2 0
#include<iostream>
using namespace std;int main(){int n;cin >> n;int a[n + 2],b[n + 2]; //0,n+1可能会访问到，所以多加2a[0] = b[0] = 0;for(int i = 1;i <= n;i++) cin >> a[i];for(int i = 1;i <= n;i++) b[i] = a[i] - a[i - 1];int m;cin >> m;while(m--){int l,r,x;cin >> l >> r >> x;b[l] += x;b[r + 1] -= x;}for(int i = 1;i <= n;i++) {a[i] = a[i - 1] + b[i]; cout << a[i] << ' ';}return 0;
}
前缀和与差分
前缀和：可用来求数组a中第i到第j个数的和
如何生成前缀和
//a为数组值，s为前缀和 注意为了之后运算方便，a、s都从下标1开始存。下标0定义为0。
s[0] = 0;
for(int i = 1;i <= n;i++)s[i] = s[i - 1] + a[i]如何求区间和
sum_ij = s[j] - s[i - 1]差分——前缀和逆运算：可用来是数组的某一区间里的数加上同一个数值
设原数组为a1，a2...an，构造b数组使a数组为b数组的前缀和。即b数组为a数组的差分。
b1 = a1
b2 = a2 - a1
b3 = a3 - a2
...
bn = an - a(n-1)
则 ai = b1 + b2 + ... + bi
若bi + c，则原数组ai ai+1 ... an都加上c。 因为ai = b1 + b2 + .. + bi + c，ai + 1 = b1 + b2 + ...+bi + c + bi+1以此类推
同理若bj - c，则原数组aj ，aj+1 ... an都会减去c。
故若想让ai到aj这个的数都加上c，只需bi + c，bj+1 - c。
C 计算通讯代价
给定一个无向图，保证是一棵树，定义两个结点 ab 之间的通信代价为 ab 路径
上的边的数目，节点 a 的通信代价为 a 到其他所有节点的通信代价之和。在一
行中输出所有结点的通信代价。
样例输入：
4
1 2
2 3
2 4
输出：
5 3 5 5
#include<iostream>
#include<cstring>
using namespace std;int g[10][10];void Dig(int i,int n){bool flag[n + 1];memset(flag,0,sizeof(flag));flag[i] = true;int m = n - 1;while(m--){int min1 = 0x3f3f3f3f,pos;for(int k = 1;k <= n;k++)if(g[i][k] < min1 && !flag[k]){ // 找到集合外最小值min1 = g[i][k];pos = k;}flag[pos] = true;for(int k = 1;k <= n;k++)if(g[i][k] > g[i][pos] + g[pos][k] && !flag[k])g[i][k] = g[i][pos] + g[pos][k];}
}int main(){int n;cin >> n;int m = n - 1;memset(g,0x3f,sizeof(g));while(m--){int x,y;cin >> x >> y;g[x][y] = 1;g[y][x] = 1;}for(int i = 1;i <= n;i++)Dig(i,n);int sum[n + 1];memset(sum,0,sizeof(sum));for(int i = 1;i <= n;i++)for(int j =1;j <= n;j++)if(g[i][j] != 0x3f3f3f3f) sum[i] +=g[i][j];for(int i = 1;i <= n;i++) cout << sum[i] << ' ';return 0;
}想了一个时间复杂度为n^3的算法。分别以树中的每个顶点为源点使用digstra算法求出该点到其他点的最短距离，然后再算出来每个点到其他店的距离总和。估计大数据的时候可能会超时。
感觉工研院的机试和计院还是不太一样，计院基本上每年都会考DP，工研院这三道题则完全没有DP。
