(Live Archive) 3820 - Mr. Thompson's Problem [一般圖最大匹配，縮花演算法，O(n^4)]

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1821

縮花演算法~

請參考： http://www.csie.ntnu.edu.tw/~u91029/Matching.html#5

My code:

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

struct Blossom_n4 {
    static const int MAX_N = 206;
    bool adj[MAX_N][MAX_N];
    int n;
    void init(int n) {
        this->n = n;
        memset(adj,0,sizeof(adj));
    }
    void add_edge(int u,int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    int m[MAX_N];  //matching point
    //if m[i] == i --> deleted point
    deque<int> path[MAX_N];  //path from root, only stored even point
    int d[MAX_N];  //odd point or even point
    //0 --> even, 1-->odd, -1--<non-visited
    #define SZ(x) ((int)(x).size())
    queue<int> que;
    void label(int u,int v,int lca_id) {
        for (int i=lca_id+1;SZ(path[u])>i;i++) {
            int now=path[u][i];
            if (d[now] == 1) {
                d[now] = 0;
                que.push(now);
                path[now] = path[v];
                path[now].insert(path[now].end(),path[u].rbegin(),path[u].rend()-i);
            }
        }
    }
    bool BFS(int root) {
        for (int i=0;n>=i;i++) {
            path[i].clear();
        }
        while (!que.empty()) que.pop();
        memset(d,-1,sizeof(d));
        d[root] = 0;
        que.push(root);
        path[root].push_back(root);
        while (SZ(que)) {
            int v=que.front();
            que.pop();
            for (int u=0;n>u;u++) {
                if (adj[v][u] && m[u] != u) {
                    //have edges
                    if (d[u] == -1) {
                        if (m[u] == -1) {
                            //oh great
                            //we can update the alternation path!!!
                            for (int i=0;SZ(path[v])-1>i;i+=2) {
                                m[path[v][i]] = path[v][i+1];
                                m[path[v][i+1]] = path[v][i];
                            }
                            m[u] = v;
                            m[v] = u;
                            return true;
                        }
                        else {
                            //oh no
                            //but we find one more even point
                            int uu=m[u];
                            path[uu] = path[v];
                            path[uu].push_back(u);
                            path[uu].push_back(uu);
                            d[u] = 1;
                            d[uu] = 0;
                            que.push(uu);
                        }
                    }
                    else if (d[u] == 1) {
                        //find an odd point
                        //do nothing
                    }
                    else if (d[u] == 0) {
                        //oh jizz
                        //we find a crossing edge
                        //more even points are allowed
                        int lca_id = 0;
                        while (lca_id < SZ(path[u]) && lca_id < SZ(path[v]) && 
                               path[u][lca_id] == path[v][lca_id]) {
                            lca_id++;
                        }
                        lca_id--;
                        label(u,v,lca_id);
                        label(v,u,lca_id);
                    }
                }
            }
        }
        return false;
    }
    int matching() {
        memset(m,-1,sizeof(m));
        int ret=0;
        for (int i=0;n>i;i++) {
            if (m[i] == -1) {
                if (BFS(i)) {
                    ret++;
                }
                else {
                    m[i] = i;
                }
            }
        }
        return ret;
    }
} sagiri;

const int MAX_N = 206;
int a[MAX_N],b[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int i=0;n>i;i++) {
            scanf("%d",&a[i]);
        }
        set<int> st;
        for (int j=0;m>j;j++) {
            scanf("%d",&b[j]);
            st.insert(b[j]);
        }
        sagiri.init(n);
        for (int i=0;n>i;i++) {
            for (int j=i+1;n>j;j++) {
                if (st.find(a[i]+a[j]) != st.end()) {
                    sagiri.add_edge(i,j);
                }
            }
        }
        printf("%d\n",sagiri.matching());
    }
}

(UVa) 1625 - Color Length [對未來DP (?)]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=4500

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

const int MAX_N = 5006;
const int MAX_P = 144;
const int INF = 1e9 + 7;

int dp[MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

int f1[MAX_P],f2[MAX_P],l1[MAX_P],l2[MAX_P];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        string s1,s2;
        cin >> s1 >> s2;
        s1 = " "+s1;
        s2 = " "+s2;
        for (int i=0;MAX_P>i;i++) {
            f1[i] = f2[i] = INF;
            l1[i] = l2[i] = -INF;
        }
        int id=0;
        for (char i:s1) {
            if (f1[i] == INF) f1[i] = id;
            l1[i] = id;
            id++;
        }
        id=0;
        for (char i:s2) {
            if (f2[i] == INF) f2[i] = id;
            l2[i] = id;
            id++;
        }
        int n=s1.size(),m=s2.size();
        for (int i=0;n>i;i++) {
            for (int j=0;m>j;j++) {
                if (!i && !j) {
                    dp[i][j] = 0;
                    continue;
                }
                if (!i) {
                    //from dp[i][j-1]
                    dp[i][j] = dp[i][j-1] + cost[i][j-1];
                    cost[i][j] = cost[i][j-1];
                    //new point
                    if (f1[s2[j]]>i && f2[s2[j]] == j) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l1[s2[j]]<=i && l2[s2[j]] == j) {
                        cost[i][j]--;
                    }
                }
                else if (!j) {
                    //from dp[i-1][j]
                    dp[i][j] = dp[i-1][j] + cost[i-1][j];
                    cost[i][j] = cost[i-1][j];
                    //new point
                    if (f2[s1[i]]>j && f1[s1[i]] == i) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l2[s1[i]]<=j && l1[s1[i]] == i) {
                        cost[i][j]--;
                    }
                }
                else {
                    dp[i][j] = min(dp[i-1][j] + cost[i-1][j], dp[i][j-1] + cost[i][j-1]);
                    cost[i][j] = cost[i-1][j];
                    //new point
                    if (f2[s1[i]]>j && f1[s1[i]] == i) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l2[s1[i]]<=j && l1[s1[i]] == i) {
                        cost[i][j]--;
                    }
                }
            }
        }
        cout<<dp[n-1][m-1]<<endl;
    }
}

