랭킹전

랭킹전

A - Fox and Number Game

CodeForces - 389A

제목의 뜻

한 열의 수를 제시하여 수 사이를 상감할 수 있다(대수-소수), 횟수를 제한하지 않고 이 열의 수가 얻을 수 있는 최소 총계를 구한다.

사고의 방향

관찰 데이터에 사고를 더하면 모든 수가 마지막에 같은 수로 변할 수 있다는 것을 발견할 수 있다. 바로 그들의 최대 공약수다.

코드

#include 
#include 
using namespace std;
int main(){
    int n, num[105];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", num+i);
    int ans = num[0];
    for (int i = 1; i < n;++i)
        ans = __gcd(ans, num[i]);
    printf("%d
", ans*n);
    return 0;
}

B - Fox and Cross

CodeForces - 389B

제목의 뜻

'.'와'#'로 구성된 정사각형 도면을 제시하고, 도면'#'이 몇 개의 십자를 중첩하지 않고 구성할 수 있는지 판단해야 한다.

사고의 방향

단순 DFS.

코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
char maps[105][105];
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};

void check(int x, int y) {
    if (x == 0 || x == n-1 || y == 0 || y == n-1)
        return;
    for (int i = 0; i < 4; ++i)
        if (maps[x+dir[i][0]][y+dir[i][1]] == '.')
            return;
    for (int i = 0; i < 4; ++i)
        maps[x+dir[i][0]][y+dir[i][1]] = '.';
    maps[x][y] = '.';
}

int main(){
    bool flag = 1;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%s", maps+i);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (maps[i][j] == '#')
                check(i, j);
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j)
            if (maps[i][j] == '#')
                flag = 0;
        //printf("%s
