分析们

分析 NOIP

关于前几天的考试

比较追求速度，而忽视了程序本身的正确性，有着「因为是测试所以没关系吧」的想法，所以才出现了这种状况，小错误百出。

经过这几天的练习，基本的算法又复习了一遍又一遍，特别是 BFS，在这几天的题目中出现的次数非常多。虽然大体框架差不多，但是决定程序正确性的却是其中的细节。

常数优化

以前并没有对这方面的内容有过多的关注，只在某些神犇的 Blog 中会看到类似于「被卡常数」之类的话；而 NOIP 中也不会特别地去卡常数。

一般来说，我写代码都是为了可读性而牺牲一部分速度，也并不会用一些奇奇怪怪的东西。

但是这篇文章中提到了两种看起来差别很小但是速度差别在 9 倍左右的 Kruskal，以此看来常数优化确实有一定的必要，但是既然 NOIP 常数卡得不是很厉害，也并不需要为了这点速度优化而牺牲了代码的可读性。

关于代码规范→_→

（我打字比较快）我习惯于使用大驼峰法以及单词全拼……

我程序里空格也比较多（为了看的比较清楚），我打空格完全是下意识的不需要时间的（自动的），但是可能对其他人来说不太适应。但是看到其他人写的程序代码都缩在一起我就很难受，看的也不是很明朗（×）。

我觉得 Google 的代码规范就挺好的。（×）
虽然我们写的并不是工程代码，而只是算法程序，但是值得借鉴的地方也有很多。

Google 代码规范

以下节选一部分

内联函数 inline

只有当函数只有10行甚至更少时才会将其定义为内联函数（inline function）。

定义（Definition）：当函数被声明为内联函数之后，编译器可能会将其内联展开，无需按通常的函数调用机制调用内联函数。

优点：当函数体比较小的时候，内联该函数可以令目标代码更加高效。

缺点：滥用内联将导致程序变慢，内联有可能是目标代码量或增或减，这取决于被内联的函数的大小。内联较短小的存取函数通常会减少代码量，但内联一个很大的函数（注：如果编译器允许的话）将显著增加代码量。

局部变量 Local Variables

将函数变量尽可能置于最小作用域内，在声明变量时将其初始化。

C++允许在函数的任何位置声明变量。我们提倡在尽可能小的作用域中声明变量，离第一次使用越近越好。这使得代码易于阅读，易于定位变量的声明位置、变量类型和初始值。特别是，应使用初始化代替声明 + 赋值的方式。

像是这样：

int Variable = 1;

命名约定

函数命名、变量命名、文件命名应具有描述性，不要过度缩写，类型和变量应该是名词，函数名可以用“命令性”动词。

尽可能给出描述性名称，不要节约空间，让别人很快理解你的代码更重要，好的命名选择：  

int num_errors;                    // Good. 
int num_completed_connections;     // Good. 

丑陋的命名使用模糊的缩写或随意的字符：  

int n;                             // Bad - meaningless. 
int nerr;                          // Bad - ambiguous abbreviation. 
int n_comp_conns;                  // Bad - ambiguous abbreviation.

当然，在竞赛中，题目的大都会给出一个 N 之类的东西，大多数时候这是约定俗成的；但是如果题目中出现了一堆字母表示的量，如果还是用题目中那些毫无意义的字母表示的话，很容易混乱，不如换成有意义的变量名。

此外，有些较长的变量名，可能打起来较浪费时间……看个人情况吧……

不要用省略字母的缩写：

int error_count;   // Good. 
int error_cnt;     // Bad.

这跟最近提倡的缩写有些冲突，但是我刚刚学奥赛的时候是真不知道 cnt 是什么意思。

for 循环请务必在分号后面加一个空格。
for 循环请务必在分号后面加一个空格。
for 循环请务必在分号后面加一个空格。
重要的事情说三遍。

for (int i = 0; i < 10; ++i) {
    // code
}

