头像

ACautoman




在线 


最近来访(20)
用户头像
TinyDolphin
用户头像
霜满地
用户头像
Galen_FuckPPT
用户头像
newSoul
用户头像
evecome
用户头像
Hebuter_04
用户头像
Jsss
用户头像
硫化细菌
用户头像
Sdeyuwsatan
用户头像
TTYYAA
用户头像
alex2007
用户头像
zyaichirou
用户头像
ENDING
用户头像
从你的全世界路过_2
用户头像
Meteor_Z
用户头像
feixue
用户头像
someone
用户头像
frynb


ACautoman
19小时前
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
int fa[N], cnt[N];

int _find(int x)
{
    if(fa[x] != x)  fa[x] = _find(fa[x]);
    return fa[x];
}

int main()
{
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++) fa[i] = i,cnt[i] = 1;

    while(m--)
    {
        char op[3];
        int a, b;
        scanf("%s",op);

        if(op[0] == 'C')
        {
            scanf("%d%d",&a,&b);
            int t1 = _find(a);
            int t2 = _find(b);
            if(t1 != t2)//已在同一个连通块中
            {
                fa[t1] = t2;//t1并到t2中,即a并入b
                cnt[t2] += cnt[t1];
            }
        }

        else if(op[1] == '1')
        {
            scanf("%d%d",&a,&b);
            if(_find(a) == _find(b))    puts("Yes");
            else puts("No");
        }

        else
        {
            scanf("%d",&a);
            printf("%d\n",cnt[_find(a)]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

ACautoman
23小时前
#include <iostream>

using namespace std;
const int N = 1e5+10;
int fa[N], n, m;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) fa[i] = i;

    while(m--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if(op[0] == 'M')
        {
            fa[find(a)] = find(b);
        }

        if(op[0] == 'Q')
        {
            if(find(a) == find(b))  printf("Yes\n");
            else    printf("No\n");
        }
    }
    return 0;
}

并查集寻找祖宗+状态压缩

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


活动打卡代码 AcWing 838. 堆排序

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5+10;

int h[N], len, n, m;

void down(int index)//下标
{
    int t = index;
    int lson = t << 1, rson = t << 1 | 1;
    if(lson <= len && h[lson] < h[t])   t = lson;
    if(rson <= len && h[rson] < h[t])   t = rson;
    //此时 t是三个结点中的最小编号

    if( t != index )//根节点不是最小值
    {
        swap(h[index], h[t]);
        //现在t是所指元素是从第一次调用down的index所指元素 继续将他向下down直到不能down为止
        down(t);
    }
    //当index == t 的时候 down就停止了
}

int top()
{
    return h[1];
}

int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
    len = n;

    for(int i = n / 2; i; i--)  down(i);//构建堆

    while( m -- )
    {
        printf("%d ",top());
        h[1] = h[len];//删除堆顶(用最后一个数覆盖第一个数) 并且长度 减1
        len -- ;
        down(1);
    }

    return 0;
}


活动打卡代码 AcWing 875. 快速幂

#include <iostream>

using namespace std;
typedef long long LL;

void qmi ( int a, int k, int p)//快速幂函数
{
    int res = 1;
    while ( k )//当k不为0
    {
        if( k & 1 ) res = (LL)res * a % p;//如果k的第一位是1 将准备好的幂与答案相乘
        k >>= 1;//k右移
        a = (LL)a * a % p;//准备好下一个幂
    }

    return res;
}

int main()
{
    int t, a, k, p;
    scanf("%d",&t);//多组读入
    while (t -- )
    {
        scanf("%d%d%d",&a, &k, &p);
        printf("%d\n",qmi(a, k, p));
    }
    return 0;
}



11.png

二分法 o(logn)

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty())    return 0;//当nums数组为空的时候 缺的就是0

        //求的是橙色区间的首下标 返回r
        int l = 0, r = nums.size() - 1;
        while ( l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] == mid)    l = mid + 1;//if(在蓝色区域)    
            else r = mid;//反之
        }
        return r == nums[r] ? r + 1 : r;//当nums数组全部跟下标对应 缺的就是r加1

    }
};



class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.size() < 1)    return 0;

        int l = 0, r = nums.size() - 1;
        while ( l < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] != mid)    r = mid;
            else l = mid + 1;
        }
        return l == nums[l]? l + 1 : l;
    }
};



有序多重集 multiset的count功能

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        multiset<int> s;

        for(auto c : nums)    s.insert(c);

        return s.count(k);
    }
};

二分法找到左边界和右边界即可

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int l = -1, r = nums.size();
        while ( l + 1 < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] < k)   l = mid;
            else r = mid;
        }
        int left = l;

        l = -1, r = nums.size();
        while ( l + 1 < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] <= k)   l = mid;
            else r = mid;
        }
        int right = l;

        return right - left;
    }
};


活动打卡代码 AcWing 845. 八数码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

int bfs(string s)
{
    queue<string> q;
    unordered_map<string, int> dis;

    q.push(s);
    dis[s] = 0;

    string ans = "12345678x";
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};


    while ( q.size() )
    {
        string t = q.front();
        q.pop();

        if(t == ans)    return dis[t];

        int distance = dis[t];
        //建图
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if( xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
            {
                swap(t[k], t[xx*3 + yy]);

                if(!dis.count(t))
                {
                    q.push(t);
                    dis[t] = distance + 1;   
                }

                swap(t[k], t[xx*3 + yy]);
            }
        }
    }
    return -1;
}

int main()
{
    string s;
    for(int i = 0; i < 9; i ++)
    {
        char c;
        cin >> c;
        s += c;
    }

    cout << bfs(s);
    return 0;

}



ACautoman
10天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        int la = 0, lb = 0;
        for(auto i = headA; i; i = i->next) la++;
        for(auto i = headB; i; i = i->next) lb++;

        //默认为la > lb
        auto i = headA, j = headB;
        int k = la - lb;
        if(la - lb < 0)//若la < lb
        {
            i = headB, j = headA;
            k = lb - la;
        }

        while(k--)  i = i->next;

        while (i)
        {
            if(i == j)  return i;
            i = i->next;
            j = j->next;
        }
        return NULL;
    }
};


活动打卡代码 AcWing 35. 反转链表

ACautoman
10天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if( !head || !head->next)   return head;
        auto cur = head;
        ListNode* prev = NULL;
        //cur是头结点 prev是头结点的前驱节点 初始为NULL
        while ( cur )//不为空的时候
        {
            auto next = cur->next;//next为cur的转移做好准备
            cur->next = prev;//反转的实现
            prev = cur, cur = next;//prev和cur都后移一格
        }

        return prev;//当cur指向空的时候 prev就是反转后的头结点
    }
};