acmicpc.net 9151,9252(LCS), 11758(CCW), 11437(LCA)

https://www.acmicpc.net/problem/9251, https://www.acmicpc.net/problem/9252

LCS 란 어떤 두 문자열의 '모든 부분 수열' 중에서 가장 긴 길이를 말한다. 앞에서 했던

suffix automaton과 비슷한거 같지만 suffix automaton은 접미사가 같은 것들중 가장 긴것을 구하는거고

(즉 연속해서 나와야 한다.) 이건 연속해서 나오지 않아도 된다.

http://blog.naver.com/power2845/220677085876 참고. 아래는 9252번 소스. 9151은 r[0]만 출력.

def LCS(a,b):
    ret = []
    LCS_length = 0
    s1='0'+a
    s2='0'+b
    table = [[0 for i in xrange(len(s1))]for i in xrange(len(s2))]
    for i in xrange(1,len(s2)):
        max = 0
        for j in xrange(1,len(s1)):
            if s2[i]==s1[j]:
                max = table[i-1][j-1] + 1
                table[i][j] = max
            else:
                if table[i][j-1] > table[i-1][j]:
                    table[i][j] = table[i][j-1]
                else:
                    table[i][j] = table[i-1][j]
        if LCS_length < max:
            LCS_length = max
    ret.append(LCS_length)
 
    t1=LCS_length
    t0 = t1-1
    lcs=''
    for i in xrange(len(s2)-1,-1,-1):
        for j in xrange(len(s1)-1,-1,-1):
            if table[i][j]==t1 and table[i][j-1]==t0 and \
                table[i-1][j-1]==t0 and table[i-1][j]==t0:
                t0 -= 1
                t1 -= 1
                lcs = s2[i]+lcs
                break
    ret.append(lcs)
    return ret
r=LCS(raw_input(),raw_input())
print r[0]
print r[1]

https://www.acmicpc.net/problem/11758

https://www.acmicpc.net/blog/view/27 를 보고 이해하자.

* CCW = Counter Clock Wise 의 약자라고 한다.

# -*- encoding: cp949 -*-
def ccw(x1,y1,x2,y2,x3,y3):
    t = x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3
    return 1 if t>0 else -1 if t<0 else 0

a=[map(int,raw_input().split())for i in range(3)]
print ccw(a[0][0],a[0][1],a[1][0],a[1][1],a[2][0],a[2][1])

https://www.acmicpc.net/problem/11437

LCA는 최소 공통 조상을 뜻한다.

#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 18; 
 
int N, M;
int parent[100000][MAX]; 
int depth[100000]; 
vector<int> adj[100000]; 
 
void makeTreeByDFS(int curr){
    for(int next: adj[curr]){
        if(depth[next] == -1){
            parent[next][0] = curr;
            depth[next] = depth[curr] + 1;
            makeTreeByDFS(next);
        }
    }
}
  
  
int main()
{
    cin>>N;
    for(int i=0; i<N-1; i++){
        int u, v;
        cin>>u>>v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(parent, -1, sizeof(parent));
    fill(depth, depth+N, -1);
    depth[0] = 0;
    makeTreeByDFS(0);
  
    for(int j=0; j<MAX-1; j++)
        for(int i=1; i<N; i++)
            if(parent[i][j] != -1)
                parent[i][j+1] = parent[parent[i][j]][j];
  
    cin>>M;
    for(int i=0; i<M; i++){
        int u, v;
        cin>>u>>v;
        u--; v--;
  
        if(depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
  
        for(int j=0; diff; j++){
            if(diff % 2) u = parent[u][j];
            diff /= 2;
        }
  
        if(u != v){
            for(int j=MAX-1; j>=0; j--){
                if(parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                    u = parent[u][j];
                    v = parent[v][j];
                }
            }
            u = parent[u][0];
        }
        cout<<u+1<<"\n";
    }
}