[关闭]
@fuheimao 2015-10-11T02:45:55.000000Z 字数 5140 阅读 51

分析们

分析 NOIP


关于前几天的考试

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

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

常数优化

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

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

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

关于代码规范→_→

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

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

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

Google 代码规范

以下节选一部分

内联函数 inline

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

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

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

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

局部变量 Local Variables

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

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

像是这样:

  1. int Variable = 1;

命名约定

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

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

  1. int num_errors;                    // Good. 
  2. int num_completed_connections;     // Good. 

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

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

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

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

不要用省略字母的缩写:

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

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


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

  1. for (int i = 0; i < 10; ++i) {
  2. // code
  3. }

  1. #include "iostream"
  2. #include "cstdlib"
  3. using namespace std;
  4. struct Node {
  5. Node* Child[2];
  6. int Key;
  7. int Priority;
  8. int Size;
  9. void Maintain() {
  10. Size = 1;
  11. if (Child[0] != NULL) Size += Child[0]->Size;
  12. if (Child[1] != NULL) Size += Child[1]->Size;
  13. }
  14. };
  15. Node* Root = NULL;
  16. int Size(Node* A) {
  17. return (A == NULL ? 0 : A->Size);
  18. }
  19. Node* Merge(Node* A, Node* B) {
  20. if (A == NULL) return B;
  21. if (B == NULL) return A;
  22. if (A->Priority < B->Priority) {
  23. A->Child[1] = Merge(A->Child[1], B);
  24. A->Maintain();
  25. return A;
  26. } else {
  27. B->Child[0] = Merge(A, B->Child[0]);
  28. B->Maintain();
  29. return B;
  30. }
  31. }
  32. pair<Node*, Node*> Split(Node* A, int K) {
  33. if (A == NULL) return pair<Node*, Node*>(NULL, NULL);
  34. pair<Node*, Node*> DoubleRoot;
  35. if (K <= Size(A->Child[0])) {
  36. DoubleRoot = Split(A->Child[0], K);
  37. A->Child[0] = DoubleRoot.second;
  38. A->Maintain();
  39. DoubleRoot.second = A;
  40. } else {
  41. DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);
  42. A->Child[1] = DoubleRoot.first;
  43. A->Maintain();
  44. DoubleRoot.first = A;
  45. }
  46. return DoubleRoot;
  47. }
  48. int FindKth(int K) {
  49. pair<Node*, Node*> Left = Split(Root, K - 1);
  50. pair<Node*, Node*> Right = Split(Left.second, 1);
  51. Node* Kth = Right.first;
  52. Root = Merge(Merge(Left.first, Kth), Right.second);
  53. return Kth->Key;
  54. }
  55. int Rank(Node* Top, int Key) {
  56. if (Top == NULL) return 0;
  57. return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);
  58. // 上面一行有点长……一般来说应该拆开
  59. }
  60. void Insert(int Key) {
  61. Node* NewNode = new Node();
  62. NewNode->Key = Key;
  63. NewNode->Priority = rand();
  64. NewNode->Child[0] = NewNode->Child[1] = NULL;
  65. NewNode->Maintain();
  66. int Pos = Rank(Root, Key);
  67. pair<Node*, Node*> DoubleRoot = Split(Root, Pos);
  68. Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);
  69. }
  70. void Remove(int Key) {
  71. int K = Rank(Root, Key);
  72. pair<Node*, Node*> Left = Split(Root, K - 1);
  73. pair<Node*, Node*> Right = Split(Left.second, 1);
  74. Root = Merge(Left.first, Right.second);
  75. }
  76. void Modify(int OldKey, int NewKey) {
  77. Remove(OldKey);
  78. Insert(NewKey);
  79. }
  80. int main(int argc, char const *argv[]) {
  81. Insert(100);
  82. Insert(500);
  83. Insert(300);
  84. Insert(200);
  85. Remove(100);
  86. cout << Rank(Root, 300);
  87. return 0;
  88. }

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

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

孙浩然:

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cstdio>
  5. using namespace std;
  6. int N;
  7. int len[100],sum[100];
  8. bool vis[100];
  9. bool dfs(int now,int ream,int pos);
  10. int main(){
  11. freopen("divid.in","r", stdin);
  12. freopen("divid.out","w", stdout);
  13. scanf("%d",&N);
  14. for (int i=1;i<=N;i++)
  15. scanf("%d",len+i),sum[i]+=sum[i-1]+len[i];
  16. sort(len+1,len+N+1,greater<int>());
  17. int tot=N/2;
  18. for (int i=tot;i>0;i--){
  19. if(!sum[N]%i) continue;
  20. memset(vis,false,sizeof(vis));
  21. bool flag=true;
  22. for(int j=1;j<=N;j++){
  23. if (vis[j]) continue;
  24. if(!dfs(0,sum[N]/i,j-1)){
  25. flag=false;
  26. break;
  27. }
  28. }
  29. if(flag){
  30. printf("%d",sum[N]/i);
  31. return 0;
  32. }
  33. }
  34. fclose(stdin);
  35. fclose(stdout);
  36. return 0;
  37. }
  38. bool dfs(int now,int ream,int pos){
  39. if(now+sum[N]-sum[pos]<ream) return false;
  40. if(now>ream)
  41. return false;
  42. if(ream==now)
  43. return true;
  44. for (int i=pos+1;i<=N;++i){
  45. if (vis[i]) continue;
  46. vis[i] = true;
  47. if(dfs(now+len[i],ream,i)) return true;
  48. vis[i] = false;
  49. }
  50. return false;
  51. }

我:

  1. #include "iostream"
  2. #include "algorithm"
  3. #include "cstring"
  4. #include "cstdio"
  5. using namespace std;
  6. int N;
  7. int Length[70];
  8. bool Visited[70];
  9. int Sum[70];
  10. bool DFS(int SubSum, int NowSum, int Position) {
  11. if (NowSum > SubSum) {
  12. return false;
  13. }
  14. if (SubSum == NowSum) {
  15. return true;
  16. }
  17. for (int i = Position + 1; i <= N; ++i) {
  18. if (!Visited[i]) {
  19. Visited[i] = true;
  20. if(DFS(SubSum, NowSum + Length[i], i)) {
  21. return true;
  22. }
  23. Visited[i] = false;
  24. }
  25. }
  26. return false;
  27. }
  28. int main(int argc, char const *argv[]) {
  29. freopen("divid.in", "r", stdin);
  30. freopen("divid.out", "w", stdout);
  31. cin >> N;
  32. for (int i = 1; i <= N; ++i){
  33. cin >> Length[i];
  34. }
  35. sort(Length + 1, Length + N + 1, greater<int>());
  36. int ItemNum = N / 2;
  37. for (int i = ItemNum; i > 0; --i) {
  38. memset(Visited, 0, sizeof(Visited));
  39. int Okay = true;
  40. // ↑ 这个变量名浩然吐槽「蒙太奇式」(?),不过不要在意细节了……
  41. if (Sum[N] % i != 0) continue;
  42. for (int j = 1; j <= N; ++j) {
  43. if (Visited[j]) continue;
  44. if(!DFS(Sum[N] / i, 0, j - 1)) {
  45. Okay = false;
  46. break;
  47. }
  48. }
  49. if (Okay) {
  50. cout << Sum[N] / i;
  51. return 0;
  52. }
  53. }
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注