最近的计分赛，记得自己的都只是过了两题。遇到了两次map，自己在寒假看了一点的map，只知道在字符串匹配的时候可以用的到。但是自己对map的使用还是不够熟练使用，这回在第一次和第二次的计分赛中都遇到可以用map快速写出的AC题目。而且代码精简。
map是一种二叉树的数据存储结构。map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。
2、支持快速查找，查找的复杂度基本是Log(N)
3、快速插入，快速删除，快速修改记
map<string,int>mp; //这里的mp就是自己取的名字。定义map类型的变量mp
还可以自己定义的map<int.int>mp;
map<string ,int>mapstring; map<int,string >mapint;
map<sring,char>mapstring; map< char ,string>mapchar;
map<char,int>mapchar; map<int ,char>mapint；
二、数据的插入(与插入的循序无关，自动排序)
第一种：用insert函数插入pair数据。
#include <iostream>
#include<string.h>
#include<map>
using namespace std; int main()
{
map<int,string>mp;
mp.insert(pair<int,string>(,"student_three"));
mp.insert(pair<int,string>(,"student_one"));
mp.insert(pair<int,string>(,"student_two")); map<int,string>::iterator iter;
for(iter=mp.begin();iter!=mp.end();iter++)
cout<<iter->first<<" "<<iter->second<<endl;
return ;
}
第二种：用数组方式插入数据，下面举例说明
#include <map>
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mp;
mp[]= "student_one";
mp[]= "student_two";
mp[]= "student_three";
map<int, string>::iterator iter;
for(iter=mapStudent.begin(); iter!= mapStudent.end();iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
}
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAb4AAACbCAIAAACS+WmPAAAVPklEQVR4nO2d348k11XH589paV7nfR5HmjRoUDIRscAj1IqUhZEQGkEioWhAIKBjh5hkiSY2GMdJO44txxn3Crxm7R3vBkhkE0FbG9uyZWlXkWXh/TG7a7O7IQ88VHXV/XHO/dFdNf1jPh+dh5nq6ntv3Tr3e8/9UdUrL39nC8MwDMuyleOfnsEwDMOyDOnEMAzLNqQTwzAs25BODMOwbEM6MQzDsg3pxDAMyzakE8MwLNuQTgzDsGyLS+fPXvyT8898JcX+40d/fPPfvzTzS8IwDGvb4tL5wo+Hb/7XFd/+87+v/Hz0i5+PfjF85dJL5y+9dP7SD5578YPzvzfzS2rDhr3O1v6OcWTn7IZzJPGL6bZzdqPT2dgcGQdH+2v1kYP14u/R/lqnt22dY7F2dn+94zFpqRqyg/VOZ31oHdze66ydPbRPO9zcKq93e8+5gPqSqy9u79nVZaXTWR8KmU5v40yLLMwyj2+Qf1v3DkrfUDDqIbGiQset2iuylj2qHRv2XDdO/3QmRUq0uHS+dvHS/Qe/uv/ggWe/uvfgwT3j3wsXL71z7mE/hdH+muSy23tCA97e8+6ul1Sg2VsNrEqnVBOlsgoP3jsI5S4pYN0GwjepOem0c6yk83DbF9lgQzoz7EWut23zq8XpAKy7s7E5si+nPLlUq/ojtUlUuibJmZa1awfrvvTUlVlmYSmjVLfWCZJvWFeaXlHHTj1YhDqMYa+TdPmVT6ony+4U1CkhPkhMVggRFG/XnSr1fNHi0nnp0uV33/tl/8mLX3vqtUeefvXRwYWvP/vK229/cOvmjWvXrl67dvXmjetPHL75xOGbTUhnvKL3emJnXlalWcXDXlmbo/21zsballi5h5tbnbUtMxCQEq89+ECI4Iw75wVHApMGPk6zt+IRLwq2T7Zb4M7ZjZjWtGeHm1t2dWzt70j1Vt2sQmtKXSguRJNOtW1X0um5U0lUOw43Zf8pPLkqzMH6uJ6FMNlu7et7YenMqShbK80rTengU4dQ0ZNFd5rex8QU3Hi5qK60PuCEpPP1S5fffe/DL31j+PvfOtw9ePEPn3zhj7733Gj0/s0bH5vS+eTLP2tEOkM+WojF4eaW3wsdrAe6naIAe1LvOtpf6/TW627Ny93p3GJeuL1nX6kbNchtONWB0pNyTrYiIPOLIUVox+xiF+X0Ap9SPkb7a+NiJ0rnmePDnVFoLGwI5bh3SQi7VL3wYp9Op9PpbGyODtarNO04MXnAnlNR9t/h/lvwGaWFKhaY95DcqQGdkpKVphoUSfHshKTzlVeP3n3vw68+/coffOeF3z373Ye+/fhDj//9aPT+zesfX7t29drVqzdvXP/e5Z88+8bFKaTTjNtVNx37jR9ZRLrNsgDCDSi8zRwRiEmld8v50mkHF3bUbNzgg/VOx09qbWvDahblCW4udZhZJmW3ZOfSinquRaGaURXanhG42e28s7E5Mi+tytFXhA3fPcbSebC+Vc+lpEmnaLFuJiKdsUnSYa+z1VvfslSsvnej/TU75E8bsOdUlPf3GT873cqbmBV4Kmkq7qQ5g+XkZbuWPE1IVpyldaXGzNQehOlFcvXX1dnxuDNBOi9cfPe9Dz/3yJOb/W/9xmOPbX370c8+0Xeizh+99S+Hbw8bkk7FU41gc7S/ZsWYYhwqFcBx1nE4YE+m+Lkfbm6ZtemO2c2TMwfszvSZnZHrVZ1x3GGizQ9aJ7gThe7Q3pP7jqXCZkbbe0amo/11a6Q8voNlAaobag6mpGDKuwSjwLY+6tJZibiocW6X5lZXUDoDJ9QT5c74urc+ztERmvH8Q2/buna5T82pqOLv/Wqipmhf23HpLEKKg4zxUGh2WHEnxxnCTu57mp+svMBlhkfWSDTun2a+mnSas4KpUednHv3mb37zG7918Mj2P/71F57+izrqvHb15o3rVz66cuWjK0HplFE6OmFi2NJfR8tio876u9YNqHJxsnNzd7tBcxrR9fisqFMYX5iXWd2zwlPFVX6hVRTKbi2+y4JujIX1aLf0My+iDLYZ5yvWdclTeM61+EpXS+fegbpMVH3Rcbmt/c3wollQOhMCN6Gzr77lLXCNHSk0q+DERAkVZayFjnuR3naxhLi3XyclL+P0tgVfDV+vOuCV3ElzBl86jWTtkEtqlbJ0Fqd5d81QiWCRAtJpfZQqnVtnv/7Zx7/2+X/6q4e+/+cP//CrjnQ+uH/vwf17zcx1yt5sd0Glc6RO2BkFMCL/A6t/dm+2vfdlq/hWse+kKemMTdpW92zYE0JmqZbKg9VKWnA1ts7aSUf413FoV1gr/PbgXZcaTBn+4HYwVmiZIp11UcsLsacsIs4Wqivhu0qfVORuVtewZ4WBk0adQkUNe2b3YKqG9reZixngp018h6Qz4j+ak/sTcY5uOMlGok6v4zFvTbBIunTaDTZVOj/3D3/z29/9y9955s92nv/T3otfHo3ev3H9fwrpvHHj+ief3L19fNygdLp3UVnXNuOm+FynVePm7InXNozchYjPnCs8EemUkwp4sLLl06l8e6LA2hCTJp1FMDu+HCfqzJZOo1TmOWWy1ax0uXyUKZ3aViHheiN1JXqX7A9lsG9/t9KvHScedHug3Iqq68HcObAZjDoltUrcpxVYZvHdqQnpdJKNzHUGJ/FOSDr/9dWjt6588MiPn3/0pR/+7blnHvvn7//dy0+/8cZbtXRe//jOnds3b95oUjotaRM3f/mTF+pMjRD598SRu5C7H/HJTaVuxlGyB+xS45FKXjm0JZ2bZzfcElR7faTaTpZOe1eDW3J/wsvZOq5elHWOVdvOWpkuncN9t+eo//aa/XQDdlMf3dUMyS3HqWkzjK5HpVaUI50pUaekPmkromHp9N1Jc4Ys6bSTja2wxwa1apHcYkw+YD9/4ejXv/6/O7dv3b19687tW3fv3rl79/bdO7fu/e+nD+7f+/TTT27fuX18fOv4+FZjy0RO1WgdiD8N7MqBETk6wUhH6sPF3F3H9eM1cwI0FnVWife2q5LYK1T2ODoinVY5fXVQgwhxD5bpzanSaW7q6tjS6czxm2cmKILhx2YWewd+23aXSrbGvmRNUo/z9eskZZkoqibuJY/b554b4BhzDuWE5nTSWSeeJ53qhqTYomtKjbnupDlDnnR63u4vfHuP1VlN1RiCRIpkDXqcEK10trh0Pv/sUxcuXvLttdd/cnT53149ulwd+cEzT71zTtv7li2dlUjpEaUzAeosDsgB0dg5TOEQR2TubGA1SW85jd4gdY/3HgqSynycJp1G1RnJmmmKLi4/3mfMBKXNdVobmLwB+9C4Hc4uApNgfzCWAyvedNTTWY7vdDY2z/b8+iy/5W4wSNycFAiyytqulqfWh9ZcvOPbxW0yY0+fwHqaVlFn5AG7h7GlVF9Pd5ZhJZdL2OBsTSzKzpApnWay3uKzcDnWOd7mJK1IzrMS0qppp5OyOemj17/4zrmdd849nGA7H73+xWiC6Rb36TbNzN3aE+PdS6n2LS90SduO60uY4s3evhwt6jQkVX6Oq6HaVlfhf6oHU2IXUq3LiRtyD8Z1a25ri81aZj2xZ9aw9oSuVDa3JofWVtn1YaXFE0SdUkWZC/d6acvjobsTvArDi+LbmFpqvLPVBNPm+6VzJ/+sy/zknvd43Hxdb1rjXChr5dUhi2jJbtlS85lxq6xtvqXzNFvw0dI5tyWUztynFZfTUt7WscxmzvYgnXNn1QTNTN5p1IgtpXRi2HHWXCeGYRjmGNKJYRiWbUgnhmFYtiGdGIZh2YZ0YhiGZRvSiWEYlm2qdL753BcwDMMw0ULSubKgdPtHR/3urEsBAMtMknSu7g6OBrursytlFkgnALRNWDq7/aMxJyud04j1NNK5WJ0EAMyKoHSurhYi0u0jnQAANUkD9vak0whrx1lYh6yId3V3YIiirZCru4PxubvyB/XBMp36k343mG8II/lI+np5AGDhmKl06vGhGP3p0mkUsJCm8gPzG/U5Y/UqPrBSzYs6V3cHdcWkpC+XBwAWjplKpyU93ifp0mlLcP2fXe7quJOt+e0s6XROroqnpq+UBwAWjhkP2FeMEaw7rE2WTudkWyKFIbidzuTS6VbLOCEtfa08ALBwzF46C5xILS6dxj+qFCrlbko6g1FnRnkAYOGYpXR2d4WQTf7XLUe5puNPIZaRnTGS95MJSGfeKDo01ymmL5cHABaOoHQKi85NSqidvJOwNbq1Qs3ygCVyxgL7qrL0njRgV/LVCaywJ6RPDAqwoCzhg5gNI/UfabIKAEsL0gkAkA3SCQCQzRJKJ/slAaBtwtKZuWYyHyCdANA2EensdssVYP3Bn1ZYlNd/8LoQgNNJ8oDd2XHTMkgnAMwzWdLZvEgs8JuTtPNXdweecq/uDqy3kyzWDAgAeKRKZysTiIv+5iT5/G7f6ATGf9V78f2njwBg4UiSzraGpQv+5iTl/HHY2e0P+v1B+VD7+Nl26Zl3AFg44tLZ9nTe4r45STu/CDtXdwf9brdfPDM62F3V37QEAAtHTDqlmbs2WMQ3J4XK2d8tIs1uf7DbLf4k6gRYHuL7OtuLOBf+zUmhctaR72BgrREx1wmwBASl0xvxNhsjLcObk+Tz3WUrOXkiToCFZQkfxGwY3pwEAB5IJwBANkgnAEA2SyidM9/zw9I5wNITkU5zom9RloORTgBom4h0rq6az9zw5qSk85FOgKVnxq//0EA6AWCeSZXOlpRzCd+cpKVfl7/6pvvoqbTtSTsOALMkKp3jpttGxLmcb05S07ePF4+3+1dmzoxoxwFgxuREnY233OV8c5Kavnq5SjnV4wAwa9I3J7UV9Szfm5O09LU50GA5M6YQAODESJfOdteJlu3NSTnSqfZKjNEB5pVZDtiX9c1J2dKplFM/DgAzJmNLfONNeFnfnJQvnXI5g8cBYJYs4YOYDcObkwDAA+kEAMgG6QQAyAbpBADIBukEAMgG6QQAyAbpBADIBukEAMgG6QQAyAbpBADIBukEAMgG6QQAyAbpBADIBukEAMgG6QQAyAbpBADIBukEAMgG6Zw7Wv7lS+vXlhuh2z+d769v5Vdi5zhfsEA654406axfXp+hgoJs5qajnH8amzPSudKY/6ysrOg/qtjuL0pOSkg63R+znb/SN8483KQE6TSKmVFi/wc2c9MJnh/86aUFZVb+MA9+mEBT/mP8iI2VhnZ8LohKp/WLavNX/oaZB5eNS6d9RuIAX7i03HRi589D7TUL0hmiKf9ZXV2tjphXrR2fD5KlU/hlx6pPMCrMjFT9EV34Fx+d3xKWOhztuEionH6+ws+3GR2k9HPDWvrl8TqHYL7O4cHubswFnXaV1syEs7R0iuvxLzieb4stXqg3rZza+e7xI/EXUsfJ6P4Q+p1Yyf+D/uCRnW9R6bvlhHORS6x9RSs65S7m+mH0fE0i06UzSx+mJF066//Gd6OSHDEyNa9XC1nNHIzztf4rcwFFLaeWr3L7g9IppG8fN7+t5Wv8nbCK43hS2kBZqLtAOvUPwHf74h1V8m1piUu9X2I59fNlP9Tu70pMDtyrVfxf94fgBafmW3lMt380GPQL9TRyluotknXambl+GD1/WulseYHVIVU6Ta8ICaFYNWlV4miSprTpfYl6upbvJNIZL2b9BS3fzIHPJNKp6ZyaTnERg4FT4ATpbL6z1++XWM5gPUc68GmkU/N/1R90cqWzGi2M86sO5OWbxdxJ58lOKqYvE8l9uol7heatlM53l6GO/JoNDYmibjBBvvnSqaWvTXQI+TqZRl18ogG7kGokHc8RE/Jtpd8P+4lcTq2e4/drculM9P8Tk85IvU3NHA7YV3L0YUoy5jrtwinHp4g6RaYJQNVuUM83Lp3GP7nSmRb1tLRMFBc6v0H2+/0j/Yy4GDdFyE+0cmb4m3Z/V5qMOmcgna0vrzS1TGQemVo6C04gAG1SOiNzncJXun3pcHdX6LoDxzX0EYScr5psfSnlNPSE0qnl68px0pUZsydJLiKdqKZTldkucSTflpQzcL+UcmrnK36o3F8rA61YqXOdmV1dRr66dAb8XCd9rjPsD1I6Ef+ZUjpz9WFKGpXOlarp+xGzM3qw59TsAUXpv94YQzuuEZx8Cc5GuKU0BwGTD9gD+VZHB7uraTe9roxkBxE9UEhHmPR0VEnMN2nOdWKEeguWM+n+Oh2Wc3/984WZXW06yfWeSUYJafkGpDNQD5GMk3tA1R+UdKTz7YZdl1Q7Hi1K4qVOB08TnSa06H96uv2T8FaAuQHpPG00L5/IJpxCkE4AgGyQzpp2J+sWj5PdJgewUCCdNUinDdIJoMKbk2pOQDpb274zIfNWHoBFgTcn1SCdAJBI029OMkNV5xk1KXrVjivYcbCzb67+0Cql8/VAJv4DefJ+QHVXZzB9YZOa9Nhp6uq3sl8vsK/QqZ9AecyP3C2OwhuA/HqT90UyFwJLRKNvTrK+YWzA1jYBZ+/4X+12zf3xxoMJkqS5yceyM0rf7VsaKF9XbvormriqT2EFS5qcjlY/anmUC9LS0aVT8QeAxafJNyepb2rRvjDNJID78KKWrxWPhfMyoqrQs7UTp6+d5ByMzxsEnsVWn6GWyj+JdArpqNKp1RvA4tPkm5PcZSVlSKo9upbUrOxhpjh0NpuoLXMJIaFb6sh1ZaW/okiV9sadYDmFEyZ4c0++dAYmcNwvhf0BYKFp9Bn2lt+E5L9RJCqdlTY4I3C9bOUcrnVy4Lpy0l9RpOpEos6Tkk7G6HA6aPb1H+2+CcmLJxOks2y/g9SQ0BADdzVLSSA9faFwRsbZc53J6YTqJ+fNQGo66puHQvWW+ZoJgPmi6TcnSaP8pt6E5CzXFl8flD/Hokpn+iPWVjpV6vp15abvp1MXc8oVdjvok45p9aOURzgzkI456RJ685A/gYN0woJyCp4mant5guUPgNPH0ktn25u+2VQOcBpZYukczwe0FRG2nT4AzC9LLJ0AAG2BdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIAZIN0AgBkg3QCAGSDdAIA5PL/0I0n8LmEUI0AAAAASUVORK5CYII=" alt="" />
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(, "student_one"));
mapStudent.insert(pair<int, string>(, "student_two"));
mapStudent.insert(pair<int, string>(, "student_three"));
map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
}
五、例题
（1）MD5算法
MD5是一种信息摘要算法，它可以对任意大小的文件产生等长的密钥，当你在A主机使用MD5得到文件X的密钥后，在B主机同样对文件X使用MD5所得到密钥一定与A主机所得到的密钥相同。然后请实现MD5算法。
是的，我在开玩笑。
恩，我实现了一个MD6算法，它可以实现类似的功能。
本题包含多组样例。
输入第一行为数字N和Q，N为映射的行数，Q为询问的行数。
映射中每行包含一个字符串A(0<alen<30),和字符串A使用MD6算法对应的数字。
询问每行包含一个字符串A。
输出每个询问行中每个字符串使用MD6算法对应的数字。
5 3
fs3fwe 3
4838fdeewerwer 54
irjfhid 888
847hhhh 1
0000 0
0000
847hhhh
fs3fwe
0
1
3
#include <iostream>
#include<map>
#include<string.h>
#include<cstdio>
using namespace std; int main()
{
map<string,int>mp;
int N,M,i,num;
string str1,str2;;
while(scanf("%d%d",&N,&M)!=-)
{
mp.clear(); //一定不要忘记了把map清空
for(i=;i<N;i++)
{
cin>>str1>>num;
mp[str1]=num;
}
for(i=;i<M;i++)
{
cin>>str2;
cout<<mp[str2]<<endl;
}
}
return ;
}
（2）例2
某次张国庆脑袋抽筋时想到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
输入包含n+1行：
第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
输入
8
2
4
2
4
5
100
2
100
输出
2 3
4 2
5 1
100 2
#include <iostream>
#include<map>
#include<cstdio>
#include<string.h>
using namespace std; int main()
{
map<int,int>mp;
long long n,num1;
cin>>n;
while(n--)
{
cin>>num1;
mp[num1]++;
}
map<int,int>::iterator iter;
for(iter=mp.begin();iter!=mp.end();iter++)
cout<<iter->first<<" "<<iter->second<<endl; return ;
}
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAe0AAAD5CAIAAACF5vqVAAANGElEQVR4nO3dy3WzShYGUOdDKiTQIfRaSoRAmNwoNOxBB9Mh9EC2VBR1eEjocey9F4P7czEgqfy5VNTj63//+bfNZrPZ8m5fb78Dm81msz2yyXGbzWbLvclxm81my73JcZvNZsu9yXGbzWbLvX3n+H//+ZfNZrPZMm63HP8CIKNpjnen8fxj6N98awBsUOZ4dxqv6d0PkhwggzLH++E8nrrL/jLTAfhcdX38uxZeRjoAH6x6zvnTQK4qDpDErD7+Ux2X5QApFDk+ebR5y3QAPlmU41/dadREDvD5ihzvTuP5Gt39cBbjAAlMn3P2w3UYkBAHSMG4fIDc5DhAbnIcIDc5DpDbfFy+6Q4BMpnkeN8Xs2TpsQKQQdCuYjgnQBILOa4+DpBAO8etIgGQRSPH1cUBEqlzXIgD5DJfZ1l7CkAmdf9xdXGAXOp5a0tq5gCfz7h8gNzkOEBuchwgNzkOkFszx/vBU06AJBo5/r1IpxwHyKA1nnPoza8CkEV7PKccB8iiHs95SW85DpDFLcfLuVXkOEAW1xyfjcr3rBMgA+tIAOQmxwFyk+MAuRmXD5CbHAfITY4D5CbHAXKrx3PqOg6QyyTH+/57keXuNJ4tuQyQQdCu0p1GVXKADBZyXH0cIAHjgABya+S4ujhAIq31gIQ4QB7t9YAAyKLuP64uDpBLkeOzlSTUzAE+n3H5ALnJcYDc5DhAbnIcILdmjveDp5wASTRyvB/0VgFIozWec+jNrwKQRXs8pxwHyKIez3lJbzkOkMUtx8u5VeQ4QBbXHJ+NyvesEyAD60gA5CbHAXKT4wC5GZcPkJscB8hNjgPkJscBcpvk+LQPuaU6ARKoc1x4A+QixwFyk+MAuQXt4+IcIIlmf5VLnhvQCZBA0O+wO42CHCADOQ6QWzxPlhgHyGCS4/1gBQmAZIzLB8hNjgPkJscBcpPjALk1crw7jbPxnLcnoNMHoNF+AF6kzPGiu8okx4tgn2R8tB+A1ylyvOsuOdwP0xyfLrrcD+fzEO1XJwd4tUa7SpXjVVW7O43nMdqvRg7waus53oj1c7RfhRzg1eQ4QG7aVQByW89xzzkBPtmGHNfvEOCDFTledB//cT3MOCCAD2VcPkBuchwgNzkOkJscB8itzPHuNN4ecXpuCZDCJMf7vuhRqB8hQAZBu4pR9gBJLOS4+jhAAu0cN8geIIuN67oB8KHqHBfiALlMc7w7jdpTAFKp+4+riwPkUq6zXA4DMhQIIAfj8gFyk+MAuclxgNzkOEBuG8cBWdcN4EOVOV4s0GmdZYAkyn6H3SWH+2Ga49PJVvrhfB6i/erkAK/WaFepcryqanen8TxG+9XIAV5tPccbsX6O9quQA7yaHAfITbsKQG7rOe45J8An25Dj+h0CfLAix4vu4z+uhxkHBPChjMsHyE2OA+QmxwFyk+MAudXrc+5a1K18Mqq3CsBbTHK874sehRuS+WdmrUZfRQBeI2hX2TvKXv9xgDdZyPEduSzGAd6lneObB9n/NKkLcYA32biu24qN7ekAHK7O8XtbSDzoBHiPaY53p/HOiVK0kAO8R91//L4s1q4C8C7lOsvlMKBNQ4HKcUDmOwR4C+PyAXKT4wC5yXGA3OQ4QG7NHO+HTQ8ud8+PCMDhgnWWt+X43vkRAThcazzn0G+eX+XH3vkRAThIezznXTmuPg7wBvV4zkt6783x3bkPwEFuOV7OrbIrl9XFAd7omuOzUfkbn3UKcYC3emwdifvnRwTgGI/kuLo4wPs9kOP750cE4HDG5QPkJscBcpPjALnJcYDcJjk+fXK5tSuKbisAb1Tn+J5ALpbnlOMAb/JAjnfd5dB+kOMAb/NIffybHAd4o6B9fG/zihwHeJNmf5VLnm8dninHAd4o6He4Z30fOQ7wRnIcILd4niztKgAZTHK86BC+IcSLo/UjB3gX4/IBcpPjALnJcYDc5DhAbo0cb81feHumOX0AGu1vmkynaBE4gEOUOR7NX1gE+yTjo/2Rru+Ln9S3BeAIRY5H8xdOF12+/Svav8WecUYALGi0q1Q5XlW1r/+M9m9i7QmAg6zneCPWz0Mf799iX+UdgNgbclxdHOBAr25XEeIAx1rP8SOfc3anUXsKwKE25Phx/Q7VxQEOV+R4Y/7C62FHjAOaDAMyFAjgGMblA+QmxwFyk+MAuclxgNzkOEBuchwgNzkOkJscB8hNjgPkJscBcpPjALnJcYDc5DhAbnIcIDc5DpCbHAfITY4D5CbH32zTuqb3uyzCdOQF+uF8/ovL83Wn8S2v+13XJRM5/mbbcnzP+nlXjQzfe57g+L+YLXL8W2uZ3V3larLA43Sl9qnmVawG2XLL8Xr5zE8qOk/yCQs/b8jxvetZ3048PfSBdbHnx3en8df9Tr2rPHxCOdygCNpN67BHur4vVmpvH9+dxrp0fV/+l5W5g1Q5/vMmfVwl4Ck+4fdnPcenR2xsh2m8tL3nWTv+E969Y8nxJV13ucO6gnBX+fw5Z1Ab6IdGYRv6JzdCJhbkePF5/Oy//jUu3siyDj//4t34613sL46ffKMqiki0v2npPufXnX+JK6sUt5+9lZzo/N/7b1dYvG61ezyd1opm9Uu+7Xe+cVR0nsvrmb/g9es+MX4a71t0n9Hx9f6fT7j9+cblYfK/qk+qVf4Xy8PM7ute3vTT90OKy1XWfr9W3+hdn2KV43eVz+Wju9PYSvHNfyR25cbvEOX47V8/ReOaf806e/nhRpX58grF8dGHs/OPb3if0XWDUrSY443zT/eXPx1dt/jvDY8hG782629L471bOM+t3bEfmp9ocN0nVY/Cz6t5n/Hx7XIYfb5faxlUv9qg/MflYfEFb73utcT0w3kch0uUF1duvW8rl34sx+8qn8XPzo7tTuO8Ce9W+7qn7P9+7Rwvi+hSKjc/v6gITfdXARnF/r4/7buue0+Or9/m7Qei6+78HnrP70kUuuF5Li9iHKsb3pDjx1d34s+reZ+L7/NKbeKRHI/Kf1geYntz/Po96ud61x37rnufo3I8eNV1k0rZUr7pRf2NNuFK9JyzXdspRc1k0fH1c9Tz/ONf+ua67ePbd939OR6dP2qPaly3uuhq0bzre2vjrCvnmZX+Ddd9SlYsl5P2fUbv8/rndX+Obyz/L8vxlfftOIe0q0SHNSvjM+uFbntu/A5h+/jV0v4H6uNNj1TNw4pAfN31HC/+sTfHt9UHn/Sccz115+kwDNNuXavX3dcUutlSOYnuc0d5iz7fryPr42/I8Sd9O2rfT+sPWOtfgbKOXZ976Yf3Vhz+TtX8/hxfaR9v/Eg/tHb3p3aZiPZH4i907euGp729lO/nJXfmeHTd+m/DpldWNHJtKpetA8PzXO95escr131SjC98XsF9RscH5TD4fCcXiG5ra/v4zlzbcd04xxfKeezx9vHlctI6f1hwwngvL732Avfmxu/wQI5/XXNo/gWm+jY0bYedfu/ry4fLVbjs+Yq42DC32GhU32X5nez+dpWF6173jqduW0m7vRmbS2WzetY4T6OhvIrI5nW3t4Peo/G+Ld7nps+3+utZfb7z46tXF3wjaZaee74/bbvuQo4vvA8rF96U49NfyOkVwnLSOP+spaQsbXu+mm65zT9RGf8ynvM3i74XPa4f/tCvCHw8Of67HZ/lMhw+jRwHyO3v5vhzG3jz+TvP9uG3keNcyHHI6u/Od/iCHH9az7w7fdr9AIf4u/MdynHgd3hsvsOyEl8NWW7V66P9gek3hKp/7u1/Tu6y+vGFi8zHZ7f7HYe9xxfP3+hs25qFYGtfkqBf8EL/5er9Wbif8n/VXakb8/bN37d2/2tNVvAqD8x3OPmJYtRJ1Fl/99iq23zz5emn9zOdDqA8/drlirvvh0kgt1/X3vN/RUkfjoNdvNPN54nen/B+ghcUnSfO8aA8AE92/3yH4fxq0Q880lZTj2WPrjupqS5fq6hvTuN46XXtOH90ULVzvXlnYZ6QcH6P1v3fk+ON84Q5Hr1vwJPdP9/hbHjtwfMXfn3VrQHNFo4yL6aZu6GyXN/1yuvadf6vIDeXpxkK7rNxwB3z7e3P8YV2tvqHlssD8DwPzK/y5PkL51Nvreb4NaiqhpL43r7b/ScHL7yuPef/CnLzJfXxV+W4phT4AI/Mk/Xc+QtnNe0NOf4dJuPWynKRTPXj2OAE28/fuLniwrvbxzefZ+n92TOfX3iecL7Apfdtx3xMwE6PzXfYaow5av7CqvPD5cfH7yUJwxzfPv3H5DzXs8eva+/55+e53eaD/VWm1eHWvuj9Ce6nceTCecq2saX5AuftbHIcnuHXjed89vM1z++AD/PLcvzZI12MpAE+zq/J8Z9mm2fVlZ99foA7/ZocB/ij5DhAbnIcIDc5DpCbHAfITY4D5CbHAXKT4wC5yXGA3OQ4QG5yHCA3OQ6QmxwHyE2OA+QmxwFyk+MAuclxgNzkOEBq/wdT3TlzVDz5qQAAAABJRU5ErkJggg==" alt="" />
同时题解给出了常规求出
#include <iostream>
#include <algorithm> using namespace std; long f[]; int main()
{
long n;
cin >> n;
for (long i=;i<n;++i)
cin >> f[i];
f[n] = -;
long num = ;
sort(f, f + n);
for (long i=;i<n;++i)
{
if (f[i] == f[i + ])
++num;
else {
cout << f[i] << " " << num << endl;
num = ;
}
}
return ;
}
（3）例三
Description
得克萨斯州的一个小镇Doubleville，被外星人攻击。他们绑架了当地人并把他们带到飞船里。经过一番（相当不愉快的）人体实验，外星人克隆了一些 受害者，并释放了其中的多个副本回Doubleville。所以，现在有可能发生有6个人：原来的人和5个复制品都叫做Hugh F. Bumblebee。现在FBUC美国联邦调查局命令你负责确定每个人被复制了多少份，为了帮助您完成任务，FBUC收集每个人的DNA样本。同副本和原 来的人具有相同的DNA序列，不同的人有不同的序列（我们知道，城里没有同卵双胞胎，这不是问题）
Input
输入中含有多组数据，每一组以一行n m开始，表示共有n个人1 ≤ n ≤ 20000，其中DNA序列长度为m, 1 ≤ m ≤ 20. 接下来的n行为DNA序列：每行包含m个字符，字符为'A'，'C'，'G'或'T'。 输入以n=m=0 结尾。
Output
每一组数据应输出n行，每行一个整数。第一行表示有几个人没有被复制，第二行表示有几个人只被复制一次（也就是说有两个相同的人），第三行表示有几个是被
复制两次，依次类推，第i行表示其中有i个相同的人的共有几组。举例来说，如果有11个样本，其中之一是John Smith，和所有其余的都是从Joe
Foobar复制来的副本，那么你必须打印第一行和第10行输出1，其余行输出0。
Sample Input
9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
0 0
Sample Output
1
2
0
1
0
0
0
0
0
可以使用常规的结构体
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct dna
{
char ch[];
}
DNA[]; int cnt[]; int cmp(const void *a,const void *b)
{
struct dna *x = (struct dna *)a;
struct dna *y = (struct dna *)b;
return strcmp(x->ch,y->ch);
} int main()
{
int num,len,i,t; while(scanf("%d%d",&num,&len)&& (num + len))
{
for(i= ; i < num ; ++i)
{
scanf("%s",DNA[i].ch);
cnt[i+]= ;
} qsort(DNA,num,sizeof(DNA[]),cmp); t = ;
for(i= ; i < num ; ++i)
{
if(!strcmp(DNA[i].ch,DNA[i-].ch))
++t;
else
{
cnt[t]++;
t= ;
}
}
cnt[t]++;
for(i= ; i <= num ; ++i)
printf("%d\n",cnt[i]);
} return ;
}
这个可以想到的是map；STL中提供的map相当不错。
#include <iostream>
#include<map>
#include<string>
#include <cstdio>
using namespace std; map<string,int>m;
int cnt[]; int main()
{
string str;
int i,num,len; while(scanf("%d%d",&num,&len)&&( num + len ))
{
for(i = ; i < num ; ++i)
{
cin>>str;
m[str]++;
cnt[i+] = ;
str.clear();//一定要清空
} map<string,int>::iterator it; for( it = m.begin();it != m.end(); ++it)
cnt[it->second]++; for(i= ; i <= num ; ++i)
printf("%d\n",cnt[i]);
m.clear();
}
return ;
}