K：http://acm.uestc.edu.cn/#/problem/show/1593


解法：直接并查集加SET维护即可。



#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int a[maxn], id[maxn], fa[maxn];
LL sum[maxn],ans[maxn];
set<LL>s;
bool vis[maxn];
int n;
int find_set(int x){
    if(x==fa[x]) return fa[x];
    else return fa[x]=find_set(fa[x]);
}
void union_set(int x, int y){
    int fx=find_set(x),fy=find_set(y);
    if(fx!=fy){
        fa[fx]=fy;
        sum[fy]+=sum[fx];
    }
}

int main()
{
    while(~scanf("%d",&n)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=n; i++) scanf("%d", &id[i]);
        for(int i=0; i<=n; i++) fa[i]=i,sum[i]=a[i],vis[i]=0,ans[i]=0;
        s.clear();
        for(int i=n; i>=1; i--){
            if(s.empty()) ans[i]=0;
            else
            {
                auto it = s.end();
                it--;
                ans[i]=*it;
            }
            if(vis[id[i]-1]){
                s.erase(sum[find_set(id[i]-1)]);
                union_set(id[i]-1,id[i]);
                s.insert(sum[find_set(id[i]-1)]);
                vis[id[i]]=1;
            }
            if(vis[id[i]+1]){
                s.erase(sum[find_set(id[i]+1)]);
                union_set(id[i]+1,id[i]);
                s.insert(sum[find_set(id[i]+1)]);
                vis[id[i]]=1;
            }
            if(!vis[id[i]-1]&&!vis[id[i]+1]){
                s.insert(sum[id[i]]);
                vis[id[i]]=1;
            }
        }
        for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
    }
    return 0;
}

L：http://acm.uestc.edu.cn/#/problem/show/1594


解法：POJ的食物链，带权并查集维护，见这里 http://blog.csdn.net/just_sort/article/details/59547406



#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000100;

int N, K, relation, a, b, cnt;

int p[maxn], r[maxn];//p代表x的父亲,r代表x和fa[x]的关系0, 1, 2分别代表同类，***

int ans[1000010];

void init()
{
    for(int i = 1; i <= N; i++)
    {
        p[i] = i;
        r[i] = 0;
    }
}

int find_set(int x)
{
    int temp = p[x];
    if(x == p[x]) return p[x];
    p[x] = find_set(p[x]);
    r[x] = (r[x] + r[temp]) % 3;
    return p[x];
}

void union_set(int x, int y, int px, int py)
{
    p[px] = py;
    r[px] = (r[y] - r[x] + 3 + relation - 1) % 3;
}

int main()
{
    while(~scanf("%d%d", &N, &K))
    {
        cnt = 0;
        init();
        int tot = 0;
        memset(ans,0,sizeof(ans));
        while(K--)
        {
            ++tot;
            scanf("%d%d%d", &relation, &a, &b);
            int pa, pb;
            pa = find_set(a);
            pb = find_set(b);
            if(a > N || b > N || (relation == 2 && a == b))
            {
                ++cnt;
                ans[cnt]=tot;
                continue;
            }
            if(pa != pb)
            {
                union_set(a, b, pa, pb);
                continue;
            }
            if((r[a] - r[b] + 3) % 3 != (relation - 1))
            {
                ++cnt;
                ans[cnt]=tot;
                continue;
            }
        }
        for(int i=1; i<=cnt; i++) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

L：http://acm.uestc.edu.cn/#/problem/show/1595


解法：

他每次毒奶就会当前能力*2或*2+1，就意味着被毒奶之前能力值是⌊x/2⌋
你需要让最大值最小，并且不存在重复的值，就贪心每次选取最大的人的能力值，把他压缩为 可行的最大的x/(2^k)

#include <bits/stdc++.h>
using namespace std;
map<int,bool>vis;
priority_queue<int>q;
int a[50010];
int main()
{
    int n;
    while(~scanf("%d",&n)){
        while(!q.empty()) q.pop();
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        vis.clear();
        for(int i=1; i<=n; i++) q.push(a[i]),vis[a[i]]=1;
        int ans=0;
        while(!q.empty()){
            int x = q.top();
            vis[x]=0;
            while(x){
                x>>=1;
                if(x&&!vis[x]){
                    break;
                }
            }
            if(x&&!vis[x]){
                q.pop();
                q.push(x);
                vis[x]=1;
            }
            else{
                break;
            }
        }
        printf("%d\n", q.top());
    }
    return 0;
}