Catalogue
1.
Title Description
Before the popularization of electronic computers, people often used a rough method to check whether the four operations were correct.
For example: 248 * 15 = 3720
Sum the multiplier and the multiplicand bit by bit respectively. If it is a multi digit number, sum it bit by bit until it is 1 digit, and then get
2 + 4 + 8 = 14 ==> 1 + 4 = 5;
1 + 5 = 6
5 * 6
The bitwise sum of the results is 3
The result of 5 * 6 is consistent with 3, indicating that it is very likely to be correct!! (errors cannot be excluded)
Please write a computer program to sum the given string bit by bit:
input
The input is a string composed of numbers, representing n digits (n < 1000);
output
The output is a single digit, indicating the result of repeated bit by bit summation.
sample input
35379
sample output
9
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
stringstream ss;
void jy(string &s){
ll sum=0;
for(int i=0;i<s.length();i++){
sum+=s[i]-'0';
}
ss.clear();
ss<<sum;
ss>>s;
}
int main(){
cin>>s;
while(s.length()>1){
jy(s);
}
cout<<s;
return 0;
}2.
Title Description
Xiao h went to the United States to participate in the blue bridge cup international competition. Little h's girlfriend found that little h left at 10 a.m. and arrived in the United States at 12 a.m., so she sighed, "now the plane flies so fast that it can reach the United States in two hours.".
Little h was terrified of supersonic flight. After careful observation, it is found that the take-off and landing time of the aircraft is local time. Due to the 12 hour time difference between Beijing and the eastern United States, the plane needs a total of 14 hours of flight time.
Soon after, little h's girlfriend went to the Middle East to exchange. Xiao h doesn't know the time difference between the Middle East and Beijing. But little h got the take-off and landing time of his girlfriend's round-trip flight. Little h wants to know the flight time of his girlfriend's flight.
For a flight that may cross time zones, the take-off and landing time of the return trip is given. Assuming that the round-trip flight time of the aircraft is the same, calculate the flight time of the aircraft.
input
Read in data from standard input.
One input contains multiple sets of data.
The first input line is a positive integer T, indicating the number of input data groups.
Each group of data contains two lines, the first line is the take-off and landing time of the departure journey, and the second line is the take-off and landing time of the return journey.
The format of takeoff and landing time is as follows
h1:m1:s1 h2:m2:s2
or
h1:m1:s1 h3:m3:s3 (+1)
or
h1:m1:s1 h4:m4:s4 (+2)
Indicates that the flight takes off at h1:m1:s1 local time,
The first format indicates landing at h2:m2:s2 on the day of local time
The second format indicates landing at h3:00, m3:00, s3:00 the next day local time.
The third format indicates landing at h4:m4:s4 on the third day of local time.
For all the time given in the form of h:m:s in this topic, guarantee (0 < = h < = 23, 0 < = m, s < = 59)
output
Output to standard output.
For each group of data, one line of time hh:mm:ss is output, indicating that the flight time is HHH mm min ss.
Note that when the time is a single digit, the leading zeros should be supplemented. For example, three hours, four minutes and five seconds should be written as 03:04:05.
sample input
3 17:48:19 21:57:24 11:05:18 15:14:23 17:21:07 00:31:46 (+1) 23:02:41 16:13:20 (+1) 10:19:19 20:41:24 22:19:04 16:41:09 (+1)
sample output
04:09:05 12:10:39 14:22:05
First, learn the usage of the game getline
The advantage of getline over cin is that it can read table s and spaces (carriage return can be ignored)
#include<iostream>
#include<string>
using namespace std;
int main(){
string str;
while(getline(cin,str)){
cout<<str;
}
return 0;
} The most difficult part of this question is input
The following is the reference code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int get_second(int h, int m, int s){
return h * 3600 + m * 60 + s;
}
int get_time(){
string line;
getline(cin, line); //Similarly, the entered carriage return is ignored
if(line.back() != ')') line += " (+0)";
int h1, m1, s1, h2, m2, s2, d;
sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
return get_second(h2, m2, s2) - get_second(h1, m1, s1) + d * 24 * 3600;
}
int main(){
int t;
scanf("%d", &t);
string line;
// getline(cin, line); // Ignore the carriage return in the first line, because scanf does not read the carriage return
getchar();//Read in and enter. I don't know why. Just read it
while(t--){
int time = (get_time() + get_time()) / 2;//Time to go = flight time - time difference. Return time = flight time + time difference. If you go and add it back, you'll lose it. If you go and subtract the jet lag, you'll add it back. So the actual flight time = (time to go + time to return) / 2
int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
printf("%02d:%02d:%02d\n", hour, minute, second);
}
return 0;
}
3.
Title Description
The spiral polyline as shown in the figure passes through all integral points on the plane exactly once.
For the whole point (X, Y), we define its distance from the origin. dis(X, Y) is the length of the spiral line segment from the origin to (X, Y).
For example, dis(0, 1)=3, dis(-2, -1)=9
Given the coordinates of the whole point (X, Y), can you calculate dis(X, Y)?
input
X and Y
output
Output (x, DIS)
sample input
0 1
sample output
3
This problem was originally solved by violence, but it failed. It can be seen that the Blue Bridge Cup is no longer a violence cup
The violence code is as follows
#include<stdio.h>
int main(){
int x=0,y=0,h,l,z,s,i,cnt=0;
int a,b;
scanf("%d %d",&a,&b);
for(h=1,l=1;;h++,l++){
if(h%2!=0)z=-1;
else z=1;
if(l%2!=0)s=1;
else s=-1;
//cout<<h <<l <<z <<s <<endl;
for(i=1;i<=h;i++){
x+=z;
// cout<<x<<endl;
cnt++;
if(x==a&&y==b)break;
}
if(x==a&&y==b)break;
for(i=1;i<=l;i++){
y+=s;
// cout<<y<<endl;
cnt++;
if(x==a&&y==b)break;
}
if(x==a&&y==b)break;
}
printf("%d",cnt);
return 0;
}This question needs to find rules
This problem can directly simulate about 80% of the data. In fact, it's OK to directly find the law. You can see the figure below. We complete it into a square. The difference between two adjacent squares is 8, forming an equal difference sequence. Then calculate the distance between the required position and the position from the lower left corner each time
The correct code is as follows
#include<cstdio>
#include<iostream>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
int main(void) {
int x, y;
cin >> x >> y;
ll n = max(abs(x), abs(y));//On which square do you find it
ll ans = 0;
ll temp = 0;
if (x >= y) {//Lower right triangle
ans = 8 * n + n * (n - 1) * 8 / 2;//Divide by 2 should be put in the back, otherwise there may be errors. Here is the sum of equal difference sequence
temp = x + n + y + n;//This is basically looking at the picture to find the law
ans -= temp;
}
else {//Lower left triangle
temp = x + n + y + n;.//This is basically looking at the picture to find the law
n--;
ans = 8 * n + n * (n - 1) * 8 / 2; //Here is the total distance of n-1 floor
ans += temp;
}
cout << ans;
return 0;
}
4.
Title Description
The number of n individuals is 1~n. if they are arranged in a circle clockwise according to the number, start counting clockwise from the person whose number is 1.
(counting starts from 1) when checking in k, the person quits the game circle. The next person starts counting again from 1.
The last person to ask for the number. This is the famous Joseph Ring problem.
This topic is to find the number of the last remaining person when n and k are known.
input
The input of the title is a line, two spaces separated integer n, k
Agreement: 0 < n, K < 1 million
output
It is required to output an integer to represent the number of the last remaining person.
sample input
10 3
sample output
4
This kind of problem is mainly to find rules. You can refer to this article Joseph Ring formula method (recursive formula)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int f[maxn];
int main() {
int n,k;
cin>>n>>k;
f[1]=0;
for(int i=2; i<=n; i++) {
f[i]=(f[i-1]+k)%i;
}
cout<<f[n]+1<<endl;
return 0;
}5.
You have a NxN pixel picture of a sea area, "." Indicates the sea and "#" indicates the land, as shown below:
.......
.##....
.##....
....##.
..####.
...###.
.......
Among them, a piece of land connected in the four directions of "up, down, left and right" forms an island. For example, there are two islands in the above picture.
As global warming causes the sea to rise, scientists
It is predicted that in the coming decades, the range of a pixel on the edge of the island will be submerged by seawater. Specifically, if a land pixel is adjacent to the ocean (there is an ocean in the four adjacent pixels above, below, left and right), it will be submerged.
For example, the sea area in the above figure will look like the following in the future:
.......
.......
.......
.......
....#..
.......
.......
Please calculate: according to the prediction of scientists, how many islands in the picture will be completely submerged.
input
The first line contains an integer n. (1 <= N <= 1000)
The following n rows and N columns represent a sea area photo.
The picture ensures that the pixels in row 1, column 1, row N and column n are oceans.
output
An integer represents the answer.
sample input
7 ....... .##.... .##.... ....##. ..####. ...###. .......
sample output
1
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct node
{
int x,y;
};
queue<node>q;
char mapp[N][N];
bool vis[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,ans;
bool flag=0;
int total,none,centre;
void bfs(int u,int v)
{
vis[u][v]=0;
q.push({u,v});
while(!q.empty())
{
node tmp=q.front();
if(mapp[tmp.x][tmp.y+1]=='#'&&mapp[tmp.x][tmp.y-1]=='#'&&mapp[tmp.x-1][tmp.y]=='#'&&mapp[tmp.x+1][tmp.y]=='#')centre++;
q.pop();
for(int i=0;i<4;i++)
{
int tmp1,tmp2;
tmp1=tmp.x+dx[i];
tmp2=tmp.y+dy[i];
if(tmp1>=1&&tmp1<=n&&tmp2>=1&&tmp2<=n&&vis[tmp1][tmp2]==1){q.push({tmp1,tmp2});vis[tmp1][tmp2]=0;}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%s",mapp[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp[i][j]=='#')vis[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]==1)
{
centre=0;
bfs(i,j);
total++;
if(!centre){none++;}
}
}
}
cout<<none;
return 0;
}