(Ioicamp Judge) 26. 區間MEX

http://judge.ioicamp.org/problems/26

區間MEX

Time Limit: 5s

Description

定義一個非負整數形成集合的 mex$\mathrm{mex}$（minimum excludant）為最小不在該集合的非負整數，例如：

• mex({1,2,3})=0$\mathrm{mex}(\{1,2,3\})=0$
• mex({0,1,2,3,5,8})=4$\mathrm{mex}(\{0,1,2,3,5,8\})=4$

現在給你一個長度 N$N$ 的序列 A$A$，你要支援以下詢問：

• 求一個區間內所有數形成的集合的 mex$\mathrm{mex}$ 值。

Input Format

第一行有一個正整數 T$T$，代表總共有幾筆測試資料。

每筆測試資料第一行包含兩個正整數 N,M$N,M$，代表序列的長度以及詢問數。
接下來包含 N$N$ 個由空白隔開的非負整數 Ai$A_i$，代表序列的元素。
接下來包含 M$M$ 行，每行包含兩個正整數 l,r$l,r$，
代表一個詢問，請輸出區間 {Al,…,Ar}$\{A_l,\dots ,A_r\}$ 的 mex$\mathrm{mex}$ 值。

• 1≤T≤20$1\le T\le 20$
• 1≤N,M≤105$1\le N,M\le {10}^5$
• 0≤Ai≤109$0\le A_i\le {10}^9$
• 詢問： 1≤l≤r≤N$1\le l\le r\le N$

Output Format

對於每個詢問，請輸出一行包含一個非負整數，代表該詢問區間的 mex$\mathrm{mex}$。

Sample Input

1
10 7
1 0 2 3 1 5 4 6 3 7
1 1
1 3
6 10
3 5
4 9
2 3
1 10

Sample Output

0
3
0
0
0
1
8

這題有兩種解法：

一種是我的隊友(很電的國手：余柏序)在賽中寫的：http://codingsimplifylife.blogspot.tw/2016/02/ioi-camp-judge-26mex.html

另外的解法是說：

因為數值>10^5就沒有用了(因為mex的定義是最小的非負整數，又最多只會出現10^5的數字，所以數值>10^5就可以不用考慮了)。

所以，我先把所有的詢問按照右界排序，數值線段樹裡面存的是 "這個數值最後出現在哪裡(沒有的話就-INF)" ！之後開始慢慢的push值(因問詢問按照右界排序)。

然後再查詢線段樹的時候，盡量往左走

這樣就OK了

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
const int MAX_M = 100010;

struct QUERY {
    int l;
    int r;
    int id;
} Query[MAX_M];

int ans[MAX_N];
int v[MAX_N];

bool operator<(const QUERY& q1,const QUERY& q2) {
    return q1.r<q2.r || q1.r==q2.r&&q1.l<q2.l;
}

struct Node {
    int val;
    Node* lc;
    Node* rc;
    Node () {
        val=-1;
        lc=rc=NULL;
    }
    void pull() {
        val = min(lc->val,rc->val);
    }
};

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) return node;
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node,int L,int R,int pos,int val) {
    if (L==R) {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return; 
}

int query(Node* node,int L,int R,int val) { //val equals to query.l
    if (L==R) return L;
    int mid=(L+R)>>1;
    if (node->lc->val < val) return query(node->lc,L,mid,val);
    else return query(node->rc,mid+1,R,val);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;n>=x;x++) {
            scanf("%d",&v[x]);
            if (v[x]>100002) v[x]=100003;
        }
        Node* root = Build(0,MAX_N);
        for (int x=0;m>x;x++) {
            scanf("%d %d",&Query[x].l,&Query[x].r);
            Query[x].id=x;
        }
        sort(Query,Query+m);
        int nr;
        int id=1;
        for (int x=0;m>x;x++) {
            int L=Query[x].l;
            int R=Query[x].r;
            int t=Query[x].id;
            while (R>=id) {
                modify(root,0,MAX_N,v[id],id);
                id++;
            }
            ans[t]=query(root,0,MAX_N,L);
        }
        for (int x=0;m>x;x++) printf("%d\n",ans[x]);
    }
}

