已经有四套题没有写博客了。今天改的比较快，就有时间写。今天这套题是用的图片的形式，传上来不好看，就自己描述吧。
第一题：单词分类
题目大意：有n个单词（n<=10000），如果两个单词中每个字母的数量是一样的（比如：AABAC 和BCAAA）则为一类单词，每个单词长度不大于100，问这些单词可以分为几类？
样例：输入：3 AABCA AAABC BBCAA 输出：2
题解：
每次都在第一题是字符串的时候卡住，这次又卡了一个多小时。。一般思路，就是枚举查找，排序，然后一个一个的比较，但是只过了一半，WA了一半。这个时候，根据每一类单词按字母序排序后都是一模一样的就可以用STL 中的set，将单词按字母序排序后存入set，最后输出 s.size() 。关键是对字符串进行排序 sort(st.begin() , st.end()) 。
参考代码：
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
set<string> t;
int n;
int main()
{
freopen("word.in","r",stdin);
freopen("word.out","w",stdout);
cin>>n;
for (int i=;i<=n;i++)
{
string s;
cin>>s;
sort(s.begin(),s.end());
t.insert(s);
}
cout<<t.size();
return ;
}
第二题：过河
题目大意：一条河，要将东岸的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组。。。正解：递推。先排序。对于每一次从东岸运走，有两种情况：一是将最快的那个人从西岸回来，和东岸的一个人走；二是将最快的那个人从西岸回来，东岸的两个人一起西岸，然后西岸的第二快的人回东岸，和最快的人一起再去西岸。分别对应了运单数个人和偶数个人的情况，并取最小花费（这就是为什么直接用人数的奇偶数来找规律的错误原因，实际应该在过程中就有运一个或两个人的情况，而非全部两个人）。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 100005
using namespace std;
int n,a[inf],f[inf];
int main()
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
cin>>n;
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a++n);
f[]=a[];f[]=a[];
for (int i=;i<=n;i++)
{
if (f[i-]+a[]+a[i]<f[i-]+a[]+*a[]+a[i])
f[i]=f[i-]+a[]+a[i];
else f[i]=f[i-]+a[]+*a[]+a[i];
}
cout<<f[n];
return ;
}
第三题：最短路
题目大意：一个无向图，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 两个组。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define inf 40005 //双向边
#define maxn 3005
using namespace std;
int n,m,k,road[maxn][maxn],q[maxn][];
int tot,he[maxn],to[inf],ne[inf];
int toto,hed[maxn][maxn],tov[inf],nex[inf];
int vis[maxn][maxn];
void add(int a,int b)
{
tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot;
}
void add2(int a,int b,int c)
{
toto++;tov[toto]=c;nex[toto]=hed[a][b];hed[a][b]=toto;
}
void bfs()
{
set<int> s;
int h=,t=;
q[][]=;q[][]=;
vis[][]=;
while (h<=t)
{
s.clear();h++;
int u=q[h][],v=q[h][];
for (int i=hed[v][u];i;i=nex[i])
s.insert(tov[i]);
for (int i=he[u];i;i=ne[i])
if (!vis[u][to[i]]&&s.find(to[i])==s.end())
{
q[++t][]=to[i];q[t][]=u;
road[u][to[i]]=v;//record the last point
vis[u][to[i]]=vis[v][u]+;//from v -> u -> to[i]
if (to[i]==n) return ;//不加 TLE 2组
}
}
}
void print(int a,int b)
{
if (a) print(road[a][b],a);
printf("%d ",b);
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
cin>>n>>m>>k;
for (int i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for (int i=;i<=k;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add2(a,b,c);
}
bfs();
int min=,mi;
for (int i=;i<=n;i++)
if (vis[i][n]&&vis[i][n]<min) {
min=vis[i][n];mi=i;
}
if (min==) {
cout<<-;return ;
}
cout<<min-<<endl;
print(mi,n);
return ;
}
呼。。。刷题去