头像

har




离线:1天前



har
14天前
#define x first
#define y second
typedef pair<int,int> pii;

const int N = 10010;
int dis[N][2];

class Solution {
public:
    int minimumJumps(vector<int>& w, int a, int b, int x) {
        queue<pii> q;
        memset(dis,-1,sizeof dis);
        for(auto i:w) dis[i][0] = dis[i][1] = 1;
        dis[0][0] = 0;
        q.push({0,0});
        while(!q.empty())
        {
            auto t = q.front();
            q.pop();
            int d = dis[t.x][t.y];

            if(t.x == x) return d;
            if(t.x+a<N && dis[t.x+a][0]==-1)
             {
                dis[t.x+a][0] = d + 1;
                q.push({t.x + a,0}); 
            } 
            if (t.y == 0 && t.x - b >= 0 && dis[t.x - b][1] == -1) {
                dis[t.x - b][1] = d + 1;
                q.push({t.x - b, 1});
            }
        }
        return -1;

    }
};


活动打卡代码 LeetCode 5550. 拆炸弹

har
15天前
class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {

        int n = code.size();
        vector<int> res(n,0);

        for(int i=0;i<n;i++)
        {
            if(k==0) res[i]=0;
            else if(k>0)
            {
                for(int j=1;j<=k;j++)
                {
                    res[i]+=code[(i+j)%n];
                }
            }
            else if (k<0)
            {
                for(int j=-1;j>=k;j--)
                {
                    res[i]+=code[(i+j+n)%n];
                }
            }
        }
        return res;

    }
};


活动打卡代码 AcWing 796. 子矩阵的和

har
20天前
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        cout<<ans<<endl;
    }

}


活动打卡代码 AcWing 2768. 直播获奖

har
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n,w;
int main()
{
    cin>>n>>w;

    priority_queue<int> left;
    priority_queue<int,vector<int>,greater<int>> right;

    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;

        if(right.empty() || x>=right.top()) right.push(x);
        else left.push(x);

        int k = max(1,(i*w)/100);

        while(right.size() > k) left.push(right.top()),right.pop();
        while(right.size() < k) right.push(left.top()),left.pop();

        cout<<right.top()<<" ";
    }
}


活动打卡代码 AcWing 2770. 方格取数

har
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
typedef long long ll;
ll f[N][N][2];
int g[N][N];
int main()
{
    int n,m;
    cin>>n>>m;

    memset(f,-0x3f,sizeof f);
    f[1][0][0] = 0;
    f[1][0][1] = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];

    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
            f[i][j][0] = max(max(f[i-1][j][0],f[i][j-1][0]),f[i][j-1][1])+g[i][j];


        for(int i=n;i;i--)
            f[i][j][1] = max(max(f[i+1][j][1],f[i][j-1][0]),f[i][j-1][1])+g[i][j];

    }

    cout<<f[n][m][0];



}


活动打卡代码 AcWing 2767. 优秀的拆分

har
21天前
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;

    if(n%2)
    {
        cout<<-1;
        return 0;
    }
    for(int i=23;i>=1;i--)
    {
        if(n >> i & 1)
            cout<< (1 << i) <<" ";
    }
}


活动打卡代码 LeetCode 134. 加油站

har
3个月前
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();

        for(int i=0,j;i<n;i++)
        {
            int left=0;
            for(j=0;j<n;j++)
            {
                int k=(i+j)%n;
                left+=gas[k]-cost[k];
                if(left<0) break;
            }

            if(j==n) return i;
            i=i+j;
        }
        return -1;

    }
};


活动打卡代码 LeetCode 133. 克隆图

har
3个月前
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node* ,Node* > hash;

    Node* cloneGraph(Node* node) {
        if(!node) return NULL;
        dfs(node);

        for(auto [st,ed]:hash)
        {
            for(auto ver:st->neighbors)
            {
                ed->neighbors.push_back(hash[ver]);
            }
        }

        return hash[node];

    }
    void dfs(Node* node)
    {
        hash[node] = new Node(node->val);

        for(auto ver:node->neighbors)
            if(!hash.count(ver))
            {
                dfs(ver);
            }
    }
};



har
3个月前
class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        s=' '+s;
        vector<vector<bool>> g(n+1,vector<bool>(n+1));
        vector<int> f(n+1,1e8);

        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++)
                if(i == j) g[i][j]=1;
                else if(s[i] == s[j])
                    if(i+1>j-1 || g[i+1][j-1]) g[i][j] = 1;
      // cout<<g[n];
        f[0]=0;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                if(g[j][i]) f[i]=min(f[j-1]+1,f[i]);



        return f[n]-1;
    }
};


活动打卡代码 LeetCode 131. 分割回文串

har
3个月前
class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> f;
    void dfs(string& s,int u)
    {
        if(u == s.size()) 
        {
           res.push_back(path);
           return ;
        }

        for(int i=u;i<s.size();i++)
        {
            if(f[u][i])
            {
                path.push_back(s.substr(u,i-u+1));
                dfs(s,i+1);
                path.pop_back();
            }
        }

    }
    vector<vector<string>> partition(string s) {
        int n = s.size();
        //s = " " + s;
        f = vector<vector<bool>> (n+1,vector<bool>(n+1));
        for(int j=0;j<n;j++)
            for(int i=0;i<=j;i++)
                if(i == j) f[i][j]=1;
                else if(s[i] == s[j])
                {
                    if(i+1 > j-1 || f[i+1][j-1]) f[i][j] = 1;
                }

        dfs(s,0);

        return res;

    }
};