DQS DQS

HIT Summer Training Contest2

辛苦打了一周的rating一天掉没了,非常伤心

智商不够,不会做构造题…………


A : hdu - 5723

给一张图,求最小生成树,以及在最小生成树上任选两点的距离长度期望值。

每条边被计算的次数是左右两边点数之积。

死于少个强转longlong…………

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,head[SZ],nxt[SZ],tot = 1,sz[SZ];

struct edge2
{
    int t;
    double d;
}l[SZ];

void build(int f,int t,double d)
{
    l[++ tot] = (edge2){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}

int f[SZ];

void dfs(int u,int fa)
{
    sz[u] = 1;
    f[u] = fa;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
    }
}

struct edge
{
    int f,t;
    double d;
}ll[SZ];

bool cmp(edge a,edge b)
{
    return a.d < b.d;
}

int fa[SZ];

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

bool use[SZ];

int main()
{
    int T = read();
    while(T --)
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(use,0,sizeof(use));
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i ++) fa[i] = i;
        for(int i = 1;i <= m;i ++)
            scanf("%d%d%lf",&ll[i].f,&ll[i].t,&ll[i].d);
        if(n == 1) { printf("0 0\n"); continue; }
        sort(ll + 1,ll + 1 + m,cmp);
        double ans1 = 0;
        for(int i = 1;i <= m;i ++)
        {
            int a = ll[i].f,b = ll[i].t;
            int x = find(a),y = find(b);
            if(x != y)
            {
                fa[x] = y;
                ans1 += ll[i].d;
                build(a,b,ll[i].d); build(b,a,ll[i].d);
                use[i] = 1;
            }
        }
        dfs(1,0);
        double ans2 = 0,sum = 0;
        for(int i = 1;i <= m;i ++)
        {
            if(use[i])
            {
                int a = ll[i].f,b = ll[i].t;
                if(f[b] == a) swap(a,b);
                sum += (double)sz[a] * (n - sz[a]) * ll[i].d * 2.0 / ((double)n * (n - 1));
            }
        }
        printf("%.0f %.2f\n",ans1,sum);
    }
    return 0;
}
/*

*/


B : codeforces - 567E


C : hdu - 1285

拓扑排序,要求点的编号小的优先,所以可以用个堆

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,rd[SZ],ans[SZ];
vector<int> g[SZ];
priority_queue<int> q;

void toposort()
{
    while(q.size()) q.pop();
    int tot = 0;
    for(int i = 1;i <= n;i ++)
        if(!rd[i])
            q.push(-i);
    while(q.size())
    {
        int u = -q.top(); q.pop();
        ans[++ tot] = u;
        for(int i = 0;i < g[u].size();i ++)
        {
            int v = g[u][i];
            if(!-- rd[v])
                q.push(-v);
        }
    }
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n;i ++) g[i].clear();
        memset(rd,0,sizeof(rd));
        for(int i = 1;i <= m;i ++)
        {
            int x = read(),y = read();
            g[x].push_back(y); rd[y] ++;
        }
        for(int i = 1;i <= n;i ++)
            sort(g[i].begin(),g[i].end());
        toposort();
        for(int i = 1;i <= n;i ++)
            printf("%d%c",ans[i],i == n ? '\n' : ' ');
    }
    return 0;
}


D : hdu - 5876

给一张无权图,求反图的最短路。

因为无权,所以反图最短路相当于反图bfs。用链表维护待拓展点集,一个点被拓展那么就把它删去。复杂度O(n)。

注意不能用set,因为迭代器在容器变化后失效。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

queue<int> q;
int vis[SZ],dist[SZ];

int nx[SZ],pre[SZ];

void erase(int v)
{
    nx[pre[v]] = nx[v];
    pre[nx[v]] = pre[v];
}


void spfa(int s)
{
    memset(dist,63,sizeof(dist));
    memset(vis,0,sizeof(vis));
    int cnt = 0;
    dist[s] = 0;
    q.push(s);
    for(int i = 0;i <= n;i ++) nx[i] = (i + 1) % (n + 1);
    for(int i = 0;i <= n;i ++) pre[nx[i]] = i;

    erase(s);
//    for(int i = 0;i <= n;i ++)
//        printf("%d %d\n",pre[i],nx[i]);
    while(q.size())
    {
        int u = q.front(); q.pop();
    //    cout << u << endl;
        cnt ++;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i];
            vis[v] = cnt;
        }
        for(int v = nx[0];v;v = nx[v])
        {
            if(vis[v] == cnt) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
            erase(v);
        }
    }
}



