# 【 题集 】 浙江省13、14年 ACM竞赛 水题

### A

Description

Calem and Serena are pokemon masters. One day they decided to have a pokemon battle practice before Pokemon World Championships. Each of them has some pokemons in each's team. To make the battle more interesting, they decided to use a special rule to determine the winner: the team with heavier total weight will win the battle!

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N and M (1 <= N, M <= 6), which describes that Calem has N pokemons andSerena has M pokemons.

The second line contains N integers indicating the weight of Calem's pokemons. The third line containsM integers indicating the weight of Serena's pokemons. All pokemons' weight are in the range of [1, 2094] pounds.

Output

For each test case, output "Calem" if Calem's team will win the battle, or "Serena" ifSerena's team will win. If the two team have the same total weight, output "Draw" instead.

Sample Input

```1
6 6
13 220 199 188 269 1014
101 176 130 220 881 396
```

Sample Output

```Serena
```

比较大小，输出谁大、

```#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
int t, h;
while(~scanf("%d",&h))
{
while(h --)
{
int sum1 = 0;
int sum2 = 0;
int n, m;
scanf("%d%d",&n,&m);
for(int i = 0; i < n; i ++)
{
scanf("%d",&t);
sum1 += t;
}
for(int i = 0; i < m; i ++)
{
scanf("%d",&t);
sum2 += t;
}
if(sum1 > sum2)
printf("Calem\n");
else if(sum2 > sum1)
printf("Serena\n");
else
printf("Draw\n");
}
}
}```

### B

Description

As we all know, Coach Gao is a talented chef, because he is able to cookM dishes in the same time. Tonight he is going to have a hearty dinner with his girlfriend at his home. Of course,Coach Gao is going to cook all dishes himself, in order to show off his genius cooking skill to his girlfriend.

To make full use of his genius in cooking, Coach Gao decides to prepareN dishes for the dinner. The i-th dish contains Ai steps. The steps of a dish should be finished sequentially. In each minute of the cooking,Coach Gao can choose at most M different dishes and finish one step for each dish chosen.

Coach Gao wants to know the least time he needs to prepare the dinner.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N and M (1 <= N, M <= 40000). The second line contains N integers Ai (1 <= Ai <= 40000).

Output

For each test case, output the least time (in minute) to finish all dishes.

Sample Input

```2
3 2
2 2 2
10 6
1 2 3 4 5 6 7 8 9 10
```

Sample Output

```3
10
```

```#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
int T;
cin >> T;
while(T --)
{
int n, m;
int sum = 0;
int maxn = 0;
int ans;
cin>>n>>m;
int temp;
for(int i = 0; i < n; i ++)
{
scanf("%d",&temp);
maxn = max(maxn, temp);
sum += temp;
}

ans = sum / m;
if(sum % m != 0)
{
ans++;
}
ans = max(ans, maxn);
cout << ans << endl;
}
}```

### C

Description

For security issues, Marjar University has an access control system for each dormitory building.The system requires the students to use their personal identification cards to open the gate if they want to enter the building.

The gate will then remain unlocked for L seconds. For example L = 15, if a student came to the dormitory at 17:00:00 (in the format of HH:MM:SS) and used his card to open the gate. Any other students who come to the dormitory between [17:00:00, 17:00:15) can enter the building without authentication. If there is another student comes to the dorm at 17:00:15 or later, he must take out his card to unlock the gate again.

There are N students need to enter the dormitory. You are given the time they come to the gate. These lazy students will not use their cards unless necessary. Please find out the students who need to do so.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N (1 <= N <= 20000) andL (1 <= L <= 3600). The next N lines, each line is a unique time between [00:00:00, 24:00:00) on the same day.

Output

For each test case, output two lines. The first line is the number of students who need to use the card to open the gate. The second line the the index (1-based) of these students in ascending order, separated by a space.

Sample Input

