11438 (LCA2)

// 최저공통조상.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100005
#define PIV 17
using namespace std;
vector<int> con[MAX];
int dep[MAX];
int par[PIV][MAX];
int lca(int a, int b)
{
    int tmp;
    if (dep[b] < dep[a]) tmp = a, a = b, b = tmp; // b의 depth 가 더 깊게
    tmp = dep[b] - dep[a];
    for (int i = 0; i < PIV; i++)
    {
        int bit = (1 << i);
        if ((tmp & bit) == bit)
            b = par[i][b];
    }
    if (b == a) return a; // a 가 바로 lca 이므로 리턴

    for (int i = PIV - 1; i >= 0; i--)
    {
        if (par[i][a] != par[i][b])
            a = par[i][a], b = par[i][b];
    }
    return par[0][a];
}
int main()
{
    /*
    int n = 21;
    int k = 7;
    int mod = 11;
    // k를 n번 곱한 수의 mod 로 나눈 나머지
    // 21 = 10101(2)
    int ret = 1;
    int seven[100];
    seven[0] = 7;
    for (int i = 1; i < 10; i++)
        seven[i] = (seven[i - 1] * seven[i - 1]) % mod;
    // seven[i] : 7을 2의i제곱한 값 (의 mod나머지)
    int val = 1;
    for (int bit = 0; bit <= 10; bit++)
    {
        //int val = (1 << bit);
        if ((n & val) == val)
            ret = (ret * seven[bit]) % mod;
        val *= 2;
    }
    printf("%d\n", ret);
    return 0;
    */

    int M, N, a, b;
    scanf("%d", &N);
    for (int i = 1; i <= N - 1; i++)
    {
        scanf("%d %d", &a, &b);
        con[a].push_back(b);
        con[b].push_back(a);
        dep[i] = 0;
    }
    queue<int> que;
    que.push(1); // value
    que.push(1); // depth
    int depth = 0;
    while (que.empty() == false)
    {
        int val = que.front(); que.pop();
        depth = que.front(); que.pop();
        dep[val] = depth;
        for (int next : con[val])
        {
            if (dep[next] == 0)
            {
                par[0][next] = val; // 부모를 저장
                que.push(next);
                que.push(depth + 1);
            }
        }
    }
    //par[0][j] : 1조상, par[1][j] : 2조상, par[2][j] : 4조상... 
    for (int i = 1; i < PIV; i++)
        for (int j = 1; j <= N; j++)
            par[i][j] = par[i - 1][par[i - 1][j]];

    scanf("%d", &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

1753(ダレストラ)

// 최단경로.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
// https://www.acmicpc.net/problem/1753

#include <stdio.h>
#include <vector>
#include <queue>
#include <memory.h>
#include <time.h>
#include <algorithm>

#define MAX 20005
#define INF 1000000005
using namespace std;

int N, M, S;
struct st { int to; int c; };
bool operator<(st a, st b)
{
    return a.c > b.c;
}

vector<st> t[MAX];
int d[MAX];

int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b1753.txt", "r", stdin);
#endif
    scanf("%d%d%d", &N, &M, &S);

    for (int i = 0; i < M; i++)
    {
        int s, e, d;
        scanf("%d%d%d", &s, &e, &d);
        t[s].push_back({ e,d });
    }
    priority_queue<st> pq;
    pq.push({ S,0 });
    memset(d, 0x3f, sizeof(d)); 
    d[S] = 0;
    while (!pq.empty())
    {
        st n = pq.top(); pq.pop();
        for (st next : t[n.to])
        {
            if (d[next.to] > n.c + next.c)
            {
                d[next.to] = n.c + next.c;
                pq.push({ next.to, d[next.to] });
            }
        }
    }
    for (int i = 1; i <= N; i++)
        if (d[i] == d[MAX - 1])
            printf("INF\n");
        else
            printf("%d\n", d[i]);
}

5719

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <memory.h>
#define MAX 501
#define TMAX 10001
#define INF 100000000
using namespace std;

int N, K, S, D;
struct st { int to, d; };
struct st2 { int from, to, d; };

bool operator<(st a, st b)
{
    return a.d > b.d;
}
priority_queue<st> pq;
vector<st> t[MAX], t2[MAX];
int d[MAX];
st2 v[TMAX]; // from,to저장
int k[MAX][MAX],  visit[MAX];
int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b5719.txt", "r", stdin);
#endif
    while (1)
    {
        scanf("%d%d", &N, &K);
        if (N == 0 && K == 0) break;
        scanf("%d%d", &S, &D);
        for (int i = 0; i < N; i++)
            t[i].clear(), t2[i].clear();
        for (int i = 0, a, b, c; i < K; i++)
            scanf("%d%d%d", &a, &b, &c),
            t[a].push_back({ b,c }), t2[b].push_back({ a,c }),
            v[i] = { a,b,c };

        pq.push({ S,0 });
        memset(d, 0x3f, sizeof(d));
        while (!pq.empty())
        {
            st n = pq.top(); pq.pop();
            for (st next : t[n.to])
            {
                if (d[next.to] > n.d + next.d)
                {
                    d[next.to] = n.d + next.d;
                    pq.push({ next.to, n.d + next.d });
                }
            }
        }
        if (d[D] == d[MAX - 1])
        {
            printf("-1\n");
            continue;
        }
        // bfs로 최단경로 제외하고 경로 재설정
        d[S] = 0;
        queue<int> q;
        q.push(D);
        int cnt = 0;
        memset(k, 0, sizeof(k));
        memset(visit, 0, sizeof(visit));
        while (!q.empty())
        {
            int node = q.front(); q.pop();
            if (visit[node]) continue;
            visit[node] = 1;
            for (st next : t2[node])
                if (d[next.to] + next.d == d[node])
                    q.push(next.to),
                    k[next.to][node] = 1; // 최단경로 저장
        }
        for (int i = 0; i < N; i++)
            t[i].clear();
        for (int i = 0; i < K; i++) // 거의최단경로 저장
            if (k[v[i].from][v[i].to] == 0)
                t[v[i].from].push_back({ v[i].to, v[i].d });

        // 다시 다익스트라 돌림
        pq.push({ S,0 });
        memset(d, 0x3f, sizeof(d));
        while (!pq.empty())
        {
            st n = pq.top(); pq.pop();
            for (st next : t[n.to])
            {
                if (d[next.to] > n.d + next.d)
                {
                    d[next.to] = n.d + next.d;
                    pq.push({ next.to, n.d + next.d });
                }
            }
        }
        if (d[D] == d[MAX - 1])
            printf("-1\n");
        else
            printf("%d\n", d[D]);
    }
}

