The fifth ACM undergraduate programming competition of Henan Institute of Engineering (part of the solution)
Question A: sensitive Xiao Ming
Xiao Ming is a person who is very sensitive to numbers. When he sees a specific number P (1 < = P < = 9), he will be excited. Now give you a numerical range (L, R). Ask how many times will Xiao Ming be excited when he sees all the numbers in this range? (for example, when l = 2, r = 22 and P = 2, Xiao Ming will be excited for 6 times, when l = 2, 12, 20 and 21, respectively, and 22 will be excited twice)
This problem can be solved by finding the number of a number in a certain interval
for instance:
The number 12105 is 2 in the thousands. How many integers have 1 in the thousands? 100019991100011999, 2x1000 in total; (2 = 10000 bits + 1)
If there is 1 in the hundreds, how many integers have 1 in the hundreds? 100-1991100-1199... 9100-919910100-10199,... 11100-1119912100-12105, 12x100+5+1 in total;
If the ten digit is 0, how many integers have 1 on the ten digit? 10-19110-119210-219... 1010-1019... 10010-10019... 12010-12019... Total: 121x10
It is distinguished by low bit, current bit and high bit
Find the number of 1 in [1, N] as follows:
If the current bit is less than 1, the number is equal to the high bit * current bit rate
If the current bit is equal to 1, the number is equal to high * current bit rate + low + 1
If the current bit is greater than 1, the number is equal to (high bit + 1) * the current bit rate
Reference website, for example:
The number 12105 is 2 in the thousands. How many integers have 1 in the thousands? 100019991100011999, 2x1000 in total; (2 = 10000 bits + 1)
If there is 1 in the hundreds, how many integers have 1 in the hundreds? 10019911001199... 910091991010010199,... 1110011199210012105, 12x100+5+1 in total;
If the ten digit is 0, how many integers have 1 on the ten digit? 1019110119210219... 10101019... 1001010019... 1201012019... Total: 121x10
It is distinguished by low bit, current bit and high bit
Find the number of 1 in [1, N] as follows:
If the current bit is less than 1, the number is equal to the high bit * current bit rate
If the current bit is equal to 1, the number is equal to high * current bit rate + low + 1
If the current bit is greater than 1, the number is equal to (high bit + 1) * the current bit rate
Reference website: http://www.voidcn.com/article/p-gswrfywk-qs.html
Reference code
#include<bits/stdc++.h>
using namespace std;
int l,r,p;
int f(int x)
{
int a=x,t=1,s=0;
while(x)
{
s+=x/10*t;
if(x%10>p)
s+=t;
else if(x%10==p)
s+=(a%t)+1;//cout<<"1="<<s<<endl;
x/=10;
t*=10;
//cout<<"2="<<s<<endl;
}
return s;
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>l>>r>>p;
cout<<f(r)-f(l-1)<<endl;
}
return 0;
}
Question B: Forest exploration
Xiao Ming is a person with a weak sense of direction. In order to prove himself, he plans to explore the forest.
His friend Xiao Hong gave him a map with full coordinates. If he passed according to the point on the map and finally remembered that he turned left (excluding backward) several times, Xiao Ming would win.
Looking at the dense coordinate axes on the map, Xiao Ming's head was big, but the smart one immediately thought of you: algorithm God!
Can you help him finish the challenge?
Problem analysis:
This problem can be solved by the problem in the series of plane equations, and the idea of point product and cross product can be used to solve the problem.
Vector product, also known as outer product and cross product in mathematics and vector product and cross product in physics, is a binary operation of vectors in vector space. Unlike dot product, its result is a vector rather than a scalar. And the cross product of the two vectors is perpendicular to the sum of the two vectors.
The calculation is this, for vectors a (x1, y1), b (x2, y2)
Their cross product a × b=x1y2-y1x2
The cross product is a vector that represents the directed area. The direction can be determined by the right-hand rule, such as a × b. If the four fingers are in the direction of rotation, the direction pointed by the thumb is the direction of cross product
Reference link:
https://blog.csdn.net/ld326/article/details/84689620?utm_source=app&app_version=4.9.1&code=app_1562916241&uLinkId=usr1mkqgl919blen
The following code is:
#include<iostream>
#include<cstdio>
#include<algorithm>
#Include < vector > / / container
#include<string.h> //string
#include<math. h> / / mathematical function
#Include < stack > / / stack
#Include < queue > / / priority queue
#include <stdlib. h> / / string to integer
#Include < ssstream > / / use istringstream (identify the string in the string, and do not read spaces)
#Include < set > / / set function. The elements in the container cannot be repeated
using namespace std;
struct p
{
int x;
int y;
}y[2000];
double panduan(p p1,p p2,p p3)
{
return ((p2.x-p1.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p2.y-p1.y));
}
int main()
{
int n;
struct p y[2000];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>y[i].x>>y[i].y;
}
int ans=0;
for(int i=2;i<n;i++)
{
if(panduan(y[i-2],y[i-1],y[i])>0)
ans++;
}
cout<<ans<<endl;
return 0 ;
}
Question C: Xiao Ming's obsessive-compulsive disorder
Xiao Ming is a patient with obsessive-compulsive disorder. He must drink a fixed amount of water every time, but the conditions for forest exploration are poor. He forgot to bring a measuring cylinder. Now he has found you, who is said to be the God of algorithms, to help him.
He has two cups A and B, the amount of water he wants to drink C, and there are three operations for cups A and B:
1. Fill the cup i with water
2. Pour the cup i of water
3. Pour the water from cup i into cup j. after this operation, it is possible that cup j is full (there may be some water in cup i) or cup i is empty (all the water in it has been poured into cup j)
In order to maintain the physical strength required for forest exploration, the operation of the cup should be as little as possible. Now please help Xiao Ming replenish water to make him better explore the forest.
This problem can be simulated recursively
Let's simplify this problem first: if c > A + b, we can always make c - (Na + MB) < A + b by pouring n times a and m times b, (N and m are non negative integers), so we only need to study the case of c < A + b. Let X be the greatest common divisor of a and b, then the mathematical condition for measuring c is that c can divide x, that is, c%x==0
Therefore, after judging whether the desired result can be obtained, we need to pour water from a to b, and then pour b, or b to a, and then pour a, and repeat until the standard is met.
Upper Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#Include < vector > / / container
#include<string.h> //string
#include<math. h> / / mathematical function
#Include < stack > / / stack
#Include < queue > / / priority queue
#include <stdlib. h> / / string to integer
#Include < ssstream > / / use istringstream (identify the string in the string, and do not read spaces)
#Include < set > / / set function. The elements in the container cannot be repeated
using namespace std;
int daoshui(int A, int B, int C)
{
int inA = 0;
int inB = 0;
int flag = 0;
int ans=0;
while(1)
{
if(flag++>999)
{
ans++;
break;
}
if(0==inA)
{
ans++;
inA=A;
}
else
{
ans++;
inB+=inA;
if(inB>=B)
{
inA=inB-B;
if(C == inA || C == inB)
{
return ans;
}
ans++;
inB = 0;
}
else
{
inA=0;
}
}
if(C == inA || C == inB)
{
return ans;
}
}
}
int main()
{
int t; cin>>t;
while(t--)
{
int A,B,C,w;
cin>>A>>B>>C;
if(C%__gcd(A,B)==0)
{
int ans1=daoshui(A,B,C);
int ans2=daoshui(B,A,C);
cout<<min(ans1,ans2)<<endl;
}
else
cout<<"impossible"<<endl;
}
return 0 ;
}
Reference website: https://blog.csdn.net/henuboy/article/details/11287183?utm_source=blogxgwz1&utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242
Question D: infrastructure mobile games
After exploring the forest, Xiao Ming plans to stay at home for a while. He is addicted to a mobile infrastructure tour.
There is a mysterious kingdom on the vast west Brooke continent. The city Lord Xiao Ming can choose to circle a square covering an area of K*K in this kingdom as his city. Xiao Ming hopes you can choose a suitable location to maximize the land value of his city.
The knowledge points of this question are prefix and.
The knowledge points of prefix and are as follows:
After understanding the prefix and code, it is not difficult to write the code
#include<iostream>
#include<cstdio>
#include<algorithm>
#Include < vector > / / container
#include<string.h> //string
#include<math. h> / / mathematical function
#Include < stack > / / stack
#Include < queue > / / priority queue
#include <stdlib. h> / / string to integer
#Include < ssstream > / / use istringstream (identify the string in the string, and do not read spaces)
#Include < set > / / set function. The elements in the container cannot be repeated
using namespace std;
int a[1000][1000],b[1000][1000];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>b[i][j];
a[i][j]=b[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
}
int max=-999999;
int x,y;
k--;
for(int i=0;i<n-k;i++)
for(int j=0;j<m-k;j++)
{
int sum=a[i+k][j+k]-a[i+k][j-1]-a[i-1][j+k]+a[i-1][j-1];
if(sum>max)
{
x=i+1;
y=j+1;
max=sum;
}
}
cout<<x<<" "<<y<<endl;
return 0 ;
}
The above is part of the code of this competition. If there is anything wrong, please communicate and correct it.