2015 ACM/ICPC Asia Regional Changchun Online(hdu 5437 - hdu 5449)

先簡單說說這次網絡賽吧，總而言之，還是題刷少了，思想一短路，反正是怎麼爬也爬不起來了。。。心塞。。。第7題，模闆題，13鐘AC，手速還是慢了，接着做題二題，由于處理細節問題，01:13:56才AC，感覺自己還是要穩一點，不然做了之後，隊友出幾組資料，沒過，又要改。。。麻煩。。。接着隊友把5題暴力敲出來了，結果逾時，然後我用離線做了一遍，可是，我掉坑裡了，其實都是離線查找+并查集，隻不過的我的方法比較笨，（具體的直接見逾時代碼吧），其實隻要每合并兩個塊，直接将兩個塊加上，然後減去原來兩個塊的和就行了，然而自己是每一個點一個點的加，一直想怎麼優化根結點，并沒有想到狀态壓縮（當時，我隊友還跟我提起過，我不知道當時怎麼沒在意這句話，現在居然記起來，我隊友跟我說過這句話），總之，真是自己犯傻了。。。欲哭無力呀，如果不是這題自己想的太死了的話，然後繼續做第10題（它們都說第10題是道：Lucas定理 + 中國剩餘定理，網上有bin神的模闆，直接拿去改就可以了。。。），可能就會進現場賽了，，然而隻是如果。。。第1題（優先隊列+模拟）和第8題（二叉樹）分别是隊友敲得。。。第5,6,10題都是賽後過得。。。

1.Alisha’s Party（優先隊列+模拟）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5437

解題思路：

題目大意：

題目大意：Alisha有k個朋友來他家，每個朋友來是有先後次序的，Alisha會開m次門，每次都是在第t個朋友到了以後，他會邀請p個

朋友進家門，因為房間不夠大，是以每次邀請所帶禮物價值高的朋友先進門，如果兩個朋友的禮物價值相同，則先來的先進門。最

後等所有朋友都到了以後，Alisha會把他所有的朋友都叫進來，進來的順序跟先前的要求一樣。題目給出q個詢問，問第ni個進門的朋友是誰。

算法思想：

按照先後次序到來的朋友進行排序，這裡可以利用優先隊列把優先級最高的朋友放到隊首。當開門的時候，從隊首取朋友進門。同

時如果不開門的時候不斷模拟朋友到來的情況，将朋友入隊。最後輸出答案即可。

注意：

給出的t時亂序的，需要排序，而且t有可能是相同的，比如t為3的時候，可能是3 1 ，3  2，對于這種情況，其實是将這些人邀請進入

房屋，如果門外沒人了就結束了。

AC代碼：

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

struct node{
    char name[205];
    int data;
    int pos;
    bool operator <(const node &a) const{
        if(data == a.data){
            return pos > a.pos;
        }
        return data < a.data;
    }
}no[150005];

struct open{
    int t;
    int p;
}op[150005];
int k,m,Q;
vector<int> ans;

bool cmp(struct open a, struct open b){
    return a.t < b.t;
}

void solve(){//用優先隊列進行模拟
    int step = 1;
    for(int i = 2; i <= m; i++){
        if(op[i].t == op[step].t)
            op[step].p += op[i].p;
        else{
            op[++step].t = op[i].t;
            op[step].p = op[i].p;
        }
    }
    node tmp;
    priority_queue<node> q;
    int cur = 1,num;//cur目前時間，num計數
    for(int i = 1; i <= step; i++){
        num = 0;
        for(int j = cur;j <= op[i].t; j++)
            q.push(no[j]);
        cur = op[i].t + 1;
        while(!q.empty() && num < op[i].p){
            tmp = q.top();
            q.pop();
            ans.push_back(tmp.pos);
            num++;
        }
    }
    for(int i = op[step].t + 1;i <= k;++ i)
        q.push(no[i]);
    while(!q.empty()){
        tmp = q.top();
        q.pop();
        ans.push_back(tmp.pos);
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T --){
        ans.clear();
        scanf("%d%d%d",&k,&m,&Q);
        for(int i = 1; i <= k; i++){
            scanf("%s%d",no[i].name,&no[i].data);
            no[i].pos = i;
        }
        for(int i = 1; i <= m; i++)
            scanf("%d%d",&op[i].t,&op[i].p);
        sort(op+1,op+m+1,cmp);
        solve();
        int x;//查詢
        for(int i = 1; i < Q; i++){
            scanf("%d",&x);
            printf("%s ",no[ans[x-1]].name);
        }
        scanf("%d",&x);
        printf("%s\n",no[ans[x-1]].name);
    }
    return 0;
}
           

2.Ponds（并查集+拓撲序）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5438

解題思路：

題目大意：

