challow

challow
13天前

## 理论基础

down 的操作就相当于每次找出root root->left root->right 这三个元素中的最小值，如果不是root则进行交换。然后从新的位置递归进行 down 操作

## 代码实现


#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int h[N];
int n, m;
int numsize;

void down(int u)
{
int t = u; // 存储的最小元素的下标
if(u * 2 <= numsize && h[u * 2] < h[t]) t = u * 2; // 保证元素有左右儿子的情况下判断左儿子是否小于根节点的值
if(u * 2 + 1 <= numsize && h[u * 2 + 1] < h[t]) t = u * 2 + 1;

if(u != t) // 如果当前最小值的位置不是根节点，那么进行元素交换并递归操作
{
swap(h[u], h[t]);
down(t);
}
}

int main()
{
scanf("%d%d",&n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
numsize = n;

for (int i = n / 2; i; i -- ) down(i); // O(n) 时间复杂度建立堆

while(m -- )
{
printf("%d ", h[1]);
h[1] = h[numsize];
numsize -- ;
down(1);
}
}



challow
14天前
class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if i < j:
if s[i].upper() != s[j].upper():
return False
else:
i += 1
j -= 1
return True



challow
14天前

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.res = -0x3f3f3f3f
self.dfs(root)
return self.res

def dfs(self, root) -> int:
if not root:
return 0
left = max(0, self.dfs(root.left))
right = max(0, self.dfs(root.right))

self.res = max(self.res, left + root.val + right)

return root.val + max(left, right)



challow
14天前

class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
f = [0] * (n + 2)
minp = 0x3f3f3f3f

for i in range(1, n + 1):
f[i] = max(f[i - 1], prices[i - 1] - minp)
minp = min(minp, prices[i - 1])

res = 0
maxp = 0
for i in range(n, 0, -1):
res = max(res, maxp - prices[i - 1] + f[i - 1])
maxp = max(maxp, prices[i - 1])
return res



challow
14天前

class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(len(prices) - 1):
res += max(0, prices[i + 1] - prices[i])
return res



challow
14天前

class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
maxp = 0x3f3f3f3f
for i in range(len(prices)):
res = max(prices[i] - maxp, res)
maxp = min(maxp, prices[i])
return res



challow
14天前

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(1, k, n);
return res;
}
void dfs(int u, int k, int n)
{
if(k == 0 && n == 0)
{
res.push_back(path);
}
for (int i = u; i <= 9; i ++ )
{
if(n - i >= 0)
{
path.push_back(i);
dfs(i + 1, k - 1, n - i);
path.pop_back();
}
}
}
};



challow
19天前

#include <iostream>

typedef long long LL;

using namespace std;

int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL) res* a % p;
k >>= 1;
a = (LL)a* a %p;
}
return res;
}

int main()
{
int n;
scanf("%d", &n);
while(n -- )
{
int a, k, p;
scanf("%d%d", &a, &p);

int res = qmi(a, p - 2, p);
if(a % p)
printf("%d\n", res);
else
printf("impossible\n");
}
return 0;
}



challow
19天前

#include <iostream>

typedef long long LL;

using namespace std;

int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL) res* a % p;
k >>= 1;
a = (LL)a* a %p;
}
return res;
}

int main()
{
int n;
scanf("%d", &n);
while(n -- )
{
int a, k, p;
scanf("%d%d%d", &a, & k, &p);

printf("%d\n", qmi(a, k, p));
}
return 0;
}



challow
23天前

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

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u, in_stk[u]  = true;
for (int i = h[u]; i != -1 ;i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
}

if(dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++;
} while(y != u);
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m -- )
{
int a, b;
scanf("%d%d",&a, &b);
add(a, b);
}

for (int i = 1;i <= n ; i ++ )
if(!dfn[i])
tarjan(i);

for (int i = 1; i <= n; i ++ )
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a != b) dout[a] ++;
}

int zeros = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ )
if (!dout[i])
{
zeros ++;
sum += Size[i];
if(zeros > 1)
{
sum = 0;
break;
}
}

printf("%d\n", sum);
return 0;
}