int main()
{
    int T = read();
    while(T --)
    {
        memset(head,0,sizeof(head)); tot = 1;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= m;i ++)
        {
            int x = read(),y = read();
            build(x,y); build(y,x);
        }
        int s = read();
        spfa(s);
        for(int i = 1,j = 0;i <= n;i ++)
            if(i != s)
                printf("%d%c",dist[i] >= INF ? -1 : dist[i],++ j == n - 1 ? '\n' : ' ');
    }
    return 0;
}
/*
233
4 3
1 2
1 3
1 4
1
4 3
2 3
3 4
4 2
1

*/


E : codeforces - 61E

给一个序列,求长度为三的递减子序列的个数。

树状数组统计左边比它大的数的个数,右边比它小的个数,枚举中间点。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 5000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,a[SZ],lsh[SZ];

int bit[SZ],f1[SZ],f2[SZ];

int add(int x,int d)
{
    for(int i = x;i <= n;i += i & -i)
        bit[i] += d;
}

int ask(int x)
{
    int ans = 0;
    for(int i = x;i > 0;i -= i & -i)
        ans += bit[i];
    return ans;
}


int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        a[i] = read(),lsh[i] = a[i];
    sort(lsh + 1,lsh + 1 + n);
    for(int i = 1;i <= n;i ++)
        a[i] = lower_bound(lsh + 1,lsh + 1 + n,a[i]) - lsh;
    for(int i = 1;i <= n;i ++)
    {
        int x = a[i];
        f1[i] = ask(n) - ask(x);
        add(x,1);
    }
    memset(bit,0,sizeof(bit));
    for(int i = n;i >= 1;i --)
    {
        int x = a[i];
        f2[i] = ask(x);
        add(x,1);
    }
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += (LL)f1[i] * f2[i];
    printf("%I64d",ans);
    return 0;
}
/*
233
4 3
1 2
1 3
1 4
1
4 3
2 3
3 4
4 2
1

*/


F : codeforces - 383C

给一棵带点权的树,两个操作:

1.给某个点的权值+d,它的儿子-d,它的孙子+d...直到叶子

2.询问某个点的点权。

可以发现,执行1操作后,子树中点权的变化为$(-1)^{D_v-D_u}*d$。D意为某点的深度。

化简得:变化为$\frac{d}{(-1)^{D_u}}*D_v$。

可以发现前半部分是一个常数,后面对于每个点也是常数。所以可以维护前面的那个系数,这样就成了区间加,询问时询问单点权值。由于是子树操作,所以可以线段树+dfs序。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int suf[SZ],pre[SZ],dfs_clock = 0,dep[SZ];
void dfs(int u,int fa)
{
    dep[u] = dep[fa] + 1;
    pre[u] = ++ dfs_clock;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(v == fa) continue;
        dfs(v,u);
    }
    suf[u] = ++ dfs_clock;
}


struct seg
{
    int l,r,sum,d;
}tree[SZ << 2];

void build_seg(int p,int l,int r)
{
    tree[p].l = l; tree[p].r = r;
    tree[p].sum = tree[p].d = 0;
    if(l == r) return ;
    int mid = l + r >> 1;
    build_seg(p << 1,l,mid); build_seg(p << 1 | 1,mid + 1,r);
}

void update(int p)
{
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

void pushdown(int p)
{
    if(tree[p].d)
    {
        int d = tree[p].d;
        tree[p << 1].d += d;
        tree[p << 1].sum += d * (tree[p << 1].r - tree[p << 1].l + 1);
        tree[p << 1 | 1].d += d;
        tree[p << 1 | 1].sum += d * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1);
        tree[p].d = 0;
    }
}

void change(int p,int l,int r,int d)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        tree[p].d += d;
        tree[p].sum += d * (tree[p].r - tree[p].l + 1);
        return ;
    }
    pushdown(p);
    int mid = tree[p].l + tree[p].r >> 1;
    if(l <= mid) change(p << 1,l,r,d);
    if(mid < r) change(p << 1 | 1,l,r,d);
    update(p);
}

int ask(int p,int l,int r)
{
    if(l <= tree[p].l && tree[p].r <= r)
        return tree[p].sum;
    pushdown(p);
    int mid = tree[p].l + tree[p].r >> 1;
    int ans = 0;
    if(l <= mid) ans += ask(p << 1,l,r);
    if(mid < r) ans += ask(p << 1 | 1,l,r);
    return ans;
}

