DE-PR-002 实操二渠道订单汇总

admin SU @ 2026-10-14 12:07:50

组织者内部题解，含参考实现。比赛中不向选手展示。

业务背景与基本概念

渠道汇总把订单事实与客户维度关联。客户表定义客户属于哪个渠道，渠道列表定义必须展示哪些渠道。订单状态会随版本变化，例如付款后取消，因此先选最新状态再决定是否计入。订单数、客户去重数和金额是三种不同指标。

公式、符号与业务口径

每订单以(version,输入位置)取最大记录。仅最新status=PAID且客户在维表的记录有效。对渠道ch：订单数=有效订单条数；客户数=该渠道有效订单客户ID集合大小；金额=Σ有效订单amount。金额以分统计，避免浮点货币误差。无订单渠道输出三个0。

样例逐步计算

O1版本2为CANCELLED，故版本1的100分不能保留贡献。O2客户C2、200分有效；O3客户CX不在维表，排除；O4客户C2、50分有效。C2归APP，因此APP有2订单、1客户、250分。SHOP和WEB无有效订单，输出0。渠道按APP、SHOP、WEB排序。

解题步骤与实现思路

准备客户映射与全渠道零值容器；订单按ID留最新，再关联汇总。时间O(k+m+n+k log k)，空间O(k+m+u)。

常见错误与边界

先过滤PAID再去重会错误计入O1。不要把同客户两单合并成一个订单或只留一笔金额。不能丢失无订单渠道，也不能根据未知客户自行创造渠道。

原始题面与输入输出

DE-PR-002 实操二渠道订单汇总题型：综合；25分

业务与规则

客户表customer_id唯一，所属渠道在给定渠道列表内；渠道列表唯一。
订单表中同order_id可能出现多次，先保留version最大者，版本相同保留输入较后者。之后才判断状态与关联。
只计入最新记录status=PAID且customer_id存在于客户表的订单；其他订单忽略。
每个渠道输出有效订单数、去重客户数和金额合计，金额按分输出；渠道无订单也输出0。按渠道字典升序。

输入第一行k，随后k行渠道名称。下一行m，随后m行customer_id channel。下一行n，随后n行order_id customer_id version status amount；status为PAID或CANCELLED，amount为非负整数分。

输出共k行：channel order_count customer_count amount_sum。

范围 1≤k≤100；0≤m,n≤100000；version≤1e9，amount≤1e12分；汇总额用64位整数。所有编号与渠道仅含大写字母、数字。建议3秒、256MB，按语言校准。

样例输入 3 WEB APP SHOP 2 C1 WEB C2 APP 5 O1 C1 1 PAID 100 O1 C1 2 CANCELLED 100 O2 C2 1 PAID 200 O3 CX 1 PAID 300 O4 C2 1 PAID 50

样例输出 APP 2 1 250 SHOP 0 0 0 WEB 0 0 0

各语言如何对应算法

各份程序实现上文同一计算口径。读取阶段将字符串编号与数值分开处理；中间状态负责累计、集合去重或版本选择；输出阶段才做规定排序、分页及六位小数格式化。按“解题步骤”对照各文件业务段，通用读取、哈希和排序辅助函数可先跳过，再回头理解。

Python/PyPy完整参考实现

文件：reference.py，与本题同文件夹。

Python与PyPy共用本文件。字典保存按业务键的状态，集合负责去重；Python整数可自动扩展，精确小数边界题使用Decimal。

运行方法：python reference.py；或pypy3 reference.py。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import sys
it=iter(sys.stdin.read().split()); k=int(next(it)); channels=[next(it) for _ in range(k)]
m=int(next(it)); customers={next(it):next(it) for _ in range(m)}
n=int(next(it)); latest={}
for _ in range(n):
    oid,cid,ver,status,amount=[next(it) for _ in range(5)]; ver=int(ver); amount=int(amount)
    if oid not in latest or ver>=latest[oid][1]: latest[oid]=(cid,ver,status,amount)
stats={c:[0,set(),0] for c in channels}
for cid,ver,status,amount in latest.values():
    if status!='PAID' or cid not in customers: continue
    st=stats[customers[cid]]; st[0]+=1; st[1].add(cid); st[2]+=amount
for c in sorted(channels):
    st=stats[c]; print(c,st[0],len(st[1]),st[2])

C完整参考实现

文件：reference.c，与本题同文件夹。

I为64位整数，F为浮点数，Group保存业务状态，Map按字符串键查找；main中的业务步骤可与上文逐项对应。

运行方法：gcc -std=c17 -O2 reference.c -lm -o reference，然后运行reference。测试数据通过标准输入送入，运行说明中的重定向不写入程序。


