all
//https://vjudge.net/contest/479381 (bit manipulation)
// https://vjudge.net/contest/477784 (number theory)
//https://vjudge.net/contest/480351(graph)
MY template:
transform(s1.begin(), s1.end(),
s1.begin(), ::toupper);//convert all character to upper
1.use of substr
string
s="ujjal";
string ss;
ss=s.substr(0,i+1);//substr(index
, number_of character)
2.array:
array<int,5> arr;
arr.fill(100);//all are fill by 100
3 . vector:
vector<int> v;//declaration(vector<int> v(5,10))
v.size()
v.push_back(1)
v.emplace_back(4);//instend of push_back() and it take
leaser time then push_back();
v.pop_back();
v.clear();
SET:
set<int> st;
//declaration
st.insert(10); /
/inserting in set
st.erase(st.begin());//pass pointer
st.erase(30);//erase
by key
for multiple erase
auto it=st.begin();
it++;
st.erase(st.begin(),it);
auto
it=st.find(5);//return pointer to th value if not find return st.end();
unordered_set<int>st1;//unordered set we use that when
element not necessary to sorted o(1) complexity
Ordered set
// C++ program to demonstrate the
// ordered set in GNU C++
#include <iostream>
using namespace std;
// Header files, namespaces,
// macros as defined above
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Driver program to test above functions
int main()
{
// Ordered set declared with name o_set
ordered_set o_set;
// insert function to insert in
// ordered set same as SET STL
o_set.insert(5);
o_set.insert(1);
o_set.insert(2);
// Finding the second smallest element
// in the set using * because
// find_by_order returns an iterator
cout << *(o_set.find_by_order(1))
<< endl;
// Finding the number of elements
// strictly less than k=4
cout << o_set.order_of_key(4)
<< endl;
// Finding the count of elements less
// than or equal to 4 i.e. strictly less
// than 5 if integers are present
cout << o_set.order_of_key(5)
<< endl;
// Deleting 2 from the set if it exists
if (o_set.find(2) != o_set.end())
o_set.erase(o_set.find(2));
// Now after deleting 2 from the set
// Finding the second smallest element in the set
cout << *(o_set.find_by_order(1))
<< endl;
// Finding the number of
// elements strictly less than k=4
cout << o_set.order_of_key(4)
<< endl;
return 0;
}
map:
map<string,int> mp;//declaration
mp["ujjal"]=1;//initialization
mp["mithu"]=2;
mp.emplace("ruddro",26);
mp.erase("ruddro");
mp.erase(mp.begin());
mp["mithu"]=2;
mp.emplace("ruddro",26);
//mp.erase(mp.begin(),mp.begin()+1);
for(auto
u:mp)cout<<u.first<<" "<<u.second<<endl;//iteration
auto it
=mp.find("ujjal");//return poinert for ujjal
mp.clear();//clear
whole map;
mp.empty();//if
empty return 1 otherwise 0
Stack
:
Problem 1:next greater element from
right
vector<ll>
nge(vector<ll>vp)
{
vector<ll>v(vp.size());
stack<ll>st;
for(ll i=0;i<vp.size();i++)
{
while(!st.empty()&&vp[st.top()]<vp[i])///4 5 2 25
{
v[st.top()]=i;
st.pop();
}
st.push(i);
}
while(!st.empty())
{
v[st.top()]=-1;
st.pop();
}
return v;
}
bitmanipulation :
https://codeforces.com/blog/entry/73490
1.decimal to binary
string to_bin(int n)//bitset<8>(n) another way
{
string s;
if(n==0)s+='0';
while(n>0)
{
if(n%2)s+='1';
else
s+='0';
n/=2;
}
reverse(s.begin(),s.end());
return s;
}
1.binary to decimal
string s;
cin>>s;
ll sum,l;
sum=0;
l=1;
for(int
i=s.size()-1;i>=0;i--)
{
sum+=(s[i]-'0')*l;
l*=2;
}
cout<<sum<<endl;
2.right shift
right shift >> shifts bits to the
right and some bits might disappear this way, like bits 01 in the example
above. An expression x >> b is equal to
the floor of x/2^b. It's more complicated
for negative numbers but we won't discuss it.
int n,a;
cin>>n>>a;
n=n>>a; // goes of last ‘a’
bit like n=101 if a=1 then 10(2 divide n by a time)(n/2^a)
cout<<n<<endl;
3.left shift
n=n<<a;//every bit shift 3 time to the left
101->101000(n=n*(2^a))
If
there is no overflow, an expression x << b is equal to x⋅2bx⋅2b, like here we had (13 << 2) = 52.
4.ith bit set or not
5.set the ith bit of a given number
int
mask=(1<<a);// if a==1 then mask=10
n=n|mask;//
n==101|010==111
6.clear last set bit
n=n&(n-1);//like n==1100(12)&1011==1000
7.power of 2;
If(n&(n-1))==0 then this is power of two
(1000&111==0)
8.count numbers of set bit
cnt=0;
while(n!=0)
{
if(n&1==1)cnt++;
n=n>>1;
}
9. Xor of
consucative numbers upto r
if(r%4==0)x=r;
else
if(r%4==3)x=0;
else
if(r%4==2)x=r+1;
else x=1;
10.property
If , X^y==b;
then
X^b==y
Summary:
2^k is just 1 <<
k or 1LL
<< k if you need long longs
Bitset
:
n C++, __builtin_popcount(x) returns popcount of a number — the number of ones in the
binary representation of xx. Use __builtin_popcountll(x) for long longs.
r=__builtin_popcountll(100);
cout<<r<<endl;
There are also __builtin_clz and __builtin_ctz (and
their long long versions) for counting the number of leading or trailing zeros
in a positive number
# the biggest power of 2 that is a
divisor of x. Example: f(12) = 4 will (1<<(Number of trailing zeor)
Compute the smallest power of 2 that is
not smaller than x. Example: f(12) = 16
1 <<
(32 - __builtin_clz (x - 1))
but this is UB (undefined behavior) for x≤1x≤1 so you'll often
need an if for x==1x==1.
bitset<32>bset(10);//direct integer push
and it automatically in binary
cout<<bset<<endl;
bset[2]=1;//direct change
cout<<bset[2 ]<<endl;//direct access like array
cout<<bset<<endl;
cout<<bset.count()<<endl;//return the number of set bit;
cout<<bset.size()<<endl;//return the number of set bit;
cout<<bset.any()<<endl;//return true if any bit is set;
cout<<bset.all()<<endl;//return true if all bits are set;
// bset.set();//set
all bit
bset.set(5,1);//do set in fixed positionset(position,value)
//bset.reset();//same as setbut reverse;
//bset.flip();//flip all bit;ones complement
cout<<bset<<endl;
bitset<32>bset1("101");//direct push binary
cout<<bset1<<endl;
Graph
/tree:
1.BFS
vector<ll>adj[100000];
ll dis[100000],vis[100000];
void bfs(ll node)
{
queue<ll>q;
q.push(node);
vis[node]=1;
while(!q.empty())
{
ll cur;
cur=q.front();
q.pop();
for(ll
i=0;i<adj[cur].size();i++)
{
ll
child=adj[cur][i];
if(vis[child]==0)
{
vis[child]=1;
dis[child]=dis[cur]+1;
q.push(child);
}
}
}
}
# In tree if noes are n then edges will (n-1)
DSU :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
ll parent[N];
ll Size[N];
void make(ll v)
{
parent[v]=v;
Size[v]=1;
}
ll Find(ll v)
{
if(parent[v]==v)return v;
return
parent[v]=Find(parent[v]);//path compression
}
void Union(ll a,ll b)
{
a=Find(a);
b=Find(b);
if(a!=b)
{
if(Size[a]<Size[b])//union by size
{
swap(a,b);
}
parent[b]=a;
Size[a]+=Size[b];
}
}
int main()
{
ll n,m;
cin>>n>>m;
for(ll
i=1;i<=n;i++)
{
make(i);
}
while(m--)
{
ll u,v;
cin>>u>>v;
Union(u,v);
}
ll
connected_cnt=0;
for(ll
i=1;i<=n;i++)
{
if(i==parent[i])connected_cnt++;
}
cout<<"Connected component :
"<<connected_cnt<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define N 100005
ll arr[N];
ll dp[N];
ll lis(ll i)
{
if(dp[i]!=-1)return dp[i];
ll ans;
ans=1;
for(ll j=0;j<i;j++)
{
if(arr[i]>arr[j])
ans=max(ans,lis(j)+1);
}
return dp[i]=ans;
}
int main()
{
memset(dp,-1,sizeof(dp));
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,i;
cin>>n;
for(i=0;i<n;i++)cin>>arr[i];
ll ans;
ans=0;
for(i=0;i<n;i++)
{
ans=max(ans,lis(i));
}
cout<<ans<<endl;
return 0;
}
0/1 knapsack
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
ll val[100005];
ll wt[100005];
ll dp[105][100005];
ll func(ll ind,ll amount)
{
if(amount==0)return 0;
if(ind<0)return
0;
if(dp[ind][amount]!=-1)return dp[ind][amount];
ll ans;
ans=func(ind-1,amount);
if(amount-wt[ind]>=0)
{
ans=max(ans,func(ind-1,amount-wt[ind])+val[ind]);
}
return
dp[ind][amount]=ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dp,-1,sizeof(dp));
ll n,w;
cin>>n>>w;
for(ll
i=0;i<n;i++)
{
cin>>wt[i]>>val[i];
}
cout<<func(n-1,w)<<endl;
return 0;
}
0 Comments