Stella-W

1.1万

Stella-W
8个月前

题目描述

C++ 代码

class Solution {
public:
int cnt[26] = {};
int res = 0;
bool check(string x)
{
unordered_map<int, int>h;
for (auto a : x)
{
h[a - 'a'] ++;
if (h[a - 'a'] > 1) return false;
}
return true;
}

bool check1(string start)
{
for (auto x :start)
{
if (cnt[x - 'a']) return false;
}
return true;
}

int maxLength(vector<string>& arr) {
vector<string> tmp;
for (auto x :arr)
{
if (check(x))
tmp.push_back(x);
}
if (tmp.empty()) return 0;

string a = "";
dfs(tmp, a, 0);
return res;
}

void dfs(vector<string>& num, string &a, int start)
{
if (res < a.size()) res = a.size();
if (start == num.size()) return;
if (check1(num[start]))
{
a += num[start];
for (auto x : num[start]) cnt[x - 'a'] ++;
dfs(num, a, start + 1);
for (auto x : num[start]) cnt[x - 'a'] --;
a = a.substr(0, a.size() - num[start].size());
}

dfs(num, a, start + 1);
}

};


Stella-W
9个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

int sg(int x)
{
if (f[x] != -1) return f[x];

unordered_set<int> S;
for (int i = 0; i < m; i ++ )
{
int sum = s[i];
if (x >= sum) S.insert(sg(x - sum));
}

for (int i = 0; ; i ++ )
if (!S.count(i))
return f[x] = i;
}

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

memset(f, -1, sizeof f);

int res = 0;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
res ^= sg(x);
}

if (res) puts("Yes");
else puts("No");

return 0;
}



Stella-W
9个月前

题目描述

C++ 代码

class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int t) {
vector<vector<int>> dist(N + 1, vector<int> (N + 1, 0x3f3f3f3f));

for (int i = 0; i < times.size(); i ++)
{
int a = times[i][0], b = times[i][1], c = times[i][2];
dist[a][b] = c;
}

for (int k = 1; k <= N; k ++)
for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

int res = 0;
for (int i = 1; i <= N; i ++)
{
if (i != t)
res = max(res, dist[t][i]);
}

if (res == 0x3f3f3f3f)
{
return -1;
}
return res;

}
};


Stella-W
9个月前

题目描述

（1）start的上一个区间的结尾是否超过了start
（2）start的下一个区间的开头是否被end超过

C++ 代码

class MyCalendar {
public:
map<int, int> hash;
MyCalendar() {

}

bool book(int start, int end) {
if (hash.empty())
{
hash[start] = end;
return true;
}
auto up = hash.lower_bound(start);
if (up != hash.end())
if (up->first < end) return false;
if (up != hash.begin())
{
up--;
if (up->second > start) return false;
}
hash[start] = end;
return true;

}
};

/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/


Stella-W
9个月前

题目描述

C++ 代码

class Solution {
public:
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

void uni(int x, int y)
{
int a = find(x), b = find(y);
if (a != b) p[a] = b;
}

int p[20000]; // 数值的范围是2000
unordered_set<int> list;
int removeStones(vector<vector<int>>& stones) {
for(int i = 0; i < 20000; i ++) p[i] = i;
for(int i = 0; i < stones.size(); i ++) uni(stones[i][0],stones[i][1] + 10000);
for(int i = 0; i < stones.size(); i ++) list.insert(find(stones[i][0]));
return stones.size() - list.size();
}
};


Stella-W
9个月前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 510, M = 5210;

int h[N], e[M], ne[M], w[M];
int n, T, idx;
int dist[N], cnt[N];
bool st[N];

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

bool spfa()
{
memset(dist, 0, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);

queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}

while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}

int main()
{
int T;
cin >> T;
while (T -- )
{
int m, w;
cin >> n >> m >> w;
memset(h, -1, sizeof h);
idx = 0;
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
}
for (int i = 0; i < w; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
}

if (spfa()) puts("YES");
else puts("NO");
}

return 0;
}



Stella-W
9个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 210;

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 = 0; i < m; i ++)
{
cin >> e[i].a >> e[i].b >> e[i].w;
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
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), w = e[i].w;
if (a != b) p[a] = b;
else res += w;
}
cout << res;
return 0;
}



Stella-W
9个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int w[N][N];
int dist[N];
bool st[N];
int n;

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

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

}
return res;
}

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

cout << prim();

return 0;
}


Stella-W
9个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 40010, M = 2 * N;

int n, m;
int h[N], ne[M], e[M], idx;
int depth[N], fa[N][16];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
queue<int> q;
depth[0] = 0, depth[root] = 1;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;   // j 向上走一步就是t
for (int k = 1; k <= 15; k ++)
fa[j][k] = fa[fa[j][k - 1]][k - 1];

}
}
}
}

int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k --)
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];           // 从最大的位开始拼凑，赋值后找更小的数，最后会在同一层
if (a == b)
return a;
for (int k = 15; k >= 0; k --)
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
// 移动到次公共祖先层
return fa[a][0];

}

int main()
{
cin >> n;
int root = 0;
memset(h, -1, sizeof h);

for (int i = 0; i < n; i ++)
{
int a, b;
cin >> a >>b;
if (b == -1) root = a;
}

bfs(root);

cin >> m;
while (m --)
{
int a, b;
cin >> a >> b;
int p = lca(a, b);
if (p == a) puts("1");
else if (p == b) puts("2");
else puts("0");
}
return 0;
}



Stella-W
9个月前
#include <iostream>
#include <cstring>
#include <sstream>
#include <queue>

using namespace std;

const int N = 510;
int dist[N], stop[N];
bool g[N][N];
int m, n;

void bfs()
{
queue<int> q;
memset(dist, 0x3f, sizeof dist);
q.push(1);
dist[1] = 0;

while (q.size())
{
int t = q.front();
q.pop();
for (int i = 1; i <= n; i ++)
if (g[t][i] &&dist[i] > dist[t] + 1)
{
dist[i] = dist[t] + 1;
q.push(i);
}
}
}

int main()
{
cin >> m >> n;
string line;

getline(cin, line);
while (m --)
{
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt ++] = p;
for (int j = 0; j < cnt; j ++)
for (int k = j + 1; k < cnt; k ++)
g[stop[j]][stop[k]] = true;
}

bfs();
if (dist[n] == 0x3f3f3f3f) puts("NO");
else cout << max(dist[n] - 1, 0) << endl;

return 0;
}