Good Bye 2014 题解

【A】水题，模拟。

【B】首先通过可以交换的矩阵建立可以交换的关系，这个用并查集可以搞定，然后暴力交换找到最小的就可以了！

【代码君】

int n, a[333], fa[maxn];
char b[333][333];
int Find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = Find(fa[x]);
}
void Union(int x, int y)
{
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}

int main()
{
    while(scanf("%d",&n) != EOF)
    {
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
            fa[i] = i;
        }
        for(int i = 0; i < n; i++){
            scanf("%s",b[i]);
            for(int j = 0; j < n; j++){
                if(b[i][j] == '1'){
                    Union(a[i],a[j]);
                }
            }
        }
        for(int i = 0 ;i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(Find(a[i]) == Find(a[j]) && a[i] > a[j]) swap(a[i], a[j]);
            }
        }
        for(int i = 0; i < n; i++){
            printf("%d%c",a[i],i==n-1?'\n':' ');
        }
    }
}

【C】题意：

有n（500）本书，成一摞。
我们有一个看书的顺序。
要看第i本书的时候，
我们要——
1，把这本书之上的书搬走，体力成本加上这本书之上的书的重量之和，再放回之上的所有书（不改变顺序）；
2，看这本书，把这本书放在最上面。
问你初始的书从上到下的顺序可以是怎么样，能够使得我们的体力成本最小

【解题方法】脑洞。实际上最开始的摆放顺序就是最优的，直接计算答案即可！

【代码君】

int n, m, w[maxn], b[maxn], vis[maxn];

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int ans = 0;
        for(int i = 1; i <= n; i++) scanf("%d",&w[i]);
        for(int i = 1; i <= m; i++) scanf("%d",&b[i]);
        for(int i = 1; i <= m; i++){
            memset(vis, 0 ,sizeof(vis));
            for(int j = i-1; j >= 1; j--){
                if(b[i] == b[j]) break;
                if(!vis[b[j]]){
                    ans = ans + w[b[j]];
                    vis[b[j]] = 1;
                }
            }
        }
        printf("%d\n",ans);
    }
}

【D】题意：

有n（1e5）个城市和n-1条边，构成一棵树。
同时我们会有q（1e5）次修改操作。
对于每次操纵，我们把一条边的边权减小l。
每次操作之后，我们任意选3个点，问你这三个点之间3条路径的距离之和的期望是多少。

【解题方法】

我们不妨以1为树根，然后研究每条边。
我们可以通过dfs，得到每条边的上下各有多少个点。
假如说在一条边i的上面有sz[i]个点，下面有n-sz[i]个点。
那么，我们就有C(sz[i],1)*C(n-sz[i],2)+C(sz[i],2)*C((n-sz[i]),1)种方案选到这条边
于是，我们累计每条边被选中的方案*边权，再/=方案数，答案就出来啦！
然而，我这样算出来的答案有问题，只有实际答案的一半，为什么呢？
因为有C(sz[i],1)*C(n-sz[i],2)+C(sz[i],2)*C((n-sz[i]),1)种方案选到这条边
而每个方案中，这个边权都被我们走了2次。于是最后再*2就可以啦
为了不最后乘这个数，我直接在中间乘上2了！

【代码君】

int n, q, cnt, sz[maxn];
struct EDGE{
    int u, v, w;
}E[maxn];
vector<int>g[maxn];
void dfs(int u, int fa)
{
    sz[u] = 1;
    for(int i = 0; i < (int)g[u].size(); i++){
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 1; i <= n; i++) g[i].clear();
        //cnt = 0;
        for(int i = 1; i < n; i++){
            scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
            int u = E[i].u, v = E[i].v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 1);
        double ans = 0;
        for(int i = 1; i < n; i++){
            int u = E[i].u, v = E[i].v, w = E[i].w;
            int x = min(sz[u], sz[v]), y = n - x;
            ans = ans + (1.0*x*(x-1)*y + 1.0*y*(y-1)*x)*w;
        }
        //cout<<ans<<endl;
        scanf("%d",&q);
        while(q--)
        {
            int r, w;
            scanf("%d%d",&r,&w);
            int x = min(sz[E[r].u], sz[E[r].v]), y = n - x;
            ans = ans + (1.0*x*(x-1)*y + 1.0*y*(y-1)*x)*(w - E[r].w);
            E[r].w = w;
            printf("%.6f\n", (double)ans*6/n/(n-1)/(n-2));
        }
    }
}

【E】参考blog http://blog.csdn.net/snowy_smile/article/details/50942417 orzzz。。

【代码君】

//
//Created by just_sort 2016/10/24
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
#define MP(x,y) make_pair(x,y)
typedef long long LL;
const int maxn = 200005;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

int p[maxn], l[maxn], n, m, top;
vector <pair<int, int> > q[maxn];
int sta[maxn], cost[1 << 19];
int ans[maxn];
struct node{
    int l, r, cost;
}Tree[maxn*4];

void pushdown(int rt)
{
    if(Tree[rt].cost)
    {
        Tree[rt*2].cost += Tree[rt].cost;
        Tree[rt*2+1].cost += Tree[rt].cost;
        Tree[rt].cost = 0;
    }
}

void Build(int l, int r, int rt)
{
    Tree[rt].l = l, Tree[rt].r = r;
    if(l == r){
        Tree[rt].cost = 0;
        return ;
    }
    int mid = (l + r) / 2;
    Build(l, mid, rt*2);
    Build(mid+1, r, rt*2+1);
}

void update(int L, int R, int v, int rt)
{
    if(L == Tree[rt].l && Tree[rt].r == R)
    {
        Tree[rt].cost += v;
        return ;
    }
    pushdown(rt);
    int mid = (Tree[rt].l + Tree[rt].r) / 2;
    if(R <= mid) update(L, R, v, rt*2);
    else if(L > mid) update(L, R, v, rt*2+1);
    else{
        update(L, mid, v, rt*2);
        update(mid+1, R, v, rt*2+1);
    }
}

int queryans(int pos, int rt)
{
    if(Tree[rt].l == Tree[rt].r)
    {
        return Tree[rt].cost;
    }
    pushdown(rt);
    int mid = (Tree[rt].l + Tree[rt].r) / 2;
    if(pos <= mid) return queryans(pos, rt*2);
    else return queryans(pos, rt*2+1);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 1; i <= n; i++){
            scanf("%d%d",&p[i],&l[i]);
            l[i] += p[i];
        }
        scanf("%d", &m);
        for(int i = 1; i <= m; i++){
            int x, y;
            scanf("%d%d", &x, &y);
            q[y].push_back(MP(x, i));
        }
        Build(1, n, 1);
        sta[0] = top = 0;
        int L, R, V, pos;
        for(int i = 1; i <= n; i++)
        {
            while(top && l[sta[top]] < p[i])
            {
                L = sta[top - 1] + 1;
                R = sta[top];
                V = p[i] - l[sta[top]];
                update(L, R, V, 1);
                --top;
            }
            for(int j = q[i].size() - 1; j >= 0 ; j--)
            {
                pos = q[i][j].first;
                ans[q[i][j].second] = queryans(pos, 1);
            }
            while(top && l[sta[top]] <= l[i]) --top;
            sta[++top] = i;
        }

        //
        for(int i = 1; i <= m; i++)
        {
            printf("%d\n", ans[i]);
        }
    }
}