最短路与拓扑（1）

1、找最长良序字符串

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int dis[N];
int vis[N];
int edge[N][N];
int n,m;
int vnum;void dij(int u, int v) {// 初始化距离数组和访问标记for(int i=0; i<vnum; i++) {vis[i] = 0;dis[i] = edge[u][i];}// Dijkstra主循环for(int i=0; i<vnum-1; i++) {int minn = 1e9;int pp;// 找到未访问节点中距离最小的for(int j=0; j<vnum; j++) {if(vis[j]==0 && dis[j] < minn) {minn = dis[j];pp = j;}}vis[pp] = 1;// 更新所有邻居的距离for(int j=0; j<vnum; j++) {if(vis[j]==0 && dis[pp] + edge[pp][j] < dis[j]) {dis[j] = dis[pp] + edge[pp][j];}}}cout << dis[v];
}int main() {cin >> n >> m;vnum = n;// 初始化邻接矩阵for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {if(i == j) edge[i][j] = 0;else edge[i][j] = 1e9;}}// 读取边信息for(int i=1; i<=m; i++) {int u, v, w;cin >> u >> v >> w;edge[u][v] = w;}int p;cin >> p;dij(0, p);return 0;
}

2、德克萨斯长角牛

#include<bits/stdc++.h>
using namespace std;
const int N=2510;
struct node{int v;int w;
};
int dis[N];//Rs-->Re的最短距离
int vis[N];//标记已经在这个队列中的点
vector<node>a[N];
queue<int>q;void display(int Rs,int Re){memset(dis,127,sizeof(dis));q.push(Rs);vis[Rs]=1;dis[Rs]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<a[u].size();i++){int v=a[u][i].v;int w=a[u][i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(vis[v]==0){vis[v]=1;q.push(v);}}}}cout<<dis[Re];
}
int main(){int T,C,Rs,Re;cin>>T>>C>>Rs>>Re;for(int i=1;i<=C;i++){int u,v,w;cin>>u>>v>>w;a[u].push_back({v,w});a[v].push_back({u,w});}display(Rs,Re);return 0;
}

3、找最长良序字符串

#include<bits/stdc++.h>
using namespace std;
int main(){string str;cin>>str;int cnt=1;int maxc=0;for(int i=0;i<str.size()-1;i++){while(str[i]<str[i+1]){cnt++;i++;}maxc=max(cnt,maxc);cnt=1;}cout<<maxc<<endl;return 0;
}

4、换位置游戏

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n;
int a[N],b[N];
int gys(int a,int b){if(a%b==0)return b;else return gys(b,a%b);
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=1;}for(int i=1;i<=n;i++){int t=a[i];while(t!=i){t=a[t];b[i]++;}}long long sum=b[1];for(int i=2;i<=n;i++){sum=b[i]*sum/gys(b[i],sum);//gyc(b[i],sum)也可以写成__gcd}cout<<sum<<endl;return 0;
}

最小公约数公式lcm(m, n) = m * n / gcd(m, n)

5、学生分组

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);int sum=0;for(int i=2;i<=n;i=i+2){sum+=a[i]-a[i-1];}cout<<sum<<endl;return 0;
}