2018湖南多校第三场

2018 中南多校 第三场

A(2063): Good Versus Evil

SubmitPage    Summary    TimeLimit: 5 Sec     MemoryLimit: 512 Mb     Submitted: 85     Solved: 15    

Description

Middle Earth is about to go to war. The forces of goodwill have many battles with the forces of evil. Different races will certainlybe involved. Each race has a certain ‘worth’ when battling against others. Onthe side of good we have the following races, with their associated worth:

Hobbits - 1

Men - 2

Elves - 3

Dwarves - 3

Eagles - 4

Wizards - 10

On the side of evil we have:

Orcs - 1

Men - 2

Wargs - 2

Goblins - 2

Uruk Hai - 3

Trolls - 5

Wizards - 11

Although weather, location, supplies and valor play apart in any battle, if you add up the worth of the side of good and compare itwith the worth of the side of evil, the side with the larger worth will tend towin. Thus, given the count of each of the races on the side of good, followedby the count of each of the races on the side of evil, determine which sidewins.

Input

The first line of input will contain an integer greaterthan 0 signifying the number of battles to process. Information for each battlewill consist of two lines of data as follows. First, there will be a linecontaining the count of each race on the side of good. Each entry will beseparated by a single space. The values will be ordered as follows: Hobbits,Men, Elves, Dwarves, Eagles, Wizards. The next line will contain the count ofeach race on the side of evil in the following order: Orcs, Men, Wargs, Goblins,Uruk Hai, Trolls, Wizards. All values are non-negative integers. The resultingsum of the worth for each side will not exceed the limit of a 32-bit integer.

Output

For each battle, print “Battle” followed by a singlespace, followed by the battle number starting at 1, followed by a “:”, followedby a single space. Then print “Good triumphs over Evil” if good wins. Print“Evil eradicates all trace of Good” if evil wins. If there is a tie, then print“No victor on this battle field”.

Sample Input

Sample Output

这种简单题只要看懂题就能写出来，除了题面上是7个数的那个 权值 11 实际上是 10。

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

   int a[]= {1,2,3,3,4,10},b[]= {1,2,2,2,3,5,10};

   long long n,x;

   long sum1,sum2;

   cin>>n;

   for(int j=1; j<=n; j++)

    {

       sum1=sum2=0;

       for(int i=0; i<6; i++)

       {

           cin>>x;

           sum1+=x*a[i];

       }

       for(int i=0; i<7; i++)

       {

           cin>>x;

           sum2+=x*b[i];

       }

       printf("Battle %d: ",j);

       if(sum1>sum2)

       {

           cout<<"Good triumphs over Evil\n";

       }

        else if(sum1<sum2)

       {

           cout<<"Evil eradicates all trace of Good\n";

       }

       else

       {

           cout<<"No victor on this battle field\n";

       }

    }

   return 0;

}

B(2064): Magic Multiple

SubmitPage    Summary    TimeLimit: 5 Sec     MemoryLimit: 512 Mb     Submitted: 28     Solved: 18    

Description

The Elvish races of Middle Earth believed that certainnumbers were more significant than others. When using a particular quantity nof metal to forge a particular sword, they believed that sword would be mostpowerful if the thickness k were chosen according to the following rule: Givena nonnegative integer n, what is the smallest k such that the decimalrepresentations of the integers in the sequence: n, 2n, 3n, 4n, 5n, ..., kncontain all ten digits (0 through 9) at least once? Lord Elrond of Rivendell hascommissioned you with the task to develop an algorithm to find the optimalthickness (k) for any given quantity of metal (n).

Input

Input will consist of a single integer n per line. Theend of input will be signaled by end of file. The input integer will be between1 and 200,000,000, inclusive.

Output

The output will consist of a single integer per line,indicating the value of k needed such that every digit from 0 through 9 is seenat least once.

Sample Input

Sample Output

一个数的1 到 K倍中 0-9全部出现过，暴力K倍就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int a[10];