int a[SZ];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        a[i] = read();
    for(int i = 1;i <= n - 1;i ++)
    {
        int x = read(),y = read();
        build(x,y); build(y,x);
    }
    dfs(1,0);
    build_seg(1,1,dfs_clock);
    for(int i = 1;i <= m;i ++)
    {
        int opt = read();
        if(opt == 1)
        {
            int x = read(),val = read();
            int mi = dep[x] & 1 ? -1 : 1;
        //    cout << val * mi << endl;
            change(1,pre[x],suf[x],val * mi);
            //cout << opt << " " << x << " " << val << endl;
        }
        else
        {
            int x = read();
            int mi = dep[x] & 1 ? -1 : 1;
            printf("%d\n",ask(1,pre[x],pre[x]) * mi + a[x]);
        }
    }
    return 0;
}
/*

*/


G : codeforces - 582A

有一列数$a_i$,一个表格中$(i,j)$点中存有$gcd(a_i,a_j)$。现在给出表中n*n个元素的乱序,求原来的长度为n的序列$a_i$。

可以发现n个元素都出现在这些n*n个元素之中。

对于这些数,最大值一定是原序列中的元素,因为它不可能是其他数的约数,于是从原表中删除。再取出一个最大数,删去它和第一个最大数的gcd(要删两次),再把它从表中删除,这样再取出的最大数一定也在答案中。

于是每次取出最大数,然后删去它和已有答案中的数的gcd,重复n次就得到了答案。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 5000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a % b);
}

int n,m,a[SZ],ans[SZ];

multiset<int> S;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n * n;i ++)
        a[i] = read(),S.insert(a[i]);
    int tot = 0;

    set<int> :: iterator it = S.end(); it --;
    ans[++ tot] = *it;
    S.erase(it);
    while(S.size())
    {
        it = S.end(); it --;
        int x = *it; S.erase(it);
        for(int i = 1;i <= tot;i ++)
        {
            int d = gcd(x,ans[i]);
            it = S.find(d); S.erase(it);
            it = S.find(d); S.erase(it);
        }
        ans[++ tot] = x;
    }
    for(int i = 1;i <= tot;i ++)
        printf("%d ",ans[i]);
    return 0;
}
/*
233
4 3
1 2
1 3
1 4
1
4 3
2 3
3 4
4 2
1

*/


H : codeforces - 141C

给出n个人,以及每个人前面比他高的人的个数,求一个满足要求的排列以及给出一个高度的解。

先对这些人按前面比他高的人的人数排序。

考虑让高度第i低的人高度为i。

如果全为0,则可以高度递增排序。

如果第i个人前面比他高的人不为0,记为v,则令从他前面的那个人向前累计v个人的这些人高度比他高。这样它的高度为i-v,而比他高的人的高度需要全部+1。

无解的情况即为前面的人不够满足v。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


struct haha
{
    string name;
    int v;
}l[SZ],ans[SZ];

bool cmp(haha a,haha b) { return a.v < b.v; }

char str[SZ];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        int x;
        scanf("%s%d",str,&x);
        l[i].name = str;l[i].v = x;
    }
    sort(l + 1,l + 1 + n,cmp);
    if(l[1].v >= 1) { puts("-1"); return 0; }
    ans[1] = (haha){l[1].name,1};
    for(int i = 2;i <= n;i ++)
    {
        if(l[i].v >= i) { puts("-1"); return 0; }
        if(l[i].v == 0) ans[i] = (haha){l[i].name,i};
        else
        {
            ans[i] = (haha){l[i].name,i - l[i].v};
            for(int j = 1;j < i;j ++)
                if(ans[j].v >= ans[i].v)
                    ans[j].v ++;
        }
    }
    for(int i = 1;i <= n;i ++)
        cout << ans[i].name << " "<< ans[i].v << endl;
    return 0;
}
/*

*/


I : LYDSY - 2733

启发式合并水题……

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;


struct node
{
    node *f,*ch[2];
    int v,sz,cnt;

