codeworrior's blog

By codeworrior, 14 years ago, In English
for studious students II i came up with following solution during the contest but it didnt work in 6 min time.
is there a better solution possible. and how to do that.
Also can anyone provide a detailed explanation for problem A and C.


#include<map>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define mod 1000000007
struct CompareMethod
{
bool operator()(const std::string &a, const std::string &b) const
{
if(a.length()>b.length())
    return 0;
return 1;
   
}
};

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        map<string,int>dp;
        priority_queue<string,vector<string>,CompareMethod>q;
        dp[s]=1;
        q.push(s);
        while(!q.empty())
        {
            string n=q.top();
            //cout << n <<"\n";
            q.pop();
            for(int i=0;i<n.length();i++)
            {
                for(int j=i+1;j<n.length();j++)
                {    bool pa=0,pb=0;
                    for(int k=i;k<=j;k++)
                        if(n[k]=='a')
                            pa=1;
                        else
                            pb=1;
                    if(pa==1 && pb==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"a"+tmp2;
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"b"+tmp2;
                   
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                    else if(pa==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"a"+tmp2;
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                    else if(pb==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"b"+tmp2;
                   
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                }
            }
        }
        int ans=0;       
        for(map<string,int>::iterator it=dp.begin();it!=dp.end();it++)
        {    ans+=dp[it->first];//cout <<it->first << " : "<<dp[it->first] << "\n";
        }
        cout << ans << "\n";
    }
}
  • Vote: I like it
  • -4
  • Vote: I do not like it