首页 > 代码库 > CodeForces 250B Restoring IPv6 解题报告
CodeForces 250B Restoring IPv6 解题报告
Description
An IPv6-address is a 128-bit number. For convenience, this number is recorded in blocks of 16 bits in hexadecimal record, the blocks are separated by colons — 8 blocks in total, each block has four hexadecimal digits. Here is an example of the correct record of a IPv6 address: "0124:5678:90ab:cdef:0124:5678:90ab:cdef". We‘ll call such format of recording an IPv6-address full.
Besides the full record of an IPv6 address there is a short record format. The record of an IPv6 address can be shortened by removing one or more leading zeroes at the beginning of each block. However, each block should contain at least one digit in the short format. For example, the leading zeroes can be removed like that: "a56f:00d3:0000:0124:0001:f19a:1000:0000" → "a56f:d3:0:0124:01:f19a:1000:00". There are more ways to shorten zeroes in this IPv6 address.
Some IPv6 addresses contain long sequences of zeroes. Continuous sequences of 16-bit zero blocks can be shortened to "::". A sequence can consist of one or several consecutive blocks, with all 16 bits equal to 0.
You can see examples of zero block shortenings below:
1. "a56f:00d3:0000:0124:0001:0000:0000:0000" → "a56f:00d3:0000:0124:0001::";
2. "a56f:0000:0000:0124:0001:0000:1234:0ff0" → "a56f::0124:0001:0000:1234:0ff0";
3. "a56f:0000:0000:0000:0001:0000:1234:0ff0" → "a56f:0000::0000:0001:0000:1234:0ff0";
4. "a56f:00d3:0000:0124:0001:0000:0000:0000" → "a56f:00d3:0000:0124:0001::0000";
5. "0000:0000:0000:0000:0000:0000:0000:0000" → "::".
It is not allowed to shorten zero blocks in the address more than once. This means that the short record can‘t contain the sequence of characters "::" more than once. Otherwise, it will sometimes be impossible to determine the number of zero blocks, each represented by a double colon.
The format of the record of the IPv6 address after removing the leading zeroes and shortening the zero blocks is called short.
You‘ve got several short records of IPv6 addresses. Restore their full record.
Input
The first line contains a single integer n — the number of records to restore (1 ≤ n ≤ 100).
Each of the following n lines contains a string — the short IPv6 addresses. Each string only consists of string characters "0123456789abcdef:".
It is guaranteed that each short address is obtained by the way that is described in the statement from some full IPv6 address.
Output
For each short IPv6 address from the input print its full record on a separate line. Print the full records for the short IPv6 addresses in the order, in which the short records follow in the input.
Sample Input
6
a56f:d3:0:0124:01:f19a:1000:00
a56f:00d3:0000:0124:0001::
a56f::0124:0001:0000:1234:0ff0
a56f:0000::0000:0001:0000:1234:0ff0
::
0ea::4d:f4:6:0
Sample Output
a56f:00d3:0000:0124:0001:f19a:1000:0000
a56f:00d3:0000:0124:0001:0000:0000:0000
a56f:0000:0000:0124:0001:0000:1234:0ff0
a56f:0000:0000:0000:0001:0000:1234:0ff0
0000:0000:0000:0000:0000:0000:0000:0000
00ea:0000:0000:0000:004d:00f4:0006:0000
题意：大意是说给定一个ipv6地址的简记形式，让你给它补全输出。一个ipv6地址是由8个小地址组成，每个小地址由‘:‘隔开。简记的规则大致是把地址中的一部分前缀0去掉，或去掉一连串的0，用：：来代替。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int main() 7 { 8 char str1[50],str2[50]; //数组str1用来存输入的ipv6地址的简记形式，数组str2用来存输出的ipv6地址的形式 9 int n,c,i,j,k,cnt,flag; //cnt用来存小地址的个数，flag用来标记是否为‘:‘，c用来判断小地址的字符数是否达到4个10 cin>>n;11 while(n--)12 {13 flag=cnt=0;14 scanf("%s",str1);15 k=strlen(str1);16 str1[k]=‘:‘; //在数组str1后加‘:‘，保证最后一个小地址能计入个数17 str1[k+1]=‘\0‘;18 for(i=0; i<=38; i++) //初始化数组str219 {20 if(i==4||i==9||i==14||i==19||i==24||i==29||i==34)21 str2[i]=‘:‘;22 else23 str2[i]=‘0‘;24 }25 for(i=0; i<=k; i++) //计算小地址的个数26 {27 if(str1[i]!=‘:‘)28 flag=1;29 else if(flag==1)30 {31 cnt++;32 flag=0;33 }34 }35 c=0;36 j=38;37 for(i=k-1; i>=0; i--) //操作j的位置来控制数组str2的字符38 {39 if(str1[i]!=‘:‘)40 {41 c++;42 str2[j--]=str1[i];43 }44 if(str1[i]==‘:‘)45 {46 if(c==4)47 j--;48 else if(c==3)49 j=j-2;50 else if(c==2)51 j=j-3;52 else if(c==1)53 j=j-4;54 c=0;55 }56 if(str1[i]==‘:‘&&str1[i-1]==‘:‘)57 {58 j=j-((8-cnt)*4+(8-cnt));59 i--;60 }61 }62 for(i=0; i<=37; i++)63 cout<<str2[i];64 cout<<str2[38]<<endl;65 }66 return 0;67 }