题目描述

blablabla

样例

blablabla

算法1

(贡献法) $O(n^2)$

blablabla

时间复杂度

线性的O(n)，因为每次判断都是O(1)

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+10;
typedef pair<int,int>PII;
int n,q;
int a[N][N],b[N][N],c[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    int res=0;
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]++;
        b[x][z]++;
        c[y][z]++;
        if(a[x][y]>=n)res++;
         if(b[x][z]>=n)res++;
          if(c[y][z]>=n)res++;
          cout<<res<<'\n';
    }
    return 0;
}

开三个数组将三维变成三个二维，长度表示另一个特征，若长度大于N说明可以放（因为保证了拿块的时候地方有所以>=n就+1次