どっどっどうけいほう

なんだかんだ言って結局はDPの強化にしかなってなかった。。。
SegTreeとかUnion-FindとかDjkstraとかKruskalとか（綴り間違ってるかも・・・）
なんだかんだいって応用になるととっても難しいw

AOJ 0179

BFSするだけ

#include <iostream>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef pair<string, int> P;
int main() {
    string w;
    while (cin>>w) {
        if (w=="0") break;
        queue<P> que;
        que.push(P(w,0));
        int res=-1;
        set<string> done;
        while (!que.empty()) {
            P p=que.front(); que.pop();
            char f=p.first[0]; bool flag=true;
            for (int i=1; i<p.first.length(); i++) if (p.first[i]!=f) {
                flag=false;
                break;
            }
            if (flag) {
                res=p.second;
                break;
            }
            for (int i=0; i<p.first.length()-1; i++) {
                if (p.first[i]!=p.first[i+1]) {
                    string temp=p.first;
                    if (temp[i]!='r'&&temp[i+1]!='r') {
                        temp[i]='r'; temp[i+1]='r';
                    } else if (temp[i]!='g'&&temp[i+1]!='g') {
                        temp[i]='g'; temp[i+1]='g';
                    } else if (temp[i]!='b'&&temp[i+1]!='b') {
                        temp[i]='b'; temp[i+1]='b';
                    }
                    if (done.count(temp)==0) {
                        que.push(P(temp,p.second+1));
                        done.insert(temp);
                    }
                }
            }
        }
        if (res==-1) puts("NA");
        else printf("%d\n",res);
    }
}

AOJ 0086

オイラー閉路でぐぐったら、オイラー閉路になるにはすべてのグラフの次数が偶数、準オイラー閉路はちょうど二つだけ奇数って書いてあって、まぁこんかいは準オイラー判定だったけれども、知識をしってしまうとやるだけ
ただ構築するほうの問題はよくわかんなかった。

#include <cstdio>
int cnt[100];
int main() {
    int a,b;
    while (scanf("%d%d",&a,&b)!=EOF) {
        for (int i=0; i<100; i++) cnt[i]=0;
        cnt[a-1]++; cnt[b-1]++;
        while (scanf("%d%d",&a,&b)) {
            if (!a&&!b) break;
            cnt[a-1]++; cnt[b-1]++;
        }
        int odd=0;
        for (int i=0; i<100; i++) {
            if (cnt[i]%2!=0) odd++;
        }
        if (odd==2) puts("OK");
        else puts("NG");
    }
}

PKU 1631

考察を要するDP第二問。
なんかテーマとか英語的に敬遠していたけれどぺりゃうどさんがブログによく見たらただのLISって書いてあってヤフーにかけてみたら本当にただのLISだったから記憶をたどってO(n log n)解を書いた。
これはもはや公式←

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=80000;
int a[40000];
int dp[40005];
int main() {
    int n; scanf("%d",&n);
    for (int ix=0; ix<n; ix++) {
        int p; scanf("%d",&p);
        fill(dp, dp+40000, INF);
        for (int i=0; i<p; i++) scanf("%d",&a[i]);
        for (int i=0; i<p; i++) {
            *lower_bound(dp, dp+p, a[i])=a[i];
        }
        printf("%d\n",lower_bound(dp,dp+p,INF)-dp);
    }
}

PKU 1065

がんばって英語読んだら二つのあたいでなるべくどちらかが降順になるようなところを少なくする問題だと判明した。
これDP？って思いながらソートしてごちゃごちゃいじっているうちに片方をソートしたらもう片方の要素の増加部分列の個数を数えればいいということに気がつく（本当はちょっとネットのフォローがあったけど大体自分で考えたので満足）
それでますますDP解で解けるのか？みたいになってたらとざんさんが図付きの類題1548を紹介してくれたのでこれで明日DP解を考えるとして、とりあえず自分の解法で書いた。
O(n log n)、ソート済み配列を見たとき増加部分列の個数は下から見ていって前の要素たちの中でその要素を超えない最大の値を更新し、またもしそのような前の値がなければ要素を付け足していくと、付け足した要素の数がすなわち増加部分列なのでこれを2分探索をつかって求めた。
詳しくはコードみてください。

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 20000;
struct wood { int w, l; };
bool comp(const wood& a, const wood& b) {
    return a.w<b.w;
}
int ans[5000];
wood stick[5000];
int main() {
    int t; scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        int n; scanf("%d",&n);
        for (int i=0; i<n; i++) scanf("%d%d",&stick[i].w,&stick[i].l);
        sort(stick, stick+n, comp);
        fill(ans, ans+n, INF);
        int x=1; ans[0]=stick[0].l;
        for (int i=1; i<n; i++) {
            sort(ans, ans+x);
            int pos=upper_bound(ans, ans+n, stick[i].l)-ans;
            if (pos==0) ans[x++]=stick[i].l;
            else ans[pos-1]=stick[i].l;
        }
        printf("%d\n",lower_bound(ans,ans+n,INF)-ans);
    }
}