memo

发表于 | 分类于
  1. 输入输出
    printf会把float隐式转换为double，所以两者的specifier都可以是'%f'
function int long long
scanf '%d' '%lld'
printf '%d' '%lld'

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); // "(10,RL)"
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.

  1. 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.

  2. 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.

  3. Dynamic programming

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