A
Thanks a lot for helping Harry Potter in finding the Sorcerer's Stone of Immortality in October. Did we not tell you that it was just an online game ? uhhh! now here is the real onsite task for Harry. You are given a magrid S ( a magic grid ) having R rows and C columns. Each cell in this magrid has either a Hungarian horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at a cell (i,j) takes away |S[i][j]| strength points from him, and a potion at a cell (i,j) increases Harry's strength by S[i][j]. If his strength drops to 0 or less at any point during his journey, Harry dies, and no magical stone can revive him.
Harry starts from the top-left corner cell (1,1) and the Sorcerer's Stone is in the bottom-right corner cell (R,C). From a cell (i,j), Harry can only move either one cell down or right i.e., to cell (i+1,j) or cell (i,j+1) and he can not move outside the magrid. Harry has used magic before starting his journey to determine which cell contains what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to start with to collect the Sorcerer's Stone. Please help him once again.
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of R C in the first line followed by the description of the grid in R lines, each containing C integers. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with S[i][j] < 0 contain dragons, others contain magic potions.
Output (STDOUT):
Output T lines, one for each case containing the minimum strength Harry should start with from the cell (1,1) to have a positive strength through out his journey to the cell (R,C).
Constraints:
1 ≤ T ≤ 5
2 ≤ R, C ≤ 500
-10^3 ≤ S[i][j] ≤ 10^3
S[1][1] = S[R][C] = 0
Sample Input:
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0
Sample Output:
2
1
2
Explanation:
Case 1 : If Harry starts with strength = 1 at cell (1,1), he cannot maintain a positive strength in any possible path. He needs at least strength = 2 initially.
Case 2 : Note that to start from (1,1) he needs at least strength = 1.
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdio> 5 #include <iomanip> 6 #include <string> 7 #include <algorithm> 8 #include <sstream> 9 #include <vector> 10 #include <set> 11 #include <map> 12 #include <queue> 13 14 using namespace std; 15 16 typedef long long LL; 17 const int INF = 0x3f3f3f3f; 18 const int MAXN = 100005; 19 const int MOD = 1e9+7; 20 21 #define Mem0(x) memset(x, 0, sizeof(x)) 22 #define MemM(x) memset(x, 0x3f, sizeof(x)) 23 24 //dp,从 i，j点到终点的最小需求分数 25 int a[505][505], dp[505][505]; 26 int main() 27 { 28 int T; 29 cin >> T; 30 while(T--) 31 { 32 Mem0(a); 33 Mem0(dp); 34 int n, m; 35 cin >> n >> m; 36 int i, j; 37 for(i = 0;i < n;++i) 38 for(j = 0;j < m;++j) 39 cin >> a[i][j]; 40 41 dp[n - 1][m - 1] = 1; 42 for(i = n - 2;i >= 0;--i) 43 dp[i][m - 1] = max(dp[i + 1][m - 1] - a[i][m - 1], 1); 44 for(i = m - 2;i >= 0;--i) 45 dp[n - 1][i] = max(dp[n - 1][i + 1] - a[n - 1][i], 1); 46 for(i = n - 2;i >= 0;--i) 47 for(j = m - 2;j >= 0;--j) 48 dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - a[i][j], 1); 49 cout << dp[0][0] << endl; 50 } 51 return 0; 52 }
---------------------------------------------------------------------------------------------------------------------------
B题是个坑！！！！
先把图画出来再遍历有多少个点就是过不了！！！
下面题目加AC码
Hogwarts is under attack by the Dark Lord, He-Who-Must-Not-Be-Named. To protect the students, Harry Potter must cast protective spells so that those who are protected by the spells cannot be attacked by the Dark Lord.
Harry has asked all the students to gather on the vast quidditch sports field so that he can cast his spells. The students are standing in a 2D plane at all grid points - these are the points (x,y) such that both x and y are integers (positive, negative or 0). Harry's spell can take the shapes of triangle, circle or square, and all who fall within that shape (including its boundaries) are protected.
Given the types of spells and the details regarding where Harry casts the spell, output the number of people saved by Harry's spells.
Input (STDIN):
The first line contains the number of test cases T. T test cases follow.
Each case contains an integer N on the first line, denoting the number of spells Harry casts. N lines follow, each containing the description of a spell.
If the ith spell is a triangle, then the line will be of the form "T x1 y1 x2 y2 x3 y3". Here, (x1,y1), (x2,y2) and (x3,y3) are the coordinates of the vertices of the triangle.
If the ith spell is a circle, then the line will be of the form "C x y r". Here, (x,y) is the center and r is the radius of the circle.
If the ith spell is a square, then the line will be of the form "S x y l". Here, (x,y) denotes the coordinates of the bottom-left corner of the square (the corner having the lowest x and y values) and l is the length of each side.
Output (STDOUT):
Output T lines, one for each test case, denoting the number of people Harry can save.
Constraints:
All numbers in the input are integers between 1 and 50, inclusive.
The areas of all geometric figures will be > 0.
Sample Input:
4
1
C 5 5 2
1
S 3 3 4
1
T 1 1 1 3 3 1
3
C 10 10 3
S 9 8 4
T 7 9 10 8 8 10
Sample Output:
13
25
6
34
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <iomanip> 7 #include <string> 8 #include <sstream> 9 #include <vector> 10 #include <set> 11 #include <queue> 12 #include <map> 13 14 using namespace std; 15 16 typedef long long LL; 17 const int MAXN = 1005; 18 const int MOD = 1e9 + 7; 19 const int INF = 0x3f3f3f3f; 20 21 #define Mem0(x) memset(x, 0, sizeof(x)) 22 #define MemM(x) memset(x, 0x3f, sizeof(x)) 23 24 int ans; 25 bool vis[205][205]; 26 int dis_squ(int x1, int y1, int x2, int y2) 27 { 28 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); 29 } 30 31 void C_judge(int x, int y, int r) 32 { 33 int i, j; 34 for(i = x - r;i <= x + r;++i) 35 for(j = y - r;j <= y + r;++j) 36 if(!vis[i][j] && dis_squ(i, j, x, y) <= r * r) 37 { 38 ans++; 39 vis[i][j] = 1; 40 } 41 } 42 43 void S_judge(int x, int y, int l) 44 { 45 for(int i = x;i <= x + l;++i) 46 for(int j = y;j <= y + l;++j) 47 { 48 if(!vis[i][j]) 49 { 50 ans++; 51 vis[i][j] = 1; 52 } 53 } 54 } 55 56 //* 叉乘 57 struct Point 58 { 59 int x, y; 60 }; 61 62 //BC * BA 63 int cal(Point a, Point b, Point c) 64 { 65 return (c.x - b.x) * (a.y - b.y) - (a.x - b.x) * (c.y - b.y); 66 } 67 68 void T_judge(int x1, int y1, int x2, int y2, int x3, int y3) 69 { 70 Point a, b, c; 71 a.x = x1, a.y = y1; 72 b.x = x2, b.y = y2; 73 c.x = x3, c.y = y3; 74 int xmi = min(x1, min(x2, x3)), xmx = max(x1, max(x2, x3)); 75 int ymi = min(y1, min(y2, y3)), ymx = max(y1, max(y2, y3)); 76 for(int i = xmi;i <= xmx;++i) 77 for(int j = ymi;j <= ymx;++j) 78 { 79 Point t; 80 t.x = i, t.y = j; 81 if(!vis[i][j] && cal(t, a, b) * cal(t, b, c) >= 0 && cal(t, b, c) * cal(t, c, a) >= 0) 82 { 83 ans++; 84 vis[i][j] = 1; 85 } 86 } 87 } 88 89 int main() 90 { 91 int T; 92 cin >> T; 93 while(T--) 94 { 95 Mem0(vis); 96 int n, x1, y1; 97 ans = 0; 98 string s; 99 cin >> n; 100 while(n--) 101 { 102 cin >> s >> x1 >> y1; 103 if(s[0] == 'C') 104 { 105 int r; 106 cin >> r; 107 C_judge(x1 + 100, y1 + 100, r); 108 } 109 else if(s[0] == 'S') 110 { 111 int l; 112 cin >> l; 113 S_judge(x1 + 100, y1 + 100, l); 114 } 115 else 116 { 117 int x2, y2, x3, y3; 118 cin >> x2 >> y2 >> x3 >> y3; 119 T_judge(x1 + 100, y1 + 100, x2 + 100, y2 + 100, x3 + 100, y3 + 100); 120 } 121 } 122 // int ans = 0; 123 // for(int i = 0;i < 200;++i) 124 // for(int j = 0;j < 200;++j) 125 // if(vis[i][j]) 126 // ans++; 127 // for(int i = 100;i < 120;++i) 128 // { 129 // for(int j = 100;j < 120;++j) 130 // cout << vis[i][j] << " "; 131 // cout << endl; 132 // } 133 cout << ans << endl; 134 } 135 return 0; 136 }
--------------------------------------------------------------------------------------------
D
You are the organizer of a Wizarding Duel tournament at Hogwarts. N players participated in the tournament and each player played with every other player exactly once, and each such game resulted in a winner and a loser (no drawn games). It is now time to declare the results. Each player's score is the number of games the player won. However, you realize that something possibly went wrong with the scoring system, and the scores that you have noted down might be wrong. In fact, the scores you have noted down could simply not be possible. For example, suppose there are 3 players and the scores that you noted are 0,0 and 2. Clearly this is not possible as the game between the first two players must have had a winner and thus both the players cannot have score 0.
While you have no way to figure out the correct scores of each player, you've decided to set the scores right by adjusting the scores of some players. The new set of scores should be possible to have arisen in the tournament, otherwise there would be ample proof that the scoring is wrong. However, making drastic changes might cause suspicion. So you've decided to adjust the scores so that the sum of the absolute differences between the old and the new scores of each player is minimized. In other words, if the original scores which you noted are a1,..,aN, you must change them to the series of possible scores b1,...bN such that the sum |ai - bi| is minimized.
Input (STDIN):
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by the set of scores which you have noted down: a1..aN.
Output (STDOUT):
Output T lines, one for each test case, containing the minimum sum of absolute values in order to make the scorecard a valid one.
Constraints:
1 <= T <= 20
2 <= N <= 50
0 <= ai <= 100
Sample Input:
2
3
0 0 2
5
5 3 2 1 4
Sample Output:
1
5
这题要注意一个点：前 i 项的和一定要 >= i * (i - 1) / 2，因为总的赢的场数不变，就是说后面的人能赢的最多场数是固定的
举个例子，0 0 2 4 4，这里第五个人赢了 4 场，那第四个人不可能赢 4 场
1 #include <iostream> 2 #include <string> 3 #include <cstring> 4 #include <cmath> 5 #include <sstream> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <vector> 10 #include <queue> 11 #include <iomanip> 12 13 using namespace std; 14 15 typedef long long LL; 16 const int INF = 0x3f3f3f3f; 17 const int MAXN = 1000005; 18 const int MOD = 1e9 + 7; 19 20 #define Mem0(x) memset(x, 0, sizeof(x)) 21 #define MemM(x) memset(x, 0x3f, sizeof(x)) 22 23 int main() 24 { 25 int T; 26 cin >> T; 27 int p[105]; 28 while(T--) 29 { 30 Mem0(p); 31 int n, i, j; 32 cin >> n; 33 int sum = 0, d = 0, ans = 0; 34 for(i = 0;i < n;++i) 35 cin >> p[i]; 36 sort(p, p + n); 37 //这里保证了每个人赢的场次在合理的范围内 38 for(i = 0;i < n;++i) 39 { 40 d += i, sum += p[i]; 41 if(sum < d) 42 { 43 ans += d - sum; 44 sum = d; 45 } 46 } 47 //不过如样例 2 ，去掉这一行会输出 0。这里保证了总场次合理 48 ans += sum - d; 49 cout << ans << endl; 50 } 51 return 0; 52 }
----------------------------------------------------------------------------------------------
H
Enough with this Harry Potter, please! What are we, twelve-year olds? Let's get our teeth into some real pumpkin pasties -- oops, programming problems!
Here we go!
Let's define the diversity of a list of numbers to be the difference between the largest and smallest number in the list.
For example, the diversity of the list (1, -1, 2, 7) = 7 - (-1) = 8.
A substring of a list is considered a non-empty sequence of contiguous numbers from the list. For example, for the list (1,3,7), the substrings are (1), (3), (7), (1,3), (3,7), (1,3,7). A subsequence of a list is defined to be a non-empty sequence of numbers obtained by deleting some elements from the list. For example, for the list (1,3,7), the subsequences are (1), (3), (7), (1,3), (3,7), (1,7), (1,3,7).
Given a list of length N find the number of substrings and subsequences in this list with the maximum diversity. If a substring/subsequence having maximum diversity occurs multiple times in the list, each of its occurences adds towards the answer. And tell Harry Potter your answer
Input (STDIN):
The first line contains T, the number of test cases. Then follow T test case blocks.
Each blocks starts with the first line containing the number N.
The second line contains a list of numbers in this list.
Output (STDOUT):
For each test case, output the number of substrings and the number of subsequences in this list with the maximum diversity.
Since the answers maybe very large, output them modulo 1000000007.
Constraints:
T <= 10
N <= 100,000
Each number in the list is between 1 and 100,000 inclusive.
Sample Input:
3
3
1 2 3
4
1 4 3 4
3
3 2 1
Sample Output:
1 2
3 6
1 2
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <cstring> 5 #include <cmath> 6 #include <sstream> 7 #include <algorithm> 8 #include <set> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <iomanip> 13 14 using namespace std; 15 16 typedef long long LL; 17 const int INF = 0x3f3f3f3f; 18 const int MAXN = 100005; 19 const int MOD = 1e9 + 7; 20 21 #define MemN(x) memset(x, -1, sizeof(x)) 22 #define Mem0(x) memset(x, 0, sizeof(x)) 23 #define MemM(x) memset(x, 0x3f, sizeof(x)) 24 25 //题目要算的是连续子串和子串 26 int main() 27 { 28 LL a[MAXN]; 29 a[0] = 1; 30 for(int i = 1;i < MAXN;++i) 31 a[i] = (a[i - 1] * 2) % MOD; 32 33 int T; 34 cin >> T; 35 while(T--) 36 { 37 int p[MAXN]; 38 int i, n, mi = INF, mx = 0; 39 cin >> n; 40 for(i = 0;i < n;++i) 41 { 42 cin >> p[i]; 43 mi = min(mi, p[i]); 44 mx = max(mx, p[i]); 45 } 46 if(mi == mx) 47 cout << ((n + 1) * n / 2) << " " << a[n] - 1 << endl; 48 else 49 { 50 int num_mi = 0, num_mx = 0; 51 int x = -1, y = -1; 52 LL ans1 = 0, ans2 = 0; 53 for(i = 0;i < n;++i) 54 { 55 if(p[i] == mi) 56 { 57 x = i; 58 num_mi++; 59 } 60 if(p[i] == mx) 61 { 62 y = i; 63 num_mx++; 64 } 65 //当最大值和最小值同时存在时计算 66 ans1 = (ans1 + min(x + 1, y + 1)) % MOD; 67 } 68 //容斥定理 69 //ans2 = 总子集 - 不包含最小值的子集 - 不包含最大值的子集 + 既没有最小值也没有最大值子集 70 //减去两个 a[i]， 最好加上 2 * MOD 71 ans2 = (a[n] - a[n - num_mi] - a[n - num_mx] + a[n - num_mi - num_mx] + 2 * MOD) % MOD; 72 cout << ans1 << " " << ans2 << endl; 73 } 74 } 75 return 0; 76 }
-----------------------------------------------------------------------------------------------
J
这题主要难点是判断一个点是之前就变化的还是现在才变化的
这里用 int vis[i][j] 标记计算变化的步数
The wizards and witches of Hogwarts School of Witchcraft found Prof. Binn's History of Magic lesson to be no less boring than you found your own history classes. Recently Binns has been droning on about Goblin wars, and which goblin civilization fought which group of centaurs where etc etc. The students of Hogwarts decided to use the new-fangled computer to figure out the outcome of all these wars instead of memorizing the results for their upcoming exams. Can you help them?
The magical world looks like a 2-D R*C grid. Initially there are many civilizations, each civilization occupying exactly one cell. A civilization is denoted by a lowercase letter in the grid. There are also certain cells that are uninhabitable (swamps, mountains, sinkholes etc.) - these cells are denoted by a '#' in the grid. All the other cells - to which the civilizations can move - are represented by a '.' in the grid.
A cell is said to be adjacent to another cell if they share the same edge - in other words, for a cell (x,y), cells (x-1, y), (x, y-1), (x+1, y), (x, y+1) are adjacent, provided they are within the boundaries of the grid. Every year each civilization will expand to all unoccupied adjacent cells. If it is already inhabited by some other civilization, it just leaves the cell alone. It is possible that two or more civilizations may move into an unoccupied cell at the same time - this will lead to a battle between the civilizations and the cell will be marked with a '*'. Note that the civilizations fighting in a particular cell do not try to expand from that cell, but will continue to expand from other cells, if possible.
Given the initial grid, output the final state of the grid after no further expansion by any civilization is possible.
Input (STDIN):
The first line contains T, the number of cases. This is followed by T test case blocks.
Each test case contains two integers, R, C.
This is followed by R lines containing a string of length C. The j-th letter in the i-th row describes the state of the cell in year 0.
Each cell is either a
1. '.' which represents an unoccupied cell
2. '#' which represents a cell that cannot be occupied
3. A civilization represented by a lowercase letter ('a' - 'z')
Output (STDOUT):
For each test case, print the final grid after no expansion is possible. Apart from the notations used in the input, use '*' to denote that a battle is being waged in that particular cell.
Print a blank line at the end of each case.
Constraints:
1 <= R, C <= 500
1 <= T <= 5
Sample Input:
5
3 5
#####
a...b
#####
3 4
####
a..b
####
3 3
#c#
a.b
#d#
3 3
#c#
...
a.b
3 5
.....
.#.#.
a...b
Sample Output:
#####
aa*bb
#####
####
aabb
####
#c#
a*b
#d#
#c#
acb
a*b
aa*bb
a#.#b
aa*bb
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iomanip> 6 #include <algorithm> 7 #include <stack> 8 #include <queue> 9 #include <string> 10 #include <vector> 11 #include <map> 12 #include <set> 13 14 using namespace std; 15 16 typedef long long LL; 17 const int INF = 0x3f3f3f3f; 18 const int MAXN = 105; 19 const int MOD = 1e9 + 7; 20 21 #define Mem0(x) memset(x, 0, sizeof(x)) 22 #define MemM(x) memset(x, 0x3f, sizeof(x)) 23 24 int vis[505][505], dis[][2] = {0, 1, 1, 0, 0, -1, -1, 0}; 25 char p[505][505]; 26 struct Point 27 { 28 int x, y; 29 char c; 30 }; 31 queue<Point> m; 32 33 void solve(int a, int b) 34 { 35 Point t; 36 int x, y, k, i, j; 37 while(!m.empty()) 38 { 39 x = m.front().x, y = m.front().y; 40 m.pop(); 41 if(p[x][y] == '*') 42 continue; 43 44 for(k = 0;k < 4;++k) 45 { 46 i = x + dis[k][0], j = y + dis[k][1]; 47 if(i < 0 || i > a || j < 0 || j > b) 48 continue; 49 if(p[i][j] == '#') 50 continue; 51 //这里可能此时i, j指向的值在后面变成 * 52 else if(p[i][j] == '.') 53 { 54 p[i][j] = p[x][y]; 55 t.x = i, t.y = j, t.c = p[i][j]; 56 m.push(t); 57 vis[i][j] = vis[x][y] + 1; 58 } 59 else if(vis[i][j] == vis[x][y] + 1 && p[i][j] != p[x][y]) 60 p[i][j] = '*'; 61 } 62 63 // cout << endl; 64 // for(int u = 0;u < a;++u) 65 // { 66 // for(int v = 0;v < b; ++v) 67 // cout << p[u][v]; 68 // cout << endl; 69 // } 70 } 71 } 72 73 int main() 74 { 75 int T; 76 cin >> T; 77 int a, b; 78 while(T--) 79 { 80 Mem0(vis); 81 Mem0(p); 82 while(!m.empty()) 83 m.pop(); 84 Point t; 85 cin >> a >> b; 86 for(int i = 0;i < a;++i) 87 { 88 getchar(); 89 for(int j = 0;j < b;++j) 90 { 91 cin >> p[i][j]; 92 if(p[i][j] >= 'a' && p[i][j] <= 'z') 93 { 94 vis[i][j] = 1; 95 t.x = i, t.y = j, t.c = p[i][j]; 96 m.push(t); 97 } 98 } 99 } 100 solve(a, b); 101 for(int i = 0;i < a;++i) 102 { 103 for(int j = 0;j < b;++j) 104 cout << p[i][j]; 105 cout << endl; 106 } 107 } 108 return 0; 109 }