D:::::::::::::::::::发现环（并查集，DFS）
题目描述
小明的实验室有 N 台电脑，编号 1⋯N。原本这 N 台电脑之间有N−1 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入描述
输入范围：
第一行包含一个整数 N 。
以下 N 行每行两个整数 a,b，表示 a 和 b 之间有一条数据链接相连。
其中， 1≤N≤105，1≤a,b≤N。
输入保证合法。
输出描述
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
输入输出样例
示例
输入
5 1 2 3 1 2 4 2 5 5 3
输出
1 2 3 5
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int n; int fa[100005]; bool vis[100005]; int find(int x){ if(fa[x]==-1) return x; return fa[x]=find(fa[x]); } vector<int> s[100005]; int qi,end1; int flage; bool pl; int j[100005]; int mm=0; void print(int step) { sort(j+1,j+1+step); for(int i=1;i<=step;i++) cout<<j[i]<<" "; } void dfs(int x,int step) { vis[x]=1; j[step]=x; if(x==end1){ print(step); return; } for(int i=0;i<s[x].size();i++) if(!vis[s[x][i]]){ dfs(s[x][i],step+1); } } int main(){ cin>>n; memset(fa,-1,sizeof(fa)); for(int i=0;i<n;i++){ int a,b; cin>>a>>b; if(find(a)==find(b)){ qi=a,end1=b; }else{ fa[find(a)]=b; s[a].push_back(b); s[b].push_back(a); } } dfs(qi,1); return 0; }
E:::::::::::::::::::大臣的旅费（双DFS）
题目描述
很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 x 千米到第 x +1 千米这一千米中（ x 是整数），他花费的路费是 x +10 这么多。也就是说走 1 千米花费 11，走 2 千米要花费 23。
J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入描述
输入的第一行包含一个整数 n，表示包括首都在内的 T 王国的城市数。
城市从 1 开始依次编号，1 号城市为首都。
接下来 n -1 行，描述 T 国的高速路（ T 国的高速路一定是 n -1 条）。
每行三个整数 Pi,Qi,Di，表示城市 P_iPi 和城市 Qi 之间有一条高速路，长度为 Di 千米。
输出描述:
输出一个整数，表示大臣 J 最多花费的路费是多少。
输入输出样例
示例
输入
5 1 2 2 1 3 1 2 4 5 2 5 4
输出
135
样例说明
大臣 J 从城市 4 到城市 5 要花费 135 的路费。
这道题好恶心，用dfs最后一个例题，数值较大，开足内存卡内存，不开内存，运行错误，用两遍dfs。
单个：80%
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int n; int a[1010][1010]; vector<int> g[10010]; int c; bool vis[10010]; long long ans; long long p; void dfs(int qi,int zhong,long long bu){ if(bu>ans){ return; } if(qi==zhong){ ans=min(ans,bu); p=max(p,ans); return; } int len=g[qi].size(); for(int i=0;i<len;i++){ if(!vis[g[qi][i]]){ vis[g[qi][i]]=1; dfs(g[qi][i],zhong,bu+a[qi][g[qi][i]]); vis[g[qi][i]]=0; } } } int main(){ cin>>n; if(n==1 || n==0){ cout<<0; return 0; } for(int i=1;i<n;i++){ int p,q,d; cin>>p>>q>>d; a[p][q]=a[q][p]=d; g[p].push_back(q); g[q].push_back(p); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ ans=1e9; vis[i]=1; dfs(i,j,0); vis[i]=0; c++; } } cout<<p*10+p*(p+1ll)/2; return 0; }
两遍：
#include <iostream> #include<vector> using namespace std; const int N =100010; int n; struct Edge { int id,w; }; vector<Edge> h[N]; int dist[N]; void dfs(int u,int father,int distance) { dist[u] = distance; for(auto node : h[u]) if(node.id!= father) dfs(node.id,u,distance + node.w); } int main() { scanf("%d",&n); for(int i=0;i<n-1;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); h[a].push_back({b,c}); h[b].push_back({a,c}); } dfs(1,-1,0); int u=1; for(int i=1;i<=n;i++) if(dist[i]>dist[u]) u=i; dfs(u,-1,0); for(int i=1;i<=n;i++) if(dist[i]>dist[u]) u=i; int v = dist[u]; printf("%lld\n",10*v + v*(v+1ll)/2); return 0; }
F:::::::::::::::::::最小公倍数（高精度）
题目描述
为什么 1 小时有 60 分钟，而不是 100 分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60 是个优秀的数字，它的因子比较多。
事实上，它是 1 至 6 的每个数字的倍数。即 1,2,3,4,5,6 都是可以除尽 60。
我们希望寻找到能除尽 1 至 n 的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如 n = 100, 则该数为：
69720375229712477164533808935312303556800
输入描述
输入一个数字 (N<100)。
输出描述
输出出 1 ~ nn 的最小公倍数。
输入输出样例
示例
输入
6
输出
60
#include<iostream> #include<cstring> using namespace std; int prime[101],ans=0; void prime_it(){ for(int i=1;i<=100;i++)prime[i]=i; for(int i=2;i<=100;i++){ for(int j=2;j<=i-1;j++)if(prime[i]%prime[j]==0)prime[i]/=prime[j]; } } int num[101],len=1; int main(){ int n; prime_it(); while(cin>>n){ memset(num,0,sizeof(num)); num[1]=1,len=1; for(int i=1;i<=n;i++){ for(int j=1;j<=len;j++){ num[j]*=prime[i]; } for(int j=1;j<=len;j++){ num[j+1]+=num[j]/10; num[j]%=10; } while(num[len+1]){ len++; num[len+1]=num[len]/10; num[len]%=10; } } for(int i=len;i>=1;i--)cout<<num[i]; cout<<endl; } return 0; }
G:::::::::::::::::::排列叙述（全排列）
题目描述
如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
⋯
现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？
输入描述
输入一行，一个串。
输出描述
输出一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。
输入输出样例
示例
输入
bdca
输出
11
#include <iostream> #include <string> #include <algorithm> using namespace std; string arr; long long ans=0; int main(){ cin>>arr; string arr1=arr; sort(arr1.begin(),arr1.end()); if(arr1==arr){ cout<<0; return 0; } while(next_permutation(arr1.begin(),arr1.end())){ if(arr1==arr){ break; } ans++; } cout<<ans+1; return 0; }
