har

5227

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;

}
};


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;

}
};


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;
}

}


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()<<" ";
}
}


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];

}


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) <<" ";
}
}


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;

}
};


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;
}
};


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;

}
};