NOIP模拟题 River Path Word[排序][贪心][DP]

本文主要是介绍NOIP模拟题 River Path Word[排序][贪心][DP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一．Word
题意：给定n个长度小于100的，全为大写字母的单词，求一共有多少种，判断是一种的标准是：两个单词中每个字母的个数都相同；n<=10000；
分析：只考虑字母个数则可以对一个单词中的字母进行排序，排除其他干扰，然后再对单词进行排序，即可把有相同特征的单词聚集在一起线性判断；
当然也有人直接用set，巧妙运用库函数也是一种方法，而且set也是用的排序二叉树实现的判重，先排序以后再扔进去就行了；
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ans,len,n;
char tmp[105];
string a[10005];
int main()
{freopen("word.in","r",stdin);freopen("word.out","w",stdout);scanf("%d",&n);getchar();for(int i=1;i<=n;i++){gets(tmp);len=strlen(tmp);sort(tmp,tmp+len);a[i]=tmp;}sort(a+1,a+n+1);for(int i=1;i<=n;i++)if(a[i-1]!=a[i])ans++;printf("%d",ans);return 0;
}

二．River
题意：给定N个人过河的时间，仅能小于等于两个人一起过河且此次过河时间为过河时间较大的那个人的时间，一次渡河后需要人把船再摇回去；N<=1e5
分析：对与四个人的最简情况进行以下分析：（a>b>c>d)
首先，先把a和b送过去一定是不会更糟的，因为剩下来的是较小的；接着，排除掉一些显然不是最优的情况后，还有两种情况需要很据当前状态讨论，即a+2*c+d或者a+b+2*d,也就是要么小的先过去再运回来，要么小的一个一个把大的运过去；那么循环每两个，判断一下就可以了；这好像是贪心？
程序：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int per[100005],ans,n,nn,plu;
int main()
{freopen("river.in","r",stdin);freopen("river.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&per[i]);sort(per+1,per+n+1);nn=n/2-1;plu=2*per[2]+per[1];for(int i=0;i<nn;i++)ans+=min(per[n-i*2]+plu,per[n-i*2]+per[n-2*i-1]+2*per[1]);if(n%2)ans+=per[3]+per[1];ans+=per[2];if(n==0)ans=0;if(n==1)ans=per[1];if(n==2)ans=per[2];printf("%d",ans);return 0;
}

三．Path
题意：求n点m边无向图1到n的最短路，其中有一些三元组限制，对于每个三元组（a,b,c),意为如果当前节点为b，上一个结点为a,则不能去往c;n<=3000；m<=20000;k(限制数）<=1e5;
分析：我的方法是存储当前节点，上一个结点是u的最短距离；然后如果用vector存储三元组（前两个为地址）的话会超时，这个时候可以用离散化（因为实际远远用不了那么多），给每个用到的a,b一个编号，用这个编号对应，然后邻接链表就可以了；
程序：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=3005,maxn2=100005;
int n,m,k,tmp1,tmp2,tmp3,f[maxn][maxn],roa[maxn][maxn],inde,inde2;
int e[maxn][maxn],banana[maxn][maxn],fr[maxn2],tov[maxn2],dada[maxn2];
int dfs(int u,int fr2)
{if(u==n)return 0;else if(f[u][fr2])return f[u][fr2];f[u][fr2]=2e9;for(int i=1;i<=e[u][0];i++){int flg=0,cur=fr[banana[fr2][u]];while(cur){if(dada[cur]==e[u][i]){flg=1;break;}cur=tov[cur];}if(flg)continue;int tmp4=dfs(e[u][i],u);if(tmp4<f[u][fr2]-1){f[u][fr2]=tmp4+1;roa[u][fr2]=e[u][i];}}return f[u][fr2];
}
int main()
{freopen("path.in","r",stdin);freopen("path.out","w",stdout);scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%d %d",&tmp1,&tmp2);e[tmp1][++e[tmp1][0]]=tmp2;;e[tmp2][++e[tmp2][0]]=tmp1;;}for(int i=1;i<=k;i++){scanf("%d %d %d",&tmp1,&tmp2,&tmp3);if(banana[tmp1][tmp2]){tov[++inde2]=fr[banana[tmp1][tmp2]];fr[banana[tmp1][tmp2]]=inde2;}else{banana[tmp1][tmp2]=++inde;fr[inde]=++inde2;   }dada[inde2]=tmp3;}if(n>1)printf("%d\n",dfs(1,0));else printf("0\n");if(n)printf("1 ");int uu=1,frr=0;while(roa[uu][frr]!=n){printf("%d ",roa[uu][frr]);int tmp5=frr;frr=uu;uu=roa[frr][tmp5];}if(n>1)printf("%d",n);return 0;
}