很多的东西用法不知道
像2维字符串怎么输入
后来知道了:
字符串数组（2维字符数组）不能直接输入
（最好增加一个字符串，每次输入这个，再把它存到字符串数组中去,也可以char s[][];scanf("%s",%s[i])）
字符串不能初始化0,新定义的字符串原本就是空的（像s=0）
题1：number
题⽬描述给定⼀个1~n的排列，每⼀次可以对该排列进⾏这样的操作：从排列中任意拿出⼀个数，放在该序列的最前⾯。问⾄少经过多少次操作，可以使该排列变为1， 2， 3......n-1， n。输⼊格式输⼊包含多组数据。第⼀⾏⼀个整数T（ T<=10），表⽰数据组数。对于每组数据，第⼀⾏⼀个整数n表⽰排列的长度，接下来⼀⾏n个数表⽰这个排列。输出格式对于每组数据，输出⼀个整数，表⽰最少经过⼏次操作可以恢复正常顺序。样例输⼊244 1 2 351 2 3 4 5
样例输出30样例说明对于50%的数据对于第⼀组数据，操作顺序为：(4,1,2,3) → (3,4,1,2) → (2,3,4,1) → (1,2,3,4)。对于第⼆组数据，已经是正常的顺序所以不需要任何操作了。数据范围对于50%的数据 n ≤ 10。对于80%的数据 n ≤ 1000。对于100%的数据 n ≤ 100000。
。。。
题目一定要看仔细
结论不要片面
从大往小的位置检查
因为从大的开始确定
只要保持大的几个连续的确定就行了
（而我片面的认为一定要在最前面）
代码：
#include<bits/stdc++.h> using namespace std; int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); int n; cin>>n; int a[2010]={}; double F[5010]={},f[5010]={}; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); double g=n*(n-1)/2; for(int i=1;i<n;i++) for(int o=i+1;o<=n;o++) f[a[o]-a[i]]+=double(1)/g; int mx=a[n]-a[1]; for(int i=1;i<=mx;i++) for(int o=1;o<=mx;o++) F[i+o]+=f[i]*f[o]; for(int i=1;i<=mx;i++) F[i]+=F[i-1]; double ans=0; for(int i=1;i<=mx;i++) ans+=F[i-1]*f[i]; printf("%.4lf",ans); fclose(stdin); fclose(stdout); return 0; }题2：sort
题⽬描述给定 n 个由⼩写字母组成的字符串，请你求出⼀个字母表顺序，使得这 n
个字符串是按照字典序升序排列的，数据保证存在合法的字母表顺序。
多个解按字典需最大输⼊格式第⼀⾏⼀个整数 n。接下来 n ⾏，每⾏⼀个字符串。输出格式⼀⾏，⼀个 a ∼ z 各出现⼀次的字符串，表⽰字母表顺序 。样例输⼊10petregorendagorionfeferivanilovetanyaromanovakostkadmitriyhmaratsnowbearbredorjaguarturnikcgyforever样例输出aghjlnopefikdmbcqrstuvwxyz数据范围对于30%的数据 n<=100。对于100%的数据 n<=1000，字符串长度<=1000。
我之前太钻牛角尖了
非要递归求不同的
用spfa求还要用万能节点
同时题意理解有些偏差
以为如果确定的不满26个字符还要
按字典序吧没有的补上去
好的解法是拓扑排序
代码：
#include<bits/stdc++.h> using namespace std; const int dd=100010; int e[dd],next[dd],link[dd],top=0; char str[dd]; int cs[200]={}; inline void into(int xx,int yy){e[++top]=yy,next[top]=link[xx],link[xx]=top;} int main() { int n; cin>>n; string s[1010]; for(int i=1;i<=n;i++) scanf("%s",&s[i]); for(int i=1;i<n;i++) { int pd=0; int l=min(s[i].size(),s[i+1].size()); for(int o=0;o<l;o++) { if(s[i][o]!=s[i+1][o]) { pd=1; into(s[i][o],s[i+1][o]); cs[s[i+1][o]]++; break; } } if(!pd&&s[i].size()>s[i+1].size()) { cout<<"Impossible"; return 0; } } queue<int>q; for(int i='a';i<='z';i++) if(!cs[i]) q.push(i); string ans; while(!q.empty()) { int u=q.front(); q.pop(); ans+=(char)u; for(int i=link[u];i;i=next[i]) { if(!--cs[e[i]]) { q.push(e[i]); } } } if(ans.size()!=26) cout<<"Impossible"; else cout<<ans; return 0; } 题3：seq 题⽬描述给定⼀个长度为n的序列， A与B 随机从序列中拿⼀个数（放回）谁的⼤算谁赢，⽐赛三局两胜，已知A与B的⽐赛结果为前两局A胜，第三局B胜。求这三局B取得数的和⽐A取得数的和⼤的概率。输⼊格式第⼀⾏⼀个整数n，⼀⾏n个正整数表⽰序列中的每⼀个数ai。输出格式输出⼀个实数，保留四位⼩数。 样例输⼊31 2 10样例输出0.0741数据范围对于20%的数据 n<=20。对于40%的数据 n<=200。对于100%的数据 n<=2000， 1<=ai<=5000。
这题正解跟dp较像
先求出相差x的概率f[]
求出A前两次大B的概率F[i+o]=f[i]*f[o]
求出A前两次大B的前缀和F[x]+=F[x-1]
枚举f
计算f[]>F[]的所有
就相当ans+=f[i]*f[i-1]
代码：
#include<bits/stdc++.h> using namespace std; int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); int n; cin>>n; int a[2010]={}; double F[5010]={},f[5010]={}; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); double g=n*(n-1)/2; for(int i=1;i<n;i++) for(int o=i+1;o<=n;o++) f[a[o]-a[i]]+=double(1)/g; int mx=a[n]-a[1]; for(int i=1;i<=mx;i++) for(int o=1;o<=mx;o++) F[i+o]+=f[i]*f[o]; for(int i=1;i<=mx;i++) F[i]+=F[i-1]; double ans=0; for(int i=1;i<=mx;i++) ans+=F[i-1]*f[i]; printf("%.4lf",ans); fclose(stdin); fclose(stdout); return 0; }