It's All In The Mind

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1179 Accepted Submission(s): 586

Problem Description

Professor Zhang has a number sequence

a1,a2,...,an. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:

1. For every

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output the answer as an irreducible fraction "

Sample Input

   2 2 0 3 1 3 1  

Sample Output

   1/1 200/201  

Author

zimpha

Source

2016 Multi-University Training Contest 2

思路：

这题的意思就是说，它是一个递减数列，然后可能会给定你几个位置的数，让你求（a1+a2）/Σai 的最大值。对表达式进行变形，其实就是1/（1+(a3+…+an)/(a1+a2)）的最大值。所以只需要a1+a2最大，a3+…+ai最小就好了。那样的话就是把给定位置之前的数都赋值成给定位置的数值，最后一个给定位置之后的全都变为0。对a1、a2是不是给定位置进行分类讨论就好，很水的一题。

代码：

#include<iostream>
using namespace std;

int a[200];
int num[200];

int gcd(int a, int b)
{
    int r=a%b;
    if(r==0) return b;
    else return gcd(b,a%b);
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        int sum=0;
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            int xi,yi;
            cin>>xi>>yi;
            num[i]=xi;
            a[xi]=yi;
        }
        //后面的值都最小 
        
    
        
        if(num[0]==2) 
        {            
            for(int i=0;i<m-1;i++)//中间的 
            {
                for(int j=num[i]+1;j<num[i+1];j++)
                {
                     a[j]=a[num[i+1]];
                }
             }
             for(int j=num[m-1]+1;j<=n;j++)//最后的 
            {
                a[j]=0;
            }
            for(int i=3;i<num[0];i++) //3-中间 
            {
                a[i]=a[num[0]];
            }
            a[1]=100;     
        }
        
        else if(num[0]==1&&num[1]!=2) 
        {            
            for(int i=0;i<m-1;i++)//中间的 
            {
                for(int j=num[i]+1;j<num[i+1];j++)
                {
                     a[j]=a[num[i+1]];
                }
             }
             for(int j=num[m-1]+1;j<=n;j++)//最后的 
            {
                a[j]=0;
            }
            for(int i=3;i<num[0];i++) //3-中间 
            {
                a[i]=a[num[0]];
            }
            a[2]=a[1]; 
        }
        
        else if(num[0]==1&&num[1]==2) 
        {            
            for(int i=0;i<m-1;i++)//中间的 
            {
                for(int j=num[i]+1;j<num[i+1];j++)
                {
                     a[j]=a[num[i+1]];
                }
             }
             for(int j=num[m-1]+1;j<=n;j++)//最后的 
            {
                a[j]=0;
            }
            for(int i=3;i<num[0];i++) //3-中间 
            {
                a[i]=a[num[0]];
            }     
        }
        
        
        else
        {            
            for(int i=0;i<m-1;i++)//中间的 
            {
                for(int j=num[i]+1;j<num[i+1];j++)
                {
                     a[j]=a[num[i+1]];
                }
             }
             for(int j=num[m-1]+1;j<=n;j++)//最后的 
            {
                a[j]=0;
            }
            for(int i=3;i<num[0];i++) //3-中间 
            {
                a[i]=a[num[0]];
            }
            a[1]=a[2]=100;     
        }//前两个数都没有输入
        
        for(int i=1;i<=n;i++)
        {
            sum=sum+a[i];
        }
        
        int ll=a[1]+a[2];
        int l=gcd(ll,sum);
       // cout<<ll<<" "<<sum<<" "<<l<<endl;
       
        if(l-1==0)cout<<ll<<"/"<<sum<<endl; 
        else   cout<<(ll/l)<<"/"<<(sum/l)<<endl;
        
    }
}

HDOJ 5742 It's All In The Mind（数学变形）

It's All In The Mind