```3
2 1
12:30:00
12:30:01
5 15
17:00:00
17:00:15
17:00:06
17:01:00
17:00:14
3 5
12:00:09
12:00:05
12:00:00
```

Sample Output

```2
1 2
3
1 2 4
2
2 3
```

简单模拟，按时间排序，遍历，时间差小于输入的即可， 可是我一直错！！！ 不知为啥、、 下面是WA 的代码， 不想再去看了、、

```#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

struct node
{
int hour, minu, sec;
int aa;
}nod;

int vis;

bool cmp(node a, node b)
{
if(a.hour > b.hour)
return true;
if(a.hour < b.hour)
return false;
if(a.minu < b.minu)
return true;
if(a.minu > b.minu)
return false;
if(a.sec < b.sec)
return true;
if(a.sec > b.sec)
return false;
return false;
}

int main()
{
int t;
int n, m;
while(~scanf("%d",&t))
{
while(t --)
{
memset(vis, 0, sizeof(vis));
scanf("%d%d",&n, &m);
for(int i = 0; i < n; i ++)
{
scanf("%d:%d:%d",&nod[i].hour, &nod[i].minu, &nod[i].sec);
nod[i].aa= i + 1;
}
sort(nod, nod + n, cmp);
int cnt = 0;
vis[cnt ++] = nod.aa;
int a = nod.hour;
int b = nod.minu;
int c = nod.sec;
/*for(int i = 0; i < n; i ++)
{
printf("%d %d %d\n",nod[i].hour, nod[i].minu, nod[i].sec);
}*/
for(int i = 1; i < n; i ++)
{
int ttmp = abs((nod[i].hour - a) * 3600 + (nod[i].minu - b) * 60 + (nod[i].sec - c));
if (ttmp >= m)
{
a = nod[i].hour;
b = nod[i].minu;
c = nod[i].sec;
vis[cnt ++] = nod[i].aa;
}
}
printf("%d\n",cnt);
int fff = 1;
sort(vis, vis + cnt);
for(int i = 0; i < cnt; i ++)
{
if(fff)
printf("%d", vis[i]);
else
printf(" %d",vis[i]);
fff = 0;
}
printf("\n");
}
}
}```

### D

Description

The balance was the first mass measuring instrument invented. In its traditional form, it consists of a pivoted horizontal lever of equal length arms, called the beam, with a weighing pan, also called scale, suspended from each arm (which is the origin of the originally plural term "scales" for a weighing instrument). The unknown mass is placed in one pan, and standard masses are added to this or the other pan until the beam is as close to equilibrium as possible. The standard weights used with balances are usually labeled in mass units, which are positive integers.

With some standard weights, we can measure several special masses object exactly, whose weight are also positive integers in mass units. For example, with two standard weights1 and 5, we can measure the object with mass 1, 4, 5 or 6 exactly.

In the beginning of this problem, there are 2 standard weights, which masses arex and y. You have to choose a standard weight to break it into 2 parts, whose weights are also positive integers in mass units. We assume that there is no mass lost. For example, the origin standard weights are4 and 9, if you break the second one into 4 and 5, you could measure 7 special masses, which are 1, 3, 4, 5, 8, 9, 13. While if you break the first one into1 and 3, you could measure 13 special masses, which are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13! Your task is to find out the maximum number of possible special masses.

Input

There are multiple test cases. The first line of input is an integer T < 500 indicating the number of test cases. Each test case contains 2 integersx and y. 2 ≤ x, y ≤ 100

Output

For each test case, output the maximum number of possible special masses.

Sample Input

```2
4 9
10 10
```

Sample Output

```13
9
```

有一个物品可以拆开，然后问最多可以称出多少质量， 一开始我以为有一个为1， 就是两个数之和，不是全为1，大的拆分成1和manx - 1， 结果错了、其实数据挺小的，用暴力就可以过了， 可是比赛的时候， 真的敢用暴力么。。！！

