Oj599: sum of two numbers 1
Title Description
Given an array from small to large and a target number t, find two numbers in it, make the sum of the two numbers equal to the target number, and output the position of the two numbers in the array.
input
The first line contains two integers n,t. (1≤n≤1000000,1≤t≤20000000)
The number of n in the next line is less than 10000000.
output
Output two numbers separated by spaces to represent the position (counting from zero), and the answer has a unique solution.
sample input
6 15 1 5 6 7 10 26
sample output
1 4
Data scale and agreement
Time limit: 1 s
Memory limit: 256 M
100% data guarantee 1 ≤ n ≤ 1000000
Idea:
Note: there is a large amount of data, and there is a risk of timeout when reading in with cin. scanf is used
Three methods:
1. Brute force solution: twolayer loop traversal will timeout, time complexity O(n^2)
2. Fix one number and find the other by dichotomy. Time complexity O(nlogn)
3. Hash table: fix one number and look up the other number from the hash table. Time complexity O(n), space complexity O(n)
4. Double finger Needling: time complexity O(n)
Code demonstration (double finger acupuncture)
#include<iostream> #include <cstdio> using namespace std; int n, t, num[1000005]; int main(int argc, char *grav[]) { scanf("%d%d", &n, &t); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } int l = 0, r = n  1; while (l < r) { if (num[l] + num[r] == t) { cout << l << " " << r << endl; return 0; } // If the number is less than the target, move the left pointer if (num[l] + num[r] < t) { l++; } else { r; } } cout << 1 << endl; return 0; }
Extension:
Sum of three numbers: fix one number, and the remaining two adopt the method of sum of two numbers. The time complexity is O(n^2)
Oj600: Young's matrix
Title Description
Given a twodimensional matrix with n rows and m columns and a target number t, the twodimensional matrix does not fall from left to right for each row (the number on the right is greater than or equal to the number on the left), and does not fall from top to bottom for each column (the number on the lower side is greater than or equal to the number on the upper side). Now find the target number t in the array and output the number of rows and columns where it is located.
Note: the data of this question has been updated, t has been changed to input at the end, and all submission records that do not meet the requirements have been deleted.
input
The first line contains two integers n, M. (1≤n,m≤3000)
Next, a twodimensional matrix, in which all numbers are less than 200000.
The last line is an integer t. (1≤t≤200000)
output
Output two numbers separated by spaces to represent the position (counting from the beginning). The answer has a unique solution.
sample input
3 4 1 2 3 4 5 6 15 20 7 10 20 25 15
sample output
2 3
Data scale and agreement
Time limit: 1 s
Memory limit: 256 M
100% data guarantee: 1 ≤ n,m ≤ 3000
Idea:
Time complexity is O(n + m)
The search number can be found from the lower left corner or the upper right corner.
 This problem is related to the sum of the two numbers, as shown in the figure below:
