//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
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)
0 Comments