```#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;

bool vis; //避免重复、

int f(int x,int y,int z)
{
memset(vis, 0, sizeof(vis));
int count = 0;
int s;
s=x;
s=y;
s=z;
s=x+y ;
s=x+z;
s=y+z;
s=x-y;
s=y-z;
s=x-z;
s=y-x;
s=z-x;
s=z-y;
s=x-y-z;
s=x-y+z;
s=y-x-z;
s=y-x+z;
s=y-z+x;
s=z-x+y;
s=z-x-y;
s=x+y+z;
for(int i = 0; i < 20; i ++)
{
if(s[i] > 0 && !vis[s[i]])
{
count ++;
vis[s[i]] = 1;
}

}
return count;
}

int main()
{
int t, a, b;
int temp, maxn, sum;
scanf("%d",&t);
while(t --)
{
// memset(vis, 0, sizeof(vis));
maxn = 0;
scanf("%d%d",&a,&b);
for(int i = 1; i < a/2 + 1; i ++)
{
temp = a - i ;
sum = f(i, temp, b);
maxn = max(maxn, sum);
}
for(int i = 1; i < b/2 + 1; i ++)
{
temp = b - i;
sum = f(a, i, temp);
maxn = max(maxn, sum);
}
printf("%d\n",maxn);
}
return 0 ;
}```

### E

Description

MightyHorse is playing a music game called osu!. After playing for several months, MightyHorse discovered the way of calculating score inosu!:

1. While playing osu!, player need to click some circles following the rhythm. Each time a player clicks, it will have three different points: 300, 100 and 50, deciding by how clicking timing fits the music.

2. Calculating the score is quite simple. Each time player clicks and gets P points, the total score will add P, which should be calculated according to following formula:

P = Point * (Combo * 2 + 1)

Here Point is the point the player gets (300, 100 or 50) and Combo is the number of consecutive circles the player gets points previously - That means if the player doesn't miss any circle and clicks theith circle, Combo should be i - 1.

Recently MightyHorse meets a high-end osu! player. After watching his replay,MightyHorse finds that the game is very hard to play. But he is more interested in another problem: What's the maximum and minimum total score a player can get if he only knows the number of 300, 100 and 50 points the player gets in one play?

As the high-end player plays so well, we can assume that he won't miss any circle while playingosu!; Thus he can get at least 50 point for a circle.

Input

There are multiple test cases.

The first line of input is an integer T (1 ≤ T ≤ 100), indicating the number of test cases.

For each test case, there is only one line contains three integers: A (0 ≤A ≤ 500) - the number of 300 point he gets, B (0 ≤ B ≤ 500) - the number of 100 point he gets andC (0 ≤ C ≤ 500) - the number of 50 point he gets.

Output

For each test case, output a line contains two integers, describing the minimum and maximum total score the player can get.

Sample Input

```1
2 1 1
```

Sample Output

```2050 3950
```

简单模拟， 根据公式，要注意题意哦、

其实根据point从小到大，从大到小，来一遍就可以了

```#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

int t;
int a, b, c;

int main()
{
while(~scanf("%d",&t))
{
while(t --)
{
int sum1 = 0;
int sum2 = 0;
scanf("%d%d%d",&a,&b,&c);
for(int i = 1; i <= a; i ++)
{
sum1 += 300 * ((i - 1) * 2 + 1);
}
for(int i = a + 1; i <= a + b; i ++)
{
sum1 += 100 * ((i - 1) * 2 + 1);
}
for(int i = a + b + 1; i <= a + b + c; i ++)
{
sum1 += 50 * ((i - 1) * 2 + 1);
}
for(int i = 1; i <= c; i ++)
{
sum2 += 50 * ((i - 1) * 2 + 1);
}
for(int i = c + 1; i <= b + c; i ++)
{
sum2 += 100 * ((i - 1) * 2 + 1);
}
for(int i = b + c + 1; i <= a + b + c; i ++)
{
sum2 += 300 * ((i - 1) * 2 + 1);
}
printf("%d %d\n", sum1, sum2);
}
}
}```

