@fuheimao
2015-10-11T10:45:55.000000Z
字数 5140
阅读 664
分析
NOIP
比较追求速度,而忽视了程序本身的正确性,有着「因为是测试所以没关系吧」的想法,所以才出现了这种状况,小错误百出。
经过这几天的练习,基本的算法又复习了一遍又一遍,特别是 BFS,在这几天的题目中出现的次数非常多。虽然大体框架差不多,但是决定程序正确性的却是其中的细节。
以前并没有对这方面的内容有过多的关注,只在某些神犇的 Blog 中会看到类似于「被卡常数」之类的话;而 NOIP 中也不会特别地去卡常数。
一般来说,我写代码都是为了可读性而牺牲一部分速度,也并不会用一些奇奇怪怪的东西。
但是这篇文章中提到了两种看起来差别很小但是速度差别在 9 倍左右的 Kruskal,以此看来常数优化确实有一定的必要,但是既然 NOIP 常数卡得不是很厉害,也并不需要为了这点速度优化而牺牲了代码的可读性。
(我打字比较快)我习惯于使用大驼峰法以及单词全拼……
我程序里空格也比较多(为了看的比较清楚),我打空格完全是下意识的不需要时间的(自动的),但是可能对其他人来说不太适应。但是看到其他人写的程序代码都缩在一起我就很难受,看的也不是很明朗(×)。
我觉得 Google 的代码规范就挺好的。(×)
虽然我们写的并不是工程代码,而只是算法程序,但是值得借鉴的地方也有很多。
以下节选一部分
只有当函数只有10行甚至更少时才会将其定义为内联函数(inline function)。
定义(Definition):当函数被声明为内联函数之后,编译器可能会将其内联展开,无需按通常的函数调用机制调用内联函数。
优点:当函数体比较小的时候,内联该函数可以令目标代码更加高效。
缺点:滥用内联将导致程序变慢,内联有可能是目标代码量或增或减,这取决于被内联的函数的大小。内联较短小的存取函数通常会减少代码量,但内联一个很大的函数(注:如果编译器允许的话)将显著增加代码量。
将函数变量尽可能置于最小作用域内,在声明变量时将其初始化。
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;
}