已经有四套题没有写博客了。今天改的比较快，就有时间写。今天这套题是用的图片的形式，传上来不好看，就自己描述吧。
第一题：单词分类
题目大意：有n个单词（n<=10000），如果两个单词中每个字母的数量是一样的（比如：AABAC 和BCAAA）则为一类单词，每个单词长度不大于100，问这些单词可以分为几类？
样例：输入：3 AABCA AAABC BBCAA 输出：2
题解：
每次都在第一题是字符串的时候卡住，这次又卡了一个多小时。。一般思路，就是枚举查找，排序，然后一个一个的比较，但是只过了一半，WA了一半。这个时候，根据每一类单词按字母序排序后都是一模一样的就可以用STL 中的set，将单词按字母序排序后存入set，最后输出 s.size() 。关键是对字符串进行排序 sort(st.begin() , st.end()) 。
参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<set> 4 #include<algorithm> 5 using namespace std; 6 set<string> t; 7 int n; 8 int main() 9 { 10 freopen("word.in","r",stdin); 11 freopen("word.out","w",stdout); 12 cin>>n; 13 for (int i=1;i<=n;i++) 14 { 15 string s; 16 cin>>s; 17 sort(s.begin(),s.end()); 18 t.insert(s); 19 } 20 cout<<t.size(); 21 return 0; 22 }
第二题：过河
题目大意：一条河，要将东岸的n个人（n<=100000）运到西岸，只有一条船，一次最多运2个人，每个人有过河的时间花费，每一次运输的花费是船上花费最高的人的花费。问总花费时间？
样例：输入:4 (n) 6 7 10 15(每个人的花费) 输出：42
样例说明：{1,2,3,4}->{}
{3,4}-(1,2)->{1,2} ans+=7
{1,3,4}<-(1)-{2} ans+=6
{1}-(3,4)->{2,3,4} ans+=15
{1,2}<-(2)-{3,4} ans+=7
{}-(1,2)->{1,2,3,4} ans+=7
题解：
考试的时候是想找规律来着，分为单数和偶数。但是只对了1组。。。正解：递推。先排序。对于每一次从东岸运走，有两种情况：一是将最快的那个人从西岸回来，和东岸的一个人走；二是将最快的那个人从西岸回来，东岸的两个人一起西岸，然后西岸的第二快的人回东岸，和最快的人一起再去西岸。分别对应了运单数个人和偶数个人的情况，并取最小花费（这就是为什么直接用人数的奇偶数来找规律的错误原因，实际应该在过程中就有运一个或两个人的情况，而非全部两个人）。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define inf 100005 5 using namespace std; 6 int n,a[inf],f[inf]; 7 int main() 8 { 9 freopen("river.in","r",stdin); 10 freopen("river.out","w",stdout); 11 cin>>n; 12 for (int i=1;i<=n;i++) 13 scanf("%d",&a[i]); 14 sort(a+1,a+1+n); 15 f[1]=a[1];f[2]=a[2]; 16 for (int i=3;i<=n;i++) 17 { 18 if (f[i-1]+a[1]+a[i]<f[i-2]+a[1]+2*a[2]+a[i]) 19 f[i]=f[i-1]+a[1]+a[i]; 20 else f[i]=f[i-2]+a[1]+2*a[2]+a[i]; 21 } 22 cout<<f[n]; 23 return 0; 24 }
第三题：最短路
题目大意：一个无向图，n个点（<=3000）m条边（<=20000）,给定 k个三元数组（<=100000）,（a,b,c）表示a 走到b不能往c走，但是b走到a可以往c走。在这个限制下，求出从1—n的最短路径，输出长度和过程中经过的点。输入：n,m,k 下m行为联通的边，下k行是限制数组。
样例：输入：4 4 2 输出： 4
1 2 1 3 2 3 4
2 3
3 4
1 3
1 2 3
1 3 4
题解：最后写到这道题没有时间了。可以用BFS或SPFA。对于判断能不能走，标程的做法值得借鉴，将head数组定为二维，表示从a->b的b的下几条边是不能走的，在BFS中，用set存不能走的路，并在拓展时判断要走的路在不在集合中，BFS中，用自定义的队列数组，并且是二维，一个存当前节点，一个存当前节点的上一个节点。在记录路径时，用倒序，存从当前节点走到下一节点的路径的上一个节点。在搜索中，因为是BFS如果找到一条路，则为最优解，就可以退出了，加一条语句，可以避免TLE 两个组。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<set> 5 #include<queue> 6 #define inf 40005 //双向边 7 #define maxn 3005 8 using namespace std; 9 int n,m,k,road[maxn][maxn],q[maxn][3]; 10 int tot,he[maxn],to[inf],ne[inf]; 11 int toto,hed[maxn][maxn],tov[inf],nex[inf]; 12 int vis[maxn][maxn]; 13 void add(int a,int b) 14 { 15 tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot; 16 } 17 void add2(int a,int b,int c) 18 { 19 toto++;tov[toto]=c;nex[toto]=hed[a][b];hed[a][b]=toto; 20 } 21 void bfs() 22 { 23 set<int> s; 24 int h=0,t=1; 25 q[1][0]=1;q[1][1]=0; 26 vis[0][1]=1; 27 while (h<=t) 28 { 29 s.clear();h++; 30 int u=q[h][0],v=q[h][1]; 31 for (int i=hed[v][u];i;i=nex[i]) 32 s.insert(tov[i]); 33 for (int i=he[u];i;i=ne[i]) 34 if (!vis[u][to[i]]&&s.find(to[i])==s.end()) 35 { 36 q[++t][0]=to[i];q[t][1]=u; 37 road[u][to[i]]=v;//record the last point 38 vis[u][to[i]]=vis[v][u]+1;//from v -> u -> to[i] 39 if (to[i]==n) return ;//不加 TLE 2组 40 } 41 } 42 } 43 void print(int a,int b) 44 { 45 if (a) print(road[a][b],a); 46 printf("%d ",b); 47 } 48 int main() 49 { 50 freopen("path.in","r",stdin); 51 freopen("path.out","w",stdout); 52 cin>>n>>m>>k; 53 for (int i=1;i<=m;i++) 54 { 55 int a,b; 56 scanf("%d%d",&a,&b); 57 add(a,b); 58 add(b,a); 59 } 60 for (int i=1;i<=k;i++) 61 { 62 int a,b,c; 63 scanf("%d%d%d",&a,&b,&c); 64 add2(a,b,c); 65 } 66 bfs(); 67 int min=99999999,mi; 68 for (int i=1;i<=n;i++) 69 if (vis[i][n]&&vis[i][n]<min) { 70 min=vis[i][n];mi=i; 71 } 72 if (min==99999999) { 73 cout<<-1;return 0; 74 } 75 cout<<min-1<<endl; 76 print(mi,n); 77 return 0; 78 }
呼。。。刷题去