牛客小白月試合21--題解報告

牛客小白月試合21–題解報告
時間:2020.01.19人のブログ:https://wyjoutstanding.github.io/初めてアルゴリズムの試合に参加して、記録します
文書ディレクトリ

牛客小白月試合21--題解報告

A. Audio

構想分析

ACコード(C++11、手算xy)

B. Bits

構想分析

ACコード(C++11,ハンノタワー再帰設計)

C. Channels

構想分析

ACコード(C++11、固定起点)

D. DDoS

構想分析

ACコード(C++11、トポロジーソート、dpカウント)

E. Exams

構想分析

ACコード(C++11)

F. Fool Problem

構想分析

ACコード(C++11、法則を探す)

G. Game

構想分析

ACコード(C++11、素因数分解)

H. "Happy New Yaer!"

ACコード(C++11)

I. I love you

構想分析

ACコード(C++,サブシーケンスカウント+dpスクロール配列)

J. Jelly

構想分析

ACコード(C++11,三次元迷路+BFS)

まとめ

タイトル番号
テストポイント
コメント
A
がいぶしんざひょうけいさん
手算/線形方程式
B
ハノタ再帰設計
手動デバッグ
C
接頭辞および/線形化
固定始点(日付計算)
D
トポロジのソート、パス数
単純dp,bfs
E
単純シミュレーション
四捨五入に注意する
F
法則を探して、大きい整数
手動推定/一般式帯入化簡略
G
しつりょうぶんかい
素因数の数を計算するだけ
H
ちょくせつしゅつりょく
問題にサインする.
I
サブシーケンスカウントdp
連続と非連続を含むスクロール配列最適化(逆ループ)
J
3 Dラビリンス
BFS検索6方向
難易度のソート:

署名:H

一般:A,C,E,J(単純シミュレーション)

思考:F,G(法則が見つかった後は巨大で簡単)

難しい:B,D,I(設計dp,図論,再帰探索)

A. Audio
構想分析
3点座標が既知で、外心座標(中垂線交点)を解く.

は直接2点式で直線方程式を書き、2元一次方程式を連立して解き、手で(x,y)結果を算出することができる.

またはガウス消元を用いて線形方程式を解く.

ACコード(C++11,手算xy)

