[문제 해결 보고서] Codeforces Round #374(Div.2)

제목 링크
A.One-dimensional Japanese Crossword(Codeforces 721A)
사고의 방향
이 문제는 문자열에 연속된 'B 블록' 의 블록 수와 각 블록의 길이를 통계하는 것이다.문자열의 'W' 를 모두 공백으로 바꾸고 문자열 문자열을 만들 수 있으며, 문자열 흐름에서 'B 블록' 을 대표하는 문자열을 입력하면서 문자열의 길이를 통계하면 답을 얻을 수 있다.
코드

#include 
using namespace std;

int n;
string s;
vector <int> ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'W') {
            s[i] = ' ';
        }
    }
    stringstream ss(s);
    while(ss >> s) {
        ans.push_back(s.size());
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

B. Passwords(Codeforces 721B)
사고의 방향
암호는 길이순으로 입력되고 같은 길이의 암호는 무작위로 입력되기 때문이다.따라서 가장 좋은 상황은 실제 비밀번호보다 길이가 적은 비밀번호를 입력한 후 (sum개 설정) 바로 실제 비밀번호를 입력하는 것이다.시간=벌시+진실시간=sum/k×5+sum+1 . 최악의 경우 실제 비밀번호보다 길이가 작은 비밀번호를 입력한 후 실제 비밀번호와 길이가 같은 다른 비밀번호(num - 1개로 설정)를 모두 입력해야 실제 비밀번호를 입력할 수 있다. 시간=벌시+실제 시간=(sum+num - 0.1)/k×5+sum+num .
코드

#include 
using namespace std;

const int maxn = 200;
int n, k, a, b, len, sum, num, cnt[maxn];
string s;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> s;
        cnt[s.size()]++;
    }
    cin >> s;
    len = s.size();
    for(int i = 1; i < len; i++) {
        sum += cnt[i];
    }
    num = cnt[len];
    a = sum / k * 5 + sum + 1;
    b = (sum + num - 1) / k * 5 + sum + num;
    cout << a << ' ' << b << endl;
    return 0;
}

C.Journey(Codeforces 721C)
사고의 방향
본 문제의 그림은 유방향 무환 연결도이기 때문에 이 그림에서 어떤 최대치를 구해야 한다.그래서 자연스럽게 동태적인 기획으로 해결하려고 한다.그러나 동적 기획은'순서'가 필요하고 이 그림은 순서가 없기 때문에 점 1부터 이 그림에 대해 토폴로지 순서를 만들고 동적 기획을 하려고 한다.그러나 토폴로지 정렬 과정에서 동적 기획은 동시에 진행할 수 있다.d[i][j]를 i에서 n까지 j개의 노드를 지나는 데 걸리는 최소 시간으로 정의합니다.그 중에서 d[u][j]=min(d[u][j], d[v][j-3-1]+w), 그 중에서 v는 토폴로지 서열 중 u의 다음 점이고 다른 w는 변경권(시간)이다.주어진 u와 j에 대해 v는 모든 상황을 포괄해야만 d[u][j]를 업데이트할 수 있습니다.주인공이 걷는 순서에 따라 출력점의 번호를 출력하기 위해 d[u][j]를 업데이트할 때 이 상황에서 u의 다음 노드를 기록하여 x[u][j]에 저장한다.시간을 T초로 제한하기 위해서는 d수조의 모든 값을 T+1으로 초기화하고 d[n][1]=0으로 해야 한다.이 알고리즘에서 모든 점은 한 번만 방문하고 방문된 점은 O(n)의 동적 기획만 하고 모든 변도 한 번만 방문하기 때문에 시간 복잡도는 O(n2+m)이다.
코드

#include 
using namespace std;

typedef pair <int, int> p;
const int maxn = 5010;
bool vis[maxn];
int n, m, T, u, v, w, ans, cur, x[maxn][maxn], d[maxn][maxn];
vector  G[maxn];

//             
void dfs(int u) {
    vis[u] = true;
    for(int i = 0; i < G[u].size(); i++) {
        p& node = G[u][i];
        int v = node.first;
        int w = node.second;
        if(vis[v] == false) {
            dfs(v);
        }
        for(int j = 2; j <= n; j++) {
            if(d[u][j] > d[v][j-1] + w) {
                //     
                d[u][j] = d[v][j-1] + w;
                //     
                x[u][j] = v;
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &T);
    while(m--) {
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back(p(v, w));
    }
    //    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            d[i][j] = T + 1;
        }
    }
    d[n][1] = 0;
    //     
    dfs(1);
    for(int j = n; j >= 1; j--) {
        if(d[1][j] <= T) {
            ans = j;
            break;
        }
    }
    printf("%d
", ans);
    //        
    cur = 1;
    for(int i = ans; i >= 1; i--) {
        printf("%d ", cur);
        cur = x[cur][i];
    }
    return 0;
}

D.Maxim and Array(Codeforces 721D)
사고의 방향
서열의 적은 두 개의 값에 의해 유일하게 결정된다. 하나는 적의 음호이고, 다른 하나는 적의 절대값이다.적의 기호가 플러스일 때, 서열에서 절대값이 가장 작은 원소를 끊임없이 줄이기만 하면 적의 크기를 줄일 수 있다.적의 기호가 마이너스일 때 적의 절대값만 커지면 적의 크기를 줄일 수 있다.적의 절대값을 증가시키기 위해 서열에서 절대값이 가장 작은 원소를 찾아 절대값을 증가시키면 된다.그러면 우리는 k를 줄이는 동시에 축적된 기호sign을 유지하고 그 값에 따라 해당하는 조작을 수행할 수 있다.현재 상태에서 시퀀스에서 절대값이 가장 작은 요소를 동적으로 얻기 위해서입니다.우리는 서열의 모든 요소의 절대값을 유지하기 위해 무더기를 사용해야 한다.이렇게 전체적인 복잡도는 O(nlogn)이다.
코드

#include 
using namespace std;

typedef long long ll;
typedef pair int> p;
const int maxn = 2e5 + 5;
// sign     0，       
int n, k, x, v, d, sign, flag;
ll a[maxn];
priority_queue < p, vector, greater
 > pq;

int main() {
    scanf("%d%d%d", &n, &k, &x);
    for(int i = 0; i < n; i++) {
        scanf("%I64d", &a[i]);
        //         ，      
        pq.push(p(abs(a[i]), i));
        //  a[i]          
        sign ^= (a[i] < 0);
    }
    //          
    while(k--) {
        p tmp = pq.top();
        pq.pop();
        v = tmp.first;
        d = tmp.second;
        //          
        flag = (a[d] < 0);
        //          
        a[d] += (sign ^ flag ? 1 : -1) * x;
        //         sign
        sign ^= flag ^ (a[d] < 0);
        pq.push(p(abs(a[d]), d));
    }
    for(int i = 0; i < n; i++) {
        printf("%I64d ", a[i]);
    }
    return 0;
}

(기타 제목 약)