记录一下，今天的战果：1-AC；2-63%（边界条件未考虑）；3-80%（超时）；4-无
还差很远！
加油
冲冲冲！！！
牛客网
867. 转置矩阵
/* * @Author: 7QQQQQQQ * @IDE: vscode * @Date: 2021-03-13 16:01:11 */#include<bits/stdc++.h>//万能头文件using namespace std;typedef long long ll;//long long 类型const int N=1e2+50;int a[N][N];int main(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ cout<<a[i][j]<<" "; } cout<<endl; } return 0;} 2 字符串里面的数字 给出一个字符串，里面包含数字和小写字母，//jslajf123djalkf009014fadf314133提取出其的数字，去掉数字的前置0并且按照从小到大的顺序输出，eg：dfaf1fa123da00da034 输出 0 1 34 123 /* * @Author: 7QQQQQQQ * @IDE: vscode * @Date: 2021-03-13 16:10:08 */#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e2+50;int main(){ string s;cin>>s; vector<string > ans; for(int i=0;i<s.size();i++){ if(s[i]>='0' && s[i]<='9'){ string q=""; while(i<s.size() && s[i]>='0' && s[i]<='9'){ q+=s[i]; ++i; } --i; string a=""; int flag=0; for(int j=0;j<q.size();j++){ if(q[j]=='0' && !flag) continue; flag=1; a+=q[j]; } if(a.size()==0) a="0"; ans.push_back(a); } } sort(ans.begin(),ans.end(),[](string a,string b){ if(a.size()!=b.size()) return a.size()<b.size(); return a<b; }); for(auto &x:ans) cout<<x<<endl; return 0;} 3 数组，滑动窗口中的众数 给定一个int数组，一个滑动窗口的大小k,从0开始向后滑动,求每次滑动的窗口大小内的众数,如果两个数，出现次数相同，返回值更小的 /* * @Author: 7QQQQQQQ * @IDE: vscode * @Date: 2021-03-13 16:12:48 */#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+50;int a[N];struct node{ int val,cnt; friend bool operator<(node a,node b){ if(a.cnt!=b.cnt) return a.cnt<b.cnt; return a.val>b.val; }};map<int,int>mp;int main(){ int n,m;cin>>n>>m; priority_queue<node> que; for(int i=1;i<=n;i++){ cin>>a[i]; if(i<=m){ que.push({a[i],++mp[a[i]]}); } } cout<<que.top().val<<endl; for(int i=m+1;i<=n;i++){ mp[a[i-m]]--; que.push({a[i],++mp[a[i]]}); while(!que.empty()){ node now=que.top(); if(now.cnt!=mp[now.val]){ que.pop(); continue; } break; } cout<<que.top().val<<endl; } return 0;} 4 树 这是一个树结构，无向图给定一个数组，表示1-n的结点权值，其中ai表示i结点的权值给定结点间边的关系，（1,3）表示结点1和结点3之间连通在这棵树中选择结点，这些结点两两之间不连通，使得结点权值加起来最大输出最大的权值和，以及这些被选中结点中最小的权值（如果有多重组合使得权值之和相同，输出其中被选结点最小权值最大的那个） /* * @Author: 7QQQQQQQ * @IDE: vscode * @Date: 2021-03-13 16:23:05 */#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+50;ll val[N];vector<int> e[N];ll dp[N][2];//表示以i为根的子树选了 1/0 当前根/不选根 的最大值ll mi[N][2];void dfs(int x,int fa){ dp[x][1]=val[x]; mi[x][1]=val[x]; dp[x][0]=0; for(auto &son:e[x]){ if(son==fa) continue; dfs(son,x); dp[x][1]+=dp[son][0]; mi[x][1]=min(mi[x][1],mi[son][0]); dp[x][0]+=max(dp[son][1],dp[son][0]); if(dp[son][1]>dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][1]); else if(dp[son][1]<dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][0]); else mi[x][0]=min(mi[x][0],max(mi[son][0],mi[son][1])); }}int main(){ memset(mi,63,sizeof mi); int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ cin>>val[i]; } for(int i=1;i<n;i++){ int x,y;cin>>x>>y; e[x].push_back(y); e[y].push_back(x); } dfs(1,0); ll S1=0,S2=0; for(int i=1;i<=n;i++){ S1=max(S1,max(dp[i][0],dp[i][1])); } cout<<S1<<" "; for(int i=1;i<=n;i++){ if(S1==dp[i][0]) S2=max(S2,mi[i][0]); if(S1==dp[i][1]) S2=max(S2,mi[i][1]); } cout<<S2; return 0;} 5 图 给你一个图，每个点有自己的权值，可以选择任意一个点开始，只能走到点权比当前小的点。最多能走多少个点。 /* * @Author: 7QQQQQQQ * @IDE: vscode * @Date: 2021-03-13 17:06:42 */#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+50;vector<int> e[N];ll val[N];ll dis[N],vis[N];void dfs(int x,int f){ vis[x]=1; ll nxt=0; for(auto &y:e[x]){ if(y==f) continue; if(!vis[y]) dfs(y,x); nxt=max(nxt,dis[y]); } dis[x]+=nxt;}int main(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ cin>>val[i]; dis[i]=1; } for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; if(val[x]>val[y]) e[x].push_back(y); if(val[x]<val[y]) e[y].push_back(x); } ll ans=0; for(int i=1;i<=n;i++){ if(!vis[i]) dfs(i,0); } for(int i=1;i<=n;i++){ ans=max(ans,dis[i]); } cout<<ans; return 0;}