    void setc(node *x,int d) { (ch[d] = x) -> f = this; }
    int dir() { return f -> ch[1] == this; }
    void maintain()
    {
        sz = ch[0] -> sz + cnt + ch[1] -> sz;
    }
    int cmp(int x)
    {
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void pushdown() {} ;
}T[SZ], *rt[SZ], *null;

int Tcnt = 0;

node* newnode(int x,node *fa)
{
    node *k = T + Tcnt ++;
    k -> f = fa;
    k -> ch[0] = k -> ch[1] = null;
    k -> v = x;
    k -> cnt = k -> sz = 1;
    return k;
}

void rotate(node *p)
{
    node *fa = p -> f;
    int d = p -> dir();
    fa -> f -> setc(p,fa -> dir());
    fa -> setc(p -> ch[d ^ 1],d); fa -> maintain();
    p -> setc(fa,d ^ 1); p -> maintain();
}

void splay(node *p,node *rt = null)
{
    p -> pushdown();
    while(p -> f != rt)
    {
        if(p -> f -> f == rt) rotate(p);
        else
        {
            p -> f -> f -> pushdown(); p -> f -> pushdown(); p -> pushdown();
            if(p -> dir() == p -> f -> dir())
                rotate(p -> f),rotate(p);
            else
                rotate(p),rotate(p);
        }
    }
    p -> maintain();
}

void insert(node *p,int x,node* &root)
{
    if(root == null) { root = newnode(x,null); return ; }
    while(p != null)
    {
        p -> sz ++;
        int d = p -> cmp(x);
        if(d == -1) { p -> cnt ++; break; }
        if(p -> ch[d] == null)
        {
            p -> ch[d] = newnode(x,p);
            p = p -> ch[d];
            break;
        }
        p = p -> ch[d];
    }
    splay(p);
    while(root -> f != null) root = root -> f;
}

void erase(node *p,int x,node* &root)
{
    while(p != null)
    {
        p -> sz --;
        int d = p -> cmp(x);
        if(d == -1) { p -> cnt --; break;}
        p = p -> ch[d];
    }
    if(p -> cnt) return ;
    splay(p);
    while(root -> f != null) root = root -> f;
    if(p -> ch[1] == null) { root = p -> ch[0],root -> f = null; return ; }
    if(p -> ch[0] == null) { root = p -> ch[1],root -> f = null; return ; }
    p = p -> ch[0];
    while(p -> ch[1] != null) p = p -> ch[1];
    splay(p,root);
    p -> ch[1] = root -> ch[1]; p -> ch[1] -> f = p;
    p -> f = null; p -> maintain();
    root = p;
}

int ask_num(node *p,int k)
{
    while(p != null)
    {
        int l = p -> ch[0] -> sz + 1;
        int r = p -> ch[0] -> sz + p -> cnt;
        if(l <= k && k <= r) return p -> v;
        if(k > r) k -= r,p = p -> ch[1];
        else p = p -> ch[0];
    }
    return -1;
}


void init()
{
    null = newnode(-INF,null);
    null -> sz = null -> cnt = 0;
}


int n,m,fa[SZ];

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

void merge(int a,int b)
{
    int x = find(a),y = find(b);
    if(x == y) return ;
    if(rt[x] -> sz < rt[y] -> sz) swap(x,y);
    fa[y] = x;
    while(rt[y] -> sz)
    {
        int d = rt[y] -> v;
        erase(rt[y],d,rt[y]);
        insert(rt[x],d,rt[x]);
    }
}

map<int,int> mp;

int main()
{
    init();
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) rt[i] = null,fa[i] = i;
    for(int i = 1;i <= n;i ++)
    {
        int x;
        scanf("%d",&x); mp[x] = i;
        insert(rt[i],x,rt[i]);
    }
    for(int i = 1;i <= m;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        merge(x,y);
    }
    int q;
    scanf("%d",&q);
    while(q --)
    {
        char str[10];
        scanf("%s",str);
        if(str[0] == 'Q')
        {
            int x,k;
            scanf("%d%d",&x,&k);
            int xx = find(x);
            int v = ask_num(rt[xx],k); //cout << v << endl;
            int ans = v == -1 ? -1 : mp[v];
            printf("%d\n",ans);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
    }
    return 0;
}
/*
5 1
4 3 2 5 1
1 2
7
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

*/


J : LYDSY - 2329

给一个括号序列,要求支持:

1.区间修改

2.区间翻转

3.区间左括号变成右括号,右括号变成左括号

4.询问当前区间至少改变多少个括号使其变成一个合法的括号序列。

将左括号看做-1,右括号看做1。这样前三个操作就变成:区间赋值、区间翻转、区间乘-1。

对于第四种操作,考虑一个括号序列()()())))))(())((()

对于合法的匹配可以去掉,然后就变成:)))))(((

可以发现对于任意的括号序列,删除掉所有匹配后都会变成许多右括号+许多左括号。

答案显然是两种括号的个数+1再除以二(下取整)之和。

将括号看做数字之后,就变成维护区间前缀最小值和后缀最大值了。

(其实维护一个就行,因为可以用区间和减去第一个)

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