1 条题解

  • 0
    @ 2023-10-17 15:24:38

    阿斯特莱亚的救赎

    u1s1,这题没见过确实不太好想 (所以数据造的很水,直接深搜都能获得很高的分数)

    题目的意思就是给定 n n 个正整数,求从其中选出任意个数,使得这些数的和为 n n 的倍数。

    如果没看懂的话就再解释一下。根据上述证明,若存在 si s_i n n 的倍数,则选择前 i i 个数即可;否则,对于除以 n n 余数相同的 si s_i sj s_j ,选择区间 [i+1,j] [i + 1, j] 即可。

    • @ 2023-10-19 1:09:25
      #include <cstdio>
      #include <iostream>
      const int N = 1e6 + 5;
      
      int A[N], r[N];
      
      void print(int st, int ed) {
          printf("%d\n", ed - st + 1);
          for (int i = st; i <= ed; ++i) {
              printf("%d%c", A[i], i == ed ? '\n': ' ');
          }
      }
      
      int main() {
          int n; scanf("%d", &n);
          int rr = 0;
          for (int i = 1; i <= n; ++i) {
              scanf("%d", &A[i]);
              rr = (rr + A[i]) % n;
              if (rr == 0) {
                  print(1, i);
                  break;
              } else if (r[rr]) {
                  print(r[rr] + 1, i);
                  break;
              } else r[rr] = i;
              if (i == n) puts("No"); // impossible
          }
          return 0;
      }
      
  • 1

信息

ID
198
时间
1000ms
内存
256MiB
难度
8
标签
(无)
递交数
268
已通过
38
上传者