2020년 바이두의 별·프로그래밍대회 - 1차전 문제풀이

Drink http://acm.hdu.edu.cn/showproblem.php?pid=6743각 음료를 일일이 열거하면 된다

#include
#include
using namespace std;
int t,n,m;
int x[10005],y[10005];
int dp[10005];
int main()
{
    int minans;
    scanf("%d",&t);
    while(t--)
    {
        minans=1e9;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
        for(int i=1;i<=n;i++)
        {
            if((m+x[i]-1)/x[i]*y[i]<minans) minans=(m+x[i]-1)/x[i]*y[i];
        }
        printf("%d
",minans);
    }
    return 0;
}

GPA http://acm.hdu.edu.cn/showproblem.php?pid=6744GPA가 11가지 상황임을 감안하여 11^4 폭력은 각 상황을 일일이 열거하면 된다

#include
#include
using namespace std;
int pz[23][2];
int x,ans,t;
int main()
{
    pz[0][0]=0;pz[0][1]=0;
    pz[1][0]=60;pz[1][1]=10;
    pz[10][0]=95;pz[10][1]=43;
    pz[9][0]=90;pz[9][1]=40;
    pz[8][0]=85;pz[8][1]=37;
    pz[7][0]=80;pz[7][1]=33;
    pz[6][0]=75;pz[6][1]=30;
    pz[5][0]=70;pz[5][1]=27;
    pz[4][0]=67;pz[4][1]=23;
    pz[3][0]=65;pz[3][1]=20;
    pz[2][0]=62,pz[2][1]=17;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&x);
        for(int i1=0;i1<=10;i1++)
        for(int i2=0;i2<=10;i2++)
        for(int i3=0;i3<=10;i3++)
        for(int i4=0;i4<=10;i4++)
        if(pz[i1][0]+pz[i2][0]+pz[i3][0]+pz[i4][0]<=x)
        {
            if(pz[i1][1]+pz[i2][1]+pz[i3][1]+pz[i4][1]>=ans) ans=pz[i1][1]+pz[i2][1]+pz[i3][1]+pz[i4][1];
        }
        printf("%d.%d
",ans/10,ans%10);
    }
    return 0;
}

Dec http://acm.hdu.edu.cn/showproblem.php?pid=6745언뜻 보면 수론이지만 사실은DP이다. x, y의 범위가 모두 1000이라는 것을 알아차렸고 문의 횟수는 1e6회이다. 가장 좋은 방법은 각 x, y조합이 대응하는 상황을 계산한 후에 표를 작성하는 것이다.
a n s [ 1 ] [ 1 ] = 1 ans[1][1]=1 ans[1][1]=1 a n s [ i ] [ j ] = m a x ( a n s [ i − 1 ] [ j ] , a n x [ i ] [ j − 1 ] ) + ( g c d ( i , j ) = = 1 ) ans[i][j]=max(ans[i-1][j],anx[i][j-1])+(gcd(i,j)==1) ans[i][j]=max(ans[i−1][j],anx[i][j−1])+(gcd(i,j)==1)

#include
#include
using namespace std;
int ans[1005][1005];
inline int gcd(int x,int y){return x?(gcd(y%x,x)):y;}
int main()
{
    for(int i=1;i<=1000;i++) ans[i][1]=ans[1][i]=i;
    for(int i=2;i<=1000;i++)
    for(int j=2;j<=1000;j++)
    {
        ans[i][j]=max(ans[i-1][j],ans[i][j-1])+(gcd(i,j)==1);
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d
",ans[a][b]);
    }
    return 0;
}

Civilization http://acm.hdu.edu.cn/showproblem.php?pid=6746
각 점부터 필요한 최소 회합수를 각각 계산한 다음에 출발점에서 이 점에 도착하는 데 필요한 회합수를 계산하여 합쳐서 최소값을 취하면 된다.

#include
#include
using namespace std;
int a[505][505],x,y,n;
int ans[505][505];
int cot[5];
int queue[233];
int minans;
void BfsAndCalc(int x,int y)
{
    int cou=1,pro,round=0;
    cot[1]=cot[2]=cot[3]=cot[4]=0;
    for(int i=-3;i<4;i++)
    for(int j=-(3-abs(i));j<=3-(abs(i));j++)
    {
        if(x+i>0&&x+i<=n&&y+j>0&&y+j<=n) cot[a[x+i][y+j]]++;
    }
    cot[a[x][y]]--;
    cot[4]=pro=a[x][y];
    cot[4]=0;
    while(cou!=9)
    {
        int temp=(8*cou*cou-cot[4]+pro-1)/pro;
        round+=temp;cot[4]+=temp*pro;cou++;
        if(cot[3]!=0)
        {
            cot[3]--;pro+=3;
        }else
        if(cot[2]!=0)
        {
            cot[2]--;pro+=2;
        }else
        if(cot[1]!=0)
        {
            cot[1]--;pro+=1;
        }
    }
    ans[x][y]=round;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        minans=1e9;
        scanf("%d%d%d",&n,&x,&y);
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        {
            BfsAndCalc(i,j);
            if((abs(x-i)+abs(y-j)+1)/2+ans[i][j]<minans) minans=(abs(x-i)+abs(y-j)+1)/2+ans[i][j];
        }
        printf("%d
",minans);
    }
    return 0;
}