LCCUP 22秋季编程大赛
总结：
交的时候，460名 然后慢慢得掉到最后580。第三题一开始没读好题，浪费了很长时间。四五题没有什么思路，直接就没写了。（横向对比，比春季进步了一些(●ˇ∀ˇ●)—春季只A了两题 1000开外= =）
思路：
1、判断A，B趋势是否相同，然后t+=1，不然t=0; 记录过程种t得最大值 为答案
2、第二题感觉和leetcode有题很像，但是忘记是叫什么了。根据题意，一个点只可能是交通枢纽，或者交通枢纽在它连接得点上，因此只要分这两种情况判断就好。（因为题意没有说一定 输入会有连续得1-n个点，所以用个访问数组，记录一下有什么点·）
3、记忆化搜索。vist[i][j][k] 表示 坐标x,y已k方向进入 0表示没访问，1表示可以进入到洞穴，-1表示进入不到.
1. 气温变化趋势
若第 i+1 天的气温 高于 第 i 天，为 上升 趋势
若第 i+1 天的气温 等于 第 i 天，为 平稳 趋势
若第 i+1 天的气温 低于 第 i 天，为 下降 趋势
已知 temperatureA[i] 和 temperatureB[i] 分别表示第 i 天两地区的气温。
组委会希望找到一段天数尽可能多，且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势相同的最大连续天数。
即最大的 n，使得第 i~i+n 天之间，两地气温变化趋势相同
class Solution {
public:
int temperatureTrend(vector<int>& A, vector<int>& B) {
int n = A.size();
int ans = 0,t = 0;
for(int i=1;i<n;i++) {
if((A[i]==A[i-1]&&B[i]==B[i-1])||(A[i]>A[i-1]&&B[i]>B[i-1])||(A[i]<A[i-1]&&B[i]<B[i-1])) {
t++;
ans = max(ans,t);
}
else t = 0;
}
return ans;
}
};2. 交通枢纽
path[i] = [a, b] 表示有一条从地点 a通往地点 b 的 单向 交通专线。
若存在一个地点，满足以下要求，我们则称之为 交通枢纽：
所有地点（除自身外）均有一条 单向 专线 直接 通往该地点；
该地点不存在任何 通往其他地点 的单向专线。
请返回交通专线的 交通枢纽。若不存在，则返回 -1。
class Solution {
public:
int transportationHub(vector<vector<int>>& path) {
bool v[1001][1001];
bool vist[1001];
memset(v,false,sizeof(v));
memset(vist,false,sizeof(vist));
int cnt = 0;
for(auto &c: path) {
v[c[0]][c[1]] = true;
if(!vist[c[0]]){
vist[c[0]] = true;
cnt++;
}
if(!vist[c[1]]) {
vist[c[1]] = true;
cnt++;
}
}
for(int i=0;i<1001;i++) {
if(vist[i]) {
//判断i是不是交通枢纽
// 存储i可以去的地方
vector<int> t;
for(int j=0;j<1001;j++) {
if(i==j) continue;
if(v[i][j]) t.push_back(j);
}
if(t.size()==0) {
//只有i为枢纽得可能
int cntt = 0;
for(int j=0;j<1001;j++) {
if(i==j) continue;
if(v[j][i]) cntt++;
}
if(cntt==cnt-1) return i;
}
else {
//只有i可以去的地方为枢纽
for(auto &c: t) {
int tc = 0, ct = 0;
for(int j=0;j<1001;j++) {
if(j==c) continue;
if(v[j][c]) tc++;
if(v[c][j]) ct++;
}
if(tc==cnt-1&&ct==0) return c;
}
}
break;
}
}
return -1;
}
};3. 弹珠游戏
N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中，数组中的每个元素为仅由 “O”、“W”、“E”、“.” 组成的字符串。其中：
“O” 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；
“W” 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）；
“E” 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）；
“.” 表示空白区域（弹珠可通行）。
游戏规则要求仅能在边缘位置的 空白区域 处（弹珠盘的四角除外）沿 与边缘垂直 的方向打入弹珠，并且打入后的每颗弹珠最多能 前进 num 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。
class Solution {
public:
int vist[1001][1001][4];//0 1 -1
int dx[4] = {0,0,1,-1};//右左 下上
int dy[4] = {1,-1,0,0};
// 记录在[i,j]的状态
int n,m;
int dfs(int num, vector<string>& plate, int x, int y, int dir) {
if(num==-1) return -1;
if(vist[x][y][dir]!=0)
return vist[x][y][dir];
if(plate[x][y]=='O') {
return 1;
}
else if(plate[x][y]=='W') {//逆时针
if(dir==0) dir = 3;
else if(dir==1) dir = 2;
else if(dir==2) dir = 0;
else dir = 1;
}
else if(plate[x][y]=='E') {
if(dir==0) dir = 2;
else if(dir==1) dir = 3;
else if(dir==2) dir = 1;
else dir = 0;
}
if(x+dx[dir]<0||y+dy[dir]<0||x+dx[dir]>=n||y+dy[dir]>=m) return -1;
int d = dfs(num-1,plate,x+dx[dir],y+dy[dir],dir);
vist[x+dx[dir]][y+dy[dir]][dir] = d;
return d;
}
vector<vector<int>> ballGame(int num, vector<string>& plate) {
n = plate.size();
m = plate[0].size();
memset(vist,0,sizeof(vist));
vector<vector<int>> ans;
for(int i=1;i<n-1;i++) {
//左右进入
if(plate[i][0]=='.')
if(dfs(num,plate,i,0,0)==1) ans.push_back({i,0});
if(plate[i][m-1]=='.')
if(dfs(num,plate,i,m-1,1)==1) ans.push_back({i,m-1});
}
for(int j=1;j<m-1;j++) {
//上下进入
if(plate[0][j]=='.')
if(dfs(num,plate,0,j,2)==1) ans.push_back({0,j});
if(plate[n-1][j]=='.')
if(dfs(num,plate,n-1,j,3)==1) ans.push_back({n-1,j});
}
return ans;
}
};4. 二叉树灯饰
5. 舒适的湿度