头像

马角的逆袭




离线:7小时前



题意 : 给定n (n<=1e5)个点的树, 对于每个点u输出u到其他节点v的路径和

input

5
1 2
1 3
3 4
3 5

output

6 9 5 8 8

记得以前见到过,但是不会写,所以来求大佬们指点一下,或则给个原题也行 QAQ




题目描述

翻译过来大概是这样

给定一个n个点不一定联通的图,
边权全部是1
连个联通块需要2的边权连接
问联通所有点的最小边权是多少 ?

  • 直接$dfs$求联通块个数,再算一下答案就行了
  • 或者用最小生成树求联通块(因为标签打的是最小生成树)
  • 并查集统计联通块个数的方法 : for一遍fa[]数组(爹数组),统计fa[i]==i的个数就是联通块个数
  • 全联通 ans=n-1
  • 不连通 ans=(n-1) + (cnt-1) cnt是联通块的个数

/**






]]]`    ]]]`  ]]]]   ,]]]`     .]@@@\].   ,]]`    ]]]`    ]]]]]]].   
.@@@^  /@@^    \@@\ ,@@@`    ,@@@@@@@@`   =@@@\   @@@^    @@@@@@@@  
  @@@^/@@^      ,@@@@@/     ,@@@.         =@@@@@` @@@^    @@    @@  
   \@@@@`        =@@@\      =@@^          =@@^,@@\@@@^    @@@@@@@@@. 
    @@@^        /@@@@@@`    =@@@.         =@@^ .\@@@@^    @@     @@ 
    @@@^      *@@@` ,@@@^    =@@@@@@@@^   =@@^   \@@@^    @@@@@@@@@` 
    [[[`     .[[[`   .[[[`     ,[@@@/[`   ,[[`    ,[[`    [[[[[[[.   









*/

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long 
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...)                             \
    do {                                       \
        cout << "\033[31;1m " << #x << " -> "; \
        err(x);                                \
    } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO {

    char print_f[105];
    void read() { }
    void print() { putchar('\n'); }

    template <typename T, typename... T2>
        inline void read(T &x, T2 &... oth) {
            x = 0;
            char ch = getchar();
            ll f = 1;
            while (!isdigit(ch)) {
                if (ch == '-') f *= -1; 
                ch = getchar();
            }
            while (isdigit(ch)) {
                x = x * 10 + ch - 48;
                ch = getchar();
            }
            x *= f;
            read(oth...);
        }
    template <typename T, typename... T2>
        inline void print(T x, T2... oth) {
            ll p3=-1;
            if(x<0) putchar('-'), x=-x;
            do{
                print_f[++p3] = x%10 + 48;
            } while(x/=10);
            while(p3>=0) putchar(print_f[p3--]);
            putchar(' ');
            print(oth...);
        }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, pre[MAXN], sz;

struct Edge {
    int u, v, w;
    bool operator < (const Edge& y) const {
        return w < y.w;
    }
} ed[MAXN];

void init() {
    sz = 0;
    for(int i=1; i<=n; i++) pre[i] = i;
}

int fa(int x) {
    return (x==pre[x]) ? x : (pre[x]=fa(pre[x]));
}

void union_xy(int x, int y) {
    int rx = fa(x), ry = fa(y);
    if(rx != ry)
        pre[ry] = rx;
}

void krsxxx() {
    // sort(ed+1, ed+sz+1); //初始边权全是1,可以不排序
    for(int i=1; i<=sz; i++) {
        int rx = fa(ed[i].u), ry = fa(ed[i].v);
        if(rx == ry) continue ;
        union_xy(ed[i].u, ed[i].v);
    }
}

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    // freopen("out_main", "w", stdout);
    clock_t stime = clock();
#endif
    read(Q);
    int cas = 0;
    while(Q--) {
        read(n, m);
        init();
        for(int i=1; i<=m; i++) {
            ++ sz;
            read(ed[sz].u, ed[sz].v);
            ed[sz].w = 1;
        }
        krsxxx();
        int cnt = 0;
        for(int i=1; i<=n; i++)
            if(pre[i] == i) cnt ++;
        if(cnt == 1)
            printf("Case #%d: %d\n", ++cas, n-1);
        else
            printf("Case #%d: %d\n", ++cas, (n-1) + (cnt-1));
    }





#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}




求颜色不同的最近点对

给定$2N$个点,每个点只能是红色或黑色,求最近点对(A,B),并且(A,B)颜色不能相同

y总的视频讲的非常好了!!
但是还是想推荐一波福建师范大学的老师讲的最近点对视频(1个小时左右)
https://www.bilibili.com/video/BV1wT4y1G7HE?from=search&seid=1546110901679554585

本题和普通的最近点对不同点是要求颜色不同
只需在求dist的时候加判断即可

double dist(Point& A, Point& B) {
    if(A.color == B.color) return 1e18; //颜色不同直接返回正无穷
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

然后就是分治法
如图:
13.jpeg

在中间矩形框内最多存在8个点,
所以我们按y轴归并排序后只需向后暴力8个点即可

double closep(int lef, int rig) {
    if(lef == rig) return 1e18;
    if(lef+1 == rig) return dist(a[lef], a[rig]);
    int mid = (lef + rig) >> 1;
    double ret = closep(lef, mid);
    ret = min(ret, closep(mid+1, rig));
#if 1
    double mid_x = a[mid].x;

    int i = lef, j = mid+1, sz = 0;
    while(i<=mid && j<=rig)  { //按y归并
        if(a[i].y < a[j].y) T[++sz] = a[i++];
        else T[++sz] = a[j++];
    }
    while(i <= mid) T[++sz] = a[i++];
    while(j <= rig) T[++sz] = a[j++];

    for(i=1, j=lef; i<=sz; i++, j++) a[j] = T[i];

    sz = 0;
    for(i=lef, j=lef; i<=rig; i++) //把所有矩形框内的点筛选出来到T[]里
        if(fabs(a[i].x-mid_x) < ret) T[++sz] = a[i];

    for(i=1; i<=sz; i++) //每个点只需向后面暴力8个点
        for(j=i+1; j<=min(sz, i+8); j++) 
            ret = min(ret, dist(T[i], T[j]));
#endif 
    return ret;
}

完整代码如下

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)4e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
    do { \
        cout << "\033[31;1m " << #x << " -> "; \
        err(x); \
    } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

    char print_f[105];
    void read() {}
    void print() { putchar('\n'); }

    template <typename T, typename... T2>
        inline void read(T &x, T2 &... oth) {
            x = 0;
            char ch = getchar();
            ll f = 1;
            while (!isdigit(ch)) {
                if (ch == '-') f *= -1; 
                ch = getchar();
            }
            while (isdigit(ch)) {
                x = x * 10 + ch - 48;
                ch = getchar();
            }
            x *= f;
            read(oth...);
        }
    template <typename T, typename... T2>
        inline void print(T x, T2... oth) {
            ll p3=-1;
            if(x<0) putchar('-'), x=-x;
            do{
                print_f[++p3] = x%10 + 48;
            } while(x/=10);
            while(p3>=0) putchar(print_f[p3--]);
            putchar(' ');
            print(oth...);
        }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;
//平面上的颜色不同的最近点对

//给定2N个点,每个点可能是红色,可能是黑色,求颜色不同的最近点对

struct Point {
    double x, y;
    bool color;
} a[MAXN], T[MAXN];

bool cmpx(Point& A, Point& B) {
    return A.x==B.x ? A.y < B.y : A.x < B.x;
}

double dist(Point& A, Point& B) {
    if(A.color == B.color) return 1e18; //颜色不同直接返回正无穷
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

double closep(int lef, int rig) {
    if(lef == rig) return 1e18;
    if(lef+1 == rig) return dist(a[lef], a[rig]);
    int mid = (lef + rig) >> 1;
    double ret = closep(lef, mid);
    ret = min(ret, closep(mid+1, rig));
#if 1
    double mid_x = a[mid].x;

    int i = lef, j = mid+1, sz = 0;
    while(i<=mid && j<=rig)  { //按y归并
        if(a[i].y < a[j].y) T[++sz] = a[i++];
        else T[++sz] = a[j++];
    }
    while(i <= mid) T[++sz] = a[i++];
    while(j <= rig) T[++sz] = a[j++];

    for(i=1, j=lef; i<=sz; i++, j++) a[j] = T[i];

    sz = 0;
    for(i=lef, j=lef; i<=rig; i++) //把所有矩形框内的点筛选出来到T[]里
        if(fabs(a[i].x-mid_x) < ret) T[++sz] = a[i];

    for(i=1; i<=sz; i++) //每个点只需向后面暴力8个点
        for(j=i+1; j<=min(sz, i+8); j++) 
            ret = min(ret, dist(T[i], T[j]));
#endif 
    return ret;
}

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    scanf("%d ", &Q);
    while(Q--) {
        scanf("%d ", &n);
        for(int i=1; i<=n; i++) {
            scanf("%lf %lf ", &a[i].x, &a[i].y);
            a[i].color = 0;
        }
        for(int i=n+1; i<=(n<<1); i++) {
            scanf("%lf %lf ", &a[i].x, &a[i].y);
            a[i].color = 1;
        }
        sort(a+1, a+1+(n<<1), cmpx); //注意要先按y轴排序
        double ans = closep(1, (n<<1));
        printf("%.3lf\n", ans);
    }





#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}







马角的逆袭
2019-09-01 14:39

题目描述

样例


算法1 O(n)

遍历nums[1, n], 对于每个num[i], 求nums[i]-minv (minv是nums[1, i-1]里的最小值), 遍历一遍保留最大即可
‘’‘

class Solution {
public:
int maxDiff(vector[HTML_REMOVED]& nums) {
if(nums.empty()) return 0;
int minv = nums[0], ret = 0;
for(int i=1; i[HTML_REMOVED] minv) ret = max(ret, nums[i]-minv);
minv = min(minv, nums[i]);
}
return ret;
}
};

’‘’




马角的逆袭
2019-06-12 14:02

题目描述

blablabla

每次push(x)都用lower_bound(v.begin(), v.end(), x)查找x的位置插入, 类似插入排序
pop()时也删除对应vector里栈顶元素的值就好啦
很low的一种做法 T_T

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    vector<int> v; //有序的数组
    stack<int> stk;

    MinStack() {

    }

    void push(int x) {
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), x);
        v.insert(it, x); //把x插入合适的位置
        stk.push(x);
    }

    void pop() {
        int t = stk.top();
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), t); //从有序的vector里找出栈顶元素的位置 删掉
        stk.pop();
        v.erase(it);
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return v[0];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