#include "iostream"
#include "cstdlib"
using namespace std;
struct Node {
    Node* Child[2];
    int Key;
    int Priority;
    int Size;
    void Maintain() {
        Size = 1;
        if (Child[0] != NULL) Size += Child[0]->Size;
        if (Child[1] != NULL) Size += Child[1]->Size;
    }
};
Node* Root = NULL;
int Size(Node* A) {
    return (A == NULL ? 0 : A->Size); 
}
Node* Merge(Node* A, Node* B) {
    if (A == NULL) return B;
    if (B == NULL) return A;
    if (A->Priority < B->Priority) {
        A->Child[1] = Merge(A->Child[1], B);
        A->Maintain();
        return A;
    } else {
        B->Child[0] = Merge(A, B->Child[0]);
        B->Maintain();
        return B;
    }
}
pair<Node*, Node*> Split(Node* A, int K) {
    if (A == NULL) return pair<Node*, Node*>(NULL, NULL);
    pair<Node*, Node*> DoubleRoot;
    if (K <= Size(A->Child[0])) {
        DoubleRoot = Split(A->Child[0], K);
        A->Child[0] = DoubleRoot.second;
        A->Maintain();
        DoubleRoot.second = A;
    } else {
        DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);
        A->Child[1] = DoubleRoot.first;
        A->Maintain();
        DoubleRoot.first = A;
    }
    return DoubleRoot;
}
int FindKth(int K) {
    pair<Node*, Node*> Left = Split(Root, K - 1);
    pair<Node*, Node*> Right = Split(Left.second, 1);
    Node* Kth = Right.first;
    Root = Merge(Merge(Left.first, Kth), Right.second);
    return Kth->Key;
}
int Rank(Node* Top, int Key) {
    if (Top == NULL) return 0;
    return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);
    // 上面一行有点长……一般来说应该拆开
}
void Insert(int Key) {
    Node* NewNode = new Node();
    NewNode->Key = Key;
    NewNode->Priority = rand();
    NewNode->Child[0] = NewNode->Child[1] = NULL;
    NewNode->Maintain();
    int Pos = Rank(Root, Key);
    pair<Node*, Node*> DoubleRoot = Split(Root, Pos);
    Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);
}
void Remove(int Key) {
    int K = Rank(Root, Key);
    pair<Node*, Node*> Left = Split(Root, K - 1);
    pair<Node*, Node*> Right = Split(Left.second, 1);
    Root = Merge(Left.first, Right.second);
}
void Modify(int OldKey, int NewKey) {
    Remove(OldKey);
    Insert(NewKey);
}
int main(int argc, char const *argv[]) {
    Insert(100);
    Insert(500);
    Insert(300);
    Insert(200);
    Remove(100);
    cout << Rank(Root, 300);
    return 0;
}

虽然我们写竞赛程序大多数都是不需要给别人看的，但是在「自己能看懂」的基础上，提出「让代码更美观，让别人也能看懂」的要求就更好了。

再上我和孙浩然同一程序的对比：
可以看出他就是不加空格的……

孙浩然：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int N;
int len[100],sum[100];
bool vis[100];
bool dfs(int now,int ream,int pos);
int main(){
    freopen("divid.in","r", stdin);
    freopen("divid.out","w", stdout);
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
        scanf("%d",len+i),sum[i]+=sum[i-1]+len[i];
    sort(len+1,len+N+1,greater<int>());
    int tot=N/2;
    for (int i=tot;i>0;i--){
        if(!sum[N]%i) continue;
        memset(vis,false,sizeof(vis));
        bool flag=true;
        for(int j=1;j<=N;j++){
            if (vis[j]) continue;
            if(!dfs(0,sum[N]/i,j-1)){
                flag=false;
                break;
            }
        }
        if(flag){
            printf("%d",sum[N]/i);
            return 0;
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
bool dfs(int now,int ream,int pos){
    if(now+sum[N]-sum[pos]<ream) return false;
    if(now>ream)
        return false;
    if(ream==now)
        return true;
    for (int i=pos+1;i<=N;++i){
        if (vis[i]) continue;
        vis[i] = true;
        if(dfs(now+len[i],ream,i)) return true;
        vis[i] = false;
    }
    return false;
}

我：

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
int N;
int Length[70];
bool Visited[70];
int Sum[70];
bool DFS(int SubSum, int NowSum, int Position) {
    if (NowSum > SubSum) {
        return false;
    }
    if (SubSum == NowSum) {
        return true;
    }
    for (int i = Position + 1; i <= N; ++i) {
        if (!Visited[i]) {
            Visited[i] = true;
            if(DFS(SubSum, NowSum + Length[i], i)) {
                return true;
            }
            Visited[i] = false;
        }
    }
    return false;
}
int main(int argc, char const *argv[]) {
    freopen("divid.in", "r", stdin);
    freopen("divid.out", "w", stdout);
    cin >> N;
    for (int i = 1; i <= N; ++i){
        cin >> Length[i];
    }
    sort(Length + 1, Length + N + 1, greater<int>());
    int ItemNum = N / 2;
    for (int i = ItemNum; i > 0; --i) {
        memset(Visited, 0, sizeof(Visited));
        int Okay = true;
        //  ↑ 这个变量名浩然吐槽「蒙太奇式」(？)，不过不要在意细节了……
        if (Sum[N] % i != 0) continue;
        for (int j = 1; j <= N; ++j) {
            if (Visited[j]) continue;
            if(!DFS(Sum[N] / i, 0, j - 1)) {
                Okay = false;
                break;
            }
        }
        if (Okay) {
            cout << Sum[N] / i;
            return 0;
        }
    }
    return 0;
}