Education CodeForces Round 25 문제 해결

Education CodeForces Round 25 문제 해결

Contest 825 Dashboard

A. Binary Protocol

제목의 뜻

01열을 주십시오. 이 열은 10진수 encode에서 얻을 수 있습니다. 방법은 모든 숫자가 같은 수량의 1이 되고 숫자 사이를 0으로 구분하는 것입니다.

사고의 방향

물?

코드

#include 
using namespace std;

int main(){
    int n, cur = 0, cnt = 0;
    char s[100], ans[100];
    scanf("%d%s", &n, s);
    for (int i = 0; i < n; ++i)
        s[i]-'0'? ++cnt : (ans[cur++] = cnt + '0', cnt = 0);
    ans[cur++] = cnt + '0';
    ans[cur] = '\0';
    puts(ans);
    return 0;
}

B. Five-In-a-Row

제목의 뜻

오자 바둑판을 제시하여 그 중에서'X'가 필승태인지 아닌지를 판단하다.

사고의 방향

모방하다.

코드

#include 
using namespace std;

char maps[15][15];
int dir[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
bool flag = 0;

void judge(int x, int y) {
    maps[x][y] = 'X';
    for (int i = 0, cnt = 0; i < 10; ++i) {
        maps[x][i] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, cnt = 0; i < 10; ++i) {
        maps[i][y] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j){
        int u = i, v = y - x + j;
        if (y < 0 || y > 9) continue;
        maps[u][v] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j) {
        int u = i, v = y + x - j;
        if (y > 9 || y < 0) continue;
        maps[u][v] == 'X'? ++cnt : cnt = 0;
        if (cnt == 5) flag = 1;
    }
    maps[x][y] = '.';
}

void check(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int u = x + dir[i][0], v = y + dir[i][1];
        if (u < 0 || v < 0 || u > 9 || v > 9) continue;
        if (maps[u][v] == '.') judge(u, v);
        if (flag) return;
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    for (int i = 0; i < 10; ++i) scanf("%s", maps[i]);
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j) {
            if (maps[i][j] == 'X') check(i, j);
            if (flag) goto a; //     
        }
a:
    puts(flag ? "YES" : "NO");
    return 0;
}

C. Multi-judge Solving

제목의 뜻

메이크스가 난이도i의 문제를 풀었다면 i*2의 문제를 풀 수 있었다.처음에 메이커스가 풀었던 최고 난이도 문제k는 리스트에 있는 모든 문제를 다 풀고 중간에 몇 문제를 발판으로 삼아야 하는지 물었다.

사고의 방향

욕심k를 수조에 넣고 순서를 정하고upper_bound 비교k 다음 한 문제를 얻어 그것을 만들 수 있는지 판단하고, 할 수 있다면 계속upper_bound하고, 그렇지 않으면 몇 문제가 필요한지 판단해서 발판으로 삼는다.

코드

#include 
using namespace std;

int main(){
    int n, k, num[1007], ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) 
        scanf("%d", num+i);
    num[0] = k;
    sort(num, num+n+1);
    for (int now = k, nxt = upper_bound(num, num+n+1, now<<1) - num, cur = 1; nxt <= n; nxt = upper_bound(num, num+n+1, now<<1) - num) {
        now = num[nxt-1], cur = nxt-1;
        nxt = upper_bound(num, num+n+1, now<<1) - num;
        while (nxt == cur+1 && nxt != n+1) {
            ++ans, now <<= 1;
            nxt = upper_bound(num, num+n+1, now<<1) - num;
        }
    }
    printf("%d
", ans);
    return 0;
}

D. Suitable Replacement

제목의 뜻

주열s과 모드열t을 제시하는데 주열 중 약간'?'이 있으니 이것'?'을 보충해야 한다.다음 문자열을 채우려면 임의의 순서에서 가장 많은 패턴 문자열을 찾을 수 있어야 합니다. t

사고의 방향

아날로그+욕심을 생각했는데 생각해보면 코드량이 많을 거예요.
Dalao의 코드를 보고 생각을 바꾸었다. 먼저 메인 열에 '?'를 제외한 문자의 수량을 통계했다.그리고 주열을 훑어보고 '?'가 나타날 때마다 현재'?'의 수량에 대응하는 t열의 위치를 찾습니다. 만약 이 위치가 문자가 주열에 포함된 것이라면 주열이라는 문자의 수량을 다시 이 '?'열을 훑어보고 주열에 없는 문자를 훑어볼 때까지 t열로 이 문자를 채웁니다.

코드

#include 
using namespace std;

const int maxn = 1e6+7;

int main(){
    int hash[26] = {}, cur = 0, len_t;
    char s[maxn], t[maxn];
    scanf("%s%s", s, t);
    len_t = strlen(t);
    for (int i = 0; s[i]; ++i) ++hash[s[i]-'a'];
    for (int i = 0; s[i]; ++i) if (s[i] == '?') {
        ++cur, cur %= len_t;
        hash[t[cur]-'a'] > 0 ? (--hash[t[cur]-'a'], --i) : s[i] = t[cur];
    }
    puts(s);
    return 0;
}

E. Minimal Labels

제목의 뜻

유방향 무환도를 제시하고 이 그림의 토폴로지 순서에 따라 이 그림의 각 노드에 표시를 하며, 표시의 배열을 요구하는 것은 사전 순서가 가장 작을 수 있는 것이다.

사고의 방향

처음에는 토폴로지 서열을 정상적으로 뛰고 우선순위로 가장 작은 표호를 주겠다고 생각했지만 해정거hack은 이런 방법을 썼다.주요 문제는 문제의 뜻을 제대로 읽지 못한 데 있다.나는 기호가 맞은 점의 번호 배열 사전의 순서가 가장 작다고 생각한다.
기왕 정면으로 안 된다면 거꾸로 해라.역방향 도면은 여전히 우선 대기열이고 토폴로지 순서 과정에서 가장 큰 점에 가장 큰 번호를 표시할 뿐이다.이렇게 욕심을 부리면 가장 잘 어울릴 수 있다.

코드

#include 
using namespace std;
//#define LOCAL

const int maxn = 1e5+7;

struct Edge {
    int to, nxt, dis;
}edge[maxn];

int head[maxn], tot;
int degree[maxn] = {}, v[maxn], n;

priority_queue q;

void init() {
    tot = 0;
    memset(head, -1, sizeof head);
    memset(degree, 0, sizeof degree);
}

void addnode(int u, int v) {
    ++degree[v];
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}

void topo_sort(int n) {
    int cur = n;
    for (int i = 1; i <= n; ++i)
        if (!degree[i]) q.push(i);
    while (!q.empty()) {
        int u = q.top(); q.pop();
        v[u] = cur--;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].to;
            --degree[v];
            if (!degree[v]) q.push(v);
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    init();
    int m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) v[i] = i;
    for (int i = 0, u, v; i < m; ++i) {
        scanf("%d%d", &v, &u);
        addnode(u, v);
    }
    topo_sort(n);
    for (int i = 1; i < n; ++i)
        printf("%d ", v[i]);
    printf("%d
", v[n]);
    return 0;
}