数据结构与算法-刷题-牛客

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	//修改标准输入设备为in文件，提交代码时删除该部分代码以及上面的引入的os库
	fin, errin := os.Open("in")
	if errin != nil {
		panic(errin)
	}
	defer fin.Close()
	os.Stdin = fin

	//修改标准输出设备为out文件，提交代码时删除该部分代码
	fout, errout := os.OpenFile("out", os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0755)
	if errout != nil {
		panic(errout)
	}
	defer fout.Close()
	os.Stdout = fout

	//这里往下开始写解题过程
	//-----------------
	//输入预处理
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	str := strings.Split(sc.Text(), " ")
	money, _ := strconv.Atoi(str[0])
	n, _ := strconv.Atoi(str[1])
	items := make([]item, n)
	for i := 0; i < n; i++ { //构造物品
		sc.Scan()
		it := strings.Split(sc.Text(), " ")
		v, _ := strconv.Atoi(it[0])
		p, _ := strconv.Atoi(it[1])
		q, _ := strconv.Atoi(it[2])
		items[i] = item{
			v,
			p,
			q,
			nil,
			nil,
		}

	}

	for j, k := range items { //构造主物品
		if k.q != 0 {
			if items[k.q-1].acc1 == nil {
				//                 fmt.Println(k,"acc1")
				items[k.q-1].acc1 = &items[j]
			} else {
				items[k.q-1].acc2 = &items[j]
			}
		}
	}
	//     fmtx.Println("ist",items)
	//由于每个东西只能买一件，并且买了主件才能买附件，同时主键的附件数量是确定的不大于2
	//因此我们可以看成购买就是针对于主件，只不过主件的附件数量不同而已，因为只能买一次
	//因此主件和附件的搭配只能选一种，之后就可以看成01背包问题，只不过背包的物品是多选一的
	matrix := make([][]int, n+1)
	for j, _ := range matrix {
		matrix[j] = make([]int, money+1)
	}
	cnt := 1
	for i := 0; i < n; i++ {
		if items[i].q != 0 { //附件直接跳过
			continue
		}
		//构造各个选择的价格和满意度
		var (
			v0   = items[i].v //只有主件
			myd0 = v0 * items[i].p
			v1   = v0 //主件加附件1
			myd1 = myd0
			v2   = v0 //主件加附件2
			myd2 = myd0
			v3   = v0 //主件加两个附件
			myd3 = myd0
		)
		if items[i].acc1 != nil {
			v1 += items[i].acc1.v
			myd1 += items[i].acc1.v * items[i].acc1.p
		}
		if items[i].acc2 != nil {
			v2 += items[i].acc2.v
			myd2 += items[i].acc2.v * items[i].acc2.p
		}
		if items[i].acc1 != nil && items[i].acc2 != nil {
			v3 = v3 + items[i].acc1.v + items[i].acc2.v
			myd3 = myd3 + items[i].acc1.v*items[i].acc1.p + items[i].acc2.v*items[i].acc2.p
		}
		//         fmt.Println("gz",v0,myd0,v1,myd1,v2,myd2,v3,myd3)

		for j := 1; j <= money; j++ {
			matrix[cnt][j] = matrix[cnt-1][j]
			if j >= v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v0]+myd0)
			}
			if j >= v1 && v1 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v1]+myd1)
			}
			if j >= v2 && v2 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v2]+myd2)
			}
			if j >= v3 && v3 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v3]+myd3)
			}

		}

		cnt++
	}
	fmt.Println(matrix[cnt-1][money])

}

type item struct {
	v    int
	p    int
	q    int
	acc1 *item
	acc2 *item
}