Code demonstration:
#include<iostream> #include <cstdio> using namespace std; int n, m, t, num[3005][3005]; int main(int argc, char *grav[]) { scanf("%d%d", &n, &m); // Save from point (1,1) for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &num[i][j]); } } // Find from the bottom left corner int x = n, y = 1; cin >> t; while (1) { if(num[x][y] == t) { printf("%d %d\n", x, y); return 0; } if (num[x][y] > t) { x; } else { y++; } } cout << 1 << endl; return 0; }
Oj479: Table Tennis
Title Description
Since taking office, Shalala, the current president of the International Table Tennis Federation, has been determined to implement a series of reforms to promote the popularity of table tennis in the world. Among them, the 11 point system reform has caused great controversy. Some players can only choose to retire because they can't adapt to the new rules. Hua Hua is one of them. After his retirement, he embarked on the research of table tennis in order to understand the different effects of 11 point system and 21 point system on players. Before carrying out his research, he first needs to analyze the statistical data of his competitions for many years, so he needs your help.
Huahua analyzed by the following methods: first, the victory or defeat of each ball in the game was listed in a table, and then the results of the two sides under the 11 point system and 21 point system were calculated respectively (up to the end of the record).
For example, there is a record (where W means Huahua gets a point and L means Huahua's opponent gets a point):
WWWWWWWWWWWWWWWWWWWWWWLW
Under the 11 point system, the result of the game at this time is that Huahua won 110 in the first set and 110 in the second set. The third set is under way. The current score is 11. Under the 21 point system, Huahua won 210 in the first set and is in the second set, with a score of 21. If a game has just begun, the score is 00. A game does not end until the difference is greater than or equal to 2.
Your program is to input a series of game information (WL form) and output the correct results.
input
Each input file contains several lines of strings, which are composed of uppercase W, L and E. Where EE indicates the end of the competition information, and the program should ignore all contents after E.
output
The output consists of two parts, each part has several lines, and each line corresponds to the score of a game (according to the input order of game information). The first part is the result under the 11 point system, and the second part is the result under the 21 point system. The two parts are separated by a blank line.
sample input
WWWWWWWWWWWWWWWWWWWW WWLWE
sample output
11:0 11:0 1:1 21:0 2:1
Data scale and agreement
Time limit: 1 s
Memory limit: 256 M
100% data guarantee up to 25 letters per line and up to 2500 lines
Idea:
First, determine the data range:
Code demonstration:
#include<iostream> #include <cmath> using namespace std; int a11[6000][2], a21[3000][2], ind1, ind2; void p() { for (int i = 0; i <= ind1; i++) { cout << a11[i][0] << ":" << a11[i][1] << endl; } cout << endl; for (int i = 0; i <= ind2; i++) { cout << a21[i][0] << ":" << a21[i][1] << endl; } } int main(int argc, char *grav[]) { char s[30]; while (cin >> s) { for (int i = 0; s[i]; i++) { if (s[i] == 'E') { p(); return 0; } if (s[i] == 'W') { a11[ind1][0]++; a21[ind2][0]++; } else { a11[ind1][1]++; a21[ind2][1]++; } if ((a11[ind1][0] >= 11  a11[ind1][1] >= 11) && abs(a11[ind1][0]  a11[ind1][1]) >= 2) { ind1++; } if ((a21[ind2][0] >= 21  a21[ind2][1] >= 21) && abs(a21[ind2][0]  a21[ind2][1]) >= 2) { ind2++; } } } return 0; }
oj481. Curling competition
Title Description:
In the curling game, a target point P and a specified positive integer r are given. After teams a and B throw curling 8 times in turn in each game, the game ends. At this time, the curler of that party is finally closest to the target point, and that party scores, while the other party does not score. If the distance between each top of the scoring party and the target point P is less than or equal to r, and the position is closer to the target point P than all the curlers of the other team, 1 point can be obtained.
The game can last up to 10 games. After the end of a game between the two sides, the lagging party can abstain, and the game will not go on at this time. Given the distance between each curler and the target point P and the positive integer r at the end of a game, please write a program to judge the score of each game between the two teams and the total score.
Input:
Line 1 is a positive integer r.
There are several lines (no more than 20) below, with 8 positive integers in each line;
The number J in the second line indicates the distance between the jth curler of Party A and the target point P at the end of the 11th game;
The number J in the third line indicates the distance between the j curler of Party B and the target point P at the end of the 11th game;
......
The jth number in line 2k indicates the distance between the jth curler of Party A and the target point P at the end of the kth game;
The jth number in line 2k+1 represents the distance between Party B's jth curler and the target point P at the end of the kth game;
If one party abstains halfway, the last line (even line) has only an integer − 1, indicating that the waiver occurs at this time;
Output:
Output several lines, two integers in each line, separated by a colon, indicating the score of Party A and Party B in each game (Party A scores first).
There are two integers in the last line, separated by a colon in the middle, indicating the final score of Party A and Party B in the game (Party A scores first).
Sample input:
8 5 20 18 19 3 15 13 3 20 2 17 12 5 18 10 11 20 3 4 1 2 11 9 2 1 15 19 9 8 14 11 10 15 2 10 1 19 14 3 18 15 17 21 19 24 32 19 26 1
Sample output:
0:1 0:0 3:0 3:1
Idea:
Draw a circle with the nearest point of the other party from the center of the circle as the radius. There are several balls of the other party in the circle. What points will the other party get.
Code implementation:
#include<iostream> #include <algorithm> using namespace std; int r, ans[15][2]; void p(int n) { int a1 = 0, a2 = 0; for (int i = 1; i < n; i++) { a1 += ans[i][0]; a2 += ans[i][1]; cout << ans[i][0] << ":" << ans[i][1] << endl; } cout << a1 << ":" << a2 << endl; } int main(int argc, char *grav[]) { cin >> r; for (int i = 1; i <= 10; i++) { int num1[10] = {0}; int num2[10] = {0}; // input data for (int j = 0; j < 8; j++) { cin >> num1[j]; // Conditions for withdrawal if (num1[j] == 1) { p(i); // Midway exit also needs to output results. i indicates the number of rounds return 0; } } for (int j = 0; j < 8; j++) { cin >> num2[j]; } sort(num1, num1 + 8); sort(num2, num2 + 8); if (num1[0] < num2[0]) { for (int j = 0; j < 8; j++) { // Judge whether the boundary conditions are met if (num1[j] > r  num1[j] >= num2[0]) break; ans[i][0]++; // Record the score of each time } } else { for (int j= 0; j < 8; j++) { if (num2[j] > r  num2[j] >= num1[0]) break; ans[i][1]++; } } } p(11); return 0; }
oj484. Columnar statistical chart
Title Description:
Give some strings with a total length of no more than 1000, count the number of uppercase letters, and output them according to the given sample format.
Input:
A pile of strings. Every two strings may be separated by spaces and newlines.
Output:
Refer to the sample output columnar statistical chart. Each * indicates one occurrence. Note that there should be no redundant spaces in each line.
Sample input:
ABC ABC.DEF()G GCC XY 354342aaaCaa aaaaaaaabcdbcd
Sample output:
* * * * * * * * * * * * * * * * A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Idea:
Open an array, count the number of occurrences of each character, and set the height value according to the maximum number of occurrences
Difficulty: printing
Code implementation:
#include<iostream> using namespace std; int num[130]; char str[1005]; int main(int argc, char *grav[]) { while (cin >> str) { for (int i = 0; str[i]; i++) { num[str[i]]++; } } int mmax = 0; // How many lines are there for (int i = 'A'; i <= 'Z'; i++) { mmax = max(mmax, num[i]); } for (int i = mmax; i > 0; i) { int ind = 'A'; for (int j = 'Z'; j > 'A'; j) { if (num[j] >= i) { ind = j; break; } } for (int j = 'A'; j <= ind; j++) { if (j != 'A') { cout << " "; } if (num[j] >= i) { cout << "*"; } else { cout << " "; } } cout << endl; } for (char i = 'A'; i <= 'Z'; i++) { if (i != 'A') { cout << " "; } cout << i; } cout << endl; return 0; }
oj485. Divide cards equally
Title Description:
There are N piles of cards, numbered 1, 2,..., N. There are several cards in each pile, but the total number of cards must be a multiple of N. You can take several cards from any pile and move them.
The card transfer rule is: the cards taken from the stack numbered 1 can only be moved to the stack numbered 2; Cards taken from the stack numbered N can only be moved to the stack numbered N − 1; Cards taken from other stacks can be moved to the adjacent left or right stack.
Now it is required to find a way to move with the least number of times to make the same number of cards on each pile.
For example, N=4, the number of 4 stacks of cards is:
① 9 ② 8 ③ 17 ④ 6
Move 3 times to achieve the purpose:
Take 4 cards from ③ to ④ (9,8,13,10)  > take 3 cards from ③ to ② (9,11,10,10)  > take 1 card from ② to ① (10,10,10).
Input:
The first line is an integer n. (1≤N≤100)
The second line contains N integers, A1,A2,..., An. (N stacks of cards, initial number of cards in each stack, 1 ≤ Ai ≤ 10000)
Output:
Outputs an integer representing the minimum number of moves when all heaps are equal.
Sample input:
4 9 8 17 6
Sample output:
3
Code implementation:
#include<iostream> using namespace std; int n, num[105], ans, sum, avg; int main(int argc, char *grav[]) { cin >> n; for (int i = 0; i < n; i++) { cin >> num[i]; sum += num[i]; } avg = sum / n; for (int i = 0; i < n  1; i++) { if (num[i] != avg) { ans++; num[i + 1] += num[i]  avg; num[i] = avg; } } cout << ans << endl; return 0; }
oj504. Deletion number
Title Description:
Enter a highprecision positive integer n (no more than 240 bits in length). After removing any s digits, the remaining digits will form a new positive integer according to the original leftright order. Now find a scheme to minimize the value of the new positive integer.
Input:
The first line is an integer n.
The second line is a positive integer s.
Output:
The output of a number represents the minimum value, and the leading zero of the number is ignored.
Sample input 1:
179566 4
Sample output 1:
15
Code demonstration:
#include<iostream> #include <string> using namespace std; string str; int n; int main(int argc, char *grav[]) { cin >> str >> n; for (int i = 0; i < n; i++) { int ind = str.size()  1; for (int j = 0; j < str.size()  1; j++) { if (str[j] > str[j + 1]) { ind = j; break; } } str.replace(ind, 1, ""); } int f = 0; for (int i = 0; i < str.size(); i++) { if (str[i] != '0') { f = 1; } if (f == 1) { cout << str[i]; } } cout << endl; return 0; }
oj505. Maximum integer
Title Description:
Now there are n positive integers. Connect them in a row to form the largest integer.
For example, there are now three integers 13312343, connected into a maximum integer of 34331213.
Input:
The first line is an integer n. (1≤n≤100000)
The second line contains n positive integers that do not exceed the int type range.
Output:
Outputs a number representing the largest integer of the composition.
Sample input:
3 121 12 96
Sample output:
9612121
Idea:

Read in as a string.

Sort strings, sort(s, s + n, cmp);

How to write cmp?
bool cmp(string a, string b) {return a + b > b + a;}
Code demonstration:
#include<iostream> #include <string> #include <algorithm> using namespace std; string s[100005]; int n; bool cmp(const string &a, const string &b) { return a + b > b + a; } int main(int argc, char *grav[]) { cin >> n; for (int i = 0; i < n; i++) { cin >> s[i]; } sort(s, s + n, cmp); for (int i = 0; i < n; i++) { cout << s[i]; } cout << endl; return 0; }
oj508. Two people cross the river
Title Description:
There are n people who want to cross a bridge at night. At any time, there can only be at most two people on the bridge, and you must carry a flashlight to cross the bridge. Now there is only one flashlight, so some order must be arranged so that the flashlight can be taken back to let more people cross the bridge. Everyone has a different time to cross the bridge. The time spent by two people crossing the bridge together is equal to that of the slower one. Now we ask everyone to cross the bridge in the shortest time.
Input:
The first line is an integer n. (1≤n≤1000)
In the next n lines, an integer in each line represents the bridge crossing time ti of the ith person. (1≤Ti≤100)
Output:
Output the shortest time for everyone to cross the bridge
Sample input:
4 1 5 2 10
Sample output:
17
Example description
Let 1 and 2 cross the bridge first, then let 1 come back, let 5 and 10 cross the bridge, and then let 2 come back and cross the bridge with 1. The time is 2 + 1 + 10 + 2 + 2 = 17.
Idea:
 First, sort everyone's time from small to large
 There are several situations as follows:
 n == 1 ,ans = num[0]
 n == 2 ,ans = num[1]
 n == 3 ,ans = num[2] + num[0] + num[1]
 n == 4  > n can be selected in two cases: 1. Flashlight block. 2. Cross the river quickly
1. Flashlight fast: slowest and fastest – > fastest – > second slowest and fastest – > fastest
num[i] + num[1] + num[i  1] + num[1]
2. Cross the river fast: fastest second fast – > fastest – > slowest second slow  > second fast
num[2] + num[1] + num[i] + num[2]
Code demonstration:
#include<iostream> #include <algorithm> using namespace std; int n, num[1005], ans; int main(int argc, char *grav[]) { cin >> n; for (int i = 1; i <= n; i++) { cin >> num[i]; } sort(num + 1, num + n + 1); for (int i = n; i > 0; i = 2) { if (i == 1) { ans += num[1]; break; } else if (i == 2) { ans += num[2]; } else if (i == 3) { ans += num[3] + num[1] + num[2]; break; } else { ans += min(num[i] + num[1] + num[i  1] + num[1], num[2] + num[1] + num[i] + num[2]); } } cout << ans << endl; return 0; }
oj513. Floor number
Title Description
Xiao Ming travels and lives in a hotel. The hotel has a cursed number t, which will not appear in the number of floors of the hotel.
For example, when t=3, the floors of 3, 13, 31, 33 and so on do not exist, and the floor numbers are 1, 2, 4, 5,..., so in fact, the real number of floors of the fourth floor is the third floor.
It is known that Xiao Ming has booked a room on the m floor. Now find out the real number of floors on this floor (m must be the floor existing in the hotel).
input
There are two integers m,t in one line. (1≤m≤100000,0≤t≤9)
output
Output real floors.
sample input
14 3
sample output
12
Code demonstration:
#include<iostream> using namespace std; int func(int x, int t) { while (x) { if (x % 10 == t) return 0; x /= 10; } return 1; } int main(int argc, char *grav[]) { int m, t, ans = 0; cin >> m >> t; for (int i = 1; i <= m; i++) { if (func(i, t)) { ans++; } } cout << ans << endl; return 0; }
oj514. Matchstick equation
Title Description
Given n matchsticks, how many equations can be spelled out, such as a+b=c.
A, B and C in the equation are integers spelled with matchsticks (no leading zeros). The number of matchsticks used for numbers and symbols is as follows:
0:6 1:2 2:5 3:5 4:4 5:5 6:6 7:3 8:7 9:6 +:2 =:2
There are the following precautions:
1. The plus sign and the equal sign each require two matchsticks
2. If a ≠ b, then a+b=c and b+a=c are regarded as different equations, and a, b and C are not less than 0.
 All n matchsticks must be used.
input
An integer n on one line. (1≤n≤24)
output
Output the number of equations that can be composed.
sample input
14
sample output
2
Example description
The two equations are as follows:
0+1=1 1+0=1
Code demonstration:
#include<iostream> using namespace std; int num[15] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 3, 7, 6}; int sum(int x) { if (x == 0) { return num[0]; } int ans = 0; while (x) { ans += num[x % 10]; x /= 10; } return ans; } int func(int a, int b) { int x = sum(a), y = sum(b), z = sum(a + b); return x + y + z + 4; } int main(int argc, char *grav[]) { int n, ans = 0; cin >> n; for (int i = 0; i < 2000; i++) { for (int j = 0; j < 2000; j++) { if (func(i, j) == n) { ans++; } } } cout << ans << endl; return 0; }
oj516. Cow inscription
Title Description
John and his cows roamed the prairie and found some interesting inscriptions on a stone. The inscription seems to be a mysterious and ancient language, which only includes three capital letters C, O and W. Although John couldn't understand it, he was happy that the sequential forms of C, O and W formed his favorite COW word "COW". Now, he wants to know how many times COW appears in the text. If other characters are interspersed in the COW, John doesn't mind as long as the COW characters appear in the correct order. Even, he doesn't mind different COW sharing some letters. For example, there is one COW in CWOW, two COW in CCOW and eight COW in CCOOWW.
input
The first line is an integer n. (1≤N≤105))
The second line contains a string of N characters. The characters can only be C,O,W.
output
The number of times that the output COW appears as the string of the input string (not necessarily continuous).
The answer could be big.
sample input
6 COOWWW
sample output
6
Code demonstration:
#include<iostream> using namespace std; int n, num[100005], wcnt; long long ans; char str[100005]; int main(int argc, char *grav[]) { cin >> n >> &str[1]; for (int i = 1; i <= n; i++) { if (str[i] == 'C') { num[i] = num[i  1] + 1; } else { num[i] = num[i  1]; } } for (int i = n; i > 0; i) { if (str[i] == 'W') { wcnt++; } if (str[i] == 'O') { ans += (long long)num[i  1] * wcnt; } } cout << ans << endl; return 0; }
oj517. Number of triangles
Title Description
Input the length n of a wooden stick, divide it into three sections, the length of each section is a positive integer, and output the different number of triangles composed of these three small sections of wooden sticks.
input
The first line is an integer n. (1≤n≤104)
output
Output the number of triangles with different composition.
sample input
10
sample output
2
Example description
The side lengths of two triangles are 2,4,4 and 3,3,4 respectively.
Code demonstration:
#include<iostream> using namespace std; int main(int argc, char *grav[]) { int n, ans = 0; cin >> n; for (int i = 1; i <= n / 3; i++) { for (int j = i; j <= (n  i) / 2; j++) { if (i + j > n  i  j) { ans++; } } } cout << ans << endl; return 0; }
oj519. Elegant number
Title Description
Given two numbers L and R, find how many "elegant numbers" there are between L and R (including).
Definition of elegant number: a number is regarded as a string of length n (without leading zeros). N − 1 of the n characters are all the same, and there is only one character different. For example, 33323119 are elegant and 99992332 are not elegant.
input
Enter two integers L,R in a row. (100≤L≤R≤1016)
output
Output the number of elegant numbers between two numbers.
sample input
110 133
sample output
13
Example description
110,112,113,114,115,116,117,118,119,121,122,131,133
Code demonstration:
#include<iostream> using namespace std; int main(int argc, char *grav[]) { long long left, right; cin >> left >> right; int ans = 0; // Enumerate a stack of numbers for (int i = 0; i < 10; i++) { // Enumerate a number for (int j = 0; j < 10; j++) { if (i == j) { continue; } // Length of number for (int k = 3; k <= 17; k++) { // Position of number for (int l = 1; l <= k; l++) { if (i == 0 && l != 1) { break; } if (j == 0 && l == 1) { continue; } long long t = 0; // Construction elegant number for (int m = 1; m <= k; m++) { if (m == l) { t = t * 10 + j; } else { t = t * 10 + i; } } if (left <= t && t <= right) { ans++; } } } } } cout << ans << endl; return 0; }