/* Native C17 reference. Read stdin, write stdout; no Python dependency. */
#include <ctype.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long I;
typedef double F;
typedef struct {
  char *key;
  I v[8];
  F f[8];
  char *s[4];
  int flag;
} Group;
typedef struct {
  Group *a;
  int count, cap;
  int *slots;
  int size;
} Map;
char ***L;
int *lc, lines, n;
char **h, ***r;
Map groups;
I iv(const char *s) { return strtoll(s, NULL, 10); }
F fv(const char *s) { return strtod(s, NULL); }
int eq(const char *a, const char *b) { return strcmp(a, b) == 0; }
F divide(F a, F b) { return b ? a / b : 0; }
char *dupstr(const char *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  return p;
}
uint64_t hash(const char *s) {
  uint64_t v = 1469598103934665603ULL;
  for (; *s; s++)
    v = (v ^ (unsigned char)*s) * 1099511628211ULL;
  return v;
}
void mapinit(Map *m) {
  m->size = 131071;
  m->slots = malloc(m->size * sizeof(int));
  for (int i = 0; i < m->size; i++)
    m->slots[i] = -1;
  m->count = 0;
  m->cap = 16;
  m->a = calloc(m->cap, sizeof(Group));
}
int lookup(Map *m, const char *k) {
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0) {
    int i = m->slots[p];
    if (eq(m->a[i].key, k))
      return i;
    p = (p + 1) % m->size;
  }
  return -1;
}
int ensure(Map *m, const char *k) {
  int i = lookup(m, k);
  if (i >= 0)
    return i;
  if (m->count == m->cap) {
    m->cap *= 2;
    m->a = realloc(m->a, m->cap * sizeof(Group));
  }
  i = m->count++;
  memset(&m->a[i], 0, sizeof(Group));
  m->a[i].key = dupstr(k);
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0)
    p = (p + 1) % m->size;
  m->slots[p] = i;
  return i;
}
Group *get(Map *m, const char *k) {
  int i = ensure(m, k);
  return &m->a[i];
}
char *pairkey(const char *a, const char *b) {
  size_t z = strlen(a) + strlen(b) + 2;
  char *p = malloc(z);
  snprintf(p, z, "%s\037%s", a, b);
  return p;
}
char *numpair(I a, const char *b) {
  char q[40];
  snprintf(q, sizeof(q), "%lld", a);
  return pairkey(q, b);
}
int cmpkey(const void *a, const void *b) {
  return strcmp((*(Group *const *)a)->key, (*(Group *const *)b)->key);
}
Group **ordered(Map *m, int (*cmp)(const void *, const void *)) {
  Group **a = malloc((m->count + 1) * sizeof(Group *));
  for (int i = 0; i < m->count; i++)
    a[i] = &m->a[i];
  qsort(a, m->count, sizeof(Group *), cmp ? cmp : cmpkey);
  return a;
}
int fields[8], modes[8], dirs[8], sortcount;
void sorting(int count, int *a, int *b, int *c) {
  sortcount = count;
  for (int i = 0; i < count; i++) {
    fields[i] = a[i];
    modes[i] = b[i];
    dirs[i] = c[i];
  }
}
int rowcmp(const void *a, const void *b) {
  int ia = *(const int *)a, ib = *(const int *)b;
  for (int j = 0; j < sortcount; j++) {
    int f = fields[j], v;
    if (modes[j]) {
      F x = fv(r[ia][f]), y = fv(r[ib][f]);
      v = (x > y) - (x < y);
    } else
      v = strcmp(r[ia][f], r[ib][f]);
    if (v)
      return dirs[j] * v;
  }
  return (ia > ib) - (ia < ib);
}
int *orderrows(void) {
  int *a = malloc((n + 1) * sizeof(int));
  for (int i = 0; i < n; i++)
    a[i] = i;
  qsort(a, n, sizeof(int), rowcmp);
  return a;
}
int cmpnum(const void *a, const void *b) {
  I x = (*(Group *const *)a)->v[0], y = (*(Group *const *)b)->v[0];
  return (x > y) - (x < y);
}
int cmpdaykey(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
  return c ? c : strcmp(x->s[0], y->s[0]);
}
int cmpregionmonth(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmpint(const void *a, const void *b) {
  I x = *(const I *)a, y = *(const I *)b;
  return (x > y) - (x < y);
}
int cmpdistance(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->f[0] > y->f[0]) - (x->f[0] < y->f[0]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmprisk(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (y->v[0] > x->v[0]) - (y->v[0] < x->v[0]);
  if (c)
    return c;
  c = (y->v[1] > x->v[1]) - (y->v[1] < x->v[1]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[2] > y->v[2]) - (x->v[2] < y->v[2]);
}
int digitstr(const char *s) {
  for (; *s; s++)
    if (*s < '0' || *s > '9')
      return 0;
  return 1;
}
I fixed6(const char *s) {
  int neg = *s == '-';
  if (*s == '-' || *s == '+')
    s++;
  I a = 0, b = 0;
  while (*s && *s != '.')
    a = a * 10 + (*s++ - '0');
  if (*s == '.')
    s++;
  int i = 0;
  while (*s && i < 6) {
    b = b * 10 + (*s++ - '0');
    i++;
  }
  while (i++ < 6)
    b *= 10;
  return (neg ? -1 : 1) * (a * 1000000 + b);
}
void load(void) {
  int cap = 32;
  L = malloc(cap * sizeof(char **));
  lc = malloc(cap * sizeof(int));
  lines = 0;
  while (1) {
    int z = 128, len = 0, c;
    char *s = malloc(z);
    while ((c = getchar()) != EOF && c != '\n') {
      if (len + 1 >= z)
        s = realloc(s, z *= 2);
      s[len++] = (char)c;
    }
    if (c == EOF && !len) {
      free(s);
      break;
    }
    s[len] = 0;
    int k = 16, q = 0;
    char **t = malloc(k * sizeof(char *));
    char *p = s;
    while (*p) {
      while (*p && isspace((unsigned char)*p))
        *p++ = 0;
      if (!*p)
        break;
      if (q == k)
        t = realloc(t, (k *= 2) * sizeof(char *));
      t[q++] = p;
      while (*p && !isspace((unsigned char)*p))
        p++;
    }
    if (q) {
      if (lines == cap) {
        cap *= 2;
        L = realloc(L, cap * sizeof(char **));
        lc = realloc(lc, cap * sizeof(int));
      }
      L[lines] = t;
      lc[lines++] = q;
    } else {
      free(t);
      free(s);
    }
    if (c == EOF)
      break;
  }
  h = L[0];
  n = (int)iv(h[0]);
  r = L + 1;
  mapinit(&groups);
}

int main(void) {
  load();

  int k = n, p = 1;
  Map customers, stats, seen;
  mapinit(&customers);
  mapinit(&stats);
  mapinit(&seen);
  for (int i = 0; i < k; i++)
    get(&stats, L[p++][0]);
  int m = (int)iv(L[p++][0]);
  for (int i = 0; i < m; i++, p++)
    get(&customers, L[p][0])->s[0] = L[p][1];
  n = (int)iv(L[p++][0]);
  r = L + p;
  for (int i = 0; i < n; i++) {
    char **x = r[i];
    int pos = lookup(&groups, x[0]);
    Group *g = get(&groups, x[0]);
    if (pos < 0 || iv(x[2]) >= g->v[0]) {
      g->v[0] = iv(x[2]);
      g->v[1] = iv(x[4]);
      g->s[0] = x[1];
      g->s[1] = x[3];
    }
  }
  for (int i = 0; i < groups.count; i++) {
    Group *g = &groups.a[i];
    int ci = lookup(&customers, g->s[0]);
    if (!eq(g->s[1], "PAID") || ci < 0)
      continue;
    char *ch = customers.a[ci].s[0];
    Group *s = get(&stats, ch);
    s->v[0]++;
    s->v[2] += g->v[1];
    char *key = pairkey(ch, g->s[0]);
    if (lookup(&seen, key) < 0) {
      get(&seen, key);
      s->v[1]++;
    }
    free(key);
  }
  Group **a = ordered(&stats, NULL);
  for (int i = 0; i < stats.count; i++)
    printf("%s %lld %lld %lld\n", a[i]->key, a[i]->v[0], a[i]->v[1], a[i]->v[2]);

  return 0;
}

C++完整参考实现

文件：reference.cpp，与本题同文件夹。

沿用C版的显式数组及结构体便于对照，按C++17编译；内存转换和字符串常量已适配C++类型要求，排序参数使用initializer_list。

运行方法：g++ -std=c++17 -O2 reference.cpp -o reference，然后运行reference。测试数据通过标准输入送入，运行说明中的重定向不写入程序。


/* Native C++17 reference. C-style data structures retained for comparison. */
#include <ctype.h>
#include <initializer_list>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long I;
typedef double F;
typedef struct {
  char *key;
  I v[8];
  F f[8];
  char *s[4];
  int flag;
} Group;
typedef struct {
  Group *a;
  int count, cap;
  int *slots;
  int size;
} Map;
char ***L;
int *lc, lines, n;
char **h, ***r;
Map groups;
I iv(const char *s) { return strtoll(s, NULL, 10); }
F fv(const char *s) { return strtod(s, NULL); }
int eq(const char *a, const char *b) { return strcmp(a, b) == 0; }
F divide(F a, F b) { return b ? a / b : 0; }
char *dupstr(const char *s) {
  char *p = (char *)malloc(strlen(s) + 1);
  strcpy(p, s);
  return p;
}
uint64_t hash(const char *s) {
  uint64_t v = 1469598103934665603ULL;
  for (; *s; s++)
    v = (v ^ (unsigned char)*s) * 1099511628211ULL;
  return v;
}
void mapinit(Map *m) {
  m->size = 131071;
  m->slots = (int *)malloc(m->size * sizeof(int));
  for (int i = 0; i < m->size; i++)
    m->slots[i] = -1;
  m->count = 0;
  m->cap = 16;
  m->a = (Group *)calloc(m->cap, sizeof(Group));
}
int lookup(Map *m, const char *k) {
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0) {
    int i = m->slots[p];
    if (eq(m->a[i].key, k))
      return i;
    p = (p + 1) % m->size;
  }
  return -1;
}
int ensure(Map *m, const char *k) {
  int i = lookup(m, k);
  if (i >= 0)
    return i;
  if (m->count == m->cap) {
    m->cap *= 2;
    m->a = (Group *)realloc(m->a, m->cap * sizeof(Group));
  }
  i = m->count++;
  memset(&m->a[i], 0, sizeof(Group));
  m->a[i].key = dupstr(k);
  int p = hash(k) % m->size;
  while (m->slots[p] >= 0)
    p = (p + 1) % m->size;
  m->slots[p] = i;
  return i;
}
Group *get(Map *m, const char *k) {
  int i = ensure(m, k);
  return &m->a[i];
}
char *pairkey(const char *a, const char *b) {
  size_t z = strlen(a) + strlen(b) + 2;
  char *p = (char *)malloc(z);
  snprintf(p, z, "%s\037%s", a, b);
  return p;
}
char *numpair(I a, const char *b) {
  char q[40];
  snprintf(q, sizeof(q), "%lld", a);
  return pairkey(q, b);
}
int cmpkey(const void *a, const void *b) {
  return strcmp((*(Group *const *)a)->key, (*(Group *const *)b)->key);
}
Group **ordered(Map *m, int (*cmp)(const void *, const void *)) {
  Group **a = (Group **)malloc((m->count + 1) * sizeof(Group *));
  for (int i = 0; i < m->count; i++)
    a[i] = &m->a[i];
  qsort(a, m->count, sizeof(Group *), cmp ? cmp : cmpkey);
  return a;
}
int fields[8], modes[8], dirs[8], sortcount;
void sorting(int count, std::initializer_list<int> a, std::initializer_list<int> b,
             std::initializer_list<int> c) {
  sortcount = count;
  auto x = a.begin(), y = b.begin(), z = c.begin();
  for (int i = 0; i < count; i++) {
    fields[i] = *x++;
    modes[i] = *y++;
    dirs[i] = *z++;
  }
}
int rowcmp(const void *a, const void *b) {
  int ia = *(const int *)a, ib = *(const int *)b;
  for (int j = 0; j < sortcount; j++) {
    int f = fields[j], v;
    if (modes[j]) {
      F x = fv(r[ia][f]), y = fv(r[ib][f]);
      v = (x > y) - (x < y);
    } else
      v = strcmp(r[ia][f], r[ib][f]);
    if (v)
      return dirs[j] * v;
  }
  return (ia > ib) - (ia < ib);
}
int *orderrows(void) {
  int *a = (int *)malloc((n + 1) * sizeof(int));
  for (int i = 0; i < n; i++)
    a[i] = i;
  qsort(a, n, sizeof(int), rowcmp);
  return a;
}
int cmpnum(const void *a, const void *b) {
  I x = (*(Group *const *)a)->v[0], y = (*(Group *const *)b)->v[0];
  return (x > y) - (x < y);
}
int cmpdaykey(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
  return c ? c : strcmp(x->s[0], y->s[0]);
}
int cmpregionmonth(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmpint(const void *a, const void *b) {
  I x = *(const I *)a, y = *(const I *)b;
  return (x > y) - (x < y);
}
int cmpdistance(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (x->f[0] > y->f[0]) - (x->f[0] < y->f[0]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[0] > y->v[0]) - (x->v[0] < y->v[0]);
}
int cmprisk(const void *a, const void *b) {
  Group *x = *(Group *const *)a, *y = *(Group *const *)b;
  int c = (y->v[0] > x->v[0]) - (y->v[0] < x->v[0]);
  if (c)
    return c;
  c = (y->v[1] > x->v[1]) - (y->v[1] < x->v[1]);
  if (c)
    return c;
  c = strcmp(x->s[0], y->s[0]);
  return c ? c : (x->v[2] > y->v[2]) - (x->v[2] < y->v[2]);
}
int digitstr(const char *s) {
  for (; *s; s++)
    if (*s < '0' || *s > '9')
      return 0;
  return 1;
}
I fixed6(const char *s) {
  int neg = *s == '-';
  if (*s == '-' || *s == '+')
    s++;
  I a = 0, b = 0;
  while (*s && *s != '.')
    a = a * 10 + (*s++ - '0');
  if (*s == '.')
    s++;
  int i = 0;
  while (*s && i < 6) {
    b = b * 10 + (*s++ - '0');
    i++;
  }
  while (i++ < 6)
    b *= 10;
  return (neg ? -1 : 1) * (a * 1000000 + b);
}
void load(void) {
  int cap = 32;
  L = (char ***)malloc(cap * sizeof(char **));
  lc = (int *)malloc(cap * sizeof(int));
  lines = 0;
  while (1) {
    int z = 128, len = 0, c;
    char *s = (char *)malloc(z);
    while ((c = getchar()) != EOF && c != '\n') {
      if (len + 1 >= z)
        s = (char *)realloc(s, z *= 2);
      s[len++] = (char)c;
    }
    if (c == EOF && !len) {
      free(s);
      break;
    }
    s[len] = 0;
    int k = 16, q = 0;
    char **t = (char **)malloc(k * sizeof(char *));
    char *p = s;
    while (*p) {
      while (*p && isspace((unsigned char)*p))
        *p++ = 0;
      if (!*p)
        break;
      if (q == k)
        t = (char **)realloc(t, (k *= 2) * sizeof(char *));
      t[q++] = p;
      while (*p && !isspace((unsigned char)*p))
        p++;
    }
    if (q) {
      if (lines == cap) {
        cap *= 2;
        L = (char ***)realloc(L, cap * sizeof(char **));
        lc = (int *)realloc(lc, cap * sizeof(int));
      }
      L[lines] = t;
      lc[lines++] = q;
    } else {
      free(t);
      free(s);
    }
    if (c == EOF)
      break;
  }
  h = L[0];
  n = (int)iv(h[0]);
  r = L + 1;
  mapinit(&groups);
}

int main(void) {
  load();

  int k = n, p = 1;
  Map customers, stats, seen;
  mapinit(&customers);
  mapinit(&stats);
  mapinit(&seen);
  for (int i = 0; i < k; i++)
    get(&stats, L[p++][0]);
  int m = (int)iv(L[p++][0]);
  for (int i = 0; i < m; i++, p++)
    get(&customers, L[p][0])->s[0] = L[p][1];
  n = (int)iv(L[p++][0]);
  r = L + p;
  for (int i = 0; i < n; i++) {
    char **x = r[i];
    int pos = lookup(&groups, x[0]);
    Group *g = get(&groups, x[0]);
    if (pos < 0 || iv(x[2]) >= g->v[0]) {
      g->v[0] = iv(x[2]);
      g->v[1] = iv(x[4]);
      g->s[0] = x[1];
      g->s[1] = x[3];
    }
  }
  for (int i = 0; i < groups.count; i++) {
    Group *g = &groups.a[i];
    int ci = lookup(&customers, g->s[0]);
    if (!eq(g->s[1], "PAID") || ci < 0)
      continue;
    char *ch = customers.a[ci].s[0];
    Group *s = get(&stats, ch);
    s->v[0]++;
    s->v[2] += g->v[1];
    char *key = pairkey(ch, g->s[0]);
    if (lookup(&seen, key) < 0) {
      get(&seen, key);
      s->v[1]++;
    }
    free(key);
  }
  Group **a = ordered(&stats, NULL);
  for (int i = 0; i < stats.count; i++)
    printf("%s %lld %lld %lld\n", a[i]->key, a[i]->v[0], a[i]->v[1], a[i]->v[2]);

  return 0;
}

Java完整参考实现

文件：Main.java，与本题同文件夹。

Main为入口，solve为本题业务计算；long保存整数和金额，double计算普通比率，TreeMap按字符串键有序输出。精确乘积用BigInteger，不能改用int累计金额。

运行方法：javac -encoding UTF-8 Main.java，然后java Main。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
  static List<String[]> L = new ArrayList<>(), r;
  static String[] h;
  static int n;
  static StringBuilder output = new StringBuilder();
  static class G {
    long[] v = new long[8];
    double[] f = new double[8];
    String[] s = new String[4];
  }
  static TreeMap<String, G> groups = new TreeMap<>();
  static G g(Map<String, G> m, String key) {
    return m.computeIfAbsent(key, k -> new G());
  }
  static long I(String s) {
    return Long.parseLong(s);
  }
  static double N(String s) {
    return Double.parseDouble(s);
  }
  static String f(double x) {
    return String.format(Locale.ROOT, "%.6f", x);
  }
  static double div(double a, double b) {
    return b == 0 ? 0 : a / b;
  }
  static void out(Object... values) {
    for (int j = 0; j < values.length; j++) {
      if (j > 0)
        output.append(' ');
      output.append(values[j]);
    }
    output.append('\n');
  }
  static List<String[]> rows(int start, int count) {
    return new ArrayList<>(L.subList(start, start + count));
  }
  static String key(String a, String b) {
    return a + "\u001f" + b;
  }
  static BigInteger fixed(String s) {
    return new BigDecimal(s).movePointRight(6).toBigIntegerExact();
  }
  static void sortRows(List<String[]> rows, int[] fields, boolean[] numeric, int[] dirs) {
    rows.sort((a, b) -> {
      for (int j = 0; j < fields.length; j++) {
        int p = fields[j];
        int c = numeric[j] ? Double.compare(N(a[p]), N(b[p])) : a[p].compareTo(b[p]);
        if (c != 0)
          return c * dirs[j];
      }
      return 0;
    });
  }
  static void solve() throws Exception {
    int k = n, pos = 1;
    TreeMap<String, G> stats = new TreeMap<>();
    for (int i = 0; i < k; i++) g(stats, L.get(pos++)[0]);
    int m = (int) I(L.get(pos++)[0]);
    Map<String, String> customers = new HashMap<>();
    for (int i = 0; i < m; i++) {
      String[] x = L.get(pos++);
      customers.put(x[0], x[1]);
    }
    n = (int) I(L.get(pos++)[0]);
    r = rows(pos, n);
    for (String[] x : r) {
      G p = groups.get(x[0]);
      long version = I(x[2]);
      if (p == null || version >= p.v[0]) {
        p = g(groups, x[0]);
        p.v[0] = version;
        p.v[1] = I(x[4]);
        p.s[0] = x[1];
        p.s[1] = x[3];
      }
    }
    Set<String> seen = new HashSet<>();
    for (G p : groups.values()) {
      if (!p.s[1].equals("PAID") || !customers.containsKey(p.s[0]))
        continue;
      String ch = customers.get(p.s[0]);
      G s = g(stats, ch);
      s.v[0]++;
      s.v[2] += p.v[1];
      if (seen.add(key(ch, p.s[0])))
        s.v[1]++;
    }
    for (Map.Entry<String, G> e : stats.entrySet()) {
      G p = e.getValue();
      out(e.getKey(), p.v[0], p.v[1], p.v[2]);
    }
  }
  public static void main(String[] args) throws Exception {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String line;
    while ((line = reader.readLine()) != null)
      if (!line.trim().isEmpty())
        L.add(line.trim().split("\\s+"));
    h = L.get(0);
    n = h[0].matches("[0-9]+") ? Integer.parseInt(h[0]) : 0;
    r = rows(1, Math.min(n, L.size() - 1));
    solve();
    System.out.print(output);
  }
}

Kotlin完整参考实现

文件：Main.kt，与本题同文件夹。

main读取输入，solve执行本题步骤。val表示不可重新赋值，var表示可变状态；LongArray保存整数，DoubleArray保存比率，TreeMap固定输出顺序。!!仅用于题面保证已存在的数据。

运行方法：kotlinc Main.kt -jvm-target 17 -include-runtime -d main.jar，然后java -jar main.jar。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

import java.math.BigDecimal
import java.math.BigInteger
import java.util.Locale
import java.util.TreeMap

data class G(
  val v: LongArray = LongArray(8),
  val f: DoubleArray = DoubleArray(8),
  val s: Array<String?> = arrayOfNulls(4),
)

lateinit var L: List<Array<String>>
lateinit var h: Array<String>
lateinit var r: MutableList<Array<String>>
var n = 0
val output = StringBuilder()
val groups = TreeMap<String, G>()

fun g(m: MutableMap<String, G>, key: String): G = m.getOrPut(key) { G() }

fun I(s: String): Long = s.toLong()

fun N(s: String): Double = s.toDouble()

fun f(x: Number): String = String.format(Locale.ROOT, "%.6f", x.toDouble())

fun div(a: Number, b: Number): Double =
  if (b.toDouble() == 0.0) 0.0 else a.toDouble() / b.toDouble()

fun out(vararg values: Any?) {
  output.append(values.joinToString(" ")).append('\n')
}

fun rows(start: Int, count: Int): MutableList<Array<String>> =
  L.subList(start, start + count).toMutableList()

fun key(a: String, b: String): String = a + "\u001f" + b

fun fixed(s: String): BigInteger = BigDecimal(s).movePointRight(6).toBigIntegerExact()

fun sortRows(
  rows: MutableList<Array<String>>,
  fields: IntArray,
  numeric: BooleanArray,
  dirs: IntArray,
) {
  rows.sortWith(
    Comparator { a, b ->
      var result = 0
      for (j in fields.indices) {
        val p = fields[j]
        val c = if (numeric[j]) N(a[p]).compareTo(N(b[p])) else a[p].compareTo(b[p])
        if (c != 0) {
          result = c * dirs[j]
          break
        }
      }
      result
    }
  )
}

fun solve() {

  val k = n
  var pos = 1
  val stats = TreeMap<String, G>()
  repeat(k) { g(stats, L[pos++][0]) }
  val m = I(L[pos++][0]).toInt()
  val customers = HashMap<String, String>()
  repeat(m) {
    val x = L[pos++]
    customers[x[0]] = x[1]
  }
  n = I(L[pos++][0]).toInt()
  r = rows(pos, n)
  for (x in r) {
    val old = groups[x[0]]
    val version = I(x[2])
    if (old == null || version >= old.v[0]) {
      val p = g(groups, x[0])
      p.v[0] = version
      p.v[1] = I(x[4])
      p.s[0] = x[1]
      p.s[1] = x[3]
    }
  }
  val seen = HashSet<String>()
  for (p in groups.values) {
    if (p.s[1] != "PAID" || !customers.containsKey(p.s[0])) continue
    val ch = customers[p.s[0]]!!
    val s = g(stats, ch)
    s.v[0]++
    s.v[2] += p.v[1]
    if (seen.add(key(ch, p.s[0]!!))) s.v[1]++
  }
  for ((a, p) in stats) out(a, p.v[0], p.v[1], p.v[2])
}

fun main() {
  L =
    System.`in`
      .bufferedReader()
      .lineSequence()
      .filter { it.isNotBlank() }
      .map { it.trim().split(Regex("\\s+")).toTypedArray() }
      .toList()
  h = L[0]
  n = h[0].toIntOrNull() ?: 0
  r = rows(1, minOf(n, L.size - 1))
  solve()
  print(output)
}

JavaScript/Node.js完整参考实现

文件：reference.js，与本题同文件夹。

在Node.js运行，Map和Set保存状态；Number计算普通数值，超过安全整数范围的金额累计及精确乘积使用BigInt。

运行方法：node reference.js。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

// Node.js reference. All task code runs natively in JavaScript.
const fs = require('fs');
const lines = fs.readFileSync(0, 'utf8').trim().split(/\r?\n/).filter(x => x.trim()).map(x => x
  .trim().split(/\s+/));
const h = lines[0];
let n = Number(h[0]),
  r = lines.slice(1, 1 + n);
const N = Number,
  cmp = (a, b) => a < b ? -1 : a > b ? 1 : 0;
const f = x => Number(x).toFixed(6),
  div = (a, b) => b ? a / b : 0;
const out = [];
const emit = (...a) => out.push(a.join(' '));
const grouped = new Map();
const get = (k, init = () => [0, 0]) => {
  if (!grouped.has(k)) grouped.set(k, init());
  return grouped.get(k);
};
const keys = m => [...m.keys()].sort(cmp);
const pair = (a, b) => JSON.stringify([a, b]);

function fixed6(s) {
  let neg = s[0] === '-';
  s = s.replace(/^[+-]/, '');
  let [a, b = ''] = s.split('.');
  return (neg ? -1n : 1n) * (BigInt(a) * 1000000n + BigInt((b + '000000').slice(0, 6)));
}

let p = 1;
const channels = lines.slice(p, p + n).map(x => x[0]);
p += n;
const m = N(lines[p++][0]),
  customers = new Map();
for (let i = 0; i < m; i++) {
  const [c, ch] = lines[p++];
  customers.set(c, ch);
}
n = N(lines[p++][0]);
r = lines.slice(p, p + n);
for (const [oid, cid, vs, st, amt] of r) {
  const v = N(vs);
  if (!grouped.has(oid) || v >= grouped.get(oid)[1]) grouped.set(oid, [cid, v, st, BigInt(amt)]);
}
const stats = new Map(channels.map(c => [c, [0, new Set(), 0n]]));
for (const [cid, v, st, amt] of grouped.values()) {
  if (st !== 'PAID' || !customers.has(cid)) continue;
  const s = stats.get(customers.get(cid));
  s[0]++;
  s[1].add(cid);
  s[2] += amt;
}
for (const ch of keys(stats)) {
  const [c, u, a] = stats.get(ch);
  emit(ch, c, u.size, a);
}
process.stdout.write(out.join("\n") + (out.length ? "\n" : ""));

Bash（GNU awk）完整参考实现

文件：reference.sh，与本题同文件夹。

Bash负责启动和环境检查，GNU awk在同一脚本中解析数据并完成本题算法。C[行,列]从1计数，num按十进制转换，i输出整数，f输出六位小数；-M启用GMP/MPFR，PREC=256。不是普通awk兼容脚本，必须满足运行依赖。

运行方法：bash reference.sh（需支持-M的GNU awk）。测试数据通过标准输入送入，运行说明中的重定向不写入程序。

#!/usr/bin/env bash
# Requires GNU awk with GMP/MPFR (-M). No Python, Java or Node.js subprocess.
set -euo pipefail
export LC_ALL=C
if ! command -v gawk >/dev/null 2>&1; then
  printf "%s\n" "GNU awk (gawk) with -M support is required" >&2
  exit 1
fi
exec gawk -M -v PREC=256 '
BEGIN { OFS=" "; OFMT="%.0f"; CONVFMT="%.30g" }
NF>0 { lines++; nf[lines]=NF; for(j=1;j<=NF;j++) C[lines,j]=$j }
function num(s) { return s+0 }
function eq(a,b) { return (a "")== (b "") }
function cmpstr(a,b) { a=a "";b=b "";return a<b?-1:a>b?1:0 }
function f(x) { return sprintf("%.6f",x) }
function i(x) { return sprintf("%.0f",x) }
function div(a,b) { a+=0;b+=0;return b!=0?a/b:0 }
function abs(x) { return x<0?-x:x }
function min(a,b) { return a<b?a:b }
function max(a,b) { return a>b?a:b }
function floor(x, t) { t=int(x);return t>x?t-1:t }
function fixed(s, a,negative,b) {
  negative=substr(s,1,1)=="-";sub(/^[+-]/,"",s);split(s,a,/[.]/)
  b=substr(a[2] "000000",1,6)
  return (negative?-1:1)*(num(a[1])*1000000+num(b))
}
function pair(a,b) { return (a "") SUBSEP (b "") }
function group(k) { groups[k]=1 }
function sorted_groups() { return asorti(groups,idx,"@ind_str_asc") }
function compare_rows(a,av,b,bv, j,p,x,y,c) {
  for(j=1;j<=sort_count;j++) {
    p=fields[j];x=C[base+a-1,p];y=C[base+b-1,p]
    if(modes[j]){x=num(x);y=num(y);c=x<y?-1:x>y?1:0}else c=cmpstr(x,y)
    if(c)return dirs[j]*c
  }
  return (a+0)<(b+0)?-1:(a+0)>(b+0)?1:0
}
function order_rows(fs,ms,ds, j) {
  sort_count=split(fs,fields," ");split(ms,modes," ");split(ds,dirs," ")
  delete order;for(j=1;j<=n;j++)order[j]=j
  return asorti(order,idx,"compare_rows")
}
function compare_neighbors(a,av,b,bv, c) {
  c=dist[a]<dist[b]?-1:dist[a]>dist[b]?1:0;if(c)return c
  c=cmpstr(C[base+a-1,1],C[base+b-1,1]);return c?c:(a+0)-(b+0)
}
function compare_day_key(a,av,b,bv, c) {
  c=values[a,1]<values[b,1]?-1:values[a,1]>values[b,1]?1:0
  return c?c:cmpstr(strings[a,1],strings[b,1])
}
function compare_region_month(a,av,b,bv, c) {
  c=cmpstr(strings[a,1],strings[b,1]);return c?c:values[a,1]-values[b,1]
}
function compare_risk(a,av,b,bv, c) {
  c=values[b,1]-values[a,1];if(c)return c
  c=values[b,2]-values[a,2];if(c)return c
  c=cmpstr(strings[a,1],strings[b,1]);return c?c:(a+0)-(b+0)
}
END {
  for(j=1;j<=nf[1];j++)h[j]=C[1,j]
  n=num(h[1]);base=2

  k=n;pos=2;for(j=1;j<=k;j++)channels[C[pos++,1]]=1;m=num(C[pos++,1]);for(j=1;j<=m;j++){customers[C[pos,1]]=C[pos,2];pos++};n=num(C[pos++,1]);base=pos
  for(row=base;row<base+n;row++){oid=C[row,1];version=num(C[row,3]);if(!(oid in groups)||version>=values[oid,1]){group(oid);values[oid,1]=version;values[oid,2]=num(C[row,5]);strings[oid,1]=C[row,2];strings[oid,2]=C[row,4]}}
  for(oid in groups){cid=strings[oid,1];if(strings[oid,2]!="PAID"||!(cid in customers))continue;ch=customers[cid];stats[ch,1]++;stats[ch,3]+=values[oid,2];key=pair(ch,cid);if(!(key in seen)){seen[key]=1;stats[ch,2]++}}
  count=asorti(channels,idx,"@ind_str_asc");for(j=1;j<=count;j++){ch=idx[j];print ch,i(stats[ch,1]+0),i(stats[ch,2]+0),i(stats[ch,3]+0)}

}
'

测试与评分解释

公开样例用于理解与自测；隐藏测试分项计分，每题25分。现有4组主要覆盖空输入、单记录、重复及次序变化；它们不代表所有专业边界已充分覆盖。命题人还应独立设计能区分错误实现的测试，例如错误分母、错误等号、先过滤后去重、全部排序键反转及精度阈值。参考实现通过已有测试并不能证明题库已经达到正式比赛部署标准。

本题另提供独立计算期望的补充案例：金额合计超过JavaScript安全整数。输入输出见同目录boundary_*.in/.out，已按本版所列环境核对；这些案例尚未加入原25分配置，部署时需统一调整测试点分值，不能直接叠加分数。

ID

643

Time

2000ms

Memory

256MiB

Difficulty

Tags

# Submissions

Accepted

Uploaded By

admin

1 solutions