Subset Sum

#include <iostream>

#include <cstdio>

using namespace std;

#define siz 1000005

#define INF 999999999

int a[siz],b[siz];



int main()

{

    int N,sum,n;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&N,&sum);



        for(int i=0;i<N;i++) scanf("%d",&b[i]);



        for(int i=1;i<=sum;i++) a[i]=INF;

            a[0]=0;

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

                for(int j=sum;j>=0;j--){

                    if(a[j]!=INF){

                        if(b[i]+j<=sum){

                            a[b[i]+j]=1;

                        }

                    }

                }

            }

        if(a[sum]==1) puts("1");

        else puts("0");

    }

    return 0;

}

String Matching (Naive)

#include <iostream>

using namespace std;

int Naive(string as, string bs)

{

    int n=as.size();

    int m=bs.size();

    int k=0;

    for(int s=0;s<=n-m;s++)

    {

        int p,flag=0;

        for(int i=s,p=0;i<s+m;i++)

        {

            if(bs[p]!=as[i])

            {

                flag=1;

                break;

            }

            else p++;

        }

        if(flag==0) k++;

    }

    return k;

}

int main()

{

    string as,bs;

    while(cin>>as>>bs)

    {

        cout<<Naive(as,bs)<<endl;

    }

    return 0;

}

Binary Search

#include <iostream>

using namespace std;

#define siz 100000000

int n;

int a[siz];

void Binary_search(int l, int h, int s)

{

    if(l>h) cout<<"Not Found"<<endl;

    else

    {

        int mid=(l+h)/2;

        if(a[mid]==s) cout<<"Found"<<endl;

        else if(s<mid) Binary_search(l,mid-1,s);

        else Binary_search(mid+1,h,s);

    }

}

int main()

{

    int s;

    while(cin>>n)

    {

        for(int i=0;i<n;i++) cin>>a[i];

        cin>>s;

        Binary_search(0,n-1,s);

    }

    return 0;

}

Linear Search

#include <iostream>

using namespace std;

#define siz 100000000



int a[siz];



void Linear_search(int a[], int n, int k)

{

    int flag=0;

    for(int i=0;i<n;i++)

    {

        if(a[i]==k)

        {

            flag=1;

            break;

        }

    }

    if(flag==1) cout<<"Found"<<endl;

    else cout<<"Not Found"<<endl;

}

int main()

{

    int n,k;

    while(cin>>n)

    {

        for(int i=0;i<n;i++) cin>>a[i];

        cin>>k;

        Linear_search(a,n,k);

    }

    return 0;

}

Binary Indexed Tree (BIT)

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

#define siz 1000005

int tree[siz],a[siz];

int MaxVal,n,m;

void reset(){

    for(int i=0;i<=m;i++) tree[i]=0;

}

int read(int idx){

    int sum=0;

    while(idx>0){

        sum+=tree[idx];

        idx-=(idx & -idx);

    }

    return sum;

}



void update(int idx ,int val){

 while (idx <= MaxVal){

  tree[idx] += val;

  idx += (idx & -idx);

 }

}



void updateSub(int idx ,int val){

 while (idx <= MaxVal){

  tree[idx] -= val;

  idx += (idx & -idx);

 }

}



int main()

{

    int x,y,q,k=1,z;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&m,&q);

        reset();

        MaxVal=m;

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

            scanf("%d",&a[i]);

            update(i,a[i]);

        }



        printf("Case %d:\n",k++);

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

            scanf("%d",&z);

            if(z==1){

                scanf("%d",&x);

                x+=1;

                updateSub(x,a[x]);

                printf("%d\n",a[x]);

                a[x]=0;

            }

            else if(z==2){

                scanf("%d%d",&x,&y);

                x+=1;

                a[x]+=y;

                update(x,y);

            }

            else if(z==3){

                scanf("%d%d",&x,&y);

                x+=1;

                y+=1;

                if(x==1) printf("%d\n",read(y));

                else printf("%d\n",read(y)-read(x-1));

            }

        }

    }

    return 0;

}

0/1 Knapsack

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <climits>

#include <map>

using namespace std;

#define siz 1000005

#define INF INT_MIN

typedef long long ll;



int dp[siz],query[siz];

map <int,int>mp;

int qMax;

struct data{

    int price,weight;

}a[siz];



void reset(){

    for(int i=0;i<=qMax;i++) dp[i]=INF;

}



bool cmp(data a, data b){

    if(a.weight<b.weight) return true;

    return false;

}

int main()

{

    int n,m,q,price,weight;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d",&m);

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

            scanf("%d%d",&price,&weight);

            a[i].price=price;

            a[i].weight=weight;

        }

        sort(a,a+m,cmp);

        scanf("%d",&q);

        qMax=0;

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

            scanf("%d",&query[i]);

            qMax=max(qMax,query[i]);

        }



        reset();

        dp[0]=0;

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

            for(int j=qMax;j>=0;j--){

                if(dp[j]!=INF){

                    int val=j+a[i].weight;

                    if(val<=qMax){

                        if(dp[val]==INF) dp[val]=a[i].price+dp[j];

                        else dp[val]=max(dp[val],dp[j]+a[i].price);

                    }

                }

            }

        }

        ll sum=0,mx=0;

        //for(int i=0;i<=qMax;i++) cout<<i<<" "<<dp[i]<<endl;

        int k=0;

        sort(query,query+q);

        int flag=0;

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

            mx=max(mx,(ll)dp[i]);

            if(i==query[k]){

                while(true){

                    sum+=mx;

                    if(k==q){

                        flag=1;

                        break;

                    }

                    if(i!=query[k+1]) break;

                    k++;

                }

                k++;

            }

            if(flag==1) break;

            //cout<<"s"<<sum<<endl;

        }

        cout<<sum<<endl;

    }

    return 0;

}

SCC Trick

#include <iostream>

#include <vector>

#include <cstdio>

using namespace std;

#define siz 1000009

int color[siz];

int N,M;

vector <int> vec[siz];

vector <int> ans;

void dfs_visit(int n){

    color[n]=1;

    for(int i=0;i<vec[n].size();i++){

        if(color[vec[n][i]]==0){

            dfs_visit(vec[n][i]);

        }

    }

    color[n]=2;

}

void top_sort(int p){

    color[p]=1;

    for(int i=0;i<vec[p].size();i++){

        if(color[vec[p][i]]==0) top_sort(vec[p][i]);

    }

    ans.push_back(p);

    color[p]=2;

}

int main()

{

    int n,x,y;

    #ifndef ONLINE_JUDGE

    freopen("input.txt","r",stdin);

    #endif

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&N,&M);



        //clearing vector

        for(int i=0;i<=N;i++)

            vec[i].clear();



        //pushing edges

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

            scanf("%d%d",&x,&y);

            vec[x].push_back(y);

        }



        //colouring

        for(int i=0;i<=N;i++)

            color[i]=0;



        //topsort

        for(int i=1;i<=N;i++)

            if(color[i]==0)top_sort(i);



        for(int i=0;i<=N;i++)

            color[i]=0;

        //dfs

        int cnt=0;

        for(int i=ans.size()-1;i>=0;i--){

            if(color[ans[i]]==0){

                cnt++;

                dfs_visit(ans[i]);

            }

        }

        printf("%d\n",cnt);

        ans.clear();

    }

    return 0;

}