int l;

void check(long long x)

{

   while(x>0)

    {

       if(a[x%10]==0)

       {

           l++;

           a[x%10]=1;

       }

       x/=10;

    }

}

 

int main()

{

 

   long long n;

   long sum1,sum2;

   while (cin>>n)

    {

       l=0;

       memset(a,0,sizeof(a));

       int i=1;

       for (; l!=10; i++)

       {

           check(i*n);

       }

       cout<<i-1<<endl;

    }

   return 0;

}

Description

Saruman’s army of orcs andother dark minions continuously mine and harvest lumber out of the landsurrounding his mighty tower for N continuous days. On day number i, Sarumaneither chooses to spend resources on mining coal and harvesting more lumber, oron raising the level (i.e., height) of his tower. He levels up his tower by oneunit only on days where the binary representation of i contains a total numberof 1’s that is an exact multiple of 3. Assume that the initial level of histower on day 0 is zero. For example, Saruman will level up his tower on day 7(binary 111), next on day 11 (binary 1011) and then day 13, day 14, day 19, andso on. Saruman would like to forecast the level of his tower after N days. Canyou write a program to help?

Input

The input file will containmultiple input test cases, each on a single line. Each test case consists of apositive integer N < 1016, as described above. The input ends on end offile.

Output

For each test case, outputone line: “Day N: Level = L”, where N is the input N, and L is the number oflevels after N days.

Sample Input

2

19

64

Sample Output

Day 2: Level = 0

Day 19: Level = 5

Day 64: Level = 21

这一题就是从2进制 第一个找，一个个往下找，找其中  1 的个数是3的倍数就行了。

还有一种本身就是 3的倍数要额外加一前面只是处理所有比N小的数。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int l;

long long gcd(long long a,long long b)

{

   return (b==0)?a:gcd(b,a%b);

}

long long C(long long n,long long m)

{

   long long x=1,y=1;

   if(n-m<m)m=n-m;

   for(int i=0; i<m; i++)

    {

       x*=(n-i);

       y*=1+i;

       int t=gcd(x,y);

       x/=t;

       y/=t;

    }

   return x/y;

}

 

int main()

{

   int a[1000];

   long long n,k,sum;

   while (cin>>n)

    {

       sum=0;

       k=n;

       long long  l=1,t=0;

       while(n>0)

       {

           a[l++]=(n&1);

           n>>=1;

       }

 

       for(int i=l-1; i>0; i--)

       {

           if(a[i])                        //如果当前位为1

           {

                for(int j=3; j-t<=i-1;j+=3)        //当前位数减1,还能找出是3的倍数个 1

                   if(j-t>=0)sum+=C(i-1,j-t);

                t++;

           }

       }

       if(t>0&&t%3==0)sum+=1;                  //处理本身就是3的倍数情况。

       printf("Day %lld: Level = %lld\n",k,sum);

    }

   return 0;

}

H(2070): Seating Chart

SubmitPage    Summary    TimeLimit: 10 Sec     MemoryLimit: 512 Mb     Submitted: 41     Solved: 15    

Description

Bilbo’s birthday is coming up, and Frodo and Sam are incharge of all the party planning! They have invited all the hobbits of MiddleEarth to the party, and everyone will be sitting in a single row at anextremely long dining table. However, due to poor communication, Frodo and Samhave each independently put together a seating chart for all the hobbits at thedining table. Help Frodo and Sam find out how similar their seating charts areby counting the total number of distinct pairs of hobbits who appear indifferent orders in the two charts.

Input

The input filewill contain multiple test cases. Each test case begins with a single linecontaining an integer N(1≤N≤100,000)N(1≤N≤100,000)indicating thenumber of hobbits. The next two lines represent Frodo’s and Sam’s seatingcharts, respectively. Each seating chart is specified as a single line of Nunique alphabetical strings; the set of strings in each line are guaranteed tobe identical. The end-of-input is denoted by a line containing the number 0.

