【墨鳌】【简单题,但是要细致一点,别忘了关灯的时候把自己也关了🤣】

题外话

无意间在评论区发现了原来是 125周赛题
所以晚上补充一下,他山之石,可以攻玉, @bigelephant29

解题思路

  • 每一个灯(坐标),有五个属性:
  1. 行 (横坐标 x )
  2. 列 (纵坐标 y )
  3. 撇 (直线 y=x+t \(\Longrightarrow\) 记录 x-y )
  4. 捺 (直线 x+y=t \(\Longrightarrow\) 记录 x+y )
  5. 表示坐标本身的二元组 (坐标 (x,y) )
  • 前四者之一为真,即亮灯
  • 然后用哈希表存一下,这五组特性,实时维护开关灯,就OK啦

代码

#define R row               //横坐标
#define C column            //纵坐标
#define P leftDown2RightUp  //y=x+t  => x-y
#define L rightDown2leftUp  //x+y=t  => x+y
#define O onLamps           //亮着的灯的集合
class Solution {    
public:
    const vector<vector<int>>ds{{0,0},{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_map<int,int>R,C,P,L;
        set<pair<int,int>>O;
        auto shift=[&](int&x,int&y,int o){R[x]+=o,C[y]+=o,P[x-y]+=o,L[x+y]+=o;};
        for(auto&p:lamps){
            auto&x=p[0],&y=p[1];
            auto lamp=make_pair(x,y);
            if(O.count(lamp)==0)O.insert(lamp),shift(x,y,1);
        }
        vector<int>ans;
        for(auto&p:queries){
            auto&x=p[0],&y=p[1];
            ans.push_back((R[x] || C[y] || P[x-y] || L[x+y]));
            for(auto&d:ds){
                auto nx=x+d[0],ny=y+d[1];
                auto lamp=make_pair(nx,ny);
                if(O.count(lamp)>0)O.erase(lamp),shift(nx,ny,-1);
            }
        }
        return ans;
    }
};
class Solution {
public:
    unordered_map<int, int> ver, hor;
    unordered_map<int, int> d1, d2;
    set<pair<int,int>> st;
    
    void add(pair<int,int> pr) {
        ver[pr.first]++;
        hor[pr.second]++;
        d1[pr.first+pr.second]++;
        d2[pr.first-pr.second]++;
        st.insert(pr);
    }
    
    void close(pair<int,int> pr) {
        ver[pr.first]--;
        hor[pr.second]--;
        d1[pr.first+pr.second]--;
        d2[pr.first-pr.second]--;
        st.erase(pr);
    }
    
    int query(pair<int,int> pr) {
        return ver[pr.first] > 0 || hor[pr.second] > 0 || d1[pr.first+pr.second] > 0 || d2[pr.first-pr.second] > 0;
    }
    
    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        for(auto e: lamps) {
            add(make_pair(e[0], e[1]));
        }
        vector<int> ans;
        for(auto e: queries) {
            int x = e[0], y = e[1];
            ans.push_back(query(make_pair(x,y)));
            for(int i = -1 ; i <= 1 ; i++) {
                for(int j = -1 ; j <= 1 ; j++) {
                    if(st.find(make_pair(x+i, y+j)) != st.end()) {
                        close(make_pair(x+i,y+j));
                    }
                }
            }
        }
        return ans;
    }
};

~~Jason_liu O(∩_∩)O

推荐这些文章:

【墨鳌】【经典问题】【约瑟夫环~记忆化搜索】

解题思路

经典约瑟夫环 plus 经典记忆化搜索技巧
\(f(n,m)=\begin{cases}0 & (n=0)\\ [f(n-1,m)+m]\%n&(n>0)\end{cases}\)

代码
class Solution {
public:
struct pair_hash {
inline size_t operator()(const pair<int,int>&p)const{
return (((unsigned)p.first<<17)+p.second);
...

【墨鳌】【面试题19. 正则表达式匹配】

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();

auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
...

1377. T 秒后青蛙的位置,unordered_map+bitset,学习复合类型关键字如何添加hash函数

题目链接:T 秒后青蛙的位置
bitset保存遍历状态
unordered_map保存dp值
unordered_map自定义键用法

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e2+5;
class Solution {
public:
struct hash_name{
size_t operator()(const pair<bitset<N>,int> & p) const{
r...

lc.347 统计前K个高频元素

题目:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
https://leetcode-cn.com/problems/top-k-frequent-elements/
解法一:优先队列+小根堆
//一种小根堆思路
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
unordered_map<int...

AcWing 487. 金明的预算方案

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

#define x first
#define y second

const int M = 32010;
const int N = 70;

int f[M];
PII master[N];
vector<PII> servant[N];

int main() {
int n, m;
cin ...

【墨鳌】【卡特兰数】

题目链接
题解链接
解题思路

卡特兰数

代码
// 1 2 5 14 卡特兰数从第二项开始
class Solution {
public:
unordered_map<int,int>C;
int Catalan(int n,int mod){
if(n<=1)return C[n]=1;
if(C[n])return C[n];
int ans=0;
for(int i=1;i<n;i++)
ans=(ans+1LL*Catalan(i,mod)*Catal...

简单算法模板

dijikistra模板
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define el "\n";
#define INF 0x3f3f3f3f
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
const int Max = 1e4 + 3;

int n = 2021;

int gcd(int a,int b)
{
return b == 0 ? a : gcd(b, a % b);
}

int get_m...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.size();
int m=mat[0].size();
vector<vector<int>> ans(n, vector<int>...

【墨鳌】【凸包算法:Andrew算法 & Graham算法】

解题思路

思路显而易见,计算几何求凸包
Orz大佬,这Python代码绝绝子 @z1m

补充

2022/4/23 补充Graham算法

Andrew算法
C++版本
class Solution {
public:
vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
auto cross=[](vector<int>&a,vector<int>&b,vector<int>&c)...

洛谷P1162 填涂颜色(BFS广度优先搜索)

题目地址:P1162 填涂颜色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路
这里拿Photoshop来举例。
这里是一只嘉然,如果我不要这个白色背景,只要本体可以怎么抠图呢?

对PS有了解的同学可以使用魔棒工具,即选取与点击地方颜色相近的部分。将白色点出来

右键,点击反选,就是将白色部分排除剩下的就是整只嘉然啦。

效果十分好又快

那么回到这题,我们只需选取不在框里面的0,其他的改成0就好了。
int markx[] = {0,1,-1,0};
int marky[] = {1,0,0,-1};
int n;
void bfs(int x,int y)
{...

文章标题:【墨鳌】【简单题,但是要细致一点,别忘了关灯的时候把自己也关了🤣】
文章链接:https://www.dianjilingqu.com/51503.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>