### F

Description

There are N little kids sitting in a circle, each of them are carrying some java beans in their hand. Their teacher want to selectM kids who seated in M consecutive seats and collect java beans from them.

The teacher knows the number of java beans each kids has, now she wants to know the maximum number of java beans she can get fromM consecutively seated kids. Can you help her?

Input

There are multiple test cases. The first line of input is an integer T indicating the number of test cases.

For each test case, the first line contains two integers N (1 ≤ N ≤ 200) andM (1 ≤ MN). Here N and M are defined in above description. The second line of each test case containsN integers Ci (1 ≤ Ci ≤ 1000) indicating number of java beans theith kid have.

Output

For each test case, output the corresponding maximum java beans the teacher can collect.

Sample Input

```2
5 2
7 3 1 3 9
6 6
13 28 12 10 20 75```

Sample Output

```16
158```

就是求最大连续和，而且是有限制个数的，所以只要2倍的 输入长度即可，数据不是很大、

```#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

int t;
int n, m;
int tt;

int main()
{
while(~scanf("%d",&t))
{
while(t --)
{
memset(tt, 0, sizeof(tt));
scanf("%d%d",&n, &m);
for(int i = 0; i < n; i ++)
{
scanf("%d",&tt[i]);
tt[n + i] = tt[i];
}
int maxn = 0;
for(int i = 0; i < n; i ++)
{
int sum = 0;
for(int j = i; j < i + m; j ++)
{
sum += tt[j];
}
maxn = max(sum, maxn);
}
printf("%d\n", maxn);
}
}
}```

### G

Description

The vast power system is the most complicated man-made system and the greatest engineering innovation in the 20th century. The following diagram shows a typical 14 bus power system. In real world, the power system may contains hundreds of buses and thousands of transmission lines. Network topology analysis had long been a hot topic in the research of power system. And network density is one key index representing the robustness of power system. And you are asked to implement a procedure to calculate the network density of power system.

The network density is defined as the ratio between number of transmission lines and the number of buses. Please note that if two or more transmission lines connecting the same pair of buses, only one would be counted in the topology analysis.

Input

The first line contains a single integer T (T ≤ 1000), indicating there areT cases in total.

Each case begins with two integers N and M (2 ≤ N, M ≤ 500) in the first line, representing the number of buses and the number of transmission lines in the power system. Each Bus would be numbered from 1 toN.

The second line contains the list of start bus number of the transmission lines, separated by spaces.

The third line contains the list of corresponding end bus number of the transmission lines, separated by spaces. The end bus number of the transmission lines would not be the same as the start bus number.

Output

Output the network density of the power system in a single line, as defined in above. The answer should round to 3 digits after decimal point.

Sample Input

```3
3 2
1 2
2 3
2 2
1 2
2 1
14 20
2 5 3 4 5 4 5 7 9 6 11 12 13 8 9 10 14 11 13 13
1 1 2 2 2 3 4 4 4 5 6 6 6 7 7 9 9 10 12 14
```

Sample Output

```0.667
0.500
1.429
```

```#include <stdio.h>
#include <string.h>

int s;

int main()
{
int n,m,sum,a,b;
double ans;
int t;
scanf("%d",&t);
while(t --)
{
scanf("%d%d",&n,&m);
memset(s,0,sizeof(s));
sum = 0;
for(int i = 1; i <= m; i ++)
scanf("%d",&a[i]);
for(int i = 1; i <= m; i ++)
scanf("%d",&b[i]);
for(int i = 1; i <= m; i ++)
{
if(!s[a[i]][b[i]])
sum ++;
s[a[i]][b[i]] = s[b[i]][a[i]] = 1;
}
printf("%.3lf\n",(double)sum/n);
}
return 0;
}```

### H

Description

