Scribd
Upload
72 views

ICPC Codes

Uploaded by

hby7616
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
72 views

ICPC Codes

Uploaded by

hby7616
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 13

STLs

//most of them have the sort and reverse function

VECTORs:
.push_back();
.pop_back();
.insert(v.begin+x, sth_to_insert) // x is the index
.erase(v.begin+x)
.size()
Lists:
.push_back();
.push_front();
.pop_back();
.insert(v.begin+x, sth_to_insert) // x is the index
.erase(v.begin+x)
.size()
To go throuth the list you must declare a pointer
first, for ex:
List<string>::iterator boi = l.begin();
While (boi != l.end()){
cout << *boi << endl;
}

STACK:
.push();
.pop();
.top(); returns the last element
.size();
Queue:
.push();
.pop(); removes first elment
.front(); returns the 1st element
.size();
.back(); returns the last element
Priority Queue:
Same as queue, but the larger is put on top
.push();
.pop(); removes first elment
.top(); returns the biggest element
.size();
SETs:
// right side is bigger, left side is smaller
// has no duplicates, and arranges stuff
// insert
// find
// clear
// print
// erase
set <int>::iterator it = st.begin();
while (it != st.end()){
cout << *it << endl;
it++;
}
// If you want to access it use pointer
MAPs:
// basically same as the python dict.
// If you want to access it use pointer
// to access key use ->first
// to access what’s inside use ->second

In recursion problems, most of them you just need


to make an array called visited to mark the spots you
already went to.
And in all of them, you just need to think how can
this be solved by recursion just by changing one of the
parameters.

Binary Search (sorted only)


Prime_Stuff
vector <long long> prime;

void sieve(long long n){

bool *arr = new bool [n];

for (long long i =0; i < n; i++){


arr[i] = true;
}

for (long long i =2; i < n; i++){


if (arr[i] == true){
prime.push_back(i);
for (long long j = i * i; j < n; j += i){
arr[j] = false;
}
}

}
}

bool prime(int n){

if (n == 2)
return true;

if(n <=1 || n %2 == 0)
return false;

for (long long i = 3; i*i <=n; i+= 2){


if(n%i == 0){
return false;
}

return true;
}

std::vector<int> divisors(int n){


std::vector<int> v;
long long i;
for (i = 1; i*i <n; i++){
if(n%i == 0){
v.push_back(i);
v.push_back(n/i);
}

if(i*i == n){
v.push_back(i);
}

return v;

}
************

std::vector<int> primefactors(int n){


std::vector<int> v;
long long x =3;
while(n%2 == 0){
n/=2;
v.push_back(2);
}
while(x*x <= n){
while(n%x == 0){
n/=x;
v.push_back(x);
}
x+=2;
}

return v;

nCr and nPr


long long per(long long n, long long r){
long long res = 1;
for (long long i =1; i <=r; i++, n--){
res *=n;
}

return res;
}

****
long long comp(long long n, long long r){
if (n-r < r){
r = n-r;
}
long long res = 1;
for (long long i =1; i <=r; i++, n--){
res *=n;
res/=i;
}

return res;

prefix_sum

#include <iostream>

using namespace std;

int main()
{
int n, q, r, arr[1005], cumu[1005], s ,e;
cin >> n >> q;
for(int i =1; i<=n; i++){
cin >> arr[i];
}
cumu[0] = 0;
cumu[1] = arr[1];

for(int i =2; i<=n; i++){


cumu[i] = cumu[i-1] + arr[i];
}

for(int i =0; i<q; i++){


cin >> s >> e;
cout << cumu[e] - cumu[s-1] << endl;
}

return 0;
}

prefix_sum 2d
// ‫لو فهمت حاجة تبقى جامد‬
#include <bits/stdc++.h>

using namespace std;

int main()
{
int n, q, r, arr[105][105], cumu[105][105], s ,e;

cin >> n >> q;


for(int i =1; i<=n; i++){
for(int j =1; j<=q; j++){
cin >> arr[i][j];
}
}

for(int i =1; i<=n; i++){


for(int j =1; j<=q; j++){
if (i ==0 || j ==0){
cumu[i][j] == 0;
}else{
cumu[i][j] = cumu[i][j-1] + arr[i][j];
}
}
}

for(int i =1; i<=n; i++){


for(int j =1; j<=q; j++){

cumu[i][j] += cumu[i-1][j];

}
}

int q, r1, c1, r2, c2;


cin >> q;
while(q--){
cin >> r1 >> c1 >> r2 >> c2;
int A = cumu[r2][c2];
int B = cumu[r1-1][c2];
int C = cumu[r2][c1-1];
int D = cumu[r1-1][c1-1];

int res = A - (B+C) +D;


}
return 0;
}

You might also like