本日志由ACM队08级学长CJY友情提供，针对不了解ACM/ICPC的同学提供帮助。
C/C++
1. I/O
Online Judge通常使用的是标准输入/输出，所以在比赛时通常要加上以下几行：
#include<stdio.h> //标准c输入/输出
#include<string.h> //字符串操作
#include<iostream> //标准c++输入/输出
#include<iomanip> //标准C++的I/O manipulator（操纵器？）
using namespace std; //使用std命名空间
本节只讨论double,int,long long,char的输入输出，字符串到下节再讨论。
对于stdio.h，使用的输入是 int scanf( const char *format, ... );
使用的输出是 int printf( const char *format, ... );
其中，字符串format存的是由输出到屏幕的字符串和格式控制符组成的。具体实例见下：
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF) //多组数据，读入两个整数a,b，返回值为EOF时退出；
printf("%d\n",a+b); //输出结果a+b；
}
下面给出常用的格式控制符：
%d | int型变量；
%lf | double型变量；
%.Xf | X是一个整数，在double型变量输出的时候表示输出小数点后几位小数；
%c | char型变量；
%I64 | long long型变量（64位整数）
%lld | 也是long long型变量，不过有的OJ可能不认
对于转义字符的话，本次比赛有用的似乎就是 \n (表示换行）了吧 。
对于iostream的话，使用的输入是cin>>....
使用的输出是cout>>....
对于上面的实例，使用C++的方法是这样写的：
int main()
{
int a,b;
while(cin>>a>>b) //多组数据，读入两个整数a,b，读完退出；
cout<<a+b<<endl; //输出结果a+b，endl表示换行；
}
对于double的输出，命令通常是这样写的：
double a;
int X=3;
cout<<setiosflags(ios::fixed)<<setprecision(X)<<a<<endl; // X表示的是小数点后保留几位；
和C相比，C++的输入/输出会比C“方便”许多。但是，C++的输入输出会比C慢，如果遇到Time Limit Exceeded 的话，在没有好的算法优化的情况下可以尝试使用C进行输入/输出。
2. string
C和C++的字符串是不一样的。C的话通常使用的是 char* 和 char。具体的使用可以看下面的实例：
char s000];
int main()
{
scanf("%s",&s); //读入一个字符串s，遇到空格或者换行符时停止；（"%s"为字符串的格式控制符）
gets(s); //读入一行字符；
printf("%s",s); //输出一个字符串；
puts(s); //将字符串输出在一行上；
return 0;
}
字符串的输入输出常用的大概就上面几句了。下面给几个常用的命令：
double atof( const char *str ); | 把字符串转成double型变量；
int atoi( const char *str ); | 把字符串转成int型变量；
void *memcpy( void *to,
const void *from, size_t count ); | 把字符串from拷贝count个字符到字符串to。也可用于数组。
void* memset( void* buffer,
int ch, size_t count ); | 初始化 buffer ，初始值 ch ，大小count；
size_t strlen( char *str ); | 求字符串的长度，用int存就可以了；
C++的字符串通常使用string。具体实例见下：
int main()
{
string s;
cin>>s; //读入一个字符串，遇到换行符或者空格停止；
getline( cin , s ); //读入一行字符串；
cout<<s<<endl; //输出字符串；
}
如果我没记错的话string其实是个类，所以各种功能的使用就是用类的写法（比如 s.length() ）。下面给出几个常用的函数:
string& append( const string& str ); | 在字符串末尾增加字符串str，其实可以直接用+；
void clear(); | 清空字符串；
size_type length() const; | 字符串长度；
size_type find( const string& str, size_type index ); | 在字符串str中查找字符；
还有很多函数和STL的那几种数据结构用法基本相同，在这就不多说了。
3. math & algorithm
对于没有参加算法类竞赛经验的同学经常能碰到这种情况：能想出巧妙的算法，但是由于一些最基础的函数无法实现，导致最后无法AC或者浪费很多时间。其实C和C++提供了很多数学函数以及算法，在比赛的时候可以直接调用。
首先，如果要调用这些函数，我们一般要调用以下的头文件：
#include<math.h> //数学库头文件
#include<stdlib.h> //标准库头文件
#include<algorithm> //算法库头文件
对于math.h，通常使用的是下面几个函数：
double asin( double arg ); | 求arc sin，acos和atan调用与其类似；
double sin( double arg ); | 求sin，cos和tan调用与其类似；
double exp( double arg ); | 自然对数e的arg次幂
double fabs( double arg ); | 绝对值函数
double log( double num ); | 自然对数e为底的log值
double sqrt( double num ); | 根号
double pow( double base, double exp ); | base的exp次幂
对于stdlib.h而言，在比赛中通常可能使用到的就是qsort和rand了。
qsort定义如下：
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );
buf是待排序的数组，num是待排序项数，size是每一项大小，compare是比较函数指针。下面是C++ STL Reference的实例，介绍qsort是怎么使用的：
int compare_ints( const void* a, const void* b )
{
int* arg1 = (int*) a;
int* arg2 = (int*) b;
if( *arg1 < *arg2 ) return -1;
else if( *arg1 == *arg2 ) return 0;
else return 1;
}
int array = { -2, 99, 0, -743, 2, 3, 4 };
int array_size = 7;
...
printf( "Before sorting: " );
for( int i = 0; i < array_size; i++ )
{
printf( "%d ", array[i] );
}
printf( "\n" );
qsort( array, array_size, sizeof(int), compare_ints );
printf( "After sorting: " );
for( int i = 0; i < array_size; i++ ) { printf( "%d ", array[i] ); }
printf( "\n" );
rand是求伪随机数函数。虽然在ACM/ICPC中多数问题可以使用不需要随机数的算法解决，但是随机调整的算法在一些情况下还是能活得不错的效果。在调用rand前需要调用srand初始化随机函数。下面是使用rand的一个实例：
#include<time.h>
#include<stdlib.h>
int main()
{
srand(time(NULL)); //以时间作为随机种子
int a=rand(); //获得一个随机数
return 0;
}
Algorithm里面有很多算法，而且大部分函数如果自己实现其实并不复杂。这里就介绍新手经常会感到困扰的排序和二分查找。而排序和二分在某些算法的预处理或者某些步骤中可以起到画龙点睛的作用，二分的思想经常被使用在算法的优化中，如果是没有算法比赛经验且对算法几乎没有了解的同学，我建议在比赛前收集算法入门教材，看懂书上描述算法的流程和符号，同时理解二分思想。
排序使用的函数是sort，它使用的是Introsort，一种改进的快排，最坏情况也能达到O(N log N)。它的具体形式如下：
void sort( iterator start, iterator end, StrictWeakOrdering cmp );
start是其实元素，end是终止元素，cmp是比较函数。比较函数其实作用类似<号，可以直接通过重载而使该参数缺省。sort函数可以作用于容器，当然对于容器的使用就不是这里普及的内容了，想速成的可以直接看C++ STL Reference，想带到现场赛做参考的话建议Essential C++。下面给出一个直接对数组排序的实例：
#include<stdlib.h>
#include<algorithm>
struct node
{
int node,val;
};
bool cmp(node a,node b) //判别函数，返回值为真表示a排在b前面。
{
if (a.val<b.val) return true;
retutrn false;
}
int main()
{
node a[3];
a[0].node=a[0].val=1;
a[1].node=a[1].val=2;
a[2].node=a[2].val=3;
sort(a,a+3,cmp); // +3的话，不想深究的同学直接看成待排序的数组长度好了。
return false;
}
二分搜索是其实是在一个有序数组中查找某个数是否存在。具体形式如下：
bool binary_search( iterator start, iterator end, const TYPE& val, Comp f );
如果在start到end之间存在值val，那么就返回true；否则返回false。
注：由于现场赛可携带纸质资料，参加现场赛的同学不妨可以打印一份。 |