C. Vasya and String

꿈틀꿈틀, inch worm

출처: CodeforcesC. Vasya and String

파라메트릭 서치로도 풀 수 있다.

[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<cmath>
#include<cstring>
using namespace std;

string str;
int ans = 1;
int k, n;
int main(){
    //freopen("input.txt", "r", stdin);
    cin >> n >> k >> str;

    int l, r;
    l = r = 0;
    int tk = k;
    while (r < str.size()){
        if (str[r] == 'b') tk--;
        r++;
        while (tk < 0 && l < r){
            if (str[l] == 'b') tk++;
            l++;
        }
        ans = max(ans, r - l);
    }

    l = r = 0;
    tk = k;
    while (r < str.size()){
        if (str[r] == 'a') tk--;
        r++;
        while (tk < 0 && l < r){
            if (str[l] == 'a') tk++;
            l++;
        }
        ans = max(ans, r - l);
    }

    cout << ans;

    return 0;
}

D. Hamiltonian Spanning Tree

tree, path, mst

출처: Codeforces D. Hamiltonian Spanning Tree

SOL)

x >= y 일 경우

만약 한 정점에서 나머지 모든 정점에 방문할 수 있는 모양이면 y(n-2) + x

아니면  y*(n-1)

x < y 일 때

최대한으로 이용할 수 있는경로의 수를 구하면 된다

배열을 사용하지 않는 방법도 있지만 좀 생각이 필요하다.

[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<climits>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const int N = 200010;

vector<int> adj[N];
int can[N];
int n, x, y;
int dfs(int here, int pr = -1){
    int res = 0;
    can[here] = 2;
    for (int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        if (next == pr) continue;

        res += dfs(next, here);
        if (can[here] > 0 && can[next] > 0){
            can[here]--;
            can[next]--;
            res++;
        }
    }
    return res;
}

int main(){
    //freopen("input.txt", "r", stdin);

    cin >> n >> x >> y;

    for (int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if (x >= y) {
        bool check = false;
        for (int i = 1; i <= n; i++){
            if (adj[i].size() == n - 1)
                check = true;
        }
        if (!check){
            cout << 1LL * (n - 1) *y;
        }
        else
            cout << 1LL * (n - 2) *y + x;
    }
    else{

        int use = dfs(1);
        cout << 1LL * use *x + 1LL*(n - use - 1)*y;
    }
    return 0;
}

연산자

연산자

~ 1의 보수 (ex !1001 = 0110)
! NOT (ex !111 = false, !1 = false, !0 = true)
^ XOR

색칠 공부

graph, number of cases

출처: BOJ 색칠 공부

SOL)
size가 4부터
싸이클이의 점화식이 아래와 코드와 같이 나온다.
dfs를 통해 싸이클의 사이즈를 알아내고
ans에 곱해준 후 total_cycle에 사이즈를 더해준다.

마지막으로 처리가 되지 않은 직선 점들을 처리해준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const ll mod = 1000000007;
const int N = 1000010;
int visit[N];
ll cycle[N];
int f[N];
int n, k;
int t = 1;
ll ans = 1;

int search_cycle(int start){
    int curr = start;
    while (1){
        if (visit[curr] != 0 && visit[curr] < visit[start])
            return 0;
        else if (visit[curr] != 0)
            return t - visit[curr];
        visit[curr] = t++;
        curr = f[curr];
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++){
        scanf("%d", &f[i]);
    }
    cycle[0] = 1;
    cycle[1] = k;
    cycle[2] = cycle[1]* (k - 1) % mod;
    cycle[3] = cycle[2] * (k - 2) %mod;
    for (int i = 4; i <= n; i++){
        cycle[i] = (((k - 2)*cycle[i - 1] % mod) + ((k - 1)*cycle[i - 2] % mod)) % mod;
    }

    int total_cycle = 0;
    for (int i = 1; i <= n; i++){
        if (visit[i] == 0){
            int c = search_cycle(i);
            ans = (ans * cycle[c]) % mod;
            total_cycle += c;
        }
    }

    for (int i = 0; i < n - total_cycle; i++){
        ans = ans* (k - 1) % mod;
    }

    printf("%lld", ans);

    return 0;
}

귀농

dp, partial sum

출처: BOJ 귀농

SOL)
무조건 전부 탐색을 하면 n^6정도의 시간복잡도가 나온다.
수익의 합이 최대 2500000이 안넘는 것을 이용한다.
정해진 위치에서 상근이가 만들 수 있는 총 수익 조합을 checked배열에
업데이를 해놓고 선영이가 만들 수 있는 수익에 checked값을 그냥 답에
더해준다. 즉, 만약 상근이가 만들 수 있었다면 알아서 답이 증가했을 것이다.