func max(a int, b int) int {
	if a >= b {
		return a
	}
	return b
}

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	//修改标准输入设备为in文件，提交代码时删除该部分代码以及上面的引入的os库
	fin, errin := os.Open("in")
	if errin != nil {
		panic(errin)
	}
	defer fin.Close()
	os.Stdin = fin

	//修改标准输出设备为out文件，提交代码时删除该部分代码
	fout, errout := os.OpenFile("out", os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0755)
	if errout != nil {
		panic(errout)
	}
	defer fout.Close()
	os.Stdout = fout

	//这里往下开始写解题过程
	//-----------------
	//输入预处理
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	str := strings.Split(sc.Text(), " ")
	money, _ := strconv.Atoi(str[0])
	n, _ := strconv.Atoi(str[1])
	items := make([]item, n)
	for i := 0; i < n; i++ { //构造物品
		sc.Scan()
		it := strings.Split(sc.Text(), " ")
		v, _ := strconv.Atoi(it[0])
		p, _ := strconv.Atoi(it[1])
		q, _ := strconv.Atoi(it[2])
		items[i] = item{
			v,
			p,
			q,
			nil,
			nil,
		}

	}

	for j, k := range items { //构造主物品
		if k.q != 0 {
			if items[k.q-1].acc1 == nil {
				//                 fmt.Println(k,"acc1")
				items[k.q-1].acc1 = &items[j]
			} else {
				items[k.q-1].acc2 = &items[j]
			}
		}
	}
	//     fmtx.Println("ist",items)
	//由于每个东西只能买一件，并且买了主件才能买附件，同时主键的附件数量是确定的不大于2
	//因此我们可以看成购买就是针对于主件，只不过主件的附件数量不同而已，因为只能买一次
	//因此主件和附件的搭配只能选一种，之后就可以看成01背包问题，只不过背包的物品是多选一的
	matrix := make([][]int, n+1)
	for j, _ := range matrix {
		matrix[j] = make([]int, money+1)
	}
	cnt := 1
	for i := 0; i < n; i++ {
		if items[i].q != 0 { //附件直接跳过
			continue
		}
		//构造各个选择的价格和满意度
		var (
			v0   = items[i].v //只有主件
			myd0 = v0 * items[i].p
			v1   = v0 //主件加附件1
			myd1 = myd0
			v2   = v0 //主件加附件2
			myd2 = myd0
			v3   = v0 //主件加两个附件
			myd3 = myd0
		)
		if items[i].acc1 != nil {
			v1 += items[i].acc1.v
			myd1 += items[i].acc1.v * items[i].acc1.p
		}
		if items[i].acc2 != nil {
			v2 += items[i].acc2.v
			myd2 += items[i].acc2.v * items[i].acc2.p
		}
		if items[i].acc1 != nil && items[i].acc2 != nil {
			v3 = v3 + items[i].acc1.v + items[i].acc2.v
			myd3 = myd3 + items[i].acc1.v*items[i].acc1.p + items[i].acc2.v*items[i].acc2.p
		}
		//         fmt.Println("gz",v0,myd0,v1,myd1,v2,myd2,v3,myd3)

		for j := 1; j <= money; j++ {
			matrix[cnt][j] = matrix[cnt-1][j]
			if j >= v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v0]+myd0)
			}
			if j >= v1 && v1 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v1]+myd1)
			}
			if j >= v2 && v2 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v2]+myd2)
			}
			if j >= v3 && v3 > v0 {
				matrix[cnt][j] = max(matrix[cnt][j], matrix[cnt-1][j-v3]+myd3)
			}

		}

		cnt++
	}
	fmt.Println(matrix[cnt-1][money])

}

type item struct {
	v    int
	p    int
	q    int
	acc1 *item
	acc2 *item
}

