API tools faq
paste
Advertisement
Pearlfromsu

algoses

Pearlfromsu
Sep 29th, 2023
927
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 23.58 KB | None | 0 0
raw download clone embed print report
  1. ДОБАВИТЬ В ШАБЛОН:
  2.  
  3. 17.07.22 14:19
  4. Timus №1020: построение выпуклой оболочки - поиск угла ABC по координатам:
  5. double angle(pdd A, pdd B, pdd C) {
  6.     return (B.first - A.first) * (C.second - B.second) - (B.second - A.second) * (C.first - B.first);
  7.     //B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0]
  8. }
  9. 19.07.22
  10.  
  11. 1110 функция бинарного возведения в степень, чтобы можно было работать умножать с модулями binary pow(power())
  12.  
  13. 1496 нахождение ключа и перебор map():
  14. if(mp.count(key)) {...}
  15. for (auto i = mp.begin(); i != mp.end(); i++) {
  16.         if (i->second > 1)
  17.             cout << i->first << "\n";
  18.     }
  19.  
  20. 1446
  21. ЧТЕНИЕ СТРОКИ:
  22. #include <string>
  23. getline(cin, str)
  24.  
  25. ОПАСНОСТЬ! ПОСЛЕ СЧИТЫВАНИЯ cin >> n ПЕРЕД ИСПОЛЬЗОВАНИМ getline() НУЖНО ВЫЗВАТЬ getline() ВПУСТУЮ! ИНАЧЕ ПРОЧТЁТСЯ ПУСТАЯ СТРОКА.
  26.  
  27. 1084
  28. ЗНАМЕНАТЕЛЬ ВСЕГДА В СКОБКИ
  29. 1.0 - AB * AB / 2.0 * r * r
  30. НЕ РАВНО
  31. 1.0 - AB * AB / (2.0 * r * r)
  32. к делению всегда осторожно
  33.  
  34. 1225 DP:
  35. ВСЕГДА ПРОВЕРЯТЬ НАЧАЛЬНОЕ СОСТОЯНИЕ
  36.  
  37.  
  38.  
  39.  
  40. 03.08.22
  41. ВСОПМНИТЬ СОВЕТ ПРО ПРИВЕДЕНИЕ К (int)
  42.             NEW TODO до ICPC:(2303221556)
  43.             1) Разобраться, как работают структуры в C++(как передаются в функции, объявляются и используются внутри других структур)
  44.             2) Разобраться, как работают массивы и вектора при передаче в функции и возвращении из них в C++
  45.             3) Разобраться, что за типы size_t и почему их нужно приводить к (int):
  46.             4) Как делать двоичный поиск(lower_bound, upper_bound)
  47.  
  48.             double findSquare(const vector<point> & vertex, const vector<int> & convexHull)
  49.             {
  50. !!ЭТОТ->                // если не сделать явного приведения к типу int, то будет попытка зайти в цикл,
  51.                 // т.к. convexHull.size() имеет тип size_t(безнаковое целое),
  52.                 // то если convexHull пуст. получим 0-1 = 4294967295
  53.                 double S = 0;
  54.                 for (int i = 1; i < (int)convexHull.size() - 1; i++)
  55.                 {
  56.                     S += findSquare(
  57.                         vertex[convexHull[0]],
  58.                         vertex[convexHull[i]],
  59.                         vertex[convexHull[i + 1]]);
  60.                 }
  61.  
  62.                 return Fabs(S / 2);
  63.             }
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.             TODO EXTRA NOW: 0702221334
  72.             13:34
  73.             1) До 14:00 сделать функцию хэша строки, возвращающую вектор long long с хэшами для каждого префикса и проверить его на выводе.
  74.            
  75.            
  76.            
  77.            
  78.            
  79.  
  80. №1348
  81. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  82. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  83. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  84. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  85. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  86. РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
  87.  
  88.  
  89. double ras(pair<double, double> a, pair<double, double> b) {
  90.     return sqrt((b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second));
  91. }
  92.  
  93. //ВЕКТОРА ИЗ ОДНОГО КОНЦА ИЛИ В ОДИН КОНЕЦ!!
  94. double orr (pair<double, double> AB, pair<double, double> BC) { //по знаку: тупой или острый угол - если добавить длины в знаменатель, то получится косинус
  95.     return (AB.first * BC.first + AB.second * BC.second);
  96. }
  97. double rastDoOtr(pair<double, double> A, pair<double, double> B, pair<double, double> C, double def = 1.0) {
  98.     //S = (xy - yx)/2 //ab_x bc_y - ab_y bc_x
  99.     pair<double, double> AB = { B.first - A.first, B.second - A.second },
  100.     BC = { C.first - B.first, C.second - B.second },
  101.     CB = { -BC.first, -BC.second},
  102.     AC = { C.first - A.first, C.second - A.second };
  103.  
  104.     if(orr(AB, CB) >= 0 && orr(AC, BC) >= 0) //<= 0 - значит тупоугольный
  105.         return (abs(AB.first * BC.second - AB.second * BC.first)) / ras(B, C);
  106.     return def * 2 * 1e9; //если не можем рассматривать расстояние как что-то нужное
  107. }
  108.  
  109. //A -> BC
  110. double minSegDist(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
  111.     return min(min(ras(A, B), ras(A, C)), rastDoOtr(A, B, C));
  112. }
  113. double maxSegDist(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
  114.     return max(max(ras(A, B), ras(A, C)), rastDoOtr(A, B, C, -1.0));
  115. }
  116.  
  117. int main() {
  118.     pair<double, double> B, C, A;
  119.     double D;
  120.     cout << fixed << setprecision(10);
  121.     //На вход: отрезок BC, точка A и длина верёвки от точки A.
  122.     //На выход: длина, на которую нужно удлинить верёвку, чтобы достать до одной точки отрезка '\n' чтобы достать до каждой точки отрезка
  123.     cin >> B.first >> B.second >> C.first >> C.second >> A.first >> A.second >> D;
  124.     cout << max(0.0, minSegDist(A, B, C) - D) << '\n' << max(0.0, maxSegDist(A, B, C) - D);
  125.     return 0;
  126. }
  127.            
  128. =====================================================
  129. =====================================================
  130. =====================================================
  131. =====================================================
  132. =====================================================
  133.            
  134.            
  135.            
  136.            
  137.            
  138.            
  139.            
  140. 22.08.22
  141. 1402 BIG INT(long arithmetic)
  142. Вставить реализацию длинной арифметики
  143. struct Bigint {
  144.     string a;
  145.     int sign;
  146.  
  147.     Bigint(){}
  148.     void operator = (string b) {
  149.         a= (b[0]=='-' ? b.substr(1) : b);
  150.         reverse(a.begin(), a.end());
  151.         (*this).Remove0(b[0]=='-' ? -1 : 1);
  152.     }
  153.     Bigint(string x) {(*this)=x;}
  154.     Bigint(ll x) {(*this)=to_string(x);}
  155.     void operator = (ll x){*this=to_string(x);}
  156.  
  157.     char operator[](int i){return a[i];}
  158.     int size() {return a.size();}
  159.     Bigint inverseSign() {sign*=-1; return (*this);}
  160.  
  161.     Bigint Remove0(int newSign) {
  162.         sign = newSign;
  163.         for(int i=a.size()-1; i>0 && a[i]=='0'; i--) a.pop_back();
  164.         if(a.size()==1 && a[0]=='0') sign=1;
  165.         return (*this);
  166.     }
  167.  
  168.     bool operator == (Bigint x) {return sign==x.sign && a==x.a;}
  169.     bool operator == (string x) {return *this==Bigint(x);}
  170.     bool operator == (ll x)     {return *this==Bigint(x);}
  171.     bool operator != (Bigint x) {return !(*this==x);}
  172.     bool operator != (string x) {return !(*this==x);}
  173.     bool operator != (ll x)     {return !(*this==x);}
  174.  
  175.     bool operator < (Bigint b) {
  176.         if (sign!=b.sign) return sign<b.sign;
  177.         if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
  178.         for(int i=a.size()-1; i>=0; i--)
  179.             if(a[i] != b[i]) return a[i]<b[i];
  180.         return false;
  181.     }
  182.     bool operator <  (string x) {return *this<Bigint(x);}
  183.     bool operator <  (ll x)     {return *this<Bigint(x);}
  184.     bool operator <= (Bigint b) {return *this==b || *this<b;}
  185.     bool operator <= (string b) {return *this==b || *this<b;}
  186.     bool operator <= (ll b)     {return *this==b || *this<b;}
  187.     bool operator >  (Bigint b) {return !(*this==b || *this<b);}
  188.     bool operator >  (string x) {return !(*this==x || *this<x);}
  189.     bool operator >  (ll b)     {return !(*this==b || *this<b);}
  190.     bool operator >= (Bigint b) {return *this==b || *this>b;}
  191.     bool operator >= (string b) {return *this==b || *this>b;}
  192.     bool operator >= (ll b)     {return *this==b || *this>b;}
  193.  
  194.     Bigint operator + (Bigint b) {
  195.         if(sign != b.sign) return (*this)-b.inverseSign();
  196.         Bigint sum;
  197.         for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
  198.             if (i<a.size()) carry+=a[i]-'0';
  199.             if (i<b.size()) carry+=b[i]-'0';
  200.             sum.a += (carry % 10 + 48);
  201.             carry /= 10;
  202.         }
  203.         return sum.Remove0(sign);
  204.     }
  205.     Bigint operator +  (string x) {return *this+Bigint(x);}
  206.     Bigint operator +  (ll x)     {return *this+Bigint(x);}
  207.     Bigint operator ++ (int) {*this+=1; return *this-1;}
  208.     Bigint operator ++ ()    {*this+=1; return *this;}
  209.       void operator += (Bigint x) {*this = *this+x;}
  210.       void operator += (string x) {*this = *this+x;}
  211.       void operator += (ll x)     {*this = *this+x;}
  212.  
  213.  
  214.     Bigint operator - ( Bigint b ) {
  215.         if(sign != b.sign) return (*this)+b.inverseSign();
  216.         if(*this < b) return (b - *this).inverseSign();
  217.         Bigint sub;
  218.         for(int i=0,borrow=0; i<a.size(); i++) {
  219.             borrow = a[i]-borrow-(i<b.size() ? b.a[i] : '0');
  220.             sub.a += borrow>=0 ? borrow+'0' : borrow + 58;
  221.             borrow = borrow>=0 ? 0:1;
  222.         }
  223.         return sub.Remove0(sign);
  224.     }
  225.     Bigint operator - (string x) {return *this-Bigint(x);}
  226.     Bigint operator - (ll x)     {return *this-Bigint(x);}
  227.     Bigint operator -- (int) {*this-=1; return *this+1;}
  228.     Bigint operator -- ()    {*this-=1; return *this;}
  229.       void operator -= (Bigint x) {*this = *this-x;}
  230.       void operator -= (string x) {*this = *this-x;}
  231.       void operator -= (ll x)     {*this = *this-x;}
  232.  
  233.     Bigint operator * (Bigint b) {
  234.         Bigint mult("0");
  235.         for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
  236.             while(k-- -'0') mult=mult+b;
  237.             b.a.insert(b.a.begin(),'0');
  238.         }
  239.         return mult.Remove0(sign * b.sign);
  240.     }
  241.     Bigint operator * (string x) {return *this*Bigint(x);}
  242.     Bigint operator * (ll x)     {return *this*Bigint(x);}
  243.       void operator *= (Bigint x) {*this = *this*x;}
  244.       void operator *= (string x) {*this = *this*x;}
  245.       void operator *= (ll x)     {*this = *this*x;}
  246.  
  247.     Bigint operator / (Bigint b) {
  248.         if(b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0');
  249.         Bigint c("0"), d;
  250.         for(int j=0; j<a.size(); j++) d.a += "0";
  251.         int dSign = sign*b.sign; b.sign=1;
  252.         for(int i=a.size()-1; i>=0; i--) {
  253.             c.a.insert(c.a.begin(),'0');
  254.             c=c+a.substr(i,1);
  255.             while(!(c<b)) c=c-b, d.a[i]++;
  256.         }
  257.         return d.Remove0(dSign);
  258.     }
  259.     Bigint operator / (string x) {return *this/Bigint(x);}
  260.     Bigint operator / (ll x)     {return *this/Bigint(x);}
  261.       void operator /= (Bigint x) {*this = *this/x;}
  262.       void operator /= (string x) {*this = *this/x;}
  263.       void operator /= (ll x)     {*this = *this/x;}
  264.  
  265.     Bigint operator % (Bigint b) {
  266.         if( b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0') ;
  267.         Bigint c("0");
  268.         int cSign = sign*b.sign; b.sign=1;
  269.         for( int i=a.size()-1; i>=0; i-- ) {
  270.             c.a.insert( c.a.begin(),'0');
  271.             c = c+a.substr(i,1);
  272.             while(!(c<b)) c=c-b;
  273.         }
  274.         return c.Remove0(cSign);
  275.     }
  276.     Bigint operator % (string x) {return *this%Bigint(x);}
  277.     Bigint operator % (ll x)     {return *this%Bigint(x);}
  278.       void operator %= (Bigint x) {*this = *this%x;}
  279.       void operator %= (string x) {*this = *this%x;}
  280.       void operator %= (ll x)     {*this = *this%x;}
  281.  
  282.     void print() {
  283.         if(sign==-1) putchar('-');
  284.         for(int i=a.size()-1; i>=0; i--) putchar(a[i]);
  285.     }
  286.     friend istream& operator >>(istream &in,Bigint &x){
  287.         string s; in>>s; x=s; return in;
  288.     }
  289.     friend ostream& operator <<(ostream &out,Bigint &x){
  290.         if(x.sign==-1) putchar('-');
  291.         for(int i=x.size()-1; i>=0; i--)
  292.             putchar(x[i]);
  293.         return out;
  294.     }
  295.  
  296.     friend Bigint pow(Bigint base, Bigint pw){
  297.         Bigint ans=1;
  298.         while(pw!=0){
  299.             if(pw%2 !=0) ans*=base;
  300.             base*=base, pw/=2;
  301.         }
  302.         return ans;
  303.     }
  304.     friend Bigint pow(Bigint a, Bigint b,Bigint mod) {
  305.         if (b==0) return Bigint(1);
  306.         Bigint tmp=pow(a,b/2,mod);
  307.         if ((b%2)==0) return (tmp*tmp)%mod;
  308.         else return (((tmp*tmp)%mod)*a)%mod;
  309.     }
  310.     friend Bigint sqrt(Bigint x) {
  311.         Bigint ans=x,tmp=(x+1)/2;
  312.         while (tmp<ans) ans=tmp, tmp=(tmp+x/tmp)/2;
  313.         return ans;
  314.     }
  315.     friend Bigint gcd(Bigint a,Bigint b){
  316.         return a%b==0 ? b : gcd(b, a%b);
  317.     }
  318.     friend Bigint lcm(Bigint a,Bigint b){
  319.         return a/gcd(a,b);
  320.     }
  321. };
  322.  
  323. Bigint binpow(Bigint a, Bigint b) {
  324.     if (b <= 0)
  325.         return 1;
  326.     Bigint res = binpow(a, b / 2);
  327.     if (b % 2 != 0)
  328.         return res * res * a;
  329.     else
  330.         return res * res;
  331. }
  332.  
  333.  
  334.  
  335.  
  336. 1352
  337. ТАБЛИЦА БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ!!!
  338.  
  339. https://dpva.ru/Guide/GuideMathematics/GuideMathematicsFiguresTables/SimpleFigures/SimpleFiguresPrint/
  340.            
  341.            
  342.            
  343.  
  344. 2005
  345. АЛГОРИТМ ДЕЙКСТРЫ
  346. #include <bits/stdc++.h>
  347. using namespace std;
  348. struct Edge{
  349.   int vertex;
  350.   int wt;
  351.   Edge(int d,int w){
  352.     vertex = d;
  353.     wt = w;
  354.   }
  355. };
  356. struct Compare{
  357.   bool operator()(Edge &e1,Edge &e2){
  358.     return (e1.wt < e2.wt)? false:true ;
  359.   }
  360. };
  361. struct Graph{
  362.   int V;
  363.   vector<Edge> *edges;
  364.   Graph(int V){
  365.     this->V = V;
  366.     edges = new vector<Edge>[V];
  367.   }
  368.   void addEdge(int u,int v,int wt){
  369.     edges[u].push_back(Edge(v,wt));
  370.     edges[v].push_back(Edge(u,wt));
  371.   }
  372.   int *dijkstras(int src){
  373.     int *dist = new int[V];
  374.     bool visited[V];
  375.     for(int i=0;i<V;i++){
  376.       dist[i] = INT_MAX;
  377.       visited[i] = false;
  378.     }
  379.     dist[src] = 0;
  380.     priority_queue<Edge,vector<Edge>,Compare> pq;
  381.     pq.push(Edge(src,dist[src]));
  382.     while(!pq.empty()){
  383.       Edge curr = pq.top();
  384.       pq.pop();
  385.       if(!visited[curr.vertex])
  386.         visited[curr.vertex] = true;
  387.       else
  388.         continue;
  389.       for(Edge e : edges[curr.vertex]){
  390.         if(!visited[e.vertex]){
  391.           if((curr.wt + e.wt) < dist[e.vertex]){
  392.             dist[e.vertex] = curr.wt + e.wt;
  393.             pq.push(Edge(e.vertex,dist[e.vertex]));
  394.           }
  395.         }
  396.       }
  397.     }
  398.     return dist;
  399.   }
  400. };
  401.  
  402. int main(){
  403.   int V,E;
  404.   cin>>V>>E;
  405.   Graph g(V);
  406.   for(int i=0;i<E;i++){
  407.     int u,v,wt;
  408.     cin>>u>>v>>wt;
  409.     g.addEdge(u,v,wt);
  410.   }
  411.   int *dist = g.dijkstras(0);
  412.   for(int i=0;i<V;i++){
  413.     cout<<0<<"  ->  "<<i<<" = "<<dist[i]<<endl;
  414.   }
  415.   return 0;
  416. }
  417.  
  418.            
  419.            
  420.            
  421.            
  422.            
  423.            
  424.            
  425.            
  426.            
  427.            
  428.            
  429.            
  430. ФУНКЦИИ с числами С Volga Camp
  431.            
  432. https://pastebin.com/G2QCvSqp
  433.            
  434.             #include "bits/stdc++.h"
  435.  
  436. using namespace std;
  437.  
  438. vector<long long> p;
  439. vector<int> md;
  440. long long sum_d = 0;
  441.  
  442.  
  443. long long sum_mu = 1;
  444. vector<int> mu;
  445. long long sum_fi = 1;
  446. vector<int> fi;
  447. vector<int> al1;
  448. vector<long long> pal1;
  449.  
  450. long long sum_si0 = 1;
  451. vector<int> si0;
  452.  
  453. long long sum_si1 = 1;
  454. vector<long long> si1;
  455.  
  456.  
  457. signed main() {
  458.     int n;
  459.     cin >> n;
  460.  
  461.     md.resize(n + 1);
  462.     mu.resize(n + 1);
  463.     fi.resize(n + 1);
  464.     pal1.resize(n + 1);
  465.     al1.resize(n + 1);
  466.     si0.resize(n + 1);
  467.     si1.resize(n + 1);
  468.  
  469.  
  470.     mu[1] = 1;
  471.     fi[1] = 1;
  472.     pal1[1] = 0;
  473.     al1[1] = 0;
  474.     si0[1] = 1;
  475.     si1[1] = 1;
  476.  
  477.     iota(md.begin(), md.end(), 0);
  478.     for (long long x = 2; x < n + 1; ++x) {
  479.         if (md[x] == x)
  480.             p.emplace_back(x);
  481.         for (int i = 0; i < p.size() and p[i] <= x and p[i] * x <= n; ++i) {
  482.             md[p[i] * x] = p[i];
  483.         }
  484.  
  485.  
  486.         int y = x / md[x];
  487.         if (md[y] == md[x]) {
  488.             al1[x] = al1[y] + 1;
  489.             pal1[x] = pal1[y] * md[x];
  490.             mu[x] = 0;
  491.             si0[x] = si0[y] + (si0[y] / (al1[y] + 1));
  492.             si1[x] = (pal1[x] * md[x] - 1) * si1[y] / (pal1[x] - 1);
  493.             fi[x] = md[x] * fi[y];
  494.         } else {
  495.             al1[x] = 1;
  496.             pal1[x] = md[x];
  497.             mu[x] = -mu[y];
  498.             si0[x] = si0[y] * 2;
  499.             si1[x] = (1 + md[x]) * si1[y];
  500.             fi[x] = (md[x] - 1) * fi[y];
  501.         }
  502.         sum_mu += mu[x];
  503.         sum_d += md[x];
  504.         sum_fi += fi[x];
  505.         sum_si0 += si0[x];
  506.         sum_si1 += si1[x];
  507.     }
  508.     cout << sum_d << ' ' << sum_si0 << ' ' << sum_si1 << ' ' << sum_fi << ' ' << sum_mu;
  509.     return 0;
  510. }
  511.            
  512.            
  513.            
  514.            
  515.            
  516.            
  517.            
  518.            
  519.            
  520.            
  521. 29.08.22 16:09
  522.  
  523. 1193
  524. tuple<int, int, int> tp = {1, 2, 3}; // то же самое, что и pair(и для сортировки, и для сравнения), только из 3-х элементов
  525. ПОЛУЧИТЬ ЭЛЕМЕНТЫ ТРОЙКИ: get<0>(tp), get<1>(tp), get<2>(tp)
  526. или начиная с C++17:
  527. auto [aa, bb, cc] = tp;
  528.  
  529.            
  530.            
  531.            
  532.            
  533.            
  534.            
  535.            
  536.            
  537. 11.03.23 15:06 Тульская олимпиада(квалификационный раунд)
  538.  
  539. Уравнение плоскости по трём точкам.
  540.  
  541. void equation_plane(double x1, double y1,
  542.     double z1, double x2,
  543.     double y2, double z2,
  544.     double x3, double y3, double z3)
  545. {
  546.     double a1 = x2 - x1, b1 = y2 - y1, c1 = z2 - z1, a2 = x3 - x1, b2 = y3 - y1, c2 = z3 - z1;
  547.     double a = b1 * c2 - b2 * c1, b = a2 * c1 - a1 * c2, c = a1 * b2 - b1 * a2, d = (-a * x1 - b * y1 - c * z1);
  548.     //a b c d
  549.  
  550. }
  551.            
  552.            
  553.            
  554.            
  555.            
  556.            
  557.            
  558.            
  559.            
  560.            
  561.            
  562. 25.03.23 14:26     
  563. Заполнить вектор от a до n+a-1:
  564. #include <numeric>
  565. iota(vc.begin(), vc.end(), a);
  566.  
  567.            
  568.            
  569.            
  570.            
  571.            
  572.            
  573.            
  574.            
  575.        
  576. 30.06.23 10:29
  577. Префикс-функция:
  578. vector<int> pf(string s) {
  579.     int n = (int)s.length();
  580.     vector<int> pi(n);
  581.     for (int i = 1; i < n; ++i) {
  582.         int j = pi[i - 1];
  583.         while (j > 0 && s[i] != s[j])
  584.             j = pi[j - 1];
  585.         if (s[i] == s[j])  ++j;
  586.         pi[i] = j;
  587.     }
  588.     return pi;
  589. }
  590.  
  591. z-функция:
  592. vector<int> zf(string s) {
  593.     int n = (int) s.length();
  594.     vector<int> z (n);
  595.     for (int i=1, l=0, r=0; i<n; ++i) {
  596.         if (i <= r)
  597.             z[i] = min (r-i+1, z[i-l]);
  598.         while (i+z[i] < n && s[z[i]] == s[i+z[i]])
  599.             ++z[i];
  600.         if (i+z[i]-1 > r)
  601.             l = i,  r = i+z[i]-1;
  602.     }
  603.     return z;
  604. }      
  605.            
  606.            
  607.            
  608.            
  609.            
  610.            
  611.            
  612.            
  613.            
  614.            
  615.            
  616.            
  617.            
  618.            
  619.            
  620.            
  621. ДЕРЕВО ОТРЕЗКОВ С ОБНОВЛЕНИЕМ ПОДОТРЕЗКА
  622.    
  623. vector<int> tree, add;
  624. int k;
  625.  
  626. void insert(int ind, int value) {
  627.     int uk1 = k + ind;
  628.     tree[uk1] = value;
  629.     while (uk1 != 0) {
  630.         tree[uk1 / 2] = tree[(uk1 / 2)*2] + tree[(uk1 / 2)*2 + 1];
  631.         uk1 /= 2;
  632.     }
  633. }
  634. int getSum(int v, int tl, int tr, int l, int r) {
  635.     if (r <= tl || l >= tr)
  636.         return 0;
  637.  
  638.     if (add[v] != 0) {
  639.         tree[v] += (tr - tl) * add[v];
  640.         if (tr - tl > 1) {
  641.             add[v * 2] = add[v];
  642.             add[v * 2 + 1] = add[v];
  643.         }
  644.         add[v] = 0;
  645.     }
  646.     if (tl >= l && tr <= r)
  647.         return tree[v];
  648.     int mid = tl + (tr - tl) / 2;
  649.     return getSum(v * 2, tl, mid, l, r) + getSum(v * 2+1, mid, tr, l, r);
  650. }
  651. void addRange(int v, int tl, int tr, int l, int r, int value) {
  652.     if (r <= tl || l >= tr)
  653.         return;
  654.     if (tl >= l && tr <= r) {
  655.         add[v] += value;
  656.         return;
  657.     }
  658.  
  659.     int mid = tl + (tr - tl) / 2;
  660.     addRange(v * 2, tl, mid, l, r, value);
  661.     addRange(v * 2 + 1, mid, tr, l, r, value);
  662. }
  663.  
  664. int  main() {
  665.  
  666.     int n;
  667.     cin >> n;
  668.     k = 1;
  669.     while (k < n)
  670.         k *= 2;
  671.     tree.resize(4*n+1, 0);
  672.     add.resize(4 * n + 1, 0);
  673.     vector<int> vc(n);
  674.     for (int i = 0; i < n; i++) {
  675.         cin >> vc[i];
  676.         insert(i, vc[i]);
  677.     }
  678.     for (int i = 0; i < n * 4; i++)
  679.         cout << tree[i] << ' ';
  680.    
  681.     cout << '\n';
  682.     for (int i = 0; i < n; i++)
  683.         cout << getSum(1, 0, k, i, i + 1) << ' ';
  684.     return 0;
  685. }
  686.            
  687.            
  688.            
  689.            
  690.            
  691.            
  692.            
  693. АЛГОРИТМ ДЕЙКСТРЫ оптимальный
  694. const ll inf = 10000000000000ll;
  695.  
  696. int main()
  697. {
  698.     //freopen("input.txt", "r", stdin);
  699.     //freopen("rvq.out", "w", stdout);
  700.     cin.tie(NULL);
  701.     cout.tie(NULL);
  702.     ios_base::sync_with_stdio(false);
  703.     cout << fixed << setprecision(10);
  704.  
  705.     int n, m, a, b, w;
  706.     cin >> n >> m;
  707.     vector<vector<pair<int, int>>> edges(n);
  708.     vector<ll> dist(n, inf);
  709.     vector<int> prev(n);
  710.  
  711.  
  712.     int start = 0;
  713.     int ender = n - 1;
  714.     dist[start] = 0;
  715.  
  716.     for (int i = 0; i < m; i++) {
  717.         cin >> a >> b >> w;
  718.         a--, b--;
  719.         edges[a].push_back({ b, w });
  720.         edges[b].push_back({ a, w });
  721.     }
  722.     set<pair<ll, int> > s;
  723.     s.insert({ dist[start], start });
  724.     while (s.size() > 0) {
  725.         int v = s.begin()->second;
  726.         s.erase(s.begin());
  727.  
  728.         for (int i = 0; i < (int(edges[v].size())); ++i) {
  729.             int prvi = edges[v][i].first;
  730.             int w = edges[v][i].second;
  731.  
  732.             if (dist[v] + w < dist[prvi]) {
  733.                 s.erase({ dist[prvi], prvi });
  734.                 dist[prvi] = dist[v] + w;
  735.                 prev[prvi] = v;
  736.                 s.insert({ dist[prvi], prvi });
  737.             }
  738.         }
  739.     }
  740.     vector<int> way;
  741.     if (dist[ender] == inf)
  742.         cout << -1;
  743.     else {
  744.         int c = ender;
  745.         while (c != start) {
  746.             way.push_back(c);
  747.             c = prev[c];
  748.         }
  749.        
  750.         way.push_back(start);
  751.         for (int i = (way.size()) - 1; i >= 0; --i)
  752.             cout << (way[i]+1) << ' ';
  753.     }
  754.  
  755.     return 0;
  756. }
  757.            
  758.            
  759.            
  760.            
  761.            
  762.            
  763. СНМ(система непересекающихся множеств):
  764. //parent от 0 до n заполнить числами соответственно индексу 0...n
  765. void make_set (int v) {
  766.     parent[v] = v;
  767.     rank[v] = 0;
  768. }
  769.  
  770. int find_set (int v) {
  771.     if (v == parent[v])
  772.         return v;
  773.     return parent[v] = find_set (parent[v]);
  774. }
  775.  
  776. void union_sets (int a, int b) {
  777.     a = find_set (a);
  778.     b = find_set (b);
  779.     if (a != b) {
  780.         if (rank[a] < rank[b])
  781.             swap (a, b);
  782.         parent[b] = a;
  783.         if (rank[a] == rank[b])
  784.             ++rank[a];
  785.     }
  786. }
  787.            
  788.            
  789. //функция Эйлера(кол-во взаимнопростых с n чисел от 0 до n-1)
  790. int phi(int n){
  791.     int res = n;
  792.  
  793.     for (int i = 2; i * i <= n; ++i){
  794.         if (!(n % i)){
  795.             while(!(n % i)){
  796.                 n /= i;
  797.             }
  798.             res -= res/ i;
  799.         }
  800.     }
  801.  
  802.     if (n > 1)
  803.         res -= res / n;
  804.  
  805.     return res;
  806. }
  807.  
  808.  
  809. //z-функция - z[i] - наибольшее число символов, начиная с позиции i,
  810. //совпадающих с первыми символами строки s.
  811. vector<int> z_function (string s) {
  812.     int n = (int) s.length();
  813.     vector<int> z (n);
  814.     for (int i=1, l=0, r=0; i<n; ++i) {
  815.         if (i <= r)
  816.             z[i] = min (r-i+1, z[i-l]);
  817.         while (i+z[i] < n && s[z[i]] == s[i+z[i]])
  818.             ++z[i];
  819.         if (i+z[i]-1 > r)
  820.             l = i,  r = i+z[i]-1;
  821.     }
  822.     return z;
  823. }
  824.  
  825. //префикс функция - p[i] - длина наибольшего собственного суффикса подстроки s[0..i],
  826. //совпадающего с её префиксом
  827. vector<int> prefix_function(string s) {
  828.     int n = (int)s.length();
  829.     vector<int> pi(n);
  830.     for (int i = 1; i < n; i++) {
  831.         int j = pi[i-1];
  832.         while (j > 0 && s[i] != s[j])
  833.             j = pi[j-1];
  834.         if (s[i] == s[j])
  835.             j++;
  836.         pi[i] = j;
  837.     }
  838.     return pi;
  839. }
  840.    
  841. //Дерево Фенвика(почти как Дерево Отрезков) 
  842. T a[size];
  843. /* precondition: pos > 0 */
  844. void add(int pos, const T& val) {
  845.     while (pos < size) {
  846.         a[pos] += val;
  847.         pos += pos & -pos;
  848.     }
  849. }
  850. T sum(int pos) {
  851.     T ret = T();
  852.     while (pos > 0) {
  853.         ret += a[pos];
  854.         pos -= pos & -pos;
  855.     }
  856.     return ret;
  857. }
  858.        
  859.            
  860.            
  861.            
  862.            
  863.            
  864.            
  865.            
  866.            
  867.            
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!