Complete the ternary calculation.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is a string in the form of "number1operatoranumber2operatorbnumber3". Each operator will be one of {'+', '-' , '*', '/', '%'}, and each number will be an integer in [1, 1000].

Output

For each test case, output the answer.

Sample Input

```5
1 + 2 * 3
1 - 8 / 3
1 + 2 - 3
7 * 8 / 5
5 - 8 % 3
```

Sample Output

```7
-1
0
11
3
```

#### Note

The calculation "A % B" means taking the remainder of A divided by B, and "A / B" means taking the quotient.

简单模拟， 只有三个数字和 两个运算符。根据小学的数学来，就可以了

```#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
int a,b,c,n;
char d,e;
while(~scanf("%d",&n))
{
while(n--)
{
scanf("%d %c %d %c %d",&a,&d,&b,&e,&c);
int sum=0;
if(d=='+'&&e=='+')
{
sum=a+b+c;
printf("%d\n",sum);
}
else if(d=='+'&&e=='-')
{
sum=a+b-c;
printf("%d\n",sum);
}
else if(d=='+'&&e=='*')
{
sum=a+b*c;
printf("%d\n",sum);
}
else if(d=='+'&&e=='/')
{
sum=a+b/c;
printf("%d\n",sum);
}
else if(d=='+'&&e=='%')
{
sum=a+b%c;
printf("%d\n",sum);
}
else if(d=='-'&&e=='+')
{
sum=a-b+c;
printf("%d\n",sum);
}
else if(d=='-'&&e=='-')
{
sum=a-b-c;
printf("%d\n",sum);
}
else if(d=='-'&&e=='*')
{
sum=a-b*c;
printf("%d\n",sum);
}
else if(d=='-'&&e=='/')
{
sum=a-b/c;
printf("%d\n",sum);
}
else if(d=='-'&&e=='%')
{
sum=a-b%c;
printf("%d\n",sum);
}
else if(d=='*'&&e=='+')
{
sum=a*b+c;
printf("%d\n",sum);
}
else if(d=='*'&&e=='-')
{
sum=a*b-c;
printf("%d\n",sum);
}
else if(d=='*'&&e=='*')
{
sum=a*b*c;
printf("%d\n",sum);
}
else if(d=='*'&&e=='/')
{
sum=a*b/c;
printf("%d\n",sum);
}
else if(d=='*'&&e=='%')
{
sum=a*b%c;
printf("%d\n",sum);
}
else if(d=='/'&&e=='+')
{
sum=a/b+c;
printf("%d\n",sum);
}
else if(d=='/'&&e=='-')
{
sum=a/b-c;
printf("%d\n",sum);
}
else if(d=='/'&&e=='*')
{
sum=a/b*c;
printf("%d\n",sum);
}
else if(d=='/'&&e=='/')
{
sum=a/b/c;
printf("%d\n",sum);
}
else if(d=='/'&&e=='%')
{
sum=a/b%c;
printf("%d\n",sum);
}
else if(d=='%'&&e=='+')
{
sum=a%b+c;
printf("%d\n",sum);
}
else if(d=='%'&&e=='-')
{
sum=a%b-c;
printf("%d\n",sum);
}
else if(d=='%'&&e=='*')
{
sum=a%b*c;
printf("%d\n",sum);
}
else if(d=='%'&&e=='/')
{
sum=a%b/c;
printf("%d\n",sum);
}
else if(d=='%'&&e=='%')
{
sum=a%b%c;
printf("%d\n",sum);
}

}
}
return 0;
}```

### I

Description

It's Saturday today, what day is it after 11 + 22 + 33 + ... +NN days?

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is only one line containing one integer N (1 <= N <= 1000000000).

Output

For each test case, output one string indicating the day of week.

Sample Input

```2
1
2
```

Sample Output

```Sunday
Thursday
```

#### Hint

A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

规律题， 先找出周期即可 ， 没代码 - 。-

每一个你不满意的现在，都有一个你没有努力的曾经。
一个历史类的公众号，欢迎关注 