", maps[i]);
    }
    if (flag) printf("YES
");
    else printf("NO
");
    return 0;
}

C - Fox and Box Accumulation

CodeForces - 389C

제목의 뜻

몇 개의 열로 배열할 수 있도록 일렬수를 주시오.모든 숫자의 값은 이 숫자 앞에 허용되는 숫자의 개수를 나타낸다.최소한 몇 열은 배열해 주세요.

사고의 방향

욕심이 산더미 같다.먼저 순서를 정하고 처음부터 두루 훑어보고 한 줄의 첫 번째 줄을 취한 다음에 뒤로 수열을 두루 훑어보고 이 줄에 넣을 수 있는지 없는지를 하나하나 판단하고 표시한다.

코드

#include 
#include 
#include 

using namespace std;

int main(){
    int n, num[105], ans = 0, vis[105];
    memset(vis, 0, sizeof vis);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", num+i);
    sort(num, num+n);
    for (int i = 0, cnt = 0; i < n; ++i, cnt = 0) {
        if (vis[i]) continue;
        ++vis[i], ++cnt, ++ans;
        for (int j = i+1; j < n; ++j) {
            if (vis[j]) continue;
            if (num[j] >= cnt) ++vis[j], ++cnt;
        }
    }
    printf("%d
", ans);
    return 0;
}

D - Fox and Minimal path

CodeForces - 389D

제목의 뜻

숫자n를 제시하고 몇 개의 노드가 있는 그림을 구하세요.이 그림의 인접표를 출력합니다.이 그림의 점 1에서 점 2까지의 최단로의 줄 수는 n입니다.출력할 때 이 길이 존재하면 출력Y, 그렇지 않으면 N이다.

사고의 방향

노드 수를 최소화해야 한다는 제한이 없기 때문에 임의로.
처음에는 최대한 필요한 만큼만 찾아서 이 시계로 처리하면 된다고 생각했다.그러나 최단로를 어떻게 추가했는지 정확히 알지 못해 WA가 되었다.
우리는 방식을 바꾸었다.1가 시작점이고 2가 끝점이다.우리는 먼저 하나의 메인 체인을 확정했다. 메인 체인은 이 길이 몇 개의 노드를 통과할 것인지를 규정했다.그리고 시작점부터 메인 체인의 노드 수에 따라 부 체인에 노드를 추가합니다.여기에 부체인의 한 층에는 두 개의 노드가 있는데, 이렇게 n 층은 $2^n$경로이고, 이러한 원시 그림이 완성된 후에 $2^n+1$경로이다.
그리고 경로 수를 추가하는 것을 고려합니다.i+1층 메인체인과 i층 부체인이 연결되어 $2^{i-1}$경로를 추가할 수 있습니다.
여기까지 우리의 해법이 나왔다.우선 우리는 메인 체인이 있기 때문에 먼저n-=1;그리고 가장 큰 이진 비트를 찾아라. 이것이 바로 우리 주체인의 길이이다. 그리고 모든 이진 비트에 따라 추가할지 말지를 선택한다.

코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

int maps[107][107];

void addEdge(int a, int b) {
    maps[a][b] = maps[b][a] = 1;
}

int main(){
    int n, size = 0, t;
    scanf("%d", &n);
    t = --n;
    while (t) {
        ++size;
        t >>= 1;
    }
    if (!size) {
        printf("2
NY
YN
");
        return 0;
    }
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(1, 5);
    addEdge(size*3, 2);
    for (int i = 1; i < size; ++i) {
        addEdge(i*3, (i+1)*3);
        addEdge(i*3+1, (i+1)*3+1);
        addEdge(i*3+2, (i+1)*3+2);
        addEdge(i*3+1, (i+1)*3+2);
        addEdge(i*3+2, (i+1)*3+1);
    }
    int now = 0;
    while (n) {
        ++now;
        if (n&1) {
            if (now == size)
                addEdge(2, 3*now + 1);
            else
                addEdge(3*(now+1), 3*now+1);
        }
        n >>= 1;
    }
    size = size * 3 + 2;
    printf("%d
", size);
    for (int i = 1; i <= size; ++i) {
        for (int j = 1; j <= size; ++j)
            printf("%c", maps[i][j]?'Y':'N');
        printf("
");
    }
    return 0;
}

F - Water problem

HDU - 5867

제목의 뜻

천 이내의 숫자n를 주고 1부터 n까지의 영문 자모의 총수를 구하세요.공백과 하이픈은 계산되지 않습니다.

사고의 방향

표를 작성하고 1-100을 한 다음에 1-1000의 모든 답안을 미리 처리하고O(1) 출력한다.

코드

#include 
using namespace std;

int a[1001] ={
    0,
    3, 3, 5, 4, 4, 3, 5, 5, 4, 3,
    6, 6, 8, 8, 7, 7, 9, 8, 8, 6,
    9, 9, 11, 10, 10, 9, 11, 11, 10, 6,
    9, 9, 11, 10, 10, 9, 11, 11, 10, 5,
    8, 8, 10, 9, 9, 8, 10, 10, 9, 5,
    8, 8, 10, 9, 9, 8, 10, 10, 9, 5,
    8, 8, 10, 9, 9, 8, 10, 10, 9, 7,
    10, 10, 12, 11, 11, 10, 12, 12, 11, 6,
    9, 9, 11, 10, 10, 9, 11, 11, 10, 6,
    9, 9, 11, 10, 10, 9, 11, 11, 10, 10};

int main(){
    for(int i = 20; i < 100; i += 10)
        for(int j = i+1; j < i+10; ++j)
            a[j] = a[i]+a[j-i];
    for(int i = 100; i < 1000; i += 100){
        a[i] = a[i/100] + 7;
        for(int j = i+1; j <= i+99; ++j)
            a[j]=a[i]+3+a[j-i];
    }
    a[1000] = 3+8;
    for(int i = 2; i <= 1000; ++i)
        a[i] += a[i-1];
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d
", a[n]);
    }
    return 0;
}

H - Max Sum

HDU - 1003

제목의 뜻

최대 필드와 열을 구하는 열을 주십시오.

사고의 방향

점프 DP.생각을 좀 말해 보아라.우선 마이너스가 있기 때문에 최대치의 초기값을 마이너스로 기록하여 전체 마이너스 상황을 피한다.그리고 수열을 옮겨다니며 계수기에 넣고 계수기가 마이너스가 되면 0으로 돌아간다.기록의 최대치보다 크면 기록하고 현재 하위 세그먼트의 위치를 기록합니다.

코드

#include 
using namespace std;

int main(){
    int t, cas = 0;
    scanf("%d", &t);
    while (t--) {
        int n, a, left = 1, right = 1;
        int sum = 0, maxx = -1005, cur = 1;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i){
            scanf("%d", &a);
            sum += a;
            if (sum > maxx) {
                maxx = sum;
                left = cur, right = i;
            }
            if (sum < 0) {
                sum = 0;
                cur = i + 1;
            }
        }
        printf("Case %d:
%d %d %d
", ++cas, maxx, left, right);
        if (t) printf("
");
    }
    return 0;
}