怎么才能过时限 三连击

sunzhen @ 2019-02-02 17:49:25

#include<bits/stdc++.h>
using namespace std;
int main()
{   
    int f(int x,int y,int z);
    int count=0;
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    for(int i=100;i<=999;i++)
    {
        for(int j=100;j<=999;j++)
        {
            for(int k=100;k<=999;k++)
            {
                if(i*1.0/j==a*1.0/b&&i*1.0/k==a*1.0/c&&j*1.0/k==b*1.0/c)
                {
                    if(f(i,j,k)==1)
                    {
                        printf("%d %d %d\n",i,j,k);
                        count++;
                    }

                }
            }
        }
    }
    if(count==0)
    {
        printf("No!!!");
    }
    return 0;
}

int a[10]={0};
void fun(int x)
{//192
    a[x%10]++;
    x=x/10;
    a[x%10]++;
    x=x/10;
    a[x%10]++;
}

int f(int t,int y,int z)
{
    int count=0;
    int i;
    fun(t);
    fun(y);
    fun(z);
    for(i=1;i<10;i++)
    {
        if(a[i]==1)
        {
            count++;
        }
    }
    if(count==9)
    {
        return 1;
    }
    else
    {
        for(i=1;i<10;i++)
        {
            a[i]=0;
        }
        count=0;
        return 0;
    }
}

by huangsy @ 2019-02-02 18:07:30

不能直接枚举O(n^3)必T无疑 你枚举一个数后另外两个数就已经确定了，然后判断，总枚举状态数O(n)

#include<bits/stdc++.h>
using namespace std;
int a,b,c,A,B,C,used[10];bool flag;
int main()
{
    cin>>A>>B>>C;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            for(int k=1;k<=9;k++)
            {
                memset(used,0,sizeof(used));
                a=i*100+j*10+k;
                if(B*a%A!=0)continue;else b=B*a/A;
                if(C*a%A!=0)continue;else c=C*a/A;
                if(c>=1000)continue;
                used[i]=1;
                if(used[j]==1||j==0)continue;else used[j]=1;
                if(used[k]==1||k==0)continue;else used[k]=1;
                if(used[b%100/10]==1||(b%100/10)==0)continue;else used[b%100/10]=1;
                if(used[c%100/10]==1||(c%100/10)==0)continue;else used[c%100/10]=1;
                if(used[b/100]==1||(b/100)==0)continue;else used[b/100]=1;
                if(used[c/100]==1||(b/100)==0)continue;else used[c/100]=1;
                if(used[b%10]==1||(b%10)==0)continue;else used[b%10]=1;
                if(used[c%10]==1||(b%10)==0)continue;else used[c%10]=1;
                cout<<a<<" "<<b<<" "<<c<<endl;flag=1;
            }
        }
    }
    if(!flag)cout<<"No!!!";
    return 0;
}

by 万弘 @ 2019-02-02 18:38:38

因为此题正解是dfs+剪枝

by sunzhen @ 2019-02-02 18:43:25

for(int i=123;i<=987;i++)
    {
        j=i*b/a;k=i*c/a;
        if(f(i,j,k)==1&&j<=987&&k<=987)
        {
            printf("%d %d %d\n",i,j,k);
            count++;
        }
    }

这样子ac了

by zhensama @ 2019-02-02 19:49:36

for(int i=123;i<=987;i++)
{
    int ans=0;
    int num[11]={0,1,2,3,4,5,6,7,8,9};
    for(int j=1;j<=9;j++)
    {
        if(i/100==num[j]||(i/10)%10==num[j]||i%10==num[j])
        {
            ans++;
            num[j]=0;
        }
    }
    if(ans!=3)
    continue;
    else
    {
        k=i*b/a;
        if(k>999)
        continue;
        for(int j=1;j<=9;j++)
        {
            if(num[j]==0)
            continue;
            if(k/100==num[j]||(k/10)%10==num[j]||k%10==num[j])
            {
                ans++;
                num[j]=0;
            }
        }
        if(ans!=6)
        continue;
        else
        {
            l=i*c/a;
            if(l>999)
            continue;
            for(int j=1;j<=9;j++)
            {
                if(num[j]==0)
                continue;
                if(l/100==num[j]||(l/10)%10==num[j]||l%10==num[j])
                {
                    ans++;
                    num[j]=0;
                }
            }
            if(ans!=9)
            continue;
            else
            {
                cout<<i<<" "<<k<<" "<<l<<endl;
                flag++;
            }
        }
    }
}
if(flag==0)
cout<<"No!!!";

暴力解法

by whatismyname0 @ 2019-02-14 11:15:21

暴力判断