3/29 CodeCraft-21 and Codeforces Round #711 (Div. 2)

PA GCD Sum 題目連結

題敘:

有一函式gcdSum(x)=gcd(x,sum of digitials of x)，意指x與其每一位數之和的最大公因數，求不小於n的整數中符合gcdSum(x)>1之最小x

解法:

這題主要有兩個部分:x每一位數字和的的計算(sum of digitials of x)以及其與x之最小公倍數之計算，因此我們只要寫一個函式sum(x)去求x的每位數字和並使用c++內建函式__gcd求得gcdSum(x)即可，最後從n開始枚舉直到gcdSum(x)>1

程式碼:

int f(int x) //算出x的每位數字和
{
    int sum=0;
    while(x)
    {
        sum+=x%10;
        x/=10;
    }
    return sum;
}

void sol()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=n;;i++) //從n開始窮舉
        {
            int ans=__gcd(i,f(i));
            if(ans>1) //如果所得結果>1則輸出
            {
                cout<<i<<endl;
                break;
            }
        }
    }
}

PB Box Fitting 題目連結

題敘

給定共n個積木，以及一個寬度為w的容器，求最低需要疊幾層才能將積木疊完

test 3 TLE解法:

本題用到greedy的概念，從最長的積木由下開始疊，如果發現目前所用到的層數皆無法放下積木，則再往上多疊一層

程式碼

void sol()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,w;
        cin>>n>>w;
        int x[n],y[n];
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            y[i]=w;
        }
        sort(x,x+n);
        int ans=1;
        for(int i=n-1;i>=0;i--)
        {   
            for(int j=0;j<ans;j++)
            {
                if(y[j]>=x[i])
                {
                    y[j]-=x[i];
                    break;
                }
                if(j==ans-1)
                {
                    y[ans]-=x[i];
                    ans++;
                    break;
                }
            }
        }
        cout<<ans<<endl;
    }
}

AC解法:

由於原本的解法會導致相同長度的積木重複由下往上判斷，進而造成TLE，因此用map<int,int>將相同長度的積木合併判斷，已獲得最佳效率

程式碼

尚未AC