1.9万

noobcoder
jwh
Draper
Unnatural
heMing_zero
Egbert-Lannister.
cjyasleep
Abcdefg123

mainkeys

Kole
heavens.
kwq
Fool_vamp
372_9
KKKKKKKKKKKKKKKKKKKKKK
L-China

## 23.03.29 学习

Kruskal = quicksort + 并查集，并查集真忘了，也不想写重载运算符，就用cmp比较rule

6600/52000，一道题提交前进200，把图论补完恐怕进不去前6000，还是要补完数论ToT

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

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N];

struct Edge {
int a, b, w;
}edges[M];

static bool cmp(Edge& a, Edge& b) {
return a.w < b.w;
}

int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal() {
sort(edges, edges + m, cmp);

for (int i = 1; i <= n; i ++ ) p[i] = i;

int sum = 0, cnt = 0;
for (int i = 0; i < m; i ++ ) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
if (find(a) != find(b)) {
p[find(a)] = find(b);
cnt ++ ;
sum += w;
}
}

if (cnt != n - 1) return INF;
else return sum;
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; i ++ ) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}

int res = kruskal();

if (res == INF) cout << "impossible" << endl;
else cout << res << endl;

return 0;
}

## 23.03.29学习

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
memset(dist, 0x3f, sizeof dist);
int res = 0;

for (int i = 0; i < n; i ++ ) {
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (i && dist[t] == INF) return INF;
st[t] = true;
if (i) res += dist[t];

for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}

int main() {
cin >> n >> m;
memset(g, 0x3f3f3f3f, sizeof g);
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
}

int t = prim();

if (t == INF) cout << "impossible" << endl;
else cout << t << endl;

return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int res = 0;

for (int i = 0; i < n; i ++ ) {
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (dist[t] == INF) return INF;
st[t] = true;
res += dist[t];

for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}

int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
}

int t = prim();

if (t == INF) cout << "impossible" << endl;
else cout << t << endl;

return 0;
}

## 23.03.28 学习

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N];

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

void topsort() {
queue<int> q;
int top[N], cnt = 0;
for (int i = 1; i <= n; i ++ ) {
if (d[i] == 0) {
q.push(i);
cnt ++ ;
top[cnt] = i;
}
}
// bfs,删除每个点的入度找拓扑序
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j] -- ;
if (d[j] == 0) {
q.push(j);
cnt ++ ;
top[cnt] = j;
}
}
}
// 判断
if (cnt != n) cout << -1 << endl;
else {
for (int i = 1; i <= n; i ++ ) cout << top[i] << ' ';
cout << endl;
}
}

int main()
{

cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b;
cin >> a >> b;
d[b] ++ ;
}

topsort();

return 0;
}

## 23.03.24 学习

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix.size(), m = matrix[0].size(), res = 0;
vector<int> heights(m, 0);
heights.push_back(-1);

for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
if (matrix[i][j] == '0') heights[j] = 0;
else heights[j] ++ ;
}
// for (auto x : heights) cout << x << ' ';
// cout << endl;

// 对于每一层的heights都计算一遍res，遍历完m层最大的res就出来了
stack<int> stk;
for (int i = 0; i <= m; i ++ ) {
while (!stk.empty() && heights[i] < heights[stk.top()]) {
auto cur = stk.top();
stk.pop();

if (stk.empty()) res = max(res, heights[cur] * i);
else res = max(res, heights[cur] * (i - stk.top() - 1));
}
stk.push(i);
}
}

return res;
}
};

## 23.03.24 学习

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size(), res = 0;
heights.push_back(-1);
stack<int> stk;

for (int i = 0; i <= n; i ++ ) {
while (!stk.empty() && heights[i] < heights[stk.top()]) {
auto cur = stk.top();
stk.pop();

if (stk.empty()) res = max(res, heights[cur] * i);  // 左边没有比他低的柱子
else res = max(res, heights[cur] * (i - stk.top() - 1));
}
stk.push(i);
}

return res;
}
};

## 23.03.24 学习

class Solution {
public:
static bool cmp(vector<int> a, vector<int> b) {
if (a[0] != b[0]) return a[0] > b[0];
return a[1] < b[1];
}

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);

vector<vector<int>> res;
for(auto p:people) res.insert(res.begin()+p[1],p);

return res;
}
};

## 23.03.23 学习

class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> stk;
vector<int> res(T.size());
for (int i = T.size() - 1; i >= 0; i -- ) {
while (stk.size() && T[i] >= T[stk.top()]) stk.pop();
if (stk.size()) res[i] = stk.top() - i;
stk.push(i);
}
return res;
}
};

## 23.03.23 学习

wzc1995大佬太强了，同样的人，向他学习

class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> t(26, 0);
t[c - 'A'] ++ ;

priority_queue<int> heap;
for (auto c : t)
if (c != 0)
heap.push(c);

int res = 0;
int interval = n + 1;
while (true) {
vector<int> tmp;
for (int i = 0; i < interval; i ++ ) {
if (!heap.empty()) {
tmp.push_back(heap.top() - 1);
heap.pop();
}
}

for (auto x : tmp) {
if (x)
heap.push(x);
}

if (heap.empty()) {
res += tmp.size();
break;
} else {
res += n + 1;
}
}

return res;
}
};

## 23.03.22 学习

class Solution {
public:
int countSubstrings(string s) {
int res = 0, n = s.size();
for (int i = 0; i < s.size(); i ++ ) {
for (int j = i, k = i; j >= 0 && k < n; j -- , k ++ ) {
if (s[j] != s[k]) break;
res ++ ;
}

for (int j = i, k = i + 1; j >= 0 && k < n; j -- , k ++ ) {
if (s[j] != s[k]) break;
res ++ ;
}
}

return res;
}
};

## 23.03.22 学习

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
if (!r1 && !r2) return NULL;
if (r1 && !r2) return r1;
if (!r1 && r2) return r2;

r1->val += r2->val;
r1->left = mergeTrees(r1->left, r2->left);
r1->right = mergeTrees(r1->right, r2->right);
return r1;
}
};