相等的IPV6地址
IPV6地址首选表示法：x:x:x:x:x:x:x:x，分为8段，每段x是4个字符的十六进制值，每段x地址范围从0000 至 ffff，字母大小写等价。
其他两种短格式缩写：
- 省略前导零 通过省略前导零指定IPV6地址，例如，IPV6地址1050:0000:0000:0000:0005:0600:300c:326b 可写作 1050:0000:0:0:5:600:300c:326b 或 1050:0000:0:0000:5:600:300c:326b，都算为等价地址，但每一段需缩写完整，例如0030只能省略成30，不能省略成030.
- 双冒号 通过双冒号(::)替换一系列零（不小于2段）来指定IPV6地址。例如，IPV6地址ff06:0:0:0:1:0:0:c3 可写作ff06::1:0:0:c3 或ff06:0:0:0:1::c3，都算作等价地址。一个IP地址中只可以使用一次双冒号，并要求一系列零缩写完整，例如0:0:0:0 只能省略成 ::，不能省略成0::或0::0等。
输入：一个字符串，合法的IPV6地址
输出：一个正整数，表示所有等价地址的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 样例1
输入：1050:0:1000:1234:12:3450:1234:3269
输出：4
解释：需要考虑省略前导零，等价地址有：
1050:0:1000:1234:12:3450:1234:3269
1050:0000:1000:1234:12:3450:1234:3269
1050:0:1000:1234:0012:3450:1234:3269
1050:0000:1000:1234:0012:3450:1234:3269
样例2
输入：1050:0:0:1234:6789:3450:3333:3261
输出：5
解释：需要考虑省略前导零和双冒号，等价地址有：
1050:0:0:1234:6789:3450:3333:3261
1050:0000:0:1234:6789:3450:3333:3261
1050:0:0000:1234:6789:3450:3333:3261
1050:0000:0000:1234:6789:3450:3333:3261
1050::1234:6789:3450:3333:3261
样例3
输入：1050:0:1000:1234:a000:3450:1234:3269
输出：4
解释：需要考虑省略前导零和字母大小写，等价地址有：
1050:0:1000:1234:a000:3450:1234:3269
1050:0000:1000:1234:a000:3450:1234:3269
1050:0:1000:1234:A000:3450:1234:3269
1050:0000:1000:1234:A000:3450:1234:3269
|
解析：
- 字符串分割，方便后续操作，末尾加上一个’:’，分割后存储在字符串数组v里边；
- 用一个tmp临时数组存储v，清空v，遍历tmp数组，将全为0的地址项置为”0”，遇到双冒号展开（某一地址项的长度为0），检测地址项长度和8的距离差，补全”0”。
- 枚举可能的双冒号：
- 每一次可能的情况（哪几个0缩起来）进行一次枚举
- 每次枚举，我们需要考虑，前导零和大小写，前导零（
*2），大小写（*2）
- 累加所有的枚举
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int solve2(vector<string>& v) {
int res = 1;
for(string str : v) {
if(str[0] == '0' || str.size() < 4) {
res *= 2;
}
for(char c : str) {
if(c < '0' || c > '9' ) res *= 2;
}
}
return res;
}
vector<string> getSub(vector<string>& v, int pre, int i) {
vector<string> tmp;
for(int j = 0; j <= pre; j++) {
tmp.push_back(v[j]);
}
for(; i < v.size(); i++) {
tmp.push_back(v[i]);
}
return tmp;
}
int solve(string str) {
str += ":";
vector<string> v;
string tmpStr = "";
for(auto c : str) {
if(c == ':') {
v.push_back(tmpStr);
tmpStr = "";
} else {
tmpStr += c;
}
}
vector<string> tmp = v;
v.clear();
for(int i = 0; i < tmp.size(); i++) {
if(tmp[i] == "00" || tmp[i] == "000" || tmp[i] == "0000"){
tmp[i] = "0";
}
if(tmp[i].size()) v.push_back(tmp[i]);
else {
int cnt = 8 - tmp.size() + 1;
while(cnt--) v.push_back("0");
}
}
int ans = 0;
int pre = -1;
for(int i = 0; i < v.size(); i++) {
if(v[i] != "0") {
if(i - pre > 2) {
tmp = getSub(v, pre, i);
ans += solve2(tmp);
}
pre = i;
}
}
if(v.size()- pre > 2) {
tmp = getSub(v, pre, v.size());
ans += solve2(tmp);
}
ans += solve2(v);
return ans;
}
int main() {
string str;
cin >> str;
cout << solve(str) << endl;;
return 0;
}
|
游览小镇
需要规划一条路线，保证能游览完所有的小镇，同时走的路程（走过的路径之和）最短。
假定：
- 有些小镇之间有路径直接相连，有些小镇之间不直接相连；所有小镇都至少跟其他一个小镇相连；
- 可以在任意小镇出发和停止，可以多次访问同一个小镇；
- 路径无方向（可以从A到B，也可以从B到A）；可以多次通过同一条路径；相连接的小镇间的路径长度相当；
- 小镇编号从1开始。
输入
- 假定有N个小镇（3<=N<=16），则输入N+1行数据
- 第一行输入N，表示小镇的数量；接下去N行是各个小镇的邻接信息。
- 第i+1行数据里包含n(1<=n<=N-1)个数据，且不会包含i本身，即不存在从i到i小镇的路径。
- 如果存在联通i(1<=i<=N)与j(1<=i<=N)的路径，那么这条路径在第i+1行和第j+1行都会出现。
输出
能够访问所有小镇的最短路径长度；假如不存在可以访问所有小镇的路径，则输出-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 样例1
输入：
5
2 4
1 3
2 4
1 3 5
4
输出：
4
解释：一个5个点。1号与2、4相连，2号与1、3相连，3号与2、4相连，4号与1、3、5号相连，5号与4号相连。
样例2
输入：
5
2 4
1
4
1 3 5
4
输出：
5
解释：一个5个点。1号与2、4相连，2号与1相连，3号与4相连，4号与1、3、5号相连，5号与4号相连。
|
解析：
状态压缩dp，用一个二进制数位上的0或1，代表不同的状态（取1代表位于集合中）。用二进制表示所有物品的放与不放的情况，这些二进制用十进制表示就一个维度，这个维度能表示所有物品放与不放的情况，即状态压缩。
假设每个边的权值都为1，权值矩阵w存储每个节点直接的连接情况，两点之间存在边则权值为1，不存在边则权值为inf。
初始化状态矩阵dp[i][j]，i表示状态，j表示结尾的地方。
求最短的路径和，采用Floyd算法求最短路径，是一种插点法，通过3重循环，k为中转点，v为起点，w为终点，循环比较D[v][w] 和 D[v][k] + D[k][w] 最小值，如果D[v][k] + D[k][w] 为更小值，则把D[v][k] + D[k][w] 覆盖保存在D[v][w]中。
dp转移方程，首先枚举状态，再枚举这次要访问的点，第j位置上为1，循环遍历点k，如果k这个点在当前的状态（j不在状态集合）中，比较当前状态与从k这个点的状态转移过来的最小值，即dp[i][j]=min(dp[i-(1<<j)][k]+w[k][j],dp[i][j]);
循环遍历结尾点i，更新路径和最小值mn = min(mn,dp[(1<<n)-1][i])，dp[(1<<n)-1][i]指的是结尾点为i，n位集合上全为1，代表所有节点都访问过。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N=50;
int dp[1<<20][50];
int w[50][50];
int main() {
int n;
cin >> n;
getchar();
memset(w,0x3f,sizeof w);
for(int i = 0; i < n; i++){
string str;
getline(cin, str);
int tmp = 0;
for(int j = 0; j < str.size(); j++) {
if(str[j] == ' ') {
if(tmp == 0) continue;
w[i][tmp - 1] = 1;
w[tmp - 1][i] = 1;
tmp = 0;
} else {
tmp = tmp * 10 + (str[j] - '0');
}
}
if(tmp) {
w[tmp - 1][i] = 1;
w[i][tmp - 1] = 1;
}
}
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(w[i][j] > w[i][k] + w[k][j]){
w[i][j] = w[i][k] + w[k][j];
}
}
}
}
memset(dp, 0x3f, sizeof dp);
for(int i = 0;i < n; i++) {
dp[1 << i][i]=0;
}
for(int i = 0;i < (1<<n); i++){
for(int j = 0;j < n; j++){
if((i >> j) & 1){
for(int k = 0; k < n; k++){
if(((i - (1<<j)) >> k) & 1){
dp[i][j] = min(dp[i - (1<<j)][k] + w[k][j], dp[i][j]);
}
}
}
}
}
int mn = 100000000;
for(int i=0;i<n;i++) {
mn=min(mn, dp[(1<<n) - 1][i]);
}
if(mn == 100000000) {
cout << -1 << endl;
} else {
cout<<mn<<endl;
}
}
|