{ }codelper
高阶函数P0329

向左折叠，向右折叠

给出由 n 个整数排成一行的列表 a_1, a_2, …, a_n 和 q 条命令。
一条命令的形式是 "方向 运算 初始值"。
运算是用两个整数 x、y 得出一个值的函数，共有五种。
add 是 x + y，sub 是 x - y，max 是两者中较大的值，min 是两者中较小的值，gap 是 x - y 的绝对值。
方向为 L 时做左折叠。
把值 v 设为初始值，从 a_1 到 a_n 依次把 v 换成 运算(v, a_i)。
方向为 R 时做右折叠。
把值 v 设为初始值，从 a_n 到 a_1 倒着把 v 换成 运算(a_i, v)。
在右折叠中，列表的元素放在运算的第一个位置，到目前为止的值放在第二个位置。
对每条命令，求折叠结束时的 v。
请为每个方向各写一个接收列表、运算函数和初始值的折叠函数，再按运算名选出对应的函数传进去来解题。
样例的列表是 5 2 4。
"L sub 20" 是 ((20 - 5) - 2) - 4 = 9，"R sub 20" 是 5 - (2 - (4 - 20)) = -13。
"L gap 0" 中 v 依次变为 5、3、1，答案是 1；"R gap 0" 中 v 依次变为 4、2、3，答案是 3。

输入
第一行给出 n 和 q，用空格分隔。
第二行给出 a_1 到 a_n，用一个空格分隔。
接下来 q 行每行一条命令，依次是方向（L 或 R）、运算名（add、sub、max、min、gap 之一）和初始值，用一个空格分隔。
1 ≤ n ≤ 1,000，1 ≤ q ≤ 200，-1,000,000,000 ≤ a_i ≤ 1,000,000,000，-1,000,000,000 ≤ 初始值 ≤ 1,000,000,000
输出
对每条命令，按给出的顺序每行输出一个答案。
数只写数字，不加逗号
样例 1 · stdin
3 5
5 2 4
L sub 20
R sub 20
L gap 0
R gap 0
L max -7
stdout
9
-13
1
3
5
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 8 种语言题解

把函数当作值来用，各语言的写法不同。
这里把函数放进“名字 → 函数”的表里，再作为参数传给折叠函数。
Python 的函数名本身就是值，所以内置函数也可以直接放进去：{"add": operator.add, "max": max}。
JS、TS 用箭头函数 (p, q) => p - q。
Java 把 lambda 或 Long::sum、Math::max 这样的方法引用放进 LongBinaryOperator，用 f.applyAsLong(p, q) 调用。
C# 把 lambda 或 Math.Max 放进 Func<long, long, long>。
C 用函数指针 long long (*f)(long long, long long)，C++ 把 lambda 放进 std::function。
Craykon 没有 lambda，所以要定义有名字的函数，像 ops["sub"] = 减; 这样不加括号只写名字放进去，再用 f(acc, x) 调用。
陷阱一：右折叠不只是遍历方向变了，参数的位置也变了。
从右边遍历却用 f(v, a_i) 调用，样例的 R sub 20 会变成 ((20 - 4) - 2) - 5 = 9（答案是 -13）。
JS 的 reduceRight 也是按 f(到目前为止的值, 元素) 的顺序调用，直接用就会这样出错。
反过来只换参数位置却仍从左边遍历也是错的，不区分 L 和 R 也是错的。
陷阱二：在 JS 里不要像 list.reduce(Math.max, init) 这样直接传内置函数。
reduce 会给函数传（到目前为止的值, 元素, 下标, 数组）四个参数，而 Math.max 会把收到的全部转成数来比较，结果是 NaN（样例的 L max -7）。
要用只接收两个参数的箭头函数包一层。
陷阱三：不要漏掉初始值。
Python 的 functools.reduce(f, items) 不给初始值时从第一个元素开始，样例的 L sub 20 就不是 9 而是 (5 - 2) - 4 = -1。
陷阱四：把 1,000 个 10 亿相加是 1 万亿，超过 32 位。
Java、C# 用 long，C、C++ 用 long long 来折叠。
在 C++ 里把到目前为止的值放进 int，不报错却得到错误的数。
Python 的整数没有上限，JS、TS 和 Craykon 的数在 2^53 以内是精确的。