インデックスツリー

#define PIV (1<<4) // 1~16 N 10만
int leafnode =   (1<<17); // N이 10만
int tree[PIV*2];
void update(int n, int v)
{
    n += PIV;
    tree[n] = v;
    n/=2; // 바로위 부모에서 시작
    while(n>0)
    {
        // 조상 = 왼쪽자식 + 오른쪽자식
        tree[n] = tree[n*2] + tree[n*2+1];
        n/=2; // 그 윗 조상으로 옮김
    }
}
int query(int l, int r) // 2~7 까지의 구간합
{
    l += PIV, r += PIV;
    int ret = 0;
    while(l<=r)
    {
        (l%2==1) ret += tree[l++];
        (r%2==0) ret += tree[r--];
        l/=2, r/=2;
    }
    return ret; 
}

//0,1,2... 라는 순서를 가지는 배열이 있을때
/// 3번째 값을 6으로 바꿔라 
int main()
{
    int ret = query(3,8); // 33
    update(2,6);
    ret = query(3,8); // 36
}

1572

// 중앙값.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
// https://www.acmicpc.net/problem/1572

#include <stdio.h>
#include <algorithm>
#define MIN -1
#define PIV (1<<18)
#define MAX 5005

using namespace std;

int N, K;
int tree[PIV * 2], m[PIV * 2];

int query(int i)
{
    int idx = 1;
    while (idx < PIV)
        if (tree[idx *= 2] < i)
            i -= tree[idx++];
    return idx - PIV;
}

