头像

Stella-W

带专




离线:2个月前



Stella-W
8个月前

题目描述

由于题目答案与字符的顺序无关,那么可以依次枚举是否选用当前的字符串,分为选与不选两种情况。
用dfs+回溯的方式搜索即可

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);
    }

};


活动打卡代码 AcWing 893. 集合-Nim游戏

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个月前

题目描述

求节点1到其余所有点最短路的最大值,跟acwing1128一样,可以用floyd算法

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个月前

题目描述

题目不难,看到其他的c++题解不够直观

插入每个区间的时候,只需要看两点
(1)start的上一个区间的结尾是否超过了start
(2)start的下一个区间的开头是否被end超过

用map的lower_bound可以求出下一个区间

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个月前

题目描述

题目求最多的操作次数,每次操作的要求是被选定要移除的石子所在行或者列必须还有其他的石子。采用并查集的思想,如果一个集合可以通过行或者列间接相连,那么存在一种顺序使得某一连通集合中只剩下一个石子。

为了防止行和列出现重复,对于列的值加上一个10000,因为x和y的范围都是10000,因此加上10000保证x和y的数值不会有重叠。然后开始合并能够连通的石子。答案等于 总石子数-集合数量

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();
    }
};


活动打卡代码 AcWing 904. 虫洞

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;
            add(a, b, c), add(b, a, c);
        }
        for (int i = 0; i < w; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, -c);
        }

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

    return 0;
}




活动打卡代码 AcWing 1141. 局域网

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;
}



活动打卡代码 AcWing 1140. 最短网络

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;
}


活动打卡代码 AcWing 1172. 祖孙询问

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];

void add(int a, int b)
{
    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;
        else add(a, b), add(b, 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;
}





活动打卡代码 AcWing 920. 最优乘车

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;
}