头像

__43




离线:11小时前


活动打卡代码 AcWing 239. 奇偶游戏

__43
16小时前
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;
int p[N],d[N],idx;
unordered_map<int,int>  hashmap;

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

int get(int x)
{
    if (!hashmap.count(x))   hashmap[x] = idx++;

    return hashmap[x];
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    int res = m;
    for (int i = 0;i < N;++i)   p[i] = i;
    for (int i = 1;i <= m;++i)
    {
        string op;
        int a,b;
        scanf("%d%d",&a,&b);
        cin>>op;
        a = get(a - 1),b = get(b);
        int pa = find(a),pb = find(b);
        int t = 0;
        if ("odd" == op)   t = 1;
        if (pa == pb &&  ((d[a] + d[b]) % 2 + 2) % 2 != t)//( (d[a] + d[b]) % 2 + 2) % 2 != t
        {
            res = i - 1;
            break;
        }
        if (pa != pb)
        {
            p[pa] = pb;
            d[pa] = d[a] ^ d[b] ^ t;
        }

    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

__43
19小时前
#include <iostream>
using namespace std;
const int N = 3e4 + 10;
int p[N],d[N],s[N];

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

int main(void)
{
    int m;
    scanf("%d",&m);
    for (int i = 0;i < N;++i)   p[i] = i,s[i] = 1;
    for (int i = 0;i < m;++i)
    {
        char c[2];
        int a,b;
        scanf("%s%d%d",c,&a,&b);
        int pa = find(a),pb = find(b);
        if ('M' == *c)
        {
            d[pa] += s[pb];
            s[pb] += s[pa];
            p[pa] = pb;
        }
        else
        {
            if (pa == pb)   printf("%d\n",abs(d[a] - d[b]) - 1);
            else    printf("-1\n");
        }
    }
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

__43
20小时前
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e6 + 10;
int p[N],n,t;
unordered_map<int,int>  hashmap;
struct Edge
{
    int a,b,c;
}edges[N];

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

int get(int x)
{
    if (!hashmap.count(x))    hashmap[x] = n++;
    return hashmap[x];
}

int main(void)
{
    scanf("%d",&t);
    while (t--)
    {
        int m;
        scanf("%d",&m);
        hashmap.clear();
        for (int i = 0;i < N;++i)   p[i] = i;

        for (int i = 0;i < m;++i)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            edges[i] = {get(a),get(b),c};
        }

        for (int i = 0;i < m;++i)
            if (1 == edges[i].c)
            {
                int pa = find(get(edges[i].a)),pb = find(get(edges[i].b));
                if (pa != pb)   p[pa] = pb;
            }

        bool b = true;
        for (int i = 0;i < m;++i)
            if (0 == edges[i].c)
            {
                int pa = find(get(edges[i].a)),pb = find(get(edges[i].b));
                if (pa == pb)
                {
                    b = false;
                    break;
                }
            }
        if (b)  puts("YES");
        else    puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 1252. 搭配购买

__43
1天前
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1e4 + 10;
int p[N],w[N],v[N],n,m,val,dp[N];

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

int main(void)
{
    cin>>n>>m>>val;
    for (int i = 0;i <= n;++i)  p[i] = i;
    for (int i = 1;i <= n;++i)   scanf("%d%d",&w[i],&v[i]);
    for (int i = 0;i < m;++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int pa = find(a),pb = find(b);
        if (pa != pb)
        {
            w[pb] += w[pa];
            v[pb] += v[pa];
            p[pa] = pb;
        }
    }
    for (int i = 1;i <= n;++i)
    {
        if (i == p[i])
        {
            for (int j = val;j >= w[i];--j)
            {
                dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
            }
        }
    }

    cout<<dp[val]<<endl;
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

__43
1天前

#include <iostream>
using namespace std;
const int N = 205 * 205;
int p[N + 10],n,m;
//#define _XY(x,y)    ((x) + ((y) - 1) * n)
int _XY(int x,int y)
{
    //cout<<x<<" "<<y<<endl;
    //cout<<x + (y - 1) * n<<endl;
    return x + y * (n - 1);
}

int find(int x)
{
    //cout<<x<<endl;
    if (x != p[x])    p[x] = find(p[x]);
    return p[x];
}

int main(void)
{
    scanf("%d%d",&n,&m);
    bool b = true;
    int t = 0,temp = m;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= n;++j)
            p[_XY(j,i)] = _XY(j,i);
    while (m--)
    {
        int x,y;
        char c[2];
        scanf("%d%d%s",&x,&y,c);
        int pa = find(_XY(x,y)),pb;
        if ('D' == c[0])
        {
            //cout<<Y<<endl;
            pb = find(_XY(x,y + 1));
            if (pa != pb)
                p[pb] = pa;
            else
            {
                cout<<t + 1<<endl;
                break;
            }
        }
        else
        {
            int X = x + 1;
            pb = find(_XY(x + 1,y));
            if (pa != pb)
                p[pb] = pa;
            else
            {
                cout<<t + 1<<endl;
                break;
            }
        }
        ++t;
    }
    if (t == temp)
        cout<<"draw"<<endl;
    return 0;
}



__43
2天前

class Solution {
public:
    unordered_map<int,int>  p;
    int find(int x)
    {
        if (x != p[x])  p[x] = find(p[x]);
        return p[x];
    }
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty())   return 0;
        int res = 1,n = nums.size();
        unordered_map<int,int>  hashmap;
        unordered_set<int>  Set;
        for (int i = 0;i < n;++i) hashmap[nums[i]] = 1,p[nums[i]] = nums[i];
        for (int i = 0;i < n;++i)
        {
            if (Set.count(nums[i])) continue;
            if (nums[i] > INT_MIN && hashmap[nums[i] - 1])
            {
                int pb = find(nums[i] - 1),pa = find(nums[i]);
                hashmap[pa] += hashmap[pb];
                p[pb] = pa;
                res = max(res,hashmap[pa]);
            }
            Set.insert(nums[i]);
        }
        return res;
    }
};



__43
2天前
const int N = 1e5 + 10;
int p[N],r,c;
class Solution {
public:
    int find(int x)
    {
        if (x != p[x])  p[x] = find(p[x]);
        return p[x];
    }
    void solve(vector<vector<char>>& board) {
        if (board.empty())  return;
        r = board.size();
        c = board[0].size();
        for (int i = 0;i < r * c;++i)   p[i] = i;
        for (int i = 0;i < r;++i)
        {
            for (int j = 0;j < c;++j)
            {
                if ('O' == board[i][j])
                {
                    int pt;
                    if (i && 'O' == board[i - 1][j])
                    {
                        pt = find((i - 1) * c + j);
                        p[pt] = i * c + j;
                    }
                    if (j && 'O' == board[i][j - 1])
                    {
                        pt = find(i * c + j - 1);
                        p[pt] = i * c + j;
                    }
                }
            }
        }
        unordered_set<int>  Set;
        for (int i = 0;i < r;++i)
        {
            if ('O' == board[i][0])
            {
                int p = find(i * c);
                Set.insert(p);
            }
            if ('O' == board[i][c - 1])
            {
                int p = find(i * c + c - 1);
                Set.insert(p);
            }
        }
        for (int i = 0;i < c;++i)
        {
            if ('O' == board[0][i])
            {
                int p = find(i);
                Set.insert(p);
            }
            if ('O' == board[r - 1][i])
            {
                int p = find((r - 1) * c + i);
                Set.insert(p);
            }
        }

        for (int i = 1;i < r - 1;++i)
        {
            for (int j = 1;j < c - 1;++j)
            {
                int p = find(i * c + j);
                if ('O' == board[i][j] && Set.find(p) == Set.end())
                {
                    board[i][j] = 'X';
                }
            }
        }

    }
};


活动打卡代码 LeetCode 200. 岛屿数量

__43
2天前
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int r = grid.size(), c = grid[0].size();
        p.resize(r * c);
        for (int i = 0; i < p.size(); ++i)    p[i] = i;
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                if ('1' == grid[i][j])
                {
                    int pt;
                    if (j && '1' == grid[i][j - 1])
                    {
                        pt = find(i * c + j - 1);
                        p[pt] = find(i * c + j);
                    }
                    if (i && '1' == grid[i - 1][j])
                    {
                        pt = find((i - 1) * c + j);
                        p[pt] = find(i * c + j);
                    }
                }
            }
        }
        unordered_set<int>  Set;
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                if ('1' == grid[i][j])
                {
                    int pt = find(i * c + j);
                    Set.insert(pt);
                }
            }
        }
        return Set.size();
    }
    vector<int> p;
    int find(int x)
    {
        if (x != p[x])  p[x] = find(p[x]);
        return p[x];
    }
};


