Au moment où j'ai vu le problème, je me suis demandé à quoi servait K, mais je n'en avais pas besoin (rires) La valeur moyenne de 0 à N était la somme de 0 à N divisée par N + 1. Puisqu'il est (0 + N) * (N + 1) ÷ 2 ÷ (N + 1), il devient N ÷ 2.
N, K = map(int, input().split())
print(N / 2)
J'avais une version GCD de SegmentTree, donc c'était un kill instantané (rires). Fondamentalement, c'est une méthode d'échelle. Quand GCD devient 1, c'est 1 peu importe jusqu'où vous allez, donc GCD (A i </ sub> >, A i + 1 </ sub>, ..., A j </ sub>) S'il devient 1 pour la première fois, A i </ sub> est l'extrémité gauche Le nombre de sous-chaînes pour lesquelles GCD est 1 est N --j + 1. Ensuite, considérons une sous-chaîne avec A i + 1 </ sub> à l'extrémité gauche, mais bien sûr l'extrémité droite est j. C'est le nombre ci-dessus. Ici, SegmentTree a été utilisé pour calculer GCD (A i + 1 </ sub>, ..., A j </ sub>) à grande vitesse. Si j devient N mais que GCD ne devient pas 1, alors GCD ne devient pas 1 dans la sous-colonne à sa droite, vous pouvez donc y arrêter le calcul.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
for b > 0 {
a, b = b, a%b
}
return a
}
type segmentTree struct {
data []int
offset int
}
func newSegmentTree(n int) segmentTree {
var result segmentTree
t := 1
for t < n {
t *= 2
}
result.offset = t - 1
result.data = make([]int, 2*t-1)
return result
}
func (st segmentTree) updateAll(a []int) {
for i, v := range a {
st.data[st.offset+i] = v
}
for i := st.offset - 1; i > -1; i-- {
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) update(index, value int) {
i := st.offset + index
st.data[i] = value
for i >= 1 {
i = (i - 1) / 2
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) query(start, stop int) int {
result := 0
l := start + st.offset
r := stop + st.offset
for l < r {
if l&1 == 0 {
result = gcd(result, st.data[l])
}
if r&1 == 0 {
result = gcd(result, st.data[r-1])
}
l = l / 2
r = (r - 1) / 2
}
return result
}
func main() {
defer flush()
N := readInt()
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = readInt()
}
st := newSegmentTree(N)
st.updateAll(A)
result := 0
j := 1
for i := 0; i < N; i++ {
v := st.query(i, j)
for v != 1 && j < N {
v = gcd(v, A[j])
j++
}
if v != 1 {
break
}
result += N - j + 1
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Il va dans un tourbillon dans le sens des aiguilles d'une montre, mais pensez d'abord à ce qu'est le volume (I, J) .Il s'avère que c'est la valeur minimale de I, J, N -1 --I, N -1 --J. Lorsque la valeur minimale est l, le nombre de mouvements avant d'entrer dans le lème volume est le nombre total de mouvements N * N moins le nombre de mouvements après le lème volume (N - 2 * l) * (N - 2 * l). Vous pouvez voir que c'est une chose, après cela, vous pouvez répondre en avançant d'un seul jet, en vérifiant le mouvement effectué et en additionnant le nombre de mouvements jusqu'à ce que vous entriez dans le lème jet.
Q = int(input())
for i in range(Q):
N, I, J = map(int, input().split())
l = min(I, J, N - 1 - I, N - 1 - J)
result = N * N - (N - 2 * l) * (N - 2 * l)
N, I, J = N - 2 * l, I - l, J - l
if I == 0:
result += J
elif J == N - 1:
result += N - 1 + I
elif I == N - 1:
result += 2 * (N - 1) + (N - 1) - J
elif J == 0:
result += 3 * (N - 1) + (N - 1) - I
print(result)
J'ai écrit println (result) comme print (result) et je n'ai pas pu répondre pendant le concours orz. Quand je l'ai écrit en Python avec exactement le même algorithme, WA n'est pas sorti, mais c'était TLE, donc je l'ai réécrit en langage Go. ing.
Chaque fois que j'arrive à la station-service, je ne fais que DP avec et sans carburant, donc je pense que ce n'est pas particulièrement difficile.Si la même quantité de carburant coûte cher, jetez ce schéma.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
defer flush()
N := readInt()
V := readInt()
L := readInt()
cx := 0
d := map[int]int{}
d[V] = 0
for i := 0; i < N; i++ {
x := readInt()
v := readInt()
w := readInt()
nd := map[int]int{}
for k := range d {
t := k - (x - cx)
if t < 0 {
continue
}
_, ok := nd[t]
if !ok || nd[t] > d[k] {
nd[t] = d[k]
}
t = min(t+v, V)
_, ok = nd[t]
if !ok || nd[t] > d[k]+w {
nd[t] = d[k] + w
}
}
if len(nd) == 0 {
println(-1)
return
}
d = nd
cx = x
}
result := math.MaxInt64
for k := range d {
if k-(L-cx) >= 0 {
result = min(result, d[k])
}
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Si le nombre total de méthodes de peinture utilisant i types de peinture est f (i), alors f (i) = M </ sub> C i </ sub> * i N </ sup> --f (i -1). Aussi, f (0) = 0.
Il a fallu plus de 5 heures pour y arriver, orz. ★ 2 ou mentir.
from sys import setrecursionlimit
setrecursionlimit(1000000)
N, M = map(int, input().split())
fac = [0] * (M + 1)
fac[0] = 1
for i in range(M):
fac[i + 1] = fac[i] * (i + 1) % 1000000007
def mcomb(n, k):
if n == 0 and k == 0:
return 1
if n < k or k < 0:
return 0
return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007
def f(i):
if i == 0:
return 0
return (mcomb(M, i) * pow(i, N, 1000000007) - f(i - 1)) % 1000000007
print(f(M))
Recommended Posts