Output

For each input test case, output a single integerdenoting, out of the N choose 2 distinct pairs of hobbits, how many pairsappear in different orders in Frodo’s and Sam’s seating arrangements.

Sample Input

Sample Output

这一题就是一道求逆序数，逆序数怎么求就自己找模板吧，另外这个题超了int 要用longlong。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

const int maxn=1e6+5;

int a[maxn];

map<string,int>m;

long long n=0;//全局变量，用于统计逆序对数

void merge(int a[],int first,int mid,intlast)

{

   int *temp = new int[last-first+1];//临时数组，用于临时存放比较后的数字

   int i=first,j=mid+1,k=0;

   while(i<=mid&&j<=last)//遍历比较左右两个部分

    {

       if(a[i]<=a[j])

           temp[k++] = a[i++]; //左半部分元素小于右半部分的元素，将左边该元素存入临时数组

       else

       {

           temp[k++] = a[j++];

           n=n+(mid-i+1);//统计左半边能和右半边该元素构成的逆序对数

       }

    }

   while(i<=mid)

       temp[k++]=a[i++];

   while(j<=last)

       temp[k++]=a[j++];

   for(i=0; i < k; i++)

       a[first + i] = temp[i];//从临时数组取出放回原数组

}

void mergesort(int a[],int first,int last)

{

   if(first < last)

    {

       int mid = (first+last)/2;

       mergesort(a,first,mid);//递归排序左半部分

       mergesort(a,mid+1,last);//递归排序右半部分

       merge(a,first,mid,last);//将处理后的两个部分合并

    }

}

int main()

{

   int N;

   string k;

   while (cin>>N&&N)

    {

       m.clear();

       for(int i=0;i<N;i++)

       {

           cin>>k;

           m[k]=i;

       }

       for(int i=0;i<N;i++)

       {

           cin>>k;

           a[i]=m[k];

       }

    mergesort(a,0,N-1);

    cout<<n<<endl;

    n=0;

    }

   return 0;

}

J(2072): Temple Build

SubmitPage    Summary    TimeLimit: 10 Sec     MemoryLimit: 512 Mb     Submitted: 8     Solved: 1    

Description

The Dwarves of Middle Earth are renowned for theirdelving and smithy ability, but they are also master builders. During the timeof the dragons, the dwarves found that above ground the buildings that weremost resistant to attack were truncated square pyramids (a square pyramid thatdoes not go all the way up to a point, but instead has a flat square on top).The dwarves knew what the ideal building shape should be based on the heightthey wanted and the size of the square base at the top and bottom. Theytypically had three different sizes of cubic bricks with which to work. Theirgoal was to maximize the volume of such a building based on the followingrules:

The building is constructed of layers; each layer is asingle square of bricks of a single size. No part of any brick may extend outfrom the ideal shape, either to the sides or at the top. The resultingstructure will have jagged sides and may be shorter than the ideal shape, butit must fit completely within the ideal design. The picture at the right is avertical cross section of one such tower. There is no limit on how many bricksof each type can be used.

Input

Each line of input will contain six entries, eachseparated by a single space. The entries represent the ideal temple height, thesize of the square base at the bottom, the size of the square base at the top(all three as non-negative integers less than or equal to one million), thenthree sizes of cubic bricks (all three as non-negative integers less than orequal to ten thousand). Input is terminated upon reaching end of file.

Output

For each line of input, output the maximum possiblevolume based on the given rules, one output per line.

Sample Input

Sample Output

这一题就是一个，dp，dp[0]=0.dp[i]=max(dp[i-a[j]]+V[a[j]])(0<=j<3);

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<algorithm>

#include<cmath>

 

using namespace std;

const int maxn=1e7+5;

long long dp[maxn];

int main()