有p個池塘，每個池塘有一個價值，他們之間有水管相連。有一個操作：如果一個池塘相連的水管少于2根，就可以将這個池塘拆

掉，然後一直重複這個操作，直到不能操作為止。問最後剩下的這些池塘組成的聯通塊中，塊裡的池塘數目為奇數的價值和。

算法思想：

利用拓撲序的思想，将能拆除的池塘，一一拆除，直到不能再被拆除為止。剩下的池塘肯定都形成了環，是以我們隻要求出每個環

中所含池塘數為奇數的這些池塘價值的和。

AC代碼：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
int p,m;
ll a[10005];
int pa[10005];
int deg[10005];
int vis[10005];
int num[10005];
int tt[10005];
vector<int> v[10005];

int findset(int x){
    if(x == pa[x])
        return pa[x];
    return pa[x] = findset(pa[x]);
}

void topSort(){//将度數小于2的點都删去
    int flag = 1,l;
    while(flag){
        flag = 0;
        for(int i = 1; i <= p; i++){
            if(!vis[i] && deg[i] <= 1){
                vis[i] = 1;
                l = v[i].size();
                for(int j = 0; j < l; j++){
                    //cout<<v[i][j]<<endl;
                    deg[v[i][j]]--;
                }
                flag = 1;
            }
        }
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        memset(deg,0,sizeof(deg));
        memset(num,0,sizeof(num));
        scanf("%d%d",&p,&m);
        for(int i = 0; i <= p; i++){
            pa[i] = i;
            v[i].clear();
        }
        for(int i = 1; i <= p; i++)
            scanf("%lld",&a[i]);
        int x,y;
        for(int i = 0; i < m; i++){
            scanf("%d%d",&x,&y);
            deg[x]++;
            deg[y]++;
            v[x].push_back(y);
            v[y].push_back(x);
            x = findset(x);
            y = findset(y);
            if(x != y)
                pa[x] = y;
        }
        topSort();
        int sum = 0;
        for(int i = 1; i <= p; i++){
            //找出所有的根節點
            if(!vis[i]){
                pa[i] = findset(i);
                num[pa[i]]++;
            }
        }
        for(int i = 1;i <= p; i++){
            //找出符合題意的根結點，即該塊的結點數為奇數
            if(num[i]%2)
                tt[sum++] = i;
        }
        ll ans = 0;
        for(int i = 1; i <= p; i++){
            if(!vis[i]){
                for(int j = 0; j < sum; j++){
                    if(pa[i] == tt[j]){
                        ans += a[i];
                        break;
                    }
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
           

5.Travel（離線操作+并查集路徑壓縮）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5441

解題思路：

http://blog.csdn.net/piaocoder/article/details/48437701

AC代碼：

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

struct node{
    int x,y,l;
    bool operator < (const node &a) const{
        return l < a.l;
    }
}no[100005];

struct Query{
    int id,l;
     bool operator < (const Query &a) const{
        return l < a.l;
    }
}qq[5005];
int pa[20005];
int num[20005];
int ans[5005];

int findset(int x){
    if(x == pa[x])
        return pa[x];
    return pa[x] = findset(pa[x]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
            num[i] = 1;
        }
        for(int i = 0; i < m; i++)
            scanf("%d%d%d",&no[i].x,&no[i].y,&no[i].l);
        for(int i = 0; i < q; i++){
            scanf("%d",&qq[i].l);
            qq[i].id = i;
        }
        sort(no,no+m);
        sort(qq,qq+q);
        int x,y,j = 0,sum = 0;
        for(int i = 0; i < q; i++){
            while(j < m && no[j].l <= qq[i].l){
                x = findset(no[j].x);
                y = findset(no[j].y);
                if(x != y){
                    sum += (num[x]+num[y])*(num[x]+num[y]-1)-num[x]*(num[x]-1)-num[y]*(num[y]-1);
                    pa[x] = y;
                    num[y] += num[x];
                }
                j++;
            }
            ans[qq[i].id] = sum;
        }
        for(int i = 0; i < q; i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}
           

7.The Water Problem（區間最大值）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5443

解題思路：

求區間最大值，模闆題。。。

AC代碼：

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

const int maxn = 1005;
struct node{
    int l,r,maxn;
}tree[maxn<<2];
int a[maxn];

void build(int m,int l,int r){
    tree[m].l = l;
    tree[m].r = r;
    if(l == r){
        tree[m].maxn = a[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(m<<1,l,mid);
    build((m<<1)+1,mid+1,r);
    tree[m].maxn = max(tree[m<<1].maxn,tree[(m<<1)+1].maxn);
}

int query(int m,int l,int r){
    if(l == tree[m].l && r == tree[m].r)
        return tree[m].maxn;
    int mid = (tree[m].l+tree[m].r)>>1;
    if(r <= mid)
        return query(m<<1,l,r);
    if(l > mid)
        return query((m<<1)+1,l,r);
    return max(query(m<<1,l,mid), query((m<<1)+1,mid+1,r));
}


int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int q, l, r ,n;
        scanf("%d",&n);
        if(n == 0){
            scanf("%d",&q);
            while(q--){
                scanf("%d%d",&l,&r);
            }
            continue;
        }
        for(int  i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        build(1,1,n);
        scanf("%d",&q);
        while(q--){
            scanf("%d%d",&l,&r);
            printf("%d\n",query(1,l,r));
        }
    }
    return 0;
}
           

8.Elven Postman（二叉樹）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5444

解題思路：

首先将所有節點初始化，然後再邊加點，邊模拟路徑并儲存，最後再給你q個詢問，依次将建樹過程中，儲存的路徑輸出即可。。。

AC代碼：

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

const int maxn = 1010;
struct node{
    int l,r;
    int sum;
    char ans[maxn];
}tree[maxn];

void update(int id,int tmp){
    if (tmp < id){
        if (tree[id].r == 0){
            tree[id].r = tmp;
            tree[tmp].sum = id;
            strcpy(tree[tmp].ans,tree[id].ans);
            strcat(tree[tmp].ans,"E");
        }
        else{
            id = tree[id].r;
            update(id,tmp);
        }
    }
    else{
        if(tree[id].l == 0){
            tree[id].l = tmp;
            tree[id].sum = id;
            strcpy(tree[tmp].ans,tree[id].ans);
            strcat(tree[tmp].ans,"W");
        }
        else{
            id = tree[id].l;
            update(id,tmp);
        }
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        for(int i = 0; i <= 1000; i++){
            tree[i].l = 0;
            tree[i].r = 0;
            tree[i].sum = 0;
            tree[i].ans[0] = '\0';
        }
        int n,q,root,tmp;
        scanf("%d", &n);
        scanf("%d", &root);
        tree[root].sum = -1;
        n--;
        while(n--){
            scanf("%d",&tmp);
            update(root,tmp);
        }
        scanf("%d", &q);
        while(q--){
            scanf("%d",&tmp);
            printf("%s\n",tree[tmp].ans);
        }
    }
    return 0;
}
           

10.Unknown Treasure(lucas定理+中國剩餘定理)

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5446

解題思路：

http://blog.csdn.net/piaocoder/article/details/48445757

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;
const int maxn = 20;
ll a[maxn];
ll mod[maxn] ;

ll mul(ll a,ll b,ll mod){
    ll ans = 0;
    while(b){
        if(b&1)
            ans = (ans+a)%mod;
        b >>= 1;
        a = (a+a)%mod;
    }
    return ans;
}

ll quick_mod(ll a,ll b,ll m){
    ll ans = 1;
    a %= m;
    while(b){
        if(b&1)
            ans = ans * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}

ll getC(ll n, ll m,int cur){
    ll p = mod[cur];
    if(m > n)
        return 0;
    if(m > n-m)
        m = n-m;
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ll a = (n + i - m) % p;
        ll b = i % p;
        ans = mul(ans,mul(a,quick_mod(b,p-2,p),p),p);  //p為素數，i對p的逆元可以不用擴充歐幾裡得進行求解  re=i^(p-2)
    }
    return ans%p;
}

ll Lucas(ll n,ll k,int cur){
    ll p = mod[cur];
    if(k == 0)
        return 1%p;
    return mul(getC(n%p,k%p,cur),Lucas(n/p,k/p,cur),p);
}

void extend_Euclid(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    extend_Euclid(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - a / b * y;
}

ll solve(ll a[],ll m[],int k){
    ll M = 1;
    ll ans = 0;
    for(int i=0; i<k; i++)
        M *= mod[i];
    for(int i=0; i<k; i++){
        ll x,y,tmp;
        ll Mi = M / m[i];
        extend_Euclid(Mi, m[i], x, y);
        if(x < 0){
            x=-x;
            tmp = mul(Mi,x,M);
            tmp = mul(tmp,a[i],M);
            tmp = -tmp;
        }
        else {
            tmp = mul(Mi,x,M);
            tmp = mul(tmp,a[i],M);
        }
        ans = (ans + tmp) % M;
    }
    while(ans < 0)
        ans += M;
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n,m;
        int k;
        scanf("%lld%lld%d",&n,&m,&k);
        for(int i = 0; i < k; i++)
            scanf("%lld",&mod[i]);
        for(int i = 0;i < k; i++)
            a[i] = Lucas(n,m,i)%mod[i];
        printf("%lld\n",solve(a,mod,k));
    }
    return 0;
}