2018-08-04

nowcoder contest6

测试比赛环境是否支持__int128;

树上任意两个节点之间的距离的求解

可以说是一个板子题了，只要统计每一条边对答案产生的贡献的次数

hdu2376

一遍dfs就可以了

ac code

时间复杂度为O(n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
int n;
struct Edge{
    int v, w;
};
vector<Edge> G[maxn];
int num[maxn];
ll dp[maxn];
void init(){
    memset(num, 0, sizeof(num));
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<maxn; i++)G[i].clear();
}
void dfs(int u, int fa){
    num[u] = 1;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i].v;
        ll w = G[u][i].w;
        if(v == fa) continue;
        dfs(v, u);
        num[u] += num[v];
        dp[u] += dp[v]+1ll*(n-num[v])*num[v]*w;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    scanf("%d", &_);
    while(_--){
        init();
        scanf("%d", &n);
        int u, v, w;
        for(int i=0; i<n-1; i++){
            scanf("%d%d%d", &u, &v, &w);
            G[u].push_back(Edge{v, w});
            G[v].push_back(Edge{u, w});
        }
        dfs(0, -1);
        printf("%.8lf\n", 1.0*dp[0]/(n*(n-1))*2);
    }
    return 0;
}

I team rocket

题目里面有一个很奇怪的运算，目的就是为了强制在线。

可以使用权值线段树(zkw)来维护
要维护删除区间的操作，操作简化为一个点
若使用树状数组来维护，就要对纵坐标排序，

树状数组

感觉有点骚，还是应该学习一下线段树的做法

AC code

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n , m , X[N] , Y[N];
int d[N] , D , o[N] , v[N];
vector<int> c[N];
int lowbit(int x){
    return x&(-x);
}
struct Node{
    int y;
    int id;
}node[N];
bool cmp1(Node a, Node b){
    return a.y<b.y;
}
void work() {
    scanf("%d%d" , &n , &m);
    D = 0;
    //n个坐标
    for (int i = 1 ; i <= n ; ++ i) {
        scanf("%d%d" , X + i , Y + i);
        d[D ++] = X[i];
    }
    //离散化
    sort(d , d + D);
    D = unique(d , d + D) - d;
    for (int i = 1 ; i <= n ; ++ i) {
        //o[i] = i;//什么意思？保存y的下标
        X[i] = lower_bound(d , d + D , X[i]) - d + 1;
        c[i].clear();
        v[i] = 0;//vis?
    }
    //对Y排序，保存排好序后y的下标
    for(int i=1; i<=n; i++){
        node[i].y = Y[i];
        node[i].id = i;
    }
    sort(node+1, node+n+1, cmp1);
//    sort(o + 1 , o + n + 1 , [&](int x , int y) {
//            return Y[x] < Y[y];
//        });
    for (int i = 1 ; i <= n ; ++ i) {
        int j = node[i].id;
        //lowbit
        for (int k = X[j] ; k <= n ; k += lowbit(k)) {
            c[k].push_back(j);
        }
    }
    int res = 0;
    for (int i = 1 ; i <= m ; ++ i) {
        int x;
        scanf("%d" , &x);
        x ^= res;
        int j = upper_bound(d , d + D , x) - d;
        int cnt = 0;
        res = 1;
        for (int k = j ; k > 0 ; k -= lowbit(k)) {
            while (!c[k].empty() && Y[c[k].back()] >= x) {
                int w = c[k].back();
                if (!v[w]) {
                    v[w] = i;//第几次被弹出来
                    ++ cnt;
                    res = (long long)res * w % 998244353;//横坐标的乘积
                }
                c[k].pop_back();
            }
        }
        printf("%d\n" , cnt);
        if (cnt == 0) res = 0;
    }
    for (int i = 1 ; i <= n ; ++ i) {
        printf("%d%c" , v[i] , " \n"[i == n]);
    }
}
int main() {
    int T;
    scanf("%d" , &T);
    while (T --) {
        static int ca = 0;
        printf("Case #%d:\n" , ++ ca);
        work();
    }
}

未解决的问题

本文标题:nowcoder contest6

文章作者:Babydragon

发布时间:2018-08-04, 18:00:00

最后更新:2018-08-05, 10:56:43

原始链接:http://baolintian.github.io/2018/08/04/nowcoder-contest6/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。