{

   long long h,d,t,a[3],ans;

   while(cin>>h>>d>>t>>a[0]>>a[1]>>a[2])

    {

       ans=0;

       memset(dp,-1,sizeof(dp));

       dp[0]=0;

       for(int i=0;i<=h;i++)

       {

           if(dp[i]!=-1)

           {

                for(int j=0;j<3;j++)

                {

                    if(i+a[j]<=h)

                    {

                        doubleb=1.0*d-1.0*(i+a[j])/h*(d-t);

                        int cnt=floor(b/a[j]);

                        long longv=cnt*cnt*pow(a[j],3);

                       if(dp[i+a[j]]==-1)dp[i+a[j]]=dp[i]+v;

                        elsedp[i+a[j]]=max(dp[i+a[j]],dp[i]+v);       // 我是从一个状态跳所有它可以跳到的状态。

                       ans=max(ans,dp[i+a[j]]);

                    }

                }

            }

       }

       cout<<ans<<endl;

    }

   return 0;

}

L(2074): Tongues

SubmitPage    Summary    TimeLimit: 5 Sec     MemoryLimit: 512 Mb     Submitted: 44     Solved: 18    

Description

Gandalf’s writings have long been available for study,but no one has yet figured out what language they are written in. Recently, dueto programming work by a hacker known only by the code name ROT13, it has beendiscovered that Gandalf used nothing but a simple letter substitution scheme,and further, that it is its own inverse—the same operation scrambles themessage as unscrambles it. This operation is performed by replacing vowels inthe sequence (a i y e o u) with the vowel three advanced, cyclicly, whilepreserving case (i.e., lower or upper). Similarly, consonants are replaced fromthe sequence (b k x z n h d c w g p v j q t s r l m f) by advancing tenletters. So for instance the phrase One ring to rule them all. translates toIta dotf ni dyca nsaw ecc. The fascinating thing about this transformation isthat the resulting language yields pronounceable words. For this problem, youwill write code to translate Gandalf’s manuscripts into plain text.

Input

The input file will contain multiple test cases. Eachtest case consists of a single line containing up to 100 characters,representing some text written by Gandalf. All characters will be plain ASCII,in the range space (32) to tilde (126), plus a newline terminating each line.The end of the input is denoted by the end-of-file.

Output

For each input test case, print its translation intoplaintext. The output should contain exactly the same number of lines andcharacters as the input.

Sample Input

Sample Output

字符串替换，XJB暴力就行,就是耗神。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<algorithm>

#include<cmath>

 

using namespace std;

const int maxn=1e2+5;

char s[maxn];

int main()

{

//b k x z n h d c w g   //p v j q t s r l m f

   char c1[]={"bkxznhdcwg"};

   char c2[]={"pvjqtsrlmf"};

   char a[500]={0};

   for(int i=0;i<strlen(c1);i++)

    {

       a[c1[i]]=c2[i];

       a[c1[i]-('a'-'A')]=c2[i]-('a'-'A');

    }

   for(int i=0;i<strlen(c1);i++)

    {

       a[c2[i]]=c1[i];

       a[c2[i]-('a'-'A')]=c1[i]-('a'-'A');

    }

   strcpy(c1,"aiy");

   strcpy(c2,"eou");

   for(int i=0;i<strlen(c1);i++)

    {

       a[c1[i]]=c2[i];

       a[c1[i]-('a'-'A')]=c2[i]-('a'-'A');

    }

   for(int i=0;i<strlen(c1);i++)

    {

       a[c2[i]]=c1[i];

       a[c2[i]-('a'-'A')]=c1[i]-('a'-'A');

    }

   while(~scanf("%c",&s[0]))

    {

       int i=0;

       while(s[i++]!='\n')

       {

           scanf("%c",&s[i]);

       }

        i=0;

       do

       {

           if(a[s[i]]==0)

           {

                printf("%c",s[i]);

           }

           else printf("%c",a[s[i]]);

       }while(s[i++]!='\n');

    }

 

   return 0;

}