void update(int i, int num)
{
    i += PIV;
    tree[i] += num;
    while(i>>=1)
        tree[i] += num;
}

int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b9426.txt", "r", stdin);
#endif
    scanf("%d %d", &N, &K);
    int mid;
    long long ans = 0;
    for (int i = 0; i < K; i++)
        scanf("%d", &m[i]), update(m[i], 1);

    for (int i = 0; i <= N - K; i++)
    {
        mid = query((K + 1) / 2);
        ans += mid;
        update(m[i], -1); // 이전 숫자 카운트는 줄이고
        scanf("%d", &m[i + K]);
        update(m[i + K], 1); // 다음숫자 카운트는 늘림
    }
    printf("%lld\n", ans);
    return 0;
}

14003(最大増加数列)

#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define PIV (1<<20) 
#define INF 1000000005
using namespace std;
int tree[PIV * 2];
void update(int n, int v)
{
    tree[n += PIV] = v;
    while (n >>= 1)
        tree[n] = max(tree[n], v);
}
int query(int n)
{
    int l = PIV, r = n + PIV;
    int ret = 0;
    while (l <= r)
    {
        if (l & 1) ret = max(ret, tree[l++]);
        if (!(r & 1)) ret = max(ret, tree[r--]);
        l >>= 1, r >>= 1;
    }
    return ret;
}
int N, b[PIV], p[PIV], r[PIV];
struct st {
    int n, th;
};
bool operator<(st a, st b)
{
    if (a.n == b.n)
        return a.th > b.th;
    return a.n < b.n;
}
st a[PIV];
int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b14003.txt", "r", stdin);
#endif
    scanf("%d", &N);
    for (int i = 0, n; i < N; i++)
        scanf("%d", &n), a[i] = { n, i }, p[i] = n;
    sort(a, a + N);
    int ans = 0, retval;
    for (int i = 0; i < N; i++)
    {
        int ret = query(a[i].th - 1);
        retval = ret + 1;
        update(a[i].th, retval);
        b[a[i].th] = retval;
        ans = max(ans, retval);
    }
    printf("%d\n", ans);

    int cnt = ans, ret = INF;
    for (int i = N - 1; i >= 0; i--)
        if (b[i] == cnt && p[i] < ret)
            r[--cnt] = p[i], ret = p[i];
    for (int i = 0; i < ans; i++)
        printf("%d ", r[i]);
    printf("\n");

}

1102

/*
백준 1102번 문제풀이
*/
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define MAX 17
#define PIV (1<<MAX)
using namespace std;
int N, P;
int p[MAX][MAX];
int dp[PIV + 1], cnt[PIV];
int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b1102.txt", "r", stdin);
#endif
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &p[i][j]); // i를 켜야 j가 켜짐. 그때 비용

    // 최초 켜져있는 발전소 세팅
    int bit = 0;
    char tmp[MAX];
    scanf("%s", tmp);
    for (int i = 0; i < N; i++)
        bit |= (tmp[i] == 'Y' ? (1 << i) : 0);
    memset(dp, 0x3f, sizeof(dp));
    dp[bit] = 0;
    int B = (1 << N);
    // 
    scanf("%d", &P);
    for (int i = 0; i < B; i++) 
        for (int j = 0; j < N; j++)
            if ((i&(1 << j))) cnt[i]++;

    for (int i = 0; i < B; i++) // 켜져있는 발전소들의 비트 변환수
    {
        for (int j = 0; j < N; j++) // j발전소가 켜져있는지 체크
        {
            if (!(i&(1 << j))) continue;
            for (int k = 0; k < N; k++) // k발전소가 켜질 수 있는지 체크해서 켬
            {
                if (j == k) continue;
                if (dp[i | (1 << k)] > dp[i] + p[j][k])
                    dp[i | (1 << k)] = dp[i] + p[j][k];
            }
        }
    }
    int ans = 1000000000;
    for (int i = 0; i < B; i++)
        if (cnt[i] >= P)
            ans = min(ans, dp[i]);
    if (ans == 1000000000) ans = -1;
    printf("%d\n", ans);
}