topcoder SRM 572 Div1 250+500

00:00/00:00

250:NewArenaPassword

题意:

给你一串字符串,你要把前k个字符和后k个字符转换成一样的,问你最少要几步。

分析:

因为长度小于50所以如果k小于len/2,我们直接暴力做就好了,如果大于一半我们发现相隔len-k的长度字符是一样的,我们直接找最多的就好了。。。

代码:

int len,ans;
int num[30];
int NewArenaPassword::minChange(string oldPassword, int K) 
{
    ans=0;
    len=oldPassword.size();
    if(K<len/2)
    {
        for(int i=0;i<K;i++)
            if(oldPassword[i]!=oldPassword[len-K+i])
                ans++;
    }
    else 
    {
        int flag=len-K;
        for(int i=0;i<flag;i++)
        {
            memset(num,0,sizeof(num));
            int maxn=0,tot=0;
            for(int j=0;j*flag+i<len;j++)
            {
                tot++;
                num[oldPassword[i+j*flag]-'a']++;
                maxn=max(maxn,num[oldPassword[i+j*flag]-'a']);
            }
            ans+=tot-maxn;
        }
    }
    return ans;
}

500:EllysBulls

题意:

某人有一个长度小于9的密码,你连续猜小于50次,每次他都会告诉你你猜对了几位,然后,问你密码是多少,有多个就输出”Ambiguity”,没有答案输出”Liar”。。。

分析:

这个题目我请教了周发发大佬,大佬一看是tc的题目,就给出了一个暴力加优化,然后说tc一秒十个亿,然后我打完T掉了。。。是这样的长度是9时,我们枚举前5位,然后剩下的询问中找对最多的,然后枚举哪几位对,最后验证就好了,理论可以过然后我太菜了,打了一个晚上没过。。。

代码:

int num,siz,ret;
int ans[10];
vector q;
vector r;
vector mdzz[5];
int anss[55];
int last[55];
inline void dfs_small(int now)
{
    if(ret>=2)return;
    if(now==num)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(register int j=0;j<num;++j)
                if(q[i][j]-'0'==ans[j])
                    good++;
            if(good!=r[i])
                return;
        }   
        ret++;
        for(register int i=0;i<num;++i)
            anss[i]=ans[i];
        return;
    }
    for(register int i=0;i=2)
        return;
    if(now==num)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(int j=6;j<num;++j)
                if(q[i][j]-'0'==ans[j])
                    good++;
            if(good!=last[i])
                return;
        }
        ret++;
        for(register int i=0;i>1,now+1);
    }
    else 
        for(register int i=0;i>1,now+1);
}
inline void dfs(int now)
{
    if(ret>=2)
        return;
    if(now==6)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(int j=0;jr[i])
                return;
            last[i]=r[i]-good;
        }
        int maxn=-1;
        for(register int i=0;ilast[maxn])
                maxn=i; 
        if(last[maxn]>num-6)return;
        for(register int i=0;i<mdzz[last[maxn]].size();++i)
            dfs_GG(maxn,mdzz[last[maxn]][i],6);
        return ;
    }
    for(register int i=0;i<=9;i++)
    {
        ans[now]=i;
        dfs(now+1);
    }
}
inline void init()
{
    for(register int i=0;i<=4;++i)
        mdzz[i].clear();
    for(int i=0;i<(1<<(num-6));++i)
        mdzz[__builtin_popcount(i)].push_back(i);
}
inline string EllysBulls::getNumber(vector  guesses, vector  bulls) 
{
    ret=0;q=guesses;r=bulls;
    num=guesses[0].size();
    siz=guesses.size();
    if(num>6)
        init();
    if(num<=6)dfs_small(0);
    else dfs(0);
    if(ret==1)
    {
        string zz;
        for(register int i=0;i1)
        return "Ambiguity";
    else return "Liar";
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注