177 - B. 猜數字

domen111

不知道這種code貼在解題分享應該嗎? 陣列大小和迴圈次數都是憑感覺和透過測試決定的，感覺不算很好的解法

主要的概念就是遞迴+DP處存算過的答案，2個function的功能就是算阿勝和阿哲在第i步時是否算得出答案，枚舉所有可能然後遞迴詢問對手在前一步是否能算出答案，理論上對手前一次不可能算出答案，否則不會呼叫目前的function，對手如果只有一種可能會算不出答案表示這一種可能就是這次的答案。

上傳MLE,RE了好幾次，稍微調整for迴圈的次數和陣列大小，終於脫離RE了，本來以為for才跑5次可能會WA，沒想到直接AC

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cstring>
#define endl '\n'
using namespace std;
char dp1[25][11000],dp2[25][251000];
bool prime[1000001];
bool can1ans(int i,int sum);
bool can2ans(int i,int prod);
bool can1ans(int i,int sum)
{
        if(dp1[i][sum]!=-1)
                return dp1[i][sum];
        if(i==1)
                return dp1[i][sum]= sum==2 || sum==3;
        int cantAnsC=0;
        for(int a=1;a<sum;a++)
        {
                int b=sum-a;
                if(b<a)break;
                if(!can2ans(i-1,a*b))
                        cantAnsC++;
                if(cantAnsC>1)
                        return dp1[i][sum]=0;
        }
        if(cantAnsC==1)
                return dp1[i][sum]=1;
        throw;
}
bool can2ans(int i,int prod)
{
        if(dp2[i][prod]!=-1)
                return dp2[i][prod];
        if(i==1)
                return dp2[i][prod]= prime[prod];
        int cantAnsC=0;
        for(int a=1;a<prod;a++)
        {
                int b=prod/a;
                if(b<a)break;
                if(a*b!=prod)continue;
                if(!can1ans(i-1,a+b))
                        cantAnsC++;
                if(cantAnsC>1)
                        return dp2[i][prod]=0;
        }
        if(cantAnsC==1)
                return dp2[i][prod]=1;
        throw;
}
void setprime()
{
        for(int i=0;i<=1000000;i++)
                prime[i]=1;
        for(int i=2;i<=1000;i++)
                if(prime[i])
                        for(int j=i+i;j<=1000000;j+=i)
                                prime[j]=0;
}
int main()
{
        ios::sync_with_stdio(false);
        //cin.tie(0);
        setprime();
        int T;
        cin>>T;
        while(T--)
        {
                memset(dp1,-1,sizeof dp1);
                memset(dp2,-1,sizeof dp2);
                int a,b;
                cin>>a>>b;
                for(int i=1;;i++)
                {
                        if(i>5)
                        {
                                cout<<"-1 -1"<<endl;
                                break;
                        }
                        bool c1a=can1ans(i,a+b),c2a=can2ans(i,a*b);
                        if(c1a&&c2a)
                                cout<<i<<" "<<i<<endl;
                        else if(c1a)
                                cout<<i<<" "<<i+1<<endl;
                        else if(c2a)
                                cout<<i+1<<" "<<i<<endl;
                        else continue;
                        break;
                }
        }
}

Sylveon

紙筆分析~

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;

int apb(int n)
{
    if(n<=3)return 1;
    if(n==4)return 2;
    if(n==5)return 4;
    return 9999;
}
bool isprime(int n)
{
    if(n<=1)return false;
    for(int i=2;i<n;++i)
        if(n%i==0)
            return false;
    return true;
}
int amb(int n)
{
    if( n==1 || isprime(n) )
        return 1;
    if(n==4)return 3;
    if(n==6)return 5;
    return 9999;
}
int main()
{
    int T,a,b;
    cin>>T;
    while(T--)
    {
        cin>>a>>b;
        int N=apb(a+b);
        int M=amb(a*b);
        int m=min(N,M);
        if( min(N,M) == 9999 )
            cout<<"-1 -1\n";
        else
        {
            if(N!=1) N=min(N,m+1);
            if(M!=1) M=min(M,m+1);
            cout<<N<<" "<<M<<'\n';
        }
            
    }
}