https://www.acwing.com/problem/content/description/90/
type MinStack struct {
s1 []int
s2 []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{[]int{}, []int{}}
}
func (this *MinStack) Push(x int) {
this.s1 = append(this.s1, x)
if len(this.s2) == 0 {
this.s2 = append(this.s2, x)
} else {
this.s2 = append(this.s2, min_i(x, this.s2[len(this.s2)-1]))
}
}
func (this *MinStack) Pop() {
this.s1 = this.s1[:len(this.s1)-1]
this.s2 = this.s2[:len(this.s2)-1]
}
func (this *MinStack) Top() int {
return this.s1[len(this.s1)-1]
}
func (this *MinStack) GetMin() int {
return this.s2[len(this.s2)-1]
}
func min_i(a, b int) int {
if a < b {
return a
}
return b
}
https://www.acwing.com/problem/content/description/130/
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
var sum = make([]int, 1e6+100)
var f = make([]int, 1e6+100)
var left = make([]int, 0)
var right = make([]int, 0)
var num int
var s string
func main() {
// ===== fast io =====
in := bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
ri := func() int { // read int
in.Scan()
x, _ := strconv.Atoi(string(in.Bytes()))
return x
}
rs := func() []byte { in.Scan(); return in.Bytes() } // read string
// rf := func() float64 { // read float64
// in.Scan()
// f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
// return f
// }
// ===== fast io =====
f[0] = -1 << 31
q := ri()
for ; q > 0; q-- {
s = string(rs())
if s == "I" {
num = ri()
left = append(left, num)
sum[len(left)] = sum[len(left)-1] + left[len(left)-1]
f[len(left)] = max_i(f[len(left)-1], sum[len(left)])
} else if s == "D" {
if len(left) != 0 {
left = left[:len(left)-1]
}
} else if s == "L" {
if len(left) != 0 {
right = append(right, left[len(left)-1])
left = left[:len(left)-1]
}
} else if s == "R" {
if len(right) != 0 {
left = append(left, right[len(right)-1])
right = right[:len(right)-1]
sum[len(left)] = sum[len(left)-1] + left[len(left)-1]
f[len(left)] = max_i(f[len(left)-1], sum[len(left)])
}
} else if s == "Q" {
num = ri()
fmt.Fprintln(out, f[num])
}
}
}
func max_i(a, b int) int {
if a < b {
return b
}
return a
}
https://www.acwing.com/problem/content/description/131/
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
var (
in *bufio.Scanner
out *bufio.Writer
)
func main() {
// ===== fast io =====
in = bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords) // 分割
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
ri := func() int { // read int
in.Scan()
x, _ := strconv.Atoi(string(in.Bytes()))
return x
}
// ===== fast io =====
// ----- ----- ----- ----- ----- ----- -----
n = ri()
dfs()
}
var (
n int = 0
st1 []int = []int{} // vector
st2 []int = []int{} // stack
st3 int = 1
cnt int = 20
)
func dfs() {
if cnt == 0 {
return
}
if len(st1) == n {
cnt--
for _, x := range st1 {
fmt.Fprint(out, x)
}
fmt.Fprintln(out)
return
}
if len(st2) > 0 { // 取出栈顶元素加入到st1 且只在栈非空时进行
st1 = append(st1, st2[len(st2)-1])
st2 = st2[:len(st2)-1]
dfs()
st2 = append(st2, st1[len(st1)-1])
st1 = st1[:len(st1)-1]
}
if st3 <= n { // 取出st3为入栈元素入栈 且只在st3容器中的元素个数不为0时进行
st2 = append(st2, st3)
st3++
dfs()
st2 = st2[:len(st2)-1]
st3--
}
}
https://www.acwing.com/problem/content/description/132/
package main
import (
"bufio"
"fmt"
"math/big"
"os"
"strconv"
)
var (
in *bufio.Scanner
out *bufio.Writer
)
func ri() int { // read int
in.Scan()
x, _ := strconv.Atoi(string(in.Bytes()))
return x
}
func rf() float64 { // read float64
in.Scan()
f, _ := strconv.ParseFloat(string(in.Bytes()), 64)
return f
}
func main() {
// ===== fast io =====
in = bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords) // 分割
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
// ===== fast io =====
// ----- ----- ----- ----- ----- ----- -----
n := int64(ri())
fmt.Fprintln(out, calc(n))
}
func calc(n int64) *big.Int {
res, res1, res2 := big.NewInt(1), big.NewInt(1), big.NewInt(1)
tmp := big.NewInt(n + 1)
res1.MulRange(1, n) // 累乘
res2.MulRange(1, 2*n)
res.Mul(res1, res1).Div(res2, res).Div(res, tmp)
return res
}