Pythonmain.py · 33 行
import sysfrom operator import add, sub def gap(p, q):    return abs(p - q) # 이름 → 함수. 함수도 값이라서 사전에 넣을 수 있다 (max, min은 내장 함수 그대로)OPS = {"add": add, "sub": sub, "max": max, "min": min, "gap": gap} def fold_left(items, f, init):    acc = init    for x in items:        acc = f(acc, x)          # 지금까지의 값이 왼쪽    return acc def fold_right(items, f, init):    acc = init    for x in reversed(items):        acc = f(x, acc)          # 지금까지의 값이 오른쪽    return acc def main():    lines = sys.stdin.read().split("\n")    n, q = map(int, lines[0].split())    items = [int(v) for v in lines[1].split()]    out = []    for line in lines[2:2 + q]:        side, name, init = line.split()        fold = fold_left if side == "L" else fold_right        out.append(fold(items, OPS[name], int(init)))    print("\n".join(map(str, out))) main()
JavaScriptmain.js · 32 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items = lines[1].trim().split(/\s+/).map(Number); // 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS = {  add: (p, q) => p + q,  sub: (p, q) => p - q,  max: (p, q) => Math.max(p, q),  min: (p, q) => Math.min(p, q),  gap: (p, q) => Math.abs(p - q),}; function foldLeft(list, f, init) {  let acc = init;  for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽  return acc;} function foldRight(list, f, init) {  let acc = init;  for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽  return acc;} const out = [];for (let k = 0; k < q; k++) {  const [side, name, init] = lines[2 + k].trim().split(/\s+/);  const fold = side === "L" ? foldLeft : foldRight;  out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
TypeScriptmain.ts · 37 行
import { readFileSync } from "node:fs"; type Op = (p: number, q: number) => number;type Fold = (list: number[], f: Op, init: number) => number; const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items: number[] = lines[1].trim().split(/\s+/).map(Number); // 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS: Record<string, Op> = {  add: (p, q) => p + q,  sub: (p, q) => p - q,  max: (p, q) => Math.max(p, q),  min: (p, q) => Math.min(p, q),  gap: (p, q) => Math.abs(p - q),}; const foldLeft: Fold = (list, f, init) => {  let acc = init;  for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽  return acc;}; const foldRight: Fold = (list, f, init) => {  let acc = init;  for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽  return acc;}; const out: number[] = [];for (let k = 0; k < q; k++) {  const [side, name, init] = lines[2 + k].trim().split(/\s+/);  const fold: Fold = side === "L" ? foldLeft : foldRight;  out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
JavaMain.java · 48 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.StringTokenizer;import java.util.function.LongBinaryOperator; public class Main {    static long foldLeft(long[] items, LongBinaryOperator f, long init) {        long acc = init;        for (long x : items) acc = f.applyAsLong(acc, x);      // 지금까지의 값이 왼쪽        return acc;    }     static long foldRight(long[] items, LongBinaryOperator f, long init) {        long acc = init;        for (int i = items.length - 1; i >= 0; i--) acc = f.applyAsLong(items[i], acc);   // 지금까지의 값이 오른쪽        return acc;    }     public static void main(String[] args) throws Exception {        // 이름 → 함수. 이미 있는 메서드는 Long::sum처럼, 없는 것은 람다로 적는다        Map<String, LongBinaryOperator> ops = new HashMap<>();        ops.put("add", Long::sum);        ops.put("sub", (p, q) -> p - q);        ops.put("max", Math::max);        ops.put("min", Math::min);        ops.put("gap", (p, q) -> Math.abs(p - q));         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(br.readLine());        int n = Integer.parseInt(st.nextToken());        int q = Integer.parseInt(st.nextToken());        long[] items = new long[n];        st = new StringTokenizer(br.readLine());        for (int i = 0; i < n; i++) items[i] = Long.parseLong(st.nextToken());         StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            st = new StringTokenizer(br.readLine());            String side = st.nextToken();            LongBinaryOperator f = ops.get(st.nextToken());            long init = Long.parseLong(st.nextToken());            out.append(side.equals("L") ? foldLeft(items, f, init) : foldRight(items, f, init)).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 47 行
using System;using System.Collections.Generic;using System.Text; class Program{    static long FoldLeft(long[] items, Func<long, long, long> f, long init)    {        long acc = init;        foreach (long x in items) acc = f(acc, x);      // 지금까지의 값이 왼쪽        return acc;    }     static long FoldRight(long[] items, Func<long, long, long> f, long init)    {        long acc = init;        for (int i = items.Length - 1; i >= 0; i--) acc = f(items[i], acc);   // 지금까지의 값이 오른쪽        return acc;    }     static void Main()    {        // 이름 → 함수. Math.Max는 형이 여러 가지라 Func<long, long, long>에 넣으면 long용이 골라진다        var ops = new Dictionary<string, Func<long, long, long>>        {            ["add"] = (p, q) => p + q,            ["sub"] = (p, q) => p - q,            ["max"] = Math.Max,            ["min"] = Math.Min,            ["gap"] = (p, q) => Math.Abs(p - q),        };         string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int q2 = int.Parse(first[1]);        long[] items = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse);         var sb = new StringBuilder();        for (int k = 0; k < q2; k++)        {            string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            Func<long, long, long> f = ops[parts[1]];            long init = long.Parse(parts[2]);            sb.Append(parts[0] == "L" ? FoldLeft(items, f, init) : FoldRight(items, f, init)).Append('\n');        }        Console.Write(sb);    }}
C++main.cpp · 47 行
#include <algorithm>#include <cstdlib>#include <functional>#include <iostream>#include <map>#include <string>#include <vector> using Op = std::function<long long(long long, long long)>; long long foldLeft(const std::vector<long long> &items, const Op &f, long long init) {    long long acc = init;    for (long long x : items) acc = f(acc, x);                        // 지금까지의 값이 왼쪽    return acc;} long long foldRight(const std::vector<long long> &items, const Op &f, long long init) {    long long acc = init;    for (auto it = items.rbegin(); it != items.rend(); ++it) acc = f(*it, acc);   // 지금까지의 값이 오른쪽    return acc;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);     // 이름 → 함수. 람다를 std::function에 담는다    const std::map<std::string, Op> ops = {        {"add", [](long long p, long long q) { return p + q; }},        {"sub", [](long long p, long long q) { return p - q; }},        {"max", [](long long p, long long q) { return std::max(p, q); }},        {"min", [](long long p, long long q) { return std::min(p, q); }},        {"gap", [](long long p, long long q) { return std::llabs(p - q); }},    };     int n, q;    std::cin >> n >> q;    std::vector<long long> items(n);    for (auto &x : items) std::cin >> x;    for (int k = 0; k < q; k++) {        std::string side, name;        long long init;        std::cin >> side >> name >> init;        const Op &f = ops.at(name);        std::cout << (side == "L" ? foldLeft(items, f, init) : foldRight(items, f, init)) << '\n';    }}
Cmain.c · 46 行
#include <stdio.h>#include <string.h> /* 함수를 가리키는 포인터의 형: long long 둘을 받아 long long을 돌려주는 함수 */typedef long long (*Op)(long long, long long); long long op_add(long long p, long long q) { return p + q; }long long op_sub(long long p, long long q) { return p - q; }long long op_max(long long p, long long q) { return p > q ? p : q; }long long op_min(long long p, long long q) { return p < q ? p : q; }long long op_gap(long long p, long long q) { return p > q ? p - q : q - p; } /* 이름 → 함수 표 */struct { const char *name; Op f; } OPS[] = {    {"add", op_add}, {"sub", op_sub}, {"max", op_max}, {"min", op_min}, {"gap", op_gap},}; long long fold_left(const long long *items, int n, Op f, long long init) {    long long acc = init;    for (int i = 0; i < n; i++) acc = f(acc, items[i]);        /* 지금까지의 값이 왼쪽 */    return acc;} long long fold_right(const long long *items, int n, Op f, long long init) {    long long acc = init;    for (int i = n - 1; i >= 0; i--) acc = f(items[i], acc);   /* 지금까지의 값이 오른쪽 */    return acc;} long long items[1000]; int main(void) {    int n, q;    scanf("%d %d", &n, &q);    for (int i = 0; i < n; i++) scanf("%lld", &items[i]);    for (int k = 0; k < q; k++) {        char side[4], name[8];        long long init;        scanf("%3s %7s %lld", side, name, &init);        Op f = NULL;        for (int j = 0; j < 5; j++)            if (strcmp(OPS[j].name, name) == 0) f = OPS[j].f;        printf("%lld\n", side[0] == 'L' ? fold_left(items, n, f, init) : fold_right(items, n, f, init));    }    return 0;}
Craykonmain.cray · 70 行
더하기(p, q){    返回 p + q;} 덜기(p, q){    返回 p - q;} 큰쪽(p, q){    返回 数学.较大值(p, q);} 작은쪽(p, q){    返回 数学.较小值(p, q);} 차이(p, q){    返回 数学.绝对值(p - q);} // 이름 → 함수. 함수 이름을 괄호 없이 쓰면 함수 자체가 값이 된다ops = 字典();ops["add"] = 더하기;ops["sub"] = 덜기;ops["max"] = 큰쪽;ops["min"] = 작은쪽;ops["gap"] = 차이; 왼쪽접기(items, f, init){    acc = init;    遍历 (x 在 items)    {        acc = f(acc, x); // 지금까지의 값이 왼쪽    }    返回 acc;} 오른쪽접기(items, f, init){    acc = init;    循环 (i = items.数量 - 1; i >= 0; i--)    {        acc = f(items[i], acc); // 지금까지의 값이 오른쪽    }    返回 acc;} 첫줄 = 控制台.读数字();q = 첫줄[1];items = 控制台.读数字();循环 (k = 0; k < q; k++){    parts = 控制台.读行().分割(" ");    f = ops[parts[1]];    init = parts[2].转数字();    如果 (parts[0] == "L")    {        控制台.输出(왼쪽접기(items, f, init));    }    否则    {        控制台.输出(오른쪽접기(items, f, init));    }}