방향은 (왼쪽 위, 오르쪽 아래), (오른쪽 위, 왼쪽 아래) 경우가 나오는데
전자의 경우를 계산했다면 checked배열을 왼상태로 돌려놓고
후자의 경우를 계산해준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const int mx = 50 * 50 * 1000;

int bot[100][100];
int psum[100][100];
int checked[2 * mx + 100];
int n;
int ans = 0;

void cal(int r, int c){
    //1
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][c] - psum[i - 1][c] - psum[r][j - 1] + psum[i - 1][j - 1];

            checked[val+mx]++;
        }
    }
    //1-2
    for (int i = r + 1; i <= n; i++){
        for (int j = c + 1; j <= n; j++){
            int val = psum[i][j] - psum[r][j] - psum[i][c] + psum[r][c];
            ans += checked[val+mx];
        }
    }
    //1-3
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][c] - psum[i - 1][c] - psum[r][j - 1] + psum[i - 1][j - 1];

            checked[val+mx]--;
        }
    }
    /////////////////////////////////

    //2-1
    for (int i = 1; i <= r; i++){
        for (int j = n; j >= c; j--){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][j] - psum[i - 1][j] - psum[r][c - 1] + psum[i - 1][c - 1];

            checked[val+mx]++;
        }
    }
    //2-2

    for (int i = r + 1; i <= n; i++){
        for (int j = c - 1; j >= 1; j--){
            int val = psum[i][c-1] - psum[i][j-1] - psum[r][c - 1] + psum[r][j-1];
            ans += checked[val+ mx];
        }
    }

    //2-3
    for (int i = 1; i <= r; i++){
        for (int j = n; j >= c; j--){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][j] - psum[i - 1][j] - psum[r][c - 1] + psum[i - 1][c - 1];

            checked[val+mx]--;
        }
    }

}

int main(){
    //freopen("input.txt", "r", stdin);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            scanf("%d", &bot[i][j]);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){

            for (int r = 1; r <= i; r++){
                for (int c = 1; c <= j; c++){
                    psum[i][j] += bot[r][c];
                }
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){

            cal(i, j);
        }
    }

    printf("%d", ans);

    return 0;
}

음식 평론가

math, divide

출처: BOJ 음식 평론가

SOL)
길이 1짜리 소시지를 일열로 쭉 이어 놓고 생각을 하면
총길이가 n짜리인 소시지가 나올 것이다.
이것을 이제 m등분하는 것이다.
즉 최소 m-1번 보다는 답이 커질 수 없다.

*그런데 n/m 길이 만큼 컷팅을 하는데
이미 잘려있는 곳을 또 자르는 경우가 있다.
이것을 찾아내어 답에서 -1을 빼준다.

n/m = (등분해야 할 길이)

(n/m) x i = (현재 확실히 컷팅한 길이)

n x i = m(현재 확실히 컷팅한 길이)

여기서 현재 확실히 컷팅한 길이가 정수형태가 나오면
이미 처음부터 잘려진 길이이다.
그래서 (n x i) % m == 0이면 답에서 1을 빼준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);


int main(){
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;

    if (n % m == 0) cout << 0;
    else {
        if (n > m) n -= m;
        int ans = m;
        for (int i = 1; i <= m; i++){
            if (i *n % m == 0) ans--;
        }
        cout << ans;
    }

    return 0;
}