活动打卡代码 LeetCode 399. 除法求值

__43
3天前
class Solution {
public:
    unordered_map<string, string> p;
    unordered_map<string, double> w;
    string find(string& x)
    {
        auto it = p.find(x);
        if (it == p.end())
        {
            p[x] = x;
            w[x] = 1.0;
            return x;
        }
        if (it->second != x)
        {
            string t = p[x];
            p[x] = find(p[x]);
            w[x] *= w[t];
        }
        return p[x];
    }
    vector<double> calcEquation(vector<vector<string>>& e, vector<double>& v, vector<vector<string>>& q) {
        vector<double>  r;
        int count = 0;
        for (auto i : e)
        {
            string pa = find(i[0]), pb = find(i[1]);
            p[pa] = i[1];
            w[pa] = v[count] / w[i[0]];
            count++;
        }
        for (auto i : q)
        {
            if (p.end() == p.find(i[0]) || p.end() == p.find(i[1]))
            {
                r.push_back(-1.0);
                continue;
            }
            string pa = find(i[0]), pb = find(i[1]);
            if (pa != pb)   r.push_back(-1.0);
            else    r.push_back(w[i[0]] / w[i[1]]);
        }
        return r;
    }
};


活动打卡代码 AcWing 244. 谜一样的牛

__43
3天前
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int tre[N],n,a[N],r[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c)
{
    for (int i = x;i <= n;i += lowbit(i))   tre[i] += c;
}

int sum(int x)
{
    int ans = 0;
    for (int i = x;i;i -= lowbit(i))    ans += tre[i];
    return ans;
}

int main(void)
{
    scanf("%d",&n);
    //add(1,1);
    for (int i = 2;i <= n;++i)
    {
        scanf("%d",&a[i]);
    }
    for (int i = 1;i <= n;++i)
    {
        tre[i] = 1;
        for (int j = i - 1;j >= i - lowbit(i) + 1;j -= lowbit(j))
            tre[i] += tre[j];
    }
    for (int i = n;i > 0;--i)
    {
        int l = 1,rr = n;
        int k = a[i] + 1;
        while (l < rr)
        {
            int m = (l + rr) >> 1;
            if (sum(m) >= k) rr = m;
            else    l = m + 1;
        }
       //cout<<l+1<<endl;
        add(l,-1);
        r[i] = l;
    }
    for (int i = 1;i <= n;++i)  printf("%d\n",r[i]);
    return 0;
}