In dem Moment, als ich das Problem sah, fragte ich mich, wofür K war, aber ich brauchte es nicht (lacht). Der Durchschnittswert von 0 bis N war die Summe von 0 bis N geteilt durch N + 1. Da es (0 + N) * (N + 1) ≤ 2 ≤ (N + 1) ist, wird es N ≤ 2.
N, K = map(int, input().split())
print(N / 2)
Ich hatte eine GCD-Version von SegmentTree, also war es ein sofortiger Kill (lacht). Im Grunde ist es eine Skalierungsmethode. Wenn GCD 1 wird, ist es 1, egal wie weit Sie von dort entfernt sind, also GCD (A i </ sub>) >, A i + 1 </ sub>, ..., A j </ sub>) Wenn es zum ersten Mal 1 wird, ist A i </ sub> das linke Ende Die Anzahl der Teilzeichenfolgen, für die GCD 1 ist, ist N - j + 1. Als nächstes betrachten wir eine Teilzeichenfolge mit A i + 1 </ sub> als linkem Ende, aber natürlich ist das rechte Ende j. Dies ist die obige Zahl. Hier wurde SegmentTree verwendet, um die GCD (A i + 1 </ sub>, ..., A
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...)
}
Es dreht sich im Uhrzeigersinn, aber denken Sie zuerst darüber nach, welches Volumen (I, J) ist. Ich weiß, dass es der Minimalwert von I, J, N -1 - I, N -1 - J ist. Wenn der Minimalwert l ist, ist die Anzahl der Bewegungen vor dem Betreten des l-ten Volumens die Gesamtzahl der Bewegungen N * N abzüglich der Anzahl der Bewegungen nach dem l-ten Volumen (N - 2 * l) * (N - 2 * l). Danach können Sie antworten, indem Sie die Bewegung überprüfen, indem Sie nur eine Rolle vorrücken und sie zur Anzahl der Bewegungen addieren, bis Sie in die l. Rolle eintreten.
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)
Ich schrieb "println (Ergebnis)" als "Druck (Ergebnis)" und konnte während des Wettbewerbs nicht antworten. Als ich es in Python mit genau demselben Algorithmus schrieb, kam WA nicht heraus, aber es war TLE, also schrieb ich es in Go-Sprache um. ing.
Jedes Mal, wenn ich an der Tankstelle ankomme, mache ich DP nur mit und ohne Kraftstoff, daher denke ich, dass es nicht besonders schwierig ist. Wenn die gleiche Menge Kraftstoff teuer ist, verwerfen Sie dieses Muster.
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...)
}
Wenn die Gesamtzahl der Malmethoden, die i Farbtypen verwenden, f (i) ist, dann ist f (i) = M </ sub> C i </ sub> * i N. </ sup> --f (i -1). Auch f (0) = 0.
Es dauerte mehr als 5 Stunden, um dorthin zu gelangen, orz. ★ 2 oder lügen.
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