memo

1. 输入输出
   printf会把float隐式转换为double，所以两者的specifier都可以是'%f'

read a single character ignoring whitespace
scanf(" %c", &c) place a whitespace before %c

use sscanf to read from a C string

1
2
3
4

char s[100];
scanf("%s", s); 
int n;
sscanf(&s[1], "%d", &n); // n = 10

read a whole line

1
2
3
4
5
6
7
8
9
10
11
12
13
14

string s;
getline(cin, s);

char s[100];
cin.getline(s, 100);

char s[100];
scanf("%[^n]%*c", s);

char s[100];
// no gets
// gets(s);
// fgets stores 'n' into s
fgets(s, 100, stdin);

stringstream 清空

1
2
3

stringstream ss;
ss.str(""); // clear the content
ss.clear(); // set a new value for stream's internal error state flags

from stackoverflow

Typically to ‘reset’ a stringstream you need to both reset the underlying sequence to an empty string with str and to clear any fail and eof flags with clear.
parser.str( std::string() );
parser.clear();
Typically what happens is that the first >> reaches the end of the string and sets the eof bit, although it successfully parses the first short. Operations on the stream after this immediately fail because the stream’s eof bit is still set.

2. bit operation
   attention! -1 >> 1 => -1 not 0
   from USACO

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   This means that certain bit operations can exploit these definitions of negation and subtraction to yield interesting results, the proofs of which are left to the reader (see [a table of these](http://realtimecollisiondetection.net/blog/?p=78) offsite): Binary Value Sample Meaning x 00101100 the original x value x & -x 00000100 extract lowest bit set x | -x 11111100 create mask for lowest-set-bit & bits to its left x ^ -x 11111000 create mask bits to left of lowest bit set x & (x-1) 00101000 strip off lowest bit set --> useful to process words in O(bits set) instead of O(nbits in a word) x | (x-1) 00101111 fill in all bits below lowest bit set x ^ (x-1) 00000111 create mask for lowest-set-bit & bits to its right ~x & (x-1) 00000011 create mask for bits to right of lowest bit set x | (x+1) 00101101 toggle lowest zero bit x / (x&-x) 00001011 shift number right so lowest set bit is at bit 0 There's no reason to memorize these expressions, but rather remember what's possible to refer back to this page for saving time when you processing bits.

3. Graph
   from USACO
   邻接矩阵(A)的(K)次方的元素(A^K(i,j))表示从结点(i)到结点(j)恰好包含(K)条边的路径的数目

   1 2 3 4 5 6 7 8 9 10

   The sample undirected graph would be represented by the following adjacency matrix: V1 V2 V3 V4 V5 V6 V1 0 0 1 0 0 1 V2 0 0 0 0 1 0 V3 1 0 0 1 0 1 V4 0 0 1 0 0 0 V5 0 1 0 0 0 0 V6 1 0 1 0 0 0 It is sometimes helpful to use the fact that the (i,j) entry of the adjacency matrix raised to the k-th power gives the number of paths from vertex i to vertex j consisting of exactly k edges.

4. Dynamic programming

   The basic idea is to try to avoid solving the same problem or subproblem twice.