func max(a int, b int) int {
	if a >= b {
		return a
	}
	return b
}

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func main() {
	////修改标准输入设备为in文件，提交代码时删除该部分代码以及上面的引入的os库
	//fin, errin := os.Open("in")
	//if errin != nil {
	//	panic(errin)
	//}
	//defer fin.Close()
	//os.Stdin = fin
	//
	////修改标准输出设备为out文件，提交代码时删除该部分代码
	//fout, errout := os.OpenFile("out", os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0755)
	//if errout != nil {
	//	panic(errout)
	//}
	//defer fout.Close()
	//os.Stdout = fout

	//这里往下开始写解题过程
	//-----------------
	//输入预处理
	A, B, C, D, E, erripormask, private := 0, 0, 0, 0, 0, 0, 0
	b := bufio.NewReader(os.Stdin)
	//mmm := map[byte]int{
	//	'A': (1<<8 - 1) << 24,
	//	'B': (1<<16 - 1) << 16,
	//	'C': (1<<24 - 1) << 8,
	//	'D': 1<<32 - 1,
	//	'E': 1<<32 - 1,
	//}
	//for k, v := range mmm {
	//	fmt.Printf("%d:%b\n", k, v)
	//}
tag:
	for true {
		//fmt.Println()
		ip := make([]int, 4)
		mask := make([]int, 4)
		s, err := b.ReadString('\n')
		if err != nil {
			//fmt.Println(err)
			if err == io.EOF {
				break
			}
			erripormask++
			//fmt.Println("erripormask++")
			continue
		}
		if _, err := fmt.Sscanf(s, "%d.%d.%d.%d~%d.%d.%d.%d\n",
			&ip[0], &ip[1], &ip[2], &ip[3],
			&mask[0], &mask[1], &mask[2], &mask[3]); err != nil {
			//fmt.Println("erripormask++")
			erripormask++
			continue
		}
		//fmt.Println("ip:", ip, "mask", mask)
		m := 0
		for _, v := range mask {
			m <<= 8
			m += v
		}
		ipn := 0
		for _, v := range ip {
			ipn *= 1000
			ipn += v
		}
		//fmt.Println("ipn:", ipn, "\tm:", m)

		if !((ipn >= 1000000000 && ipn <= 126255255255) ||
			(ipn >= 128000000000 && ipn <= 191255255255) ||
			(ipn >= 192000000000 && ipn <= 223255255255) ||
			(ipn >= 224000000000 && ipn <= 239255255255) ||
			(ipn >= 240000000000 && ipn <= 255255255255)) {
			continue
		}

		if m == 0 || m == (1<<32-1) {
			erripormask++
			continue
		}
		for tmp, flag := 1<<31, true; tmp != 0; tmp >>= 1 {
			if tmp&m != 0 && flag {
				continue
			} else if tmp&m == 0 && flag {
				flag = false
			} else if tmp&m != 0 && !flag {
				//fmt.Printf("errmusk,m:%b,tmp:%b,m&tmp:%b", m, tmp, m&tmp)
				//fmt.Println("erripormask++")
				erripormask++
				continue tag
			}
		}
		//fmt.Printf("ipn:%d\tm:%b\n", ipn, m)
		switch {
		case ipn >= 1000000000 && ipn <= 126255255255:
			//if m != mmm['A'] {
			//	erripormask++
			//	continue tag
			//}
			//fmt.Println("A++")
			A++
		case ipn >= 128000000000 && ipn <= 191255255255:
			//if m != mmm['B'] {
			//	erripormask++
			//	continue tag
			//}
			//fmt.Println("B++")
			B++
		case ipn >= 192000000000 && ipn <= 223255255255:
			//if m != mmm['C'] {
			//	erripormask++
			//	continue tag
			//}
			//fmt.Println("C++")
			C++
		case ipn >= 224000000000 && ipn <= 239255255255:
			//if m != mmm['D'] {
			//	erripormask++
			//	continue tag
			//}
			//fmt.Println("D++")
			D++
		case ipn >= 240000000000 && ipn <= 255255255255:
			//if m != mmm['E'] {
			//	erripormask++
			//	continue tag
			//}
			//fmt.Println("E++")
			E++
		default:
			continue tag
		}
		if (ipn >= 10000000000 && ipn <= 10255255255) ||
			(ipn >= 172016000000 && ipn <= 172031255255) ||
			(ipn >= 192168000000 && ipn <= 192168255255) {
			//fmt.Println("private++")
			private++
		}

	}

	fmt.Println(A, B, C, D, E, erripormask, private)
}