A.AKU NEGARAKU 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/A 来源：牛客网
1st Academy is an international leadership training academy based in Kuala Lumpur. Every year, the company trains thousands of people to be supplied to companies around the world. To be fair amongst all the trainees, the company will do the selection process using numbering system. The trainees will choose a number from 1 to N, and one number is not limited to only one trainee. The N represents the total number of companies that request trainees from the academy. A number, M, would be picked at random, and the selection starts with a trainee whose number is 1, and then in every M’th people after that, wrapping around to 1 after N, and ignoring trainees already selected. For example, if N = 15 and M = 6, trainees would be selected in the order: 6, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7. All the selected trainees except the last one (which is number 7) will be supplied to companies outside of Malaysia. However, Leong preferred to stay and work in Malaysia. To him, there is no better place other than Malaysia. He does not mind being located anywhere as long it is Malaysia. As a friend of him, you could help him to choose a number that will save him from being located outside.
题意： N个人，从第一个人开始，每次数到M的人出局，然后接着从1开始数，直到最后一个人，问最后那个人的位置。
思路： 经典的约瑟夫环问题，直接公式递归。
代码：
#include<iostream> using namespace std; int yuesefu(int n,int m) { if(n == 1) { return 0; } else { return (yuesefu(n-1,m) + m) % n; } } int main() { int a , b; while(cin >> a >> b) { if(a==0&&b==0) { break; } cout << yuesefu(a,b)+1 << endl; } return 0; }C.ELI’S CURIOUS MIND 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/C 来源：牛客网
Eli is a teenager who loves to study chemistry. She recently joined a chemistry research lab. Dr. Phil wants her to just play around with some chemicals and observe their reaction. Therefore, he gave her a one-row tray of test tubes with the different chemical inside of them and told her:
"Mix these chemical together anyhow that you like, but the you have to follow two rules:
Never make a mixture that has two chemicals that their tubes are next to each other. Keep adding more chemical to the mixture until it is not violating the new rule. "
For example, in the image you can see she was given 5 tubes and she is able to make 4 different mixture without violating the rule: {1,3,5},\ {2,4},\ {2,5},\ {1,4}\ .{1,3,5}, {2,4}, {2,5}, {1,4} .
But she cannot mix 1 and 3 only because she still can add 5 without violating the rules.
She is curious to know how many different mixtures she can make without violating the rule with any given number of tubes. That’s why she asks you write a code to calculate it for her.
题意： 给出N个试管，不相邻的试管可以综合到一起形成新的试剂，新的试剂是没有被使用过的，问最多可以产生多少种新的试剂。
思路： 第一印象是组合数，手推几个就发现，好像有些规律。因为他是隔着取，那当我新增试管的时候，假设该试管位置为k，对k-1试管是没有影响的，对k-2试管是有影响的，可以加到k-2试管的所有组合中，又因为k-2试管与k-3试管相邻没有交集，所以k试管也可以加到k-3试管的所有组合中。k-4和k-2是不相邻的，那么k-4的组合包括在k-2组合中，前面同理。所以，写出前几个式子之后，递推式为 a[i]=a[i-2]+a[i-3];
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read() { int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int a[MAXN]; struct rec { int x , y , z; }edge[MAXN]; int f[MAXN]; int n , m , res , t; bool operator<(rec a , rec b) { return a.z < b.z; } int get(int x) { if(x == f[x]) return x; return f[x] = get(f[x]); } int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int z = 1; a[1]=0; a[2]=0; a[3]=1; a[4]=2; a[5]=2; for(int i=6;i<=76;i++) a[i]=a[i-2]+a[i-3]; while(scanf("%d",&n)&&n) { printf("Case #%d: %lld\n",z,a[n-1]+a[n]); z++; } return 0; }D.EXPLORACE 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/D 来源：牛客网
CodingSchool is conducting an explorace to welcome new students. It is compulsory for each team to visit all check points (not necessarily following the sequence). At each check point, the team will have to complete a specific activity. Each team can plan a strategy on the sequence of check points to visit. The distance of each path is no more than 500 meters. Because they don’t want the new student to wander away and get lost, CodingSchool wants to put their committee on the paths and only allow the student to use path that have a committee. But CodingSchool only have a limited number of committee, so they don’t want to use all path. Shorter path is preferred because it use less committee. While at the same time, they must make sure that there exists a way to travel between every two checkpoints. Help CodingSchool by determining the minimum total distance of path that they must cover.
题意： 将所有点连接起来的最短路径是多长。
思路： 最小生成树裸题。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int a[MAXN]; struct rec { int x , y , z; }edge[MAXN]; int f[MAXN]; int n , m , res , t; bool operator<(rec a , rec b) { return a.z < b.z; } int get(int x) { if(x == f[x]) return x; return f[x] = get(f[x]); } int main() { std::ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> t; for(int z = 1 ; z <= t ; z++) { cin >> n >> m; res = 0; for(int i = 1 ; i <= m ; i++) { cin >> edge[i].x >> edge[i].y >> edge[i].z; } sort(edge+1,edge+1+m); for(int i = 1 ; i <= n ; i++) { f[i] = i; } for(int i = 1 ; i <= m ; i++) { int x = get(edge[i].x); int y = get(edge[i].y); if(x == y) continue; f[x] = y; res = res + edge[i].z; } printf("Case #%d: %d meters\n",z,res); } return 0; }E.MATRIX MULTIPLICATION CALCULATOR 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/E 来源：牛客网
Matrix multiplication is a basic tool of linear algebra, and has numerous applications in many areas of mathematics, as well as in applied mathematics, computer graphics, physics, and engineering.
We can only multiply two matrices if their dimensions are compatible, which means the number of columns in the first matrix is the same as the number of rows in the second matrix.
题意： 矩阵乘法，如果能相乘，输出结果；不能相乘，则输出undefined。
思路： 判断矩阵是否能相乘，能的话直接模拟相乘就行。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int a[100][100]; int b[25][25]; int c[25][25]; int t , k , n; int main() { int n1 , m1 , n2 , m2; int z = 0; while(cin >> n1 >> m1 >> n2 >> m2) { z++; if(n1==0&&n2==0&&m1==0&&m2==0) { break; } for(int i = 0 ; i < n1 ; i++) { for(int j = 0 ; j < m1 ; j++) { cin >> a[i][j]; } } for(int i = 0 ; i < n2 ; i++) { for(int j = 0 ; j < m2 ; j++) { cin >> b[i][j]; } } printf("Case #%d:\n",z); if(m1 != n2) cout << "undefined" << endl; else { CL(c,0); for(int i = 0 ; i < n1 ; i++) { for(int j = 0 ; j < m2 ; j++) { for(int x = 0 ; x < m1 ; x++) c[i][j]+=a[i][x]*b[x][j]; } } for(int i = 0 ; i < n1 ; i++) { cout << "|" << " "; for(int j = 0 ; j < m2 ; j++) { cout << c[i][j] << " "; } cout << "|" << endl; } } } return 0; }F.SUM OF SUB RECTANGLE AREAS 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/F 来源：牛客网
The following code snippet calculates the sum of the areas of all the sub rectangular grid in a rectangular grid from (0,0) to (N,N)\ .(N,N) . Find an efficient way to compute that. sum = 0 for r1 = 0 to N-1 for c1 = 0 to N-1 for r2 = r1+1 to N for c2 = r2+1 to N sum = sum + (r2-r1)*(c2-c1) print(sum)
题意： 计算（0，0）到（N,N）中，所有子矩形网格面积的总和。
思路： 数据范围很大，就想到了可能是道规律题，推了几个之后发现，就是x*(x+1)*(x+2)/6再平方。可惜菜的一批的我写python的过程中耗费了半个小时加三次WA。。
代码：
import math def fib(n): if n < 1: return (1, 0) f_m_1, f_m = fib(n >> 1) if n & 1: return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2 else: return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m) def main(): n = input() n = int(n) while n!=0 : n = n-1 x = input() x = int(x) # print(x) res = x*(x+1)*(x+2)//6 print(res*res) if __name__ == '__main__': main()J.VIRUS OUTBREAK 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/J 来源：牛客网
The State Veterinary Services Department recently reported an outbreak of a newly found cow disease. All cows found to have affected by the disease have since euthanized because of the risk to the industry. Number of affected cows increased to 21, 34 and reached 55 after eight, nine and ten hours respectively. You have been assigned by the authority to study the pattern of the outbreak and develop a program to predict the next number of affected cows so that the authorities could prepare and act accordingly.
题意： 8，9，10小时之后被感染的牛的数量是21，34，55，任意给出一个小时数，让你预测被感染的牛的数量是多少。
思路： 一看就是规律题，根据他的测试样例以及题目中的数据，手推了几个，发现就是我们熟悉的斐波那契数列，用python写一下即可。
代码：
import math def fib(n): if n < 1: return (1, 0) f_m_1, f_m = fib(n >> 1) if n & 1: return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2 else: return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m) def main(): n = input() n = int(n) while n != -1: res = fib(n) # print(res[1]) # print("Hour: n: res[1] cow(s) affected\n") print("Hour: ", end="") print(n, end="") print(": ", end="") print(res[1], end="") print(" cow(s) affected\n", end="") n = input() n = int(n) if __name__ == '__main__': main()菜的一批的我就只写了这么点题，下面的是补题： G.WAK SANI SATAY 题目： 链接：https://ac.nowcoder.com/acm/contest/7818/G 来源：牛客网
Wak Sani Satay is a humble stall located in Kajang and has been around since 1969. Many like Wak Sani’ s satay because the meat is juicy and tender, served with creamy and sweet kuah kacang, alongside with nasi impit, cucumber and onion slices.
Wak Sani usually calculates his net profit at the end of the week. The net profit is calculated by subtracting the cost from the gross profit. He can get 85 sticks of satay from 1 kg meat. The price for 3 types of satay are shown in Table 1. The price for nasi impit is RM0.80 each while cucumber and onion slices are free of charge.
The cost for making satay for each meat type in shown in Table 2. The cost of spices to marinate satay for every kilogram of meat is RM8.00 and the cost for each nasi impit is RM0.20 each.
题意： 计算价钱，直接模拟计算就行。
代码：
#include <bits/stdc++.h> using namespace std; signed main() { int n; int d=1; double x1=0.8-(7.5+8.0)/85.0; double x2=1.0-(24.0+8.0)/85.0; double x3=1.2-(32.0+8.0)/85.0; double x4=0.6; while(cin>>n) { if(n==0) break; double ans=0; for(int i=1;i<=n;i++) { double a,b,c,d; cin>>a>>b>>c>>d; ans+=a*x1+b*x2+c*x3+d*x4; } printf("Case #%d: RM%.2f\n",d++,ans); } }