donplehanov

Конспект книги олимпиадное программирование

May 24th, 2019
142
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Конспект книги олимпиадное программирование Анти Лааксонен
  2.  
  3. Сайты: Codeforces, Atcoder, CodeChef, CS Academy, HackerRank, Topcoder
  4.  
  5. Сайт с адачами из книги:
  6. cses.fi/problemset
  7.  
  8. Task 1. Странный алгоритм
  9. Принимается на вход целое положительное число n, если оно четно,
  10. то алгоритм делит на 2, иначе умножает на три
  11. и прибавляет 1
  12. 3→10→5→16→8→4→2→1
  13. #include <bits/stdc++.h>
  14.  
  15. int main()
  16. {
  17. long long n;
  18. scanf("%lld", &n);
  19. while (true)
  20. {
  21. printf("%lld ", n);
  22. if (n==1) break;
  23. if (n%2==0) n/=2;
  24. else n = n*3+1;
  25. }
  26. }
  27. #include <bits/stdc++.h>
  28. //#include<iostream>
  29. //using namespace std;
  30.  
  31. int main()
  32. {
  33. //ios::sync_with_stdio(0);
  34. //cin.tie(0);
  35. long long n = 1;
  36. long long k = 0;
  37. //scanf("%lld %d", &n, &k );
  38. while (k <50)
  39. {
  40. printf("%lld ", n); //0.017
  41. //cout<<n<<" "; //0.025, fastcout == 0.015
  42. n*=2;
  43. k++;
  44. }
  45. }
  46.  
  47. ios::sync_with_stdio(0) // пространство имен: синхронизация с потоковым
  48. вводом выводом отключена
  49. cin.tie(0) //
  50.  
  51. long long int a, b;
  52. scanf("%lld %lld", &a, %b);
  53. printf("%lld %lld\n", a, b );
  54.  
  55. '\n' — перевод строки;
  56. '\t' — горизонтальная табуляция;
  57. '\v' — вертикальная табуляция;
  58. '\b' — возврат на символ;
  59. '\r' — возврат на начало строки;
  60. '\a' — звуковой сигнал.
  61.  
  62. %d — целое число типа int со знаком в десятичной системе счисления;
  63. %u — целое число типа unsigned int;
  64. %x — целое число типа int со знаком в шестнадцатеричной системе счисления;
  65. %o — целое число типа int со знаком в восьмеричной системе счисления;
  66. %hd — целое число типа short со знаком в десятичной системе счисления;
  67. %hu — целое число типа unsigned short;
  68. %hx — целое число типа short со знаком в шестнадцатеричной системе счисления;
  69. %ld — целое число типа long int со знаком в десятичной системе счисления;
  70. %lu — целое число типа unsigned long int;
  71. %lx — целое число типа long int со знаком в шестнадцатеричной системе счисления;
  72. %f — вещественный формат (числа с плавающей точкой типа float);
  73. %lf — вещественный формат двойной точности (числа с плавающей точкой типа double);
  74. %e — вещественный формат в экспоненциальной форме (числа с плавающей точкой типа
  75. float в экспоненциальной форме);
  76. %c — символьный формат;
  77. %s — строковый формат.
  78.  
  79.  
  80. string s;
  81. getline(cin, s); передает всю строку целиком переменной s
  82.  
  83. while (cin>>x) {}// на случай, если количество вводимых не известно
  84.  
  85.  
  86. freopen("input.txt", "r", stdin);
  87. freopen("output.txt", "w", stdout);
  88.  
  89. int a = 1123456789;
  90. long long b = a*a// будет хуйня
  91. long long b = (long long)a*a;
  92.  
  93. __int128_t a= 123412341234134123412341234132;
  94.  
  95.  
  96.  
  97. свойства остатков от целочисленного деления
  98. (a + b) mod m = (a mod m + b mod m) mod m;
  99. (a - b) mod m = (a mod m - b mod m) mod m;
  100. (a * b) mod m = (a mod m * b mod m) mod m;
  101.  
  102. Важная особенность: остаток от деления отрицательных чисел в с++ есть
  103. отрицательное число
  104. фикс:
  105. x = x%m;
  106. if (x<0) x+=m;
  107.  
  108. long double a = 1.231242522512525251;
  109. printf("%.9lf\n", x)//1.231242522
  110.  
  111. числа в с++ с плавающей запятой такой же гемор как и в питоне
  112. фикс:
  113. if (abs(a-b) < 1e-9){равны}
  114.  
  115. сокращение кода
  116. typedef long long ll;
  117. typedef vector<int> vi;
  118. typedef pair<int, int> pi;
  119.  
  120. Заметь что typedef меняет название типов данных и записывается
  121. сначала тип данных, а потом его замена
  122.  
  123. Макросы
  124. #define F first
  125. #define S second
  126. #define PB push_back
  127. #define MP make_pair
  128.  
  129. пример
  130. v.PB(MP(y1, x1));
  131. v.PB(MP(y2, x2));
  132. ll d = v[i].F+v[i].S;
  133.  
  134.  
  135. #define REP(i, a, b) for (int i = a; i<=b; i++)
  136.  
  137. REP(i, 1, n){ search(i)};
  138.  
  139.  
  140. Рекурсивные ф-ии
  141. Порождение подмножеств из {1, 2, 3}
  142. в 0, 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3
  143.  
  144. vector<int> subset;
  145. void search(int k)
RAW Paste Data