VanHope

2891

insistance

centauri
acid001011

xcm

Aurora0915

VanHope
4天前
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp[nums.size()];
dp[0] = nums[0];
int res = dp[0];
for(int i = 1; i < nums.size(); i++)
{
if(dp[i-1] < 0) dp[i] = nums[i];
else            dp[i] = dp[i-1] + nums[i];

res = max(res, dp[i]);
}
return res;
}
};


VanHope
4天前
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int ans = 0;
unordered_map<int, int> mp;
int n = wall.size();
for(int i = 0; i < n; ++i)
{
int pre = 0;
for(int j = 0; j < wall[i].size() - 1; ++j)
{
pre += wall[i][j];
// cout << pre << endl;
if(mp.find(pre) != mp.end()) mp[pre]++;
else                         mp[pre] = 1;
ans = max(ans, mp[pre]);
}
}
return n - ans;
}
};


VanHope
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

class Solution {
public:
int calculate(string s) {
//
stack<char> ops;
stack<long long> nums;

int i = 0;
// for(auto &c : s)
// cout << "zhang" << endl;
while(i < s.length())
{
// i++;
char c = s[i];

cout << c << endl;

if(c == ' ')
{
i++;
continue;
}

if(c >= '0' && c <= '9')
{
long long t = 0;
while(c >= '0' && c <= '9')
{
t = t*10 + c - '0';
i++;
c = s[i];
}
nums.push(t);
}
else
{
if(ops.empty()) ops.push(c);
else if((c == '*' || c == '/'))
{
while(!ops.empty() && (ops.top() == '*' || ops.top() == '/'))
{
if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else if(ops.top() == '/')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}
ops.pop();
}
ops.push(c);
}
else  // + -
{
while(!ops.empty())
{
if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else if(ops.top() == '/')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}
else if(ops.top() == '+')
{
long long t2 = nums.top(); nums.pop();
long long  t1 = nums.top(); nums.pop();
nums.push(t1 + t2);
}
else if(ops.top() == '-')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 - t2);
}
ops.pop();
}
ops.push(c); //
}
i++;
}
}

while(!ops.empty())
{
if(ops.top() == '+')
{
long long t2 = nums.top(); nums.pop();
long long  t1 = nums.top(); nums.pop();
nums.push(t1 + t2);
}
else if(ops.top() == '-')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 - t2);
}
else if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}

ops.pop();
}
return (int)nums.top();
}
};


VanHope
8天前

#### C++ 代码

class Solution {
private:
bool visited[55][55];
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};
int res = 0;
int n, m;
int area = 0;
public:
void dfs(int x, int y, vector<vector<int>>& grid)
{
for(int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny])
{
visited[nx][ny] = true;
area += 1;
dfs(nx, ny, grid);
}
}

}
int maxAreaOfIsland(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(!visited[i][j] && grid[i][j] == 1)
{
area = 1;
visited[i][j] = true;
dfs(i, j, grid);
res = max(area, res);
}
}
}
return res;
}
};



VanHope
8天前

#### C++ 代码

class Solution {
private:
int n;
vector<vector<int>> res;
vector<int> flag = vector<int> (8, 0);
vector<int> index = vector<int> (8, 0);
public:
void dfs(int step, vector<int>& nums)
{
if(step == n)
{
vector<int> tmp;
for(int i = 0; i < n; i++) tmp.push_back(nums[index[i]]);
res.push_back(tmp);
return;
}
for(int i = 0; i < n; i++)
{
if(!flag[i])
{
flag[i] = 1;
index[step] = i;
dfs(step + 1, nums);
flag[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size(); // index 1 - n的全排列
dfs(0,  nums);
return res;
}
};


VanHope
8天前

done

VanHope
2022-03-22 16:03
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010, M = 20010; // 因为是有向边！所以边都开2倍
int h[N], e[M], ne[M], idx = 0;
int d[N];
int s[N];
int dt[N];

int n, m;
void init()
{
memset(h, -1, sizeof h);
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

bool topo()
{

for(int i = 1; i <= n; i++)
{
int t = s[i];

if(dt[t]) return false; // 入度不为0返回false

else
{
for(int k = h[t]; k != -1; k = ne[k])
{
int j = e[k];
dt[j]--;
}
}
}

return true;
}

int main()
{
init();
scanf("%d%d", &n, &m);
while(m --)
{
int a, b;
scanf("%d%d", &a, &b);
d[b]++; // 入度++
}
int q;
vector<int> res;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &s[j]), dt[j] = d[j];

if(!topo()) res.push_back(i);
}

for(auto t : res)
{
printf("%d ", t);
}
return 0;
}



VanHope
2022-03-22 11:16

[toc]

## 题目描述

1≤n≤100,
1≤ai≤2×10^9

#### 输入样例：

3 3 6 8

#### 输出样例：

2 2 4

## 欧拉函数

### 代码

#include<iostream>
using namespace std;

int phi(int x)
{
int res = x;
for(int i = 2; i <= x/i; i++)
{
// 找到一个质因子
if(x % i == 0)
{
res = res / i * (i-1); // 即 res*(1 - 1/i);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}

int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
cout << phi(x) << endl;
}

return 0;
}


## 参考文章

VanHope
2022-03-22 11:03

=>

#include<iostream>
#include<cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 50010;
struct Cow
{
LL w, s, ws;
}cows[N];

bool cmp(Cow a, Cow b)
{
return a.ws < b.ws; //按照w+s从小到大排序才是重点！！！
}

int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
int s, w;
cin >> s >> w;
cows[i] = {s, w, s+w};
}
sort(cows, cows + n, cmp);

int res = -0x3f3f3f3f;
LL tot = 0;
for(int i = 0; i < n; i++)
{
int t = tot - cows[i].s;

res = max(res, t);

tot += cows[i].w;
}
cout << res << endl;
return 0;
}



VanHope
2022-03-22 10:46

# acwing 104. 货仓选址（排序不等式）

[toc]

## 题目描述

1≤N≤100000
0≤Ai≤40000

#### 输入样例：

4 6 2 9 1

#### 输出样例：

12

## 排序不等式

### 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];

sort(a, a + n); // 从小到大排序

int x = a[n/2]; // 选取中位数

int res = 0;
for(int i = 0; i < n; i++)  res += abs(a[i] - x);

cout << res ;
return 0;
}