(UVa) 1153 - Keep the Customer Satisfied [Greedy]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=845&page=show_problem&problem=3594

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

typedef long long LL;
typedef pair<LL,LL> pii;

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        vector<pii> v;
        for (int i=0;n>i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            v.push_back({b,a});
        }
        sort(v.begin(),v.end());
        int sum=0;
        priority_queue<LL> pq;
        for (pii p:v) {
            sum += p.second;
            pq.push(p.second);
            while (sum > p.first) {
                sum -= pq.top();
                pq.pop();
            }
        }
        printf("%d\n",pq.size());
        if (T) puts("");
    }
}

(UVa) 1646 - Edge Case

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=851&page=show_problem&problem=4521

# -*- coding: utf-8 -*-
"""
Created on Sun Oct 22 14:30:38 2017

@author: Anan
"""

max_len = 10006

ls = []
ls1 = []
ls2 = []
ls3 = []
for i in range(max_len) :
    ls.append(0)
    ls1.append(0)
    ls2.append(0)
    ls3.append(0)

dp=[[ls,ls1],[ls2,ls3]]

dp[0][0][1] = 1
dp[1][1][1] = 1
  
for i in range(2,max_len) :
    dp[0][0][i] = dp[0][0][i-1] + dp[0][1][i-1]
    dp[0][1][i] = dp[0][0][i-1]
    dp[1][0][i] = dp[1][0][i-1] + dp[1][1][i-1]
    dp[1][1][i] = dp[1][0][i-1]

import sys

for i in sys.stdin :
    ii = int(i)
    print(dp[0][0][ii] + dp[0][1][ii] + dp[1][0][ii])

(UVa) 1645 - Count

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=851&page=show_problem&problem=4520

一開始忘記 % (1e9+7) 了QQ。

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <set>
#include <queue>
using namespace std;

#define SZ(x) ((int)(x).size())
typedef pair<int,int> pii;
const int MAX_N = 1e3 +6;
int prime[MAX_N];

void build() {
    prime[0] = prime[1] = 1;
    for (int i=2;MAX_N>i;i++) {
        if (prime[i] == 0) {
            prime[i]=i;
            for (long long j=i*1LL*i;MAX_N>j;j+=i) {
                prime[j] = i;
            }
        }
    }
}

vector<pii> get_prime_divisor(int x) {
    vector<pii> ret;
    while (x!=1) {
        pii tmp;
        tmp.first = prime[x];
        int cnt=0;
        int pp=prime[x];
        while (x%pp==0) {
            x/=pp;
            cnt++;
        }
        tmp.second = cnt;
        ret.emplace_back(tmp);
    }
    return ret;
}

vector<int> get_divisor(int x) {
    vector<pii> prime_divisor=get_prime_divisor(x);
    int sz=SZ(prime_divisor);
    queue<pii> que;
    que.push({1,0});
    vector<int> ret;
    while (!que.empty()) {
        pii p=que.front();
        que.pop();
        if (p.second == sz) {
            ret.emplace_back(p.first);
            continue;
        }
        int t=1;
        for (int i=0;prime_divisor[p.second].second>=i;i++) {
            que.push(make_pair(p.first*t,p.second+1));
            t*=prime_divisor[p.second].first;
        }
    }
    return ret;
}

vector<int> divisor[MAX_N];

typedef long long LL;
const LL mod = 1e9 +7;

LL dp[MAX_N][MAX_N];  //tot j, last i
LL ans[MAX_N];

int main () {
    build();
    int n=1000;
    for (int i=1;n>=i;i++) {
        divisor[i] = get_divisor(i);
    }
    dp[1][1] = 1;
    ans[1] = 1;
    for (int i=1;n>=i;i++) {
        for (int j=i;n>=j;j++) {
            if (i==1 && j==1) continue;
            for (int last:divisor[i]) {
                dp[i][j] += dp[last][j-i];
            }
            ans[j] += dp[i][j];
        }
    }
    int kase=1;
    while (scanf("%d",&n) != EOF) {
        printf("Case %d: %lld\n",kase++,ans[n]%mod);
    }
}