#include
using namespace std;
int main() {
    double p[3][2], m[2][2], A[2], B[2]; //     ，    ，      
    for (int i = 0; i < 3; i ++) scanf("%lf %lf", &p[i][0], &p[i][1]);
    for (int i = 0; i < 2; i ++) {
        m[i][0] = (p[i][0] + p[i+1][0]) / 2; // x
        m[i][1] = (p[i][1] + p[i+1][1]) / 2; // y
        A[i] = p[i][0] - p[i+1][0]; //    x
        B[i] = p[i][1] - p[i+1][1]; //    y
    }
    double x, y;
    x = -(-B[1]*A[0]*m[0][0] - B[0]*B[1]*m[0][1] + B[0]*B[1]*m[1][1] + B[0]*A[1]*m[1][0]) / (B[1]*A[0] - B[0]*A[1]);
    y = m[0][1] - A[0]*(x-m[0][0])/B[0];
    printf("%.3lf %.3lf
", x, y);
    return 0;
}

B. Bits
構想分析
極めて興味深い問題で、ハノタの再帰抽象原理を深く理解した.
元のハンノタワーに基づいて、パリティの配置位置を制御すればいいだけです.
再帰的な設計は比較的簡単で、手動でプレゼンテーションを行うことをお勧めします.

void hanoi(int n, vector<int>& A, vector<int>& B, vector<int>& C) { //     ：   A  n     B   C
    if (n == 1) { // 1     
        move(A, C);
        return;
    }
    hanoi(n-1, A, C, B); // A  n-1     C   B
    move(A, C);
    hanoi(n-1, B, A, C);
}

ACコード(C++11,ハノータ再帰設計)

#include
using namespace std;
int n, cnt = 0, p[3]; //    ，    ，       
vector<int> V[3]; // 3   
char a[20][100]; //     
void showRst() { //     
    int N = 3*(2*n+1) + 4; //   
    for (int i = 0; i < n + 3; i ++) { //    
        for (int j = 0; j < N; j ++) {
            if (i == n + 2) a[i][j] = '-';
            else {
                if (i != 0 && (p[0] == j || p[1] == j || p[2] == j)) a[i][j] = '|';
                else a[i][j] = '.';
            }
        }
    }
    for (int i = 0; i < 3; i ++) { //            
        int j = n+1; //  n+1    
        for (auto k : V[i]) {
            for (int k2 = p[i] - k; k2 <= p[i] + k; k2 ++) a[j][k2] = '*'; //     ：2k+1
            j --;
        }
    }
    ++ cnt; //       
    for (int i = 0; i < n+3; i ++) { //       
        if ((cnt == 1 << n) && i == n + 2) break; //             
        for (int j = 0; j < N; j ++) printf("%c", a[i][j]);
        printf("
");
    }
}
void move(vector<int>& A, vector<int>& B) { //  A         B        
    B.push_back(A.back());
    A.pop_back();
    showRst(); //        
}
void hanoi(int n, vector<int>& A, vector<int>& B, vector<int>& C) { //     ：   A  n     B   C
    if (n == 1) { // 1     
        move(A, C);
        return;
    }
    hanoi(n-1, A, C, B); // A  n-1     C   B
    move(A, C);
    hanoi(n-1, B, A, C);
}
int main() {
    scanf("%d", &n);
    for (int i = n; i > 0; i --) V[0].push_back(i); //    
    for (int i = 0; i < 3; i ++) {
        p[i] = (2*n+2)*i + 1 + n; //        
    }
    showRst(); //     
    if (n % 2 == 0) hanoi(n, V[0], V[1], V[2]); //             
    else hanoi(n, V[0], V[2], V[1]);
    return 0;
}

C. Channels
構想分析
時間帯解(接頭辞和)と同様に,始点1を固定し,それぞれ1(t 1−1)と1 t 2の時間を算出し,差をつけて結果とする.
時間1~tの解については,除法と余剰を求めればよい.
ACコード(C++11、固定起点)

#include
using namespace std;
long long getTime(long long t) {
    long long mod = t % 60;
    return (t / 60) * 50 + ((mod <= 50) ? mod : 50);
}
int main() {
    long long t1, t2;
    while(scanf("%lld %lld", &t1, &t2) == 2) {
        printf("%lld
", getTime(t2) - getTime(t1-1));
    }
    return 0;
}

D. DDoS
構想分析
タイトルの意味がはっきりしないで、天然痘が散らばっていると言って、実は1つの有向無環図を与えて、結点1~nの経路の条数を探し出します.
ここでの最良のポリシーは、同じ時間にリクエストを受信するほど、各パスの開始時間を調整することによって、nに到達するすべてのリクエスト時刻を一致させることができるため、攻撃が成功することを意味する.
したがって、トポロジーソート中に経路数の計算が完了し、dp[i]は1からiまでの経路数を表し、一方向エッジu->vに対してuの入度が0の場合、dp[v]+=dp[u]
型取りに注意し、かつ重辺の問題を考慮する必要があり、隣接テーブルで記憶すれば考慮する必要はない
テストサンプル:

//  
5 8
1 2 3
1 3 1
2 5 1
3 5 3
1 2 3
1 4 1
2 4 1
4 5 1
//  
6

ACコード(C++11,トポロジーソート,dpカウント)

#include
using namespace std;
#define MAXN 100010
#define MOD 20010905
vector<int> adj[MAXN], dp(MAXN, 0), indegree(MAXN, 0); //    ，dp[i]      i    ，  
int main() {
    int n, m, u, v, w;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i ++) {
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(v);
        indegree[v] ++; //     
    }
    //           
    queue<int> q;
    for (int i = 1; i <= n; i ++) { //        0    
        if (indegree[i] == 0) {
            dp[i] = 1;
            q.push(i);
        }
    }
    while(!q.empty()) {
        u = q.front(); q.pop();
        for (auto i : adj[u]) {
            dp[i] = (dp[i] + dp[u]) % MOD; //             
            indegree[i] --; //     
            if (indegree[i] == 0) q.push(i); //    0   
        }
    }
    printf("%d
", dp[n]);
    return 0;
}

E. Exams
構想分析
問題の規定に基づいて点数を計算すればいいです.以下の点に注意してください.

カリキュラムの性質が任意(番号2)の非計算

各科平時分、期間中、期末点数に相応の割合を乗じて加算した後、四捨五入して

を取る必要がある.

最終結果は四捨五入(小数2桁保持、すなわち千分位まで解く)

を必要とする.
ACコード(C++11)

#include
using namespace std;
int main() {
    double credit, tot=0.0, s, p, sum1=0.0, sum2=0.0;
    int n, t;
    scanf("%d", &n);
    while(n --) {
        tot = 0.0;
        scanf("%d %lf", &t, &credit);
        for (int i = 0; i < 3; i ++) {
            scanf("%lf %lf", &s, &p);
            tot += s * p;
        }
        if (t != 2) { //       
            sum1 += credit; //     
            sum2 += (int)(tot+0.5) * credit; //     
        }
    }
    //         ，           
    double ans = sum2 / sum1;
    ans = (int)(ans*100+0.5) / 100.0;
    printf("%.2lf
", ans);
    return 0;
}

F. Fool Problem
構想分析
フィボナッチの数列はリニューアルされ、2つの考え方で、fn=(-1)^nを発見しやすい.

直接法則を探して、4つの差を列挙して多く発見することができます.

fnの汎用式を式に持ち込み、簡略化して結果を得ることができる.

入力値については,一見大きな整数処理が必要であるが,実際には使わず,文字列で読み込み,最後のビットのパリティを判断するだけでよい.
ACコード(C++11、法則を探す)

#include
using namespace std;
int main() {
    string s;
    cin >>s;
    printf("%d
", ((s.back() - '0') % 2 == 0) ? 1 : -1);
    return 0;
}

G. Game
構想分析
操作可能回数は,nの素因数個数−1である.例えば8=2*2*2、3つの素因数は、2回の分解操作を行うことができ、さらに例えば40=2*2*2*5、4つの素因数、3回の分解操作を行うことができる.
このほか,n=1の場合は特例であり,0回の分解操作である.
ACコード(C++11,素因数分解)

#include
using namespace std;
#define N 400
int main() {
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 2; i < N && n != 1; i ++) { //            
        while(n % i == 0 && n != i) { //          
            cnt += 1; //     
            n /= i; //     
        }
    }
    printf("%s
", ((cnt % 2) == 0) ? "Nancy" : "Johnson");
    return 0;
}

H. “Happy New Yaer!”
問題にサインして、問題を出力すればいいです.
ACコード(C++11)

#include
using namespace std;
int main() {
    printf("\"Happy New Year!\"");
    return 0;
}

I. I love you
構想分析
サブシーケンスカウント、単純dpプラススクロール配列最適化.
dp[i]は、現在の長さにおいて、S[1...i]シーケンスを満たすシナリオ数を表し、次の文字chおよびchの前の文字から個数を算出する.
スクロール配列で最適化すると,aaのような同じアルファベット照射感染を避けるために逆順序で解くことが望ましい(ただし,この問題は存在しない)
ACコード(C++,サブシーケンスカウント+dpスクロール配列)

#include
using namespace std;
#define MOD 20010905
int dp[9] = {1,0}; // dp[0]=1，         
int main() {
    string s, str = "tiloveyou";
    cin >> s;
    for (auto ch : s) {
        for (int i = 8; i >= 1; i --) { //     ，             
            dp[i] = (dp[i] + (str[i] == tolower(ch)) * dp[i-1]) % MOD; // DP      
        }
    }
    printf("%d
", dp[8]);
    return 0;
}

J. Jelly
構想分析
2 D迷宮は段階的に進み,3 D迷宮はbfsで解いた.
2 D迷路を前後左右4方向に遍歴した上で、上下2方向を増やすだけです.
ACコード(C++11,三次元迷宮+BFS)

#include
using namespace std;
#define N 101;
int maze[101][101][101] = {0}; //       ，1    
int dict[6][3] = {{0,0,1}, {0,0,-1}, {0,1,0}, {1,0,0}, {0,-1,0}, {-1,0,0}}; //             (x,y,z)
struct Pos {
    int x, y, z, d; // x,y,z     
    Pos(int _x, int _y, int _z, int _d): x(_x), y(_y), z(_z), d(_d){}
    Pos(){}
}pos;
int n, x, y, z, ans = -1;
int main() {
    char t;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            for (int k = 0; k < n; k ++) {
                scanf(" %c", &t); //            
                if (t != '.') maze[i][j][k] = 1; //    
            }
        }
    }
    queue<Pos> q;
    q.push(Pos(0,0,0,1));
    while(!q.empty()) { // BFS
        pos = q.front();
        q.pop();
        if (pos.x == n - 1 && pos.y == n-1 && pos.z == n-1) { //   
            ans = pos.d;
            break;
        }
        for (int i = 0; i < 6; i ++) { // 6   
            x = pos.x + dict[i][0]; y = pos.y + dict[i][1]; z = pos.z + dict[i][2];
            if (x >= 0 && x < n && y >= 0 && y < n && z >= 0 && z < n //     
            && maze[x][y][z] == 0) { //    
                maze[x][y][z] = 1; //      
                q.push(Pos(x,y,z,pos.d+1));
            }
        }
    }
    printf("%d
", ans);
    return 0;
}

まとめ
小白月試合と言って、初めてアルゴリズムの試合に参加して、4つの問題しかできなくて、汗の顔をして、そのため、2日間使ってできない問題を補充して、実は本当に難しくなくて、ただ初めて出会ってどうすればいいか分かりません.
この問題はあまり厳密ではなく、テスト用例の規模の説明が少なすぎて、問題名がシーケンス番号と一致するためにこじつけられているように見えます.
しかし、試合という形で学習効率を高めることができ、他人のACコードを見て多くのことを学ぶことができます.
アルゴリズムを書くのは確かに多くの問題に対してもっと深い理解があって、例えばハノータ、大きい1 C言語はやったことがあって、ここでもう一度来て、全体の過程は明らかに少なくなくて、同時にまたどのように線形方程式のグループといくつかの基礎の数論の知識を解くことをマスターしました.