枚举

[Ir1d]

https://oi-wiki.cf/basic/enumerate/

[FTYC919]

前排

[wyy-tmy]

前排

[Tatara-Kogasa]

伪前排

[ChungZH]

前排兜售小面包

[Xecades]

好啊

[CHN-STUDENT]

请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

[xiaojian98]

其实就是现实中，你拿了个桶存放已遍历过得数据，每次拿到新数据，查看桶里的数据是否有该数据的相反数，若有，则次数增加；

[owenzjg]

可以理解为桶数组就是标记数组，标记值为桶的下标的数的个数

[QA666]

@CHN-STUDENT
请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

自己用草稿纸演算，a相当一个桶数组

[SupritYoung]

好东西

[cenchen]

思想是贪心的思想叭

[lavender-ER]

解法一和解法二并不完全相同比如数组中有零这个元素是有出入，更正应该很简单，不说了

[TTKatrina]

@CHN-STUDENT
请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

bool数组，0代表false, 1代表true
举例MAXN=10, 则数组范围[0，20)，举例a[i]=3，则循环到a[i]时，会把met[13]赋值为true, 下次再循环到某一处若遇到新的a[i]=-3, 则if条件满足，met[10-(-3)],故ans可以++.

确实在纸上画画就好懂些

[fantasy-mark]

感谢，把 met[MAXN] 想象为一面镜子，met[i]的值的绝对值相当于距离（一正一负），已经遍历的留下影子，当某次遍历能找到影子则说明相加为0

[ghost]

(:

[asukaminato0721]

最后那个优化，用 C++11 的 set 写，是这种风格（更容易懂，但是复杂度从 O(1) 变成了 O(log(n))）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> a = {1, 2, 3, 4, -1, -2, -4, 3}; // a 也可以写成数组
    set<int> sol;
    int ans = 0;
    for (auto &&i : a)
    {
        if (sol.count(i)) // 1
        {
            ans++;
        }
        sol.insert(-i);  // 2
    }
    cout << ans;
}

1 和 2 处的 i/-i 可以互换，题目用了 MAXN 来偏移，避免负数下标。建议把 MAXN 统一要么前面要么后面。

[MuVirus]

是不是没有考虑(i,-i)和(-i, i)？最后得乘一个2。

[MuVirus]

你这思路对我很有帮助，哈哈。

[yadonz]

@CHN-STUDENT
请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

哈希数组，使用数组索引表示数字，索引位置的值表示是否遍历过该值。在这里只要确定与当前遍历位置的值的相反数存在不存在就可以统计一次了。
哈希数组每个访问的时间位O(1)

[Marcythm]

@bored17 您看了吗？

[bored17]

@Marcythm
@bored17 您看了吗？
哥 对不起

[chenghui007]

@CHN-STUDENT
请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

哈希法

[Csrayz]

@CHN-STUDENT
请教各位大佬我没看懂最后的优化，有愿意帮忙解释的吗？谢谢！

总感觉那个越界了，met少了一位。而且那个MAXN也没有注释取的是绝对值后的最大值。

[Lane0218]

我也感觉 MAXN应该是指数组a每个元素取绝对值后的最大值 但是met长度应该是2*MAXN+1 因为除了0左右两侧的元素 还有元素0 所以要单独加1

[aizigao]

熄灯问题看这个视频 https://www.bilibili.com/video/BV1Hx411U7bh?p=4

[rhmangmang]

"一个数组中的数互不相同，求其中和0为的数对的个数。"
-- 题目表述有问题，没说是几个数的和，而从答案看，应该是two sum

[mmppto]

桶 ## 是个啥

[ClearVIper3]

哈希表

[gskystar]

数有正有负，开2倍空间才能将负数，正数都表示出来，数num在空间的位置为num+MAXN。判断num能不能配对，要看-num是否在空间里面。

[yangtzebrokenheaven]

请问++a和a++为何偏向前者

[Nanarikom]

虽然不知道为什么在这里问，不过我的理解是，从泛型的角度来看，iterator 的前增可能会比后增快。

[Lane0218]

我也感觉 MAXN应该是指数组a每个元素取绝对值后的最大值 但是met长度应该是2*MAXN+1 因为除了0左右两侧的元素 还有元素0 所以要单独加1

[1511545190]

数组有0元素不能乘2吧

[Enter-tainer]

请你把自动回复关掉

[TheWash7]

maxn如果等于3，met长度为6，下标0到5。如果a[i]=3，那么met[a[i] + MAXN]=met[6]。根本不存在啊？

[Marcythm]

看了一下，这里确实应当有问题，桶记录的范围（值域）是 [-MAXN, MAXN]，一共应该开 MAXN*2+1 的大小
（如果有意愿的话不妨开个 pr？👀

[zhangjialin996]

熄灯问题java AC:

import java.util.*;

public class Main{
  public static int M = 5;
  public static int N = 6;
  public static void main(String[] args){
    // input
    Scanner in = new Scanner(System.in);
    int[][] initStatus = new int[M][];
    int[][] press = new int[M][];
    for(int i = 0; i < M; i++){
      initStatus[i] = new int[N];
      press[i] = new int[N];
      for(int j = 0; j < N; j++){
        initStatus[i][j] = in.nextInt();
      }
    }

    int t;
    press[0][0] = -1;
    for(int i = 0; i < (int) Math.pow(2, N); i++){
      press[0][0]++;
      // 2=>0 1
      t = 0;
      while(press[0][t] > 1){
        press[0][t] = 0;
        t++;
        press[0][t]++;
      }

      // for (int[] line : press) {
      //   for (int item : line) {
      //     System.out.printf("%d ", item);
      //   }
      //   System.out.println();
      // }
      // System.out.println(i);

      if(guess(press, initStatus)){
        for (int[] line : press) {
          for (int item : line) {
            System.out.printf("%d ", item);
          }
          System.out.println();
        }
        return ;
      }
      // cleanPress(press);
    }
  }

  // clear press array
  public static void cleanPress(int[][] press){
    for(int[] one: press){
      Arrays.fill(one, 0);
    }
  }

  public static boolean guess(int[][] press, int[][] initStatus){
    // left right top bottom left-top left-bottom right-top right-bottom
    for(int i = 1; i < M; i++){
      for(int j = 0; j < N; j++){
        // 5 value determine nowValue
        press[i][j] = ( press[i-1][j] + initStatus[i-1][j] + (i-2>=0?press[i-2][j]:0) + (j-1>=0?press[i-1][j-1]:0) + (j+1<N?press[i-1][j+1]:0) ) % 2;
      }
    }

    for(int i = 0; i < N; i++){
      int t = (initStatus[M-1][i] + press[M-1][i] + (i-1>=0 ? press[M-1][i-1] : 0)+ (i+1<N ? press[M-1][i+1] : 0) + press[M-2][i]) % 2;
      if(t != 0) {
        return false;
      }
    }

    return true;
  }
}

[KSroido]

萌新讲一下我对最后优化的简单理解
把问题转化为对-a和+a的匹配
利用桶排序(对index)排序
但是桶排序不能直接用负数, 所以从中点开始算下标
如果遇到+a 先直接放进桶里 加上true
如果遇到-a, 就加个ans