马角的逆袭
2019-06-09 06:37

题目描述

class Solution {
public:
int NumberOf1(int n) {
unsigned int tn = (unsigned int) n, rs = 0;
while(tn) {
if(tn & 1) rs ++;
tn >>= 1;
}
return rs;
}
};

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



马角的逆袭
2019-06-09 06:31

题目描述

其实就是用并查集判断啦 模板题哟

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#define test "AcWing_联通块点的数量.txt" 
#define MAXN 100005
#include <string.h>
#include <iostream>
using namespace std;

int pre[MAXN], sum[MAXN], n, m;

void init() {
    for(int i=1; i<=n; i++)
        pre[i] = -1, sum[i] = 1;
}

int fa(int x) {
    int ret = x;
    while(pre[ret] != -1)
        ret = pre[ret];
    if(ret != x)
        pre[x] = ret;
    return ret;
}

bool union_xy(int x, int y) {
    int rx = fa(x), ry = fa(y);
    if(rx != ry) {
        sum[rx] += sum[ry];
        pre[ry] = rx; 
        return true;
    }
    return false;
}

int main(void) {
    freopen(test, "r", stdin);
    for( ; EOF != scanf("%d %d", &n, &m); ) {
        init();
        for( ; m--; ) {
            char c[4];
            int x, y;
            scanf("%s", c);

            if(c[0] == 'C') {
                scanf("%d %d", &x, &y);
                union_xy(x, y);
            } else if(c[1] == '1') {
                scanf("%d %d", &x, &y);
                printf("%s\n", fa(x)==fa(y) ? "Yes" : "No");
            } else if(c[1] == '2') {
                scanf("%d", &x);
                printf("%d\n", sum[fa(x)]);
            }
        }
    }
    return 0;
}
----------

### 算法2
##### (暴力枚举)  $O(n^2)$

blablabla

时间复杂度分析:blablabla


#### C++ 代码

blablabla
```




马角的逆袭
2019-06-09 03:46

题目描述

题目说要反转链表,我用的方法比较水, 遍历链表的同时把值压到栈里,再遍历一遍赋值就好了
l看了别人的解法, 感觉自己的方法Low到爆了 T_T …

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode
next;
* ListNode(int x) : val(x), next(NULL) {}
* };
/

include [HTML_REMOVED]

using namespace std;

class Solution {
public:
ListNode reverseList(ListNode h) {
stack[HTML_REMOVED] stk;
ListNode head = h;
while(head) {
stk.push(head->val);
head = head->next;
}
int i=0;
ListNode
h2 = h;
while(h2) {
h2->val = stk.top();
stk.pop();
h2 = h2->next;
}
return h;
}
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla