Ninja@珏

1.1万

RyanMoriarty

Loki
RE_MAKE
wehiders
JasonQ1an
lu_ren

pjc1234567
BlackAtao

whelve

Eartha
thunderclouds
acWing_lbwnb

### 1. 前序遍历+中序遍历。生成二叉树

leetcode版本1

/**
* 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:
unordered_map<int, int> pos;
vector<int> preorder, inorder;
TreeNode* buildTree(vector<int>& preorder_, vector<int>& inorder_) {
preorder = preorder_;
inorder = inorder_;
int n = inorder_.size();
for (int i = 0; i < n; i ++ ) pos[inorder_[i]] = i;

return build(0, n - 1, 0, n - 1);
}

TreeNode* build(int il, int ir, int pl, int pr) {
TreeNode* root = new TreeNode(preorder[pl]);

int k = pos[root->val];

// x - (pl + 1) = k - 1 - il;
if (il < k) root->left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
if (k < ir) root->right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
return root;
}
};


leetcode 版本2, 这种方法好像更快

/**
* 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:
unordered_map<int, int> pos;
vector<int> preorder, inorder;
TreeNode* buildTree(vector<int>& preorder_, vector<int>& inorder_) {
preorder = preorder_;
inorder = inorder_;
int n = inorder_.size();
for (int i = 0; i < n; i ++ ) pos[inorder_[i]] = i;

return build(0, n - 1, 0, n - 1);
}

TreeNode* build(int il, int ir, int pl, int pr) {
if (pl > pr) return nullptr;

TreeNode* root = new TreeNode(preorder[pl]);

int k = pos[root->val];

// x - (pl + 1) = k - 1 - il;
root->left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
root->right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
return root;
}
};


acwing 版本

### 2. 后序遍历+中序遍历。生成二叉树

leetcode版本

/**
* 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:
unordered_map<int, int> pos;
vector<int> inorder, postorder;

TreeNode* buildTree(vector<int>& inorder_, vector<int>& postorder_) {
inorder = inorder_;
postorder = postorder_;
for (int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i;

return build(0, inorder.size() - 1, 0, inorder.size() - 1);
}

TreeNode* build(int il, int ir, int pl, int pr) {
if (pl > pr) return nullptr;

TreeNode* root = new TreeNode(postorder[pr]);
int k = pos[root->val];
// x - pl = k - 1 - il
root->left = build(il, k - 1, pl, pl + k - 1 - il);
root->right = build(k + 1, ir, pl + k - 1 - il + 1, pr - 1);
return root;
}
};


acwing 版本

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 1010;

bool g[N][N], st[N][N];
int dist[N][N];

#define x first
#define y second

using PII = pair<int, int>;

int bfs(int sx, int sy)
{
memset(dist, 0x3f, sizeof dist);
dist[sx][sy] = 0;
deque<PII> q;
q.push_back({sx, sy});

while (q.size())
{
auto t = q.front();
q.pop_front();

if (st[t.x][t.y]) continue;
st[t.x][t.y] = true;
if (!t.x && !t.y) break;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

for (int i = 0; i < 4; i ++ )
{
auto x = t.x + dx[i], y = t.y + dy[i];
if (x >= 0 && x < N && y >= 0 && y < N)
{

}
else continue;

int w = 0;
if (g[x][y]) w = 1;
if (dist[x][y] > dist[t.x][t.y] + w)
{
dist[x][y] = dist[t.x][t.y] + w;
if (!w) q.push_front({x, y});
else q.push_back({x, y});
}
}
}
return dist[0][0];
}

int main()
{
int n, x, y;
cin >> n >> x >> y;
for (int i = 0; i < n; i ++ )
{
int a, b;
cin >> a >> b;
g[a][b] = true;
}

cout << bfs(x, y) << endl;
return 0;
}


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

const int N =55;

char g[N][N];
int n, m;
#define x first
#define y second
using PII = pair<int, int>;
bool st[N][N];
int dist[N][N];

int bfs(int a, int b)
{
memset(dist, 0x3f, sizeof dist);
deque<PII> q;
q.push_front({a, b});
dist[a][b] = 0;

int res = 1e9;

while (q.size())
{
auto t = q.front();
q.pop_front();
st[t.x][t.y] = true;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (st[x][y]) continue;
st[x][y] = true;

int w = 1;
if (g[x][y] == 'X') w = 0;

if (dist[x][y] > dist[t.x][t.y] + w)
{
dist[x][y] = dist[t.x][t.y] + w;

if (!w)
{
q.push_front({x, y});
if (dist[x][y] > 0)
{
res = min(res, dist[x][y]);
//cout << dist[x][y] << endl;
}
}
else
{
q.push_back({x, y});
}
}

}
}
return res;
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> g[i];

int x, y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
if (g[i][j] == 'X')
{
cout << bfs(i, j) << endl;
return 0;
}
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;

int a[N];
int b[N];

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < k; i ++ )
{
int l, r;
cin >> l >> r;
a[l]++;
a[r + 1]--;
}
for (int i = 1; i <= n; i ++)
a[i + 1] += a[i];
sort(a + 1, a + n + 1);
int m = n / 2 + 1;
cout << a[m] << endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;
const int N = 100010;

int two10(string x) {
int res = 0;
reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i ++)
{
if (x[i] == '1')
res |=  1 << i;
}
return res;
}

int base(string x) {
int res = 0;
int p = 1;
reverse(x.begin(), x.end());

for (int i = 0; i < x.size(); i ++ )
{
res += (x[i] - '0') * p;
p *= 3;
}
return res;
}

int main()
{
string a, b;
cin >> a >> b;
unordered_set<int> st;
//cout << two10(a) << endl;
// cout << base(b) << endl;

for (int i = 0; i < a.size(); i ++ ) {
string x = a;
if (x[i] == '0') x[i] = '1';
else x[i] = '0';
st.insert(two10(x));
}

for (int i = 0; i < b.size(); i ++ ) {
string x = b;
if (x[i] == '0') {
x[i] = '1';
if (st.count(base(x))) {
cout << base(x) << endl;
return 0;
}
x[i] = '2';
if (st.count(base(x))) {
cout << base(x) << endl;
return  0;
}
}
else if (x[i] == '1') {
x[i] = '0';
if (st.count(base(x))) {
cout << base(x) << endl;
return 0;
}
x[i] = '2';
if (st.count(base(x))) {
cout << base(x) << endl;
return 0;
}
}
else if (x[i] == '2') {
x[i] = '1';
if (st.count(base(x))) {
cout << base(x) << endl;
return 0;
}
x[i] = '0';
if (st.count(base(x))) {
cout << base(x) << endl;
return 0;
}
}
}

return 0;
}


Ninja@珏
10天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int mod = 200907;

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

int main()
{
int n;
cin >> n;
while (n -- )
{
int a, b, c, k;
cin >> a >> b >> c >> k;
if (a + c == 2 * b)
{
cout << (a + (b - a ) * (LL)(k - 1)) % mod << endl;
}
else
{
cout << ((LL)a * qmi(b/a, k - 1, mod)) % mod << endl;
}
}
return 0;
}


Ninja@珏
10天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] * i <= n; j ++)
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}

int main()
{
int n;
cin >> n;
init(n);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
int s = 0;
for (int j = n; j ; j /= p) s += j / p;
printf("%d %d\n", p, s);
}
return 0;
}


Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310, M = 10010;
int n, m;
struct Edge
{
int a, b , w;
bool operator<(const Edge& t) const
{
return w < t.w;
}
}e[M];

int p[N];

int find(int x)  // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 0; i < m; i ++ )
{
cin >> e[i].a >> e[i].b >> e[i].w;
}
sort(e, e + m);
int res = 0;
for (int i = 0; i < m; i ++ )
{
int a = find(e[i].a), b = find(e[i].b);
if (a == b) continue;
p[a] = b;
res = e[i].w;
}
cout << n - 1 << ' ' << res << endl;
return 0;
}


Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 210;
int n, k;
int p[N];

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

struct Edge
{
int a, b, w;
bool operator<(const Edge& e) const
{
return w < e.w;
}
}E[M];

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

int res = 0;
for (int i = 1; i <= k; i ++ )
{
int a = E[i].a, b = E[i].b, w = E[i].w;
if (find(a) == find(b)) continue;

p[find(a)] = find(b);
res += w;
}
return res;
}

int main()
{
cin >> n >> k;
int tot = 0;

for (int i = 1; i <= k; i ++ )
{
cin >> E[i].a >> E[i].b >> E[i].w;
tot += E[i].w;
}
sort(E + 1, E + k + 1);

cout << tot - kruskal() << endl;
return 0;
}


Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;

int g[N][N];
int n;
bool st[N];
int dist[N];
int res ;

int prim()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 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;

st[t] = true;
//printf("t=%d dist =%d\n", t, dist[t]);

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

int main()
{
cin >> n;

for (int i = 1 ;i <= n; i ++ )
for (int j = 1; j <= n; j ++)
{
cin >> g[i][j];
}

memset(st, 0, sizeof st);

cout << prim() << endl;

return 0;
}