(Zj) a454: TOI2010 第二題：專案時程

http://zerojudge.tw/ShowProblem?problemid=a454

先存有多少入度(指向自己)，出度(指向別人)

然後瘋狂對入度=0做bfs，然後認真dp一番，就OK了。

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX_N = 1003;
const int INF = 475634765;

int rudu[MAX_N];
int dp[MAX_N];
int pre_max[MAX_N];
bool visit[MAX_N];
bool in_que[MAX_N];
vector<int> chudu[MAX_N];
queue<int> que;

void bfs(int root) {
    int ret=-1;
    visit[root]=true;
    que.push(root);
    while (!que.empty()) {
        int tmp=que.front();
        que.pop();
        dp[tmp]+=pre_max[tmp];
        in_que[tmp]=false;
        visit[tmp]=true;
        int len=chudu[tmp].size();
        for (int x=0;len>x;x++) {
            int y=chudu[tmp][x];
            pre_max[y]=max(pre_max[y],dp[tmp]);
            rudu[y]--;
            if (rudu[y]==0) {
                if (in_que[y]==false) {
                    que.push(y);
                    in_que[y]=true;
                }
            }
        }
    }
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        memset(rudu,0,sizeof(rudu));//入度 
        memset(dp,0,sizeof(dp));    //cost
        memset(pre_max,0,sizeof(pre_max));
        int n;
        scanf("%d",&n);
        for (int x=1;n>=x;x++) {
            scanf("%d",&dp[x]);
            chudu[x].clear();
            visit[x]=false;
            int i;
            scanf("%d",&i);
            for (int y=0;i>y;y++) {
                int k;
                scanf("%d",&k);
                rudu[k]++;
                chudu[x].push_back(k);
            }
        }
        int ans=-INF;
        for (int i=1;n>=i;i++) {
            if (visit[i]==false && rudu[i]==0) bfs(i);
        }
        for (int i=1;n>=i;i++) {
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
}

(Zj) a074: TOI2011 第五題：畫作問題

http://zerojudge.tw/ShowProblem?problemid=a074

一開始完全不知如何下手

後來就想想，一個三角形，要先有三條線，這三條線互相交錯的解答不能是無解(兩條線平行)或相同(三線共點)，有了這三條線後，再判斷其他的線會不會交在這個三角形上面，就OK了。

(後記) 認真研究複雜度，發現實際上的複雜度為 O(4 * (k/4)^3 * k) = O(k^4)，以k=296的情況來看，應該不會過啊~

#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;

const int MAX_K = 310;
const int INF = 32434259;
int n,m,k;

struct Node {
    double x;
    double y;
    bool real;   //really have answer ???
    bool same;   //the same???
};
//y=ax+b
double a[MAX_K],b[MAX_K];  //yi=aix+bi
Node ans[MAX_K][MAX_K];  //yi=aix+bi 和 yj=ajx+bj 的解 

Node get_ans(int i,int j) {
    Node ret;
    if (i==j) {
        ret.real=false;
        ret.same=false;
    }
    else {
        if (a[i]==a[j]&&b[i]==b[j]) {     //一樣直線 
            ret.real=false;
            ret.same=true;
        }
        else if (a[i]==a[j]&&b[i]!=b[j]) { //斜率一樣but  y潔具不同 
            ret.real=false;
            ret.same=false;
        }
        else if (a[i]==INF) {   //x=???
            ret.x=b[i];
            ret.y=a[j]*b[i]+b[j];
            ret.real=true;
            ret.same=true;
        }
        else if (a[j]==INF) { //x=???
            ret.x=b[j];
            ret.y=a[i]*b[j]+b[i];
            ret.real=true;
            ret.same=true;
        }
        else {
            ret.x=(b[i]-b[j])/(a[j]-a[i]);
            ret.y=a[i]*ret.x+b[i];
            assert(ret.y==a[j]*ret.x+b[j]);
            ret.real=true;
            ret.same=true;
        }
    }
    return ret;
}

void fill_ans(int k) {
    k+=4;
    for (int x=0;k>x;x++) {
        for (int y=0;k>y;y++) {
            ans[x][y]=get_ans(x,y);
        }
    }
}

bool in_range(Node node,double x1,double y1,double x2,double y2) {
    if (x1>x2)swap(x1,x2);
    if (y1>y2)swap(y1,y2);
    if (node.x<x1) return false;
    if (node.x>x2) return false;
    if (node.y<y1) return false;
    if (node.y>y2) return false;
    return true;
}

bool in_range2(Node node,double x1,double y1,double x2,double y2) {
    if (x1>x2)swap(x1,x2);
    if (y1>y2)swap(y1,y2);
    if (node.x<x1) return false;
    if (node.x>x2) return false;
    if (node.y<y1) return false;
    if (node.y>y2) return false;
    return true;
}

bool operator==(const Node& n1, const Node& n2) {
    return (n1.x==n2.x&&n2.y==n1.y);
}

bool check_line(Node node1, Node node2,int i,int k) {
    double x1=node1.x;
    double x2=node2.x;
    double y1=node1.y;
    double y2=node2.y;
    for (int x=0;k>x;x++) {
        if (ans[i][x].real==true) {
            if (ans[i][x]==node1||ans[i][x]==node2) {

            }
            if (ans[i][x]==node1||ans[i][x]==node2) continue;
            if (in_range2(ans[i][x],x1,y1,x2,y2)==true) {

                return false;
            }
        }
    }
    return true;
}

int main () {
    while (scanf("%d %d %d",&n,&m,&k) != EOF) {
        for (int x=0;k>x;x++) {
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            if (x1==x2) {  //鉛直縣 
                a[x]=INF;
                b[x]=x1;
            }
            else if (y1==y2) {  //水平線 
                a[x]=0;
                b[x]=y1;
            }
            else {
                a[x]=(y2-y1)/(x2-x1);
                assert(x2-x1!=0);
                b[x]=y2-x2*a[x];
                assert(b[x]==(y1-a[x]*x1));
            }
        }
        //端點 
        a[k]=INF;
        b[k]=0;
        a[k+1]=0;
        b[k+1]=0;
        a[k+2]=INF;
        b[k+2]=n;
        a[k+3]=0;
        b[k+3]=m;
        fill_ans(k);
        k+=4;
        int anss=0;
        for (int p=0;k>p;p++) {
            for (int q=p+1;k>q;q++) {
                Node node[3];
                node[0]=ans[p][q];
                if (node[0].real==false) continue;
                for (int r=q+1;k>r;r++) {   //枚舉which三條作出的三角形 

                    node[0]=ans[p][q];
                    node[1]=ans[p][r];
                    node[2]=ans[q][r];
                    bool check=false;
                    for (int s=0;3>s;s++) {

                        if (node[s].real==false) check=true;
                        else if (in_range(node[s],0,0,n,m)!=true) check=true;
                    }

                    if (check==true) continue;
                    if (node[0]==node[1]) continue;
                    
                    check=check_line(node[0],node[1],p,k);
                    if (check==false) continue;
                    check=check_line(node[1],node[2],r,k);
                    if (check==false) continue;
                    check=check_line(node[0],node[2],q,k);
                    if (check==false) continue;
                    
                    anss++;
                }
            }
        }
        printf("%d\n",anss);
    }
}

Huffman 模板

Huffman問題

就很greedy的把最小的兩個相加丟進去，用heap優化--> O(n lg n)

範例問題：http://poj.org/problem?id=3253

//Huffman
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;

const int MAX_N = 200001;
LL num[MAX_N];

int main () {
    int n;
    priority_queue<int, vector<int>, greater<int> > pq;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            scanf("%d",&num[x]);
            pq.push(num[x]);
        }
        if (n==1) {
            printf("%d\n",num[0]);
            continue;
        }
        LL sum=0;
        while (pq.empty()==false) {
            int ta=pq.top();
            pq.pop();
            int tb=pq.top();
            pq.pop();
            int tmp=ta+tb;
            sum+=tmp;
            if (pq.empty()) break;
            pq.push(tmp);
        }
        printf("%lld\n",sum);
    }
}