『コンピュータ大学院受験——機械試験ガイド』知識点整理

「コンピュータ大学院受験--機械試験ガイド」という本の知識点を簡単に復習し整理し、内容は比較的簡潔で要約されている.自分の能力と精力が限られているので、一部の内容はまだ補充しなければならないので、私と一緒に整理して、興味があれば下に伝言を残してほしいです.
にゅうしゅつりょく

scanf関数には戻り値があり、正常に与えられた変数の個数を返します.ファイルの読み書きを続けるには、

と書くことができます.

while (scanf("%d", &n) != EOF){
    pass;
}

または

while(gets(     ))

は、%4 dを使用して入力の最初の4桁の数字を取得し、%2 d%2 dを使用して後の4桁の数字を取得することができる.

ツールバーの
このsort関数は,実際に入力時にソートされる開始アドレスと終了アドレスである.C++の配列名はポインタと等価であるため,ポインタ操作は配列に格納された変数サイズ単位であると理解すればbuf+nは配列の終了位置が配列の終了アドレスである.

#include 

sort(buf, buf + n); //buf   ，n       

sortのソート規則をカスタマイズして、新しいcmp関数を定義することができます.覚えている限り、cmpがtrueを返すと、cmpの最初のパラメータが第2のパラメータの前に並んでいることを示します.
降順の表記:

#include 

bool cmp(int x, int y){
    return x > y;
}

sort(buf, buf + n, cmp); //buf   ，n       

構造体ソート方法は、cmpを定義したり、リロードしたりすることができます.
定義cmp:

struct E{
    char name[101];
    int age;
    int score;
}
int cmp(E a, E b){
        if(score != b.score) return score < b.score;
        int tmp = strcmp(name, b.name);
        if (tmp != 0): return tmp < 0;
        else return age < b.age;
}

じゅうか

struct E{
    char name[101];
    int age;
    int score;
    bool operator < (const E &b) const{
        if(score != b.score) return score < b.score;
        int tmp = strcmp(name, b.name);
        if (tmp != 0): return tmp < 0;
        else return age < b.age;
    }
}

データ構造
スタック

#include 

stack<int> S;

S.push(i);
int x = S.top();
S.pop();

プライオリティキュー

#include 

priority_queue<int> Q;  //      
priority_queue<int, vector<int>, greater<int>> Q; //   

Q.push(i);
int x = Q.top();
Q.pop();

ストリング

#include 

string s;
cin >> s;
char str[] = "test";
s = str;

s += 'c';
s += "string";
string b = "class";
s += b;

string b = "class";
string a = "Two";
if (a <= b){
    cout << a;
}

for (int i = 0; i < s.size(); i++){
    char c = s[i];
}

s.erase(10, 8)

string a = "asfasdfadfadfa"
string b = "dfs"

int startPos = 0;
int pos = a.find(b, startPos);

string a = "AAAA";
string b = "BBB";
a.insert(2, b);
cout << a << endl;

数学の問題
%演算子
(a * b) % c = (a%c * b%c) % c
(a + b) % c = (a%c + b%c) % c
最大公約数(GCD)
a,bがすべて0である場合、gcdは存在しない.もし0があれば、gcdはゼロではありません.いずれも0でない場合は、次のようになります.
gcd(a, b) = gcd(b, a % b);
a,bのgcdコードを求めます:

int gcd(int a, int b){
    if (b == 0) return a;
    else return gcd(b, a % b);
}

最小公倍数(LCM)
a,bの最小公倍数は、それらの最大公約数を2数積で割ったものである.

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

素数を求める
基本解法は遍歴です.

#include 

bool isPrime(int n) {
    for (int i = 2; i <= (int) sqrt(n) + 1; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;//     ，   
}

少しステップアップする方法は素数ふるい法です.次のinit()関数を使用して、flag[i]=trueの場合、前100000の最初の10000の素数を求めることができます.

int prime[1000001];
int flag[1000001];
int size;

void init() {
    size = 0;
    for (int i = 1; i <= 1000000; i++) {
        flag[i] = false;
    }
    for (int i = 2; i <= 1000000; i++) {
        if (flag[i]) {
            continue;
        }
        prime[size++] = i;
        if(i >= 10000) continue;
        for (int j = i * i; j <= 1000000; j += i) {
            flag[j] = true;
        }
    }
}

にぶんべき乗
aのb乗をすばやく求める.

long long pow(int a, int b){
    long long ans = 1;
    while(b != 0){
        if(b % 2){
            ans *= a;
        }
        b /= 2;
        a *= a;
    }
    return ans;
}

典型的なテーマ:
【九度OJ】題目1441:人見人愛A^B
図論
コレクションを調べる
セットコードが通用していることを調べて、暗記すればいいです.

#define size 1000

int Tree[size];

void init(){
    for (int i = 1; i <= n; i++) {
        Tree[i] = -1;//  
    }
}

int findRoot(int x) {
    if (Tree[x] == -1) {//        
        return x;//             ，   -1
    } else {
        int temp = findRoot(Tree[x]);//     
        Tree[x] = temp;//             
        return temp;
    }
}

void union(int x, int y){
    int aRoot = findRoot(a);//     
    int bRoot = findRoot(b);
    if (aRoot != bRoot) {//       
        Tree[aRoot] = bRoot;//     
    }
}

典型的なテーマ:
【九度OJ】問題1012:円滑工事
最小生成ツリー(MST)
Kruskalアルゴリズム:

初期のすべての節は孤立した集合

に属する.

は、エッジの重みの増加に従ってすべてのエッジを巡回し、パスしたエッジの2つの頂点がまだ異なるセットに属している場合、エッジが最小生成ツリー上のエッジであると判断し、2つの頂点スコアのセットを結合します.

すべてのエッジを巡回した後、原図上のすべてのノードが同じ集合に属すると、選択されたエッジと原図中のすべてのノードが最小生成ツリーを構成する.そうでなければ、原図は連通せず、最小生成ツリーは存在しません.

#include
#include

using namespace std;
#define N 101
int Tree[N];

struct Edge {
    int a, b;
    int cost;

    bool operator<(const Edge &A) const {
        return cost < A.cost;
    }
} edge[6000];

int findRoot(int x) {
    if (Tree[x] == -1) {
        return x;
    } else {
        int temp = findRoot(Tree[x]);
        Tree[x] = temp;
        return temp;
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        int m = n * (n - 1) / 2;
        for (int i = 1; i <= m; i++) {//  
            scanf("%d%d%d", &edge[i].a,
                  &edge[i].b, &edge[i].cost);
        }
        sort(edge + 1, edge + m + 1);
        for (int i = 1; i <= N; i++) {//  
            Tree[i] = -1;
        }
        int count = 0;
        for (int i = 1; i <= m; i++) {//  
            int aRoot = findRoot(edge[i].a);
            int bRoot = findRoot(edge[i].b);
            if (aRoot != bRoot) {
                Tree[aRoot] = bRoot;
                count += edge[i].cost;
            }
        }
        printf("%d
", count);
    }

    return 0;
}

典型的なテーマ:
【九度OJ】題目1017:やはり融通工事
さいたんらくもんだい
Floydアルゴリズム
補充待ち
Dijkstraアルゴリズム
補充待ち
トポロジのソート
有方向無ループ図(DAG)については、ノードの1つのトポロジーシーケンスをトポロジーソートして求め、すべての有方向エッジ(U,V)(UによってVを指す)について、ノードUがノードVの前に並ぶ.
方法は、入度0のノードをシーケンスの次のノードとして選択するたびに、ノードとノードから出発するすべてのエッジを除去することです.
適切であれ、ある図が有向無ループ図に属しているかどうかを判断する必要がある場合、トポロジーソートをすぐに連想する必要があります.
検索
広さ優先探索(BFS)
深度優先検索(DFS)
再帰
ダイナミックプランニング
最長増分子シーケンス(LIS)
最長共通サブシーケンス(LCS)
リュックサック
データ型

long long

long longは64ビット2を用いて整数を表し、整数のオーバーフローを防止することができる.scanf,printfを使用してlong longを操作する場合は、%lldを使用します.
テクニック

大量のメモリ領域を開く必要がある場合は、関数外で定義する必要があります.すなわち、グローバル変数を定義する必要があります.

ビット演算.モジュラ演算は演算子に比較的時間がかかるクラスであり,モジュラ2の代わりにビット演算を用いるとその文の実行効率が大幅に向上する.