First algorithm job
Problem A. flower of thought - equation
Time limit 1000 ms
Memory limit 128 MB
Title Description
It can be seen as a univariate cubic equation such as ax^3+bx^2+cx+d=0. The coefficients of each item in the equation (a, b, c and d are real numbers) are given, and it is agreed that the equation has three different real roots (the range of roots is - 100 to 100), and the absolute value of the difference between roots > = 1. It is required to output the three real roots in the same line from small to large (there is a space between the roots) and accurate to 2 digits after the decimal point.
Tip: write down the equation f(x)=0. If there are two numbers X1 and X2, and X1 < X2, f (x1) * (x2) < 0, there must be a root between (x1, x2).
input data
Enter the coefficients (a, B, C, d) of each item in the equation (a, B, C, D are real numbers),
output data
From small to large, the three real roots are output on the same line (there is a space between the roots) and accurate to 22 digits after the decimal point.
sample input
1 -5 -4 20
sample output
-2.00 2.00 5.00
#include <iostream>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
double a, b, c, d;
#define f(x) (a*(x)*(x)*(x)+b*(x)*(x)+c*(x)+d)
void ef(double s, double e)
{
if (f(s) * f(e) <= 0)
{
double mid = (s + e) / 2.0;
if (fabs(f(mid)) <= 1e-8)
{
cout<<setiosflags(ios::fixed) << setprecision(2) << mid << " ";
return;
}
if (f(mid) * f(s) < 0)
ef(s, mid);
else
ef(mid, e);
}
}
int main()
{
cin >> a >> b >> c >> d;
for (double s = -101; s <= 101; s += 1)
{
ef(s, s + 1);
}
return 0;
}
Problem C. class assignments - 7-1
Time limit 1000 ms
Memory limit 64 MB
Title Description
There are n small wooden sticks. Choose any three wooden sticks to form a triangle. Ask what is the maximum circumference of the triangle. (ensure that at least one option can form a triangle)
input data
The first line is a positive integer n, 3 = < n < = 100, and the second line is n positive integers, representing the length of the small wooden stick, no more than 100
output data
Maximum value of triangle perimeter
sample input
5 1 2 3 4 5
sample output
12
Solution 1:
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 105;
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
void solve(int n, int* a)
{
qsort(a, n, sizeof(a[0]), cmp);
int sum = 0;
for (int i = n - 1; i > 1; --i)
{
if (a[i] + a[i - 1] > a[i - 2])
if (a[i] + a[i - 2] > a[i - 1])
if (a[i - 1] + a[i - 2] > a[i])
{
sum = a[i] + a[i - 1] + a[i - 2]; break;
}
}
cout << sum;
}
int main()
{
int n, a[MAX_N];
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
solve(n, a);
return 0;
}
Second algorithm job
Problem A. class assignments - 6-1
Time limit 1000 ms
Memory limit 64 MB
Title Description
If a prime number can be expressed as the sum of three different prime numbers, we call it cubic prime number. Now I'll give you a number n to judge whether it is a cubic prime number.
input data
Positive integer n, n < = 1000
output data
Yes or No
sample input
19
sample output
Yes
Solution 1
#include <iostream>
#include <cmath>
using namespace std;
//Judge whether it is a prime number
bool isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// What is not on either side of a multiple of 6 must not be a prime number
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
bool flag = false;
if (!isPrime(n)) {
cout << "No" << endl;
}
else {
for (int i = 1; i <= n; i++) {
if (isPrime(i)) {
for (int j = i + 1; j <= n; j++) {
if (isPrime(j) && isPrime(n - i - j) && (n - i - j) != i && (n - i - j) != j) {
flag = true;
}
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Problem B. class assignments - 5-1
Time limit 1000 ms
Memory limit 64 MB
Title Description
There are n lights, numbered 1-n, and the initial lights are off. There are n people, the first person will turn on all the lights, the second person will press the switches of all the lights with multiple number 2 (these lights will be turned off), the third person will press all the switches with multiple number 3, and so on, the n person will press all the switches with multiple number n. Q. how many lights are on at the end.
input data
A positive integer n, n < 100000
output data
Number of lights on
sample input
5
sample output
2
Solution 1:
#include <iostream>
using namespace std;
int check(int x) {
int cnt = 0;
int i;
for (i = 1; i * i < x; ++i) {
if (!(x % i)) {
cnt += 2;
}
}
if (i * i == x) {
++cnt;
}
return cnt;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (check(i) % 2) {
++cnt;
}
}
cout << cnt << endl;
return 0;
}
Solution 2:
# include "iostream"
# include "vector"
# include "numeric"
using namespace std;
#define MAX_SIZE 100000
int main(){
int n;
cin >>n;
vector<int> p(n+1, 1);
for(int i = 2; i <= n; i++){
for(int j = 1; j*i <= n; j++){
if(p[j*i] == 1)
p[j*i] = 0;
else
p[j*i] = 1;
}
}
p[0] = 0;
cout << accumulate(p.begin(), p.end(), 0) << endl; // Accumulation range, and accumulation initial value
return 0;
}
Solution 3:
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int i = 1;
for(; i * i <= n; i++){}
cout << i - 1 << endl;
return 0;
}
Problem C. class assignments - 4-4
Time limit 1000 ms
Memory limit 64 MB
Title Description
Xiao Ming just bought a mechanical keyboard, but when he was typing with the mechanical keyboard, he found that the Home key and End key of the keyboard were broken, so when he was typing, the cursor sometimes suddenly ran to the beginning of the line and sometimes to the End of the line. Now give you the input of the keyboard and find the string on the last screen.
input data
The input data is a line of string. The string only contains lowercase English letters, '[' symbol and ']' symbol, '[' represents pressing the Home key and ']' represents pressing the End key. The length of the string shall not exceed 100000.
output data
Output the string on the last screen.
sample input
xiechengxuz[henhao]wan
sample output
henhaoxiechengxuzwan
Example description
There may be multiple '[' and ']' or no '[' and ']'
Solution 1:
# include <iostream>
# include <string>
# include <queue>
using namespace std;
deque<string> q;
string buf;
void fun(int flag, string& buf) {
if (flag)
q.push_back(buf);
else
q.push_front(buf);
buf.clear();
}
int main() {
string s;
cin >> s;
int flag = 0;// flag=0, put it in front; flag =1, put behind
for (int i = 0; i < s.length(); i++)
{
if (s[i] != '[' && s[i] != ']') {
buf += s[i];
}else if (s[i] == '[') {
fun(flag, buf);
flag = 0;
}
else {
fun(flag, buf);
flag = 1;
}
}
fun(flag, buf);
for (auto i : q)
cout << i;
}
Problem D. Superprime
Time limit 1000 ms
Memory limit 128 MB
Title Description
Farmer John's cows always produce the best ribs. You can recognize them by the numbers marked on each rib by Farmer John and the U.S. Department of agriculture.
Farmer John determined that what he sold to the buyer was a real prime rib because he cut the rib from the right, and the numbers on the remaining ribs each time form a prime number. For example:
7 3 3 1
The number 7331 on all ribs is prime; The three ribs 733 are prime numbers; The two ribs 73 are prime numbers; Of course, the last rib 7 is also prime.
7331 is called a special prime of length 4.
Write a program to find all special prime numbers for a given number of ribs n (1 < = n < = 8). The number 1 is not considered a prime number.
input data
A single row contains N.
output data
Special prime numbers with length N are output in sequence, one for each line.
And in order of size (from small to large)
sample input
4
sample output
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
Solution 1:
#include<iostream>
#include<cmath>
#include <queue>
using namespace std;
bool isPrime(int num) { //Judge whether it is a prime number
if (num <= 3) {
return num > 1;
}
if (num % 6 != 1 && num % 6 != 5) { // What is not on either side of a multiple of 6 must not be a prime number
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
queue <int> q;
int n, m = 4;
int a[] = { 2,3,5,7 }; // A single number is a prime number
int b[] = { 1,3,7,9 }; //These numbers may end in prime numbers
cin >> n;
for (int i = 0; i < 4; i++) q.push(a[i]);
for (int i = 2; i <= n; i++) {
int l = m;
m = 0;
for (int j = 0; j < l; j++) {
for (int k = 0; k < 4; k++) //Select enum b[k]
if (isPrime(q.front() * 10 + b[k]))
q.push(q.front() * 10 + b[k]), m++;
q.pop();
}
}
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
return 0;
}
Solution 2
#include <iostream>
#include <vector>
using namespace std;
int mn = 1, mx = 1;
vector<int> bones;
bool isprime(int x) {
if (x == 2) {
return true;
}
if (x == 1 || !(x % 2)) {
return false;
}
for (int i = 3; i * i <= x; i += 2) {
if (!(x % i)) {
return false;
}
}
return true;
}
void dfs(int x) {
if (x >= mn && x < mx) {
bones.push_back(x);
return;
}
x *= 10;
for(int i = 1; i < 10; ++i) {
if (isprime(x + i)) {
dfs(x + i);
}
}
}
int main() {
int n;
cin >> n;
while (--n) {
mn *= 10;
mx = mn;
}
mx *= 10;
dfs(0);
for (int i : bones) {
cout << i << endl;
}
return 0;
}
Problem E. integer transformation
Time limit 1000 ms
Memory limit 128 MB
Title Description
Give a positive integer less than 2 ^ 32. This number can be represented by a 32-bit binary number (less than 32 bits are supplemented by 0). We call the first 16 bits of this binary number "high" and the last 16 bits "low". By exchanging its high and low bits, we can get a new number. How much is this new number (expressed in decimal).
For example, The number 1314520 is expressed in binary as 0000 0000 0001 0100 0000 1110 1101 1000 (11 leading zeros are added to complement 32 bits), of which the first 16 bits are high bits, i.e. 0000 0000 0001 0100; the last 16 bits are low bits, i.e. 0000 1110 1101 1000. By exchanging its high and low bits, we get a new binary number 0000 1110 1101 1000 0000 0000 0001 0100. It is 249036820 in decimal system.
input data
A positive integer less than 232232
output data
Output new data
sample input
1314520
sample output
249036820
Solution 1:
#include<iostream>
using namespace std;
int main()
{
unsigned long long x;
cin >> x;
cout << ((x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16) << endl;
}
The third algorithm job
Problem A. class assignments - 6-2
Time limit 1000 ms
Memory limit 64 MB
Title Description
We have n sticks. Now cut out M sticks of the same length from these sticks. How long is the longest of these m sticks?
input data
Enter two numbers in the first line. N (1 < = n < = 1000) is the number of sticks, m (1 < = m < = 1000) is the number of sticks of the same length to be cut, and then n positive integers represent the length of the original stick (< = 10000)
output data
Each group outputs a line of results, indicating the longest length of the rope after cutting (two decimal places are reserved)
sample input
4 5 5 6 7 8
sample output
4.00
Solution 1
#include <iostream>
using namespace std;
#include <vector>
#include <iomanip>
#include <cmath>
int main()
{
int n,m;
cin >>n>> m;
vector<int> v;
double max=0;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
v.push_back(t);
if (t > max)
max = t;
}
double s = 0, e = max;
double mid;
while (s + 0.01 < e) {
int cnt = 0;
mid = round(((s + e) / 2.00) * 100) / 100.00; //rounding
for (int i = 0; i < n; i++)
cnt += (double)(v[i] / mid);
if (cnt >= m) s = mid;
else e = mid;
}
cout << setiosflags(ios::fixed) << setprecision(2) << s ;
}
Problem B. class assignments - 7-2
Time limit 1000 ms
Memory limit 64 MB
Title Description
There is a river. There are some stones in the middle of the river. The number of stones and the distance between two adjacent stones are known. Now you can remove some stones. After removing up to m stones (the first and last stones cannot be removed), what is the minimum and maximum distance between two adjacent stones.
input data
In the first line, enter two numbers. N (2 < = n < = 1000) is the number of stones, m (0 < = m < = n-2) is the number of removable stones, and then n-1 numbers represent the sequence and the distance D (d < = 1000) between two adjacent stones
output data
Output the maximum value of the minimum distance
sample input
4 1 1 2 3
sample output
3
Solution 1:
#include <stdio.h>
int n, m,ans;
int d[1005];
int l[1005] = { 0 };
int main() {
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
scanf("%d", &d[i]);
l[i] = d[i] + l[i - 1];
}
int left=0,right=l[n];
while(left<=right)
{
int now=0,mid=(left+right)>>1,s=0;
for(int i=2;i<=n;++i)
{
if(l[i]-l[now]<mid) ++s;
else now=i;
}
if(s>m) right=mid-1;
else
{
ans=mid;
left=mid+1;
}
}
printf("%d",ans);
return 0;
}
Problem C. class assignments - 9-1
Time limit 1000 ms
Memory limit 64 MB
Title Description
Stairs have n steps. You can go up one step, two steps or three steps at a time. How many different walking methods are there
Because the answer is very large, mod(1e9+7) is output
input data
A positive integer n, representing the order of stairs, n < = 1000000
output data
Number of schemes
sample input
3
sample output
4
Solution 1
# include <iostream>
# include <cmath>
# include <vector>
using namespace std;
int main() {
long n;
cin >> n;
long long f[3];
f[0] = 1;
f[1] = 2;
f[2] = 4;
int mod = (1e9 + 7);
long long ans;
if (n < 3) {
ans = f[n - 1];
}
else {
for (long i = 3; i < n; i++)
{
long long t;
t = f[0];
f[0] = f[1];
f[1] = f[2];
f[2] = (t + f[0] + f[1]) % mod;
}
ans = f[2];
}
cout << ans;
}
Problem D. parcel express
Time limit 1000 ms
Memory limit 128 MB
Title Description
An express company should send n parcels to n places respectively and assign a preset route to the postman Xiao K. Xiao K needs to drive and deliver them successively according to the order of the route, and one place cannot be missed. Xiaok gets the time period that each place can sign for, and also knows the distance from one place to the next in the route. If the arrival time at a certain place is earlier than the time period that can be signed, you must stay at this place until it can be signed, but not later than the time period that can be signed. It can be considered that the signing process is completed in an instant.
In order to save fuel, Xiao K hopes that the smaller the maximum speed of the car is, the better. You find a solution for him and find out what the minimum maximum speed of the car is.
input data
The 11th line is a positive integer n (n < 2) × 104)，n (n<2 × 104), indicating the number of locations where packages need to be transported.
In line nn below, there are 33 positive integers xi,yi,si, xi,yi,si in line i+1i+1, indicating that the time period for package signing at the second place is [xi,yi], [xi,yi] according to the route sequence, that is, the earliest is from the departure time xi, xi, and the latest is from the departure time yi, yi. The distance from the previous place to the second place is si, si, and xixi increases in the route.
It can be considered that S1 is the distance from the departure place to the 11th place, and the departure time is 00.
output data
It only includes an integer, which is the minimum value of the maximum speed of the vehicle, and the result retains two decimal places.
sample input
3 1 2 2 6 6 2 7 8 4
sample output
2.00
Example description
The first segment reaches the first location at the speed of 1 at time 2, the second segment reaches the second location at the speed of 0.5 at time 6, and the third segment reaches the third location at the speed of 2 at time 8.
Solution 1:
#include <stdio.h>
#define maxn 200005
long double st=0,en=1e9,mid;
int i,n;
int v[maxn][3];
bool check(long double x) {
long double minT, totalT=0;
for (int i = 0; i < n; i++) {
minT = v[i][2] / x;
totalT = minT + totalT;
if (totalT < v[i][0])
totalT = v[i][0];
else if (totalT > v[i][1])
return false;
}
return true;
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d%d",&v[i][0], &v[i][1], &v[i][2]);
while(en-st>1e-9){
mid=(en+st)/2.00;
if(check(mid)) en=mid;
else st=mid;
}
printf("%.2f",double(st));
return 0;
}
Problem E. class assignments - 8-2
Time limit 1000 ms
Memory limit 64 MB
Title Description
There are three ABC rods and some discs. At the beginning, the discs are stacked on rod A from small to large, with the small disc on the top and the large disc on the bottom. It is stipulated that if the disc p is stacked on the disc q, then rp < = rq, rp and rq are the radii of p and q.
Now there are several discs with radius from 1 to n, and there are i discs with radius i. one disc can be moved each time. How many operations are required to move all discs from rod A to rod C at least. Since the final answer may be very large, the answer is modulo output to 1e9+7.
input data
A positive integer n, n < = 1E5
output data
Minimum number of operations
sample input
2
sample output
4
Example description
The first step is to put the disk with radius 1 from A to B. the second and third steps are to put two disks with radius 2 from A to C. The fourth step is to put the disk with radius 1 from B to C
Solution 1:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long cnt=0;
long long mod = 1e9 + 7;
for (long long i = 1; i <= n; i++)
{
cnt =(cnt*2+i)%mod;
}
cout << cnt<<endl;
}
Fourth algorithm job
Problem A. collecting medicine
Time limit 1000 ms
Memory limit 128 MB
Title Description
Chenchen is a gifted and intelligent child. His dream is to become the greatest doctor in the world. To this end, he wanted to learn from the most prestigious doctors nearby. The doctor gave him a difficult problem in order to judge his qualifications. The doctor took him to a cave full of herbs and said to him: "Child, there are some different herbs in this cave. It takes some time to pick each one, and each one has its own value. I will give you a period of time, during which you can pick some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you pick."
If you are Chenchen, can you finish this task?
input data
The first line of input has two integers, T (1 ≤ t ≤ 1000) and M (1 ≤ m ≤ 100), separated by a space. T represents the total time that can be used to collect herbs, and M represents the number of herbs in the cave. The next M lines include two integers between 1 and 100 (including 1 and 100), representing the time of picking a herb and the value of the herb respectively.
output data
The output includes a line, which contains only an integer, indicating the maximum total value of herbs that can be collected within a specified time.
sample input
70 3 71 100 69 1 1 2
sample output
3
Solution 1
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e4;
int f[maxn]; //f: Total value of herbs
int w[maxn], val[maxn]; //w: Time cost val: Herbal value
void solve(int m, int t) {
memset(f, 0, sizeof f);
for (int i = 1; i <= m; i++) {
for (int v = t; v > 0; v--) {
if (v >= w[i])
f[v] = max(f[v], f[v - w[i]] + val[i]);
}
}
cout << f[t];
}
int main() {
int m, t; //t collection time, m number of herbs
cin >> t >> m;
for (int i = 1; i <= m; i++) {
cin>>w[i] >> val[i] ;
}
solve(m,t);
return 0;
}
Problem B. packing problem
Time limit 1000 ms
Memory limit 128 MB
Title Description
There is a box with a capacity of v (positive integer, O ≤ v ≤ 20000) and n items (o ≤ n ≤ 30), and each item has a volume (positive integer). It is required to load any one thousand of n items into the box to minimize the remaining space of the box.
input data
The first line, an integer, represents the box capacity;
The second line, an integer, indicates that there are n items;
The next N lines represent the respective volumes of the n items.
output data
An integer representing the remaining space in the box.
sample input
24 6 8 3 12 7 9 7
sample output
0
Solution 1
# include <iostream>
# include <algorithm>
# include <cmath>
using namespace std;
int v;
int n;
int a[35];
int dp[20005];
int main() {
cin >> v >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++)
for(int j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
int minV = v - dp[v];
cout << minV;
return 0;
}
Problem C. chorus formation
Time limit 1000 ms
Memory limit 128 MB
Title Description
N students stand in a row, and the music teacher will ask (N-K) students to stand out, so that the remaining K students form a chorus line.
Chorus formation refers to such a formation: let K students number 1, 2..., K from left to right, and their heights are T1, T2,..., TK respectively, then their heights meet T1 <... < Ti > Ti + 1 >... > TK (1 < = I < = k).
Your task is to know the height of all N students, and calculate at least a few students, so that the remaining students can form a chorus formation.
input data
The first line of input is an integer N (2 ≤ n ≤ 100), representing the total number of students. The first line has n integers separated by spaces. The I integer Ti (130 ≤ Ti ≤ 230) is the height (CM) of the i-th student.
output data
The output includes a row, which contains only an integer, that is, at least several students are required to list.
sample input
8 186 186 150 200 160 130 197 220
sample output
4
Solution I
# include <iostream>
using namespace std;
int l[105],r[105],h[105],dp[105];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
l[i]=r[i]=1;
}
for(int i=n-1;i>=1;i--){
for (int j=i+1;j<=n;j++)
{
if(h[i]>h[j]&&r[i]<=r[j]+1)
r[i]=r[j]+1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(h[i]>h[j]&&l[i]<=l[j]+1)
l[i]=l[j]+1;
}
}
int max=0;
for(int i=1;i<=n;i++){
dp[i]=l[i]+r[i]-1;
if(dp[i]>max)
max=dp[i];
}
cout<<n-max;
}
Problem D. the horse stopped the pawn
Time limit 1000 ms
Memory limit 128 MB
Title Description
There is A river crossing pawn at point A on the chessboard. You need to go to target point B. The rule of pawn walking: it can go down or right. At the same time, there is an opponent's horse at point C on the chessboard. The point where the horse is located and all the points that can be reached by jumping one step are called the control point of the opponent's horse. Therefore, it is called "A horse blocking A pawn across the river".
The chessboard is represented by coordinates. Point a (0, 0) and point B (n, m)(n, m are integers not exceeding 15). Similarly, the position coordinates of the horse need to be given. Now you are required to calculate the number of paths that the pawn can reach point B from point A. assuming that the position of the horse is fixed, it is not that the pawn takes one step and the horse takes one step.
input data
A row of four data represents the coordinates of point B and the coordinates of the horse.
output data
A data representing the number of all paths.
sample input
6 6 3 3
sample output
6
Solution 1
#include<iostream>
#define ll long long
using namespace std;
bool a[30][30];
ll dp[30][30];
//B(n,m) ma(x,y)
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
dp[1][1] = 1;
n++; m++; x++; y++;
a[x][y] = 1;
a[x - 1][y + 2] = 1;
a[x - 1][y - 2] = 1;
a[x + 1][y + 2] = 1;
a[x + 1][y - 2] = 1;
a[x - 2][y - 1] = 1;
a[x - 2][y + 1] = 1;
a[x + 2][y - 1] = 1;
a[x + 2][y + 1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
if ((i != 1 || j != 1) && !a[i][j])
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n][m];
}
Problem E. passing game
Time limit 1000 ms
Memory limit 128 MB
Title Description
In PE class, Xiaoman's teacher often plays games with his classmates. This time, the teacher took the students to play a passing game.
The rules of the game are as follows: n students stand in a circle, one of them is holding a ball, and when the teacher blows the whistle, he starts to pass the ball, Each student can pass the ball to one of the two students around him (left and right arbitrary). When the teacher blows the whistle again, the pass stops. At this time, the student who doesn't pass the ball is the loser and wants to show you a program.
The smart Xiaoman asked an interesting question: how many different passing methods can make the ball that Xiaoman started to pass, and then return to Xiaoman's hand after passing it m times. The two passing methods are regarded as different methods, if and only if in the two methods, the sequence of students receiving the ball is different according to the order of receiving the ball. For example, there are three students No. 1, No. 2 and No. 3. Assuming that Xiaoman is No. 1, there are two ways to return the ball to Xiaoman after passing it three times: 1 - > 2 - > 3 - > 1 and 1 - > 3 - > 2 - > 1.
input data
Enter a line with two integers n, m separated by spaces (3 ≤ n ≤ 30,1 ≤ m ≤ 30).
output data
The output is a line with an integer indicating the number of methods that meet the meaning of the question.
sample input
3 3
sample output
2
Example description
40% of the data meet: 3 < = n < = 30 1 < = m < = 20
100% data meet: 3 < = n < = 30 1 < = m < = 30
Solution 1:
dp[i][j]: the number of ways to pass the ball I times to the classmate numbered j.
#include<iostream>
using namespace std;
int dp[40][40];
int main() {
int n, m, x, y;
cin >> n >> m;
dp[0][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
x = j - 1;
y = j + 1;
if (x == 0) x = n;
if (y == n + 1) y = 1;
dp[i][j] = dp[i - 1][x] + dp[i - 1][y];
}
}
cout << dp[m][1];
}
The fifth algorithm operation
Problem A. single line maximal submatrix and problem
Time limit 1000 ms
Memory limit 64 MB
Title Description
Given 1 × N, each element of the matrix is an integer between - 127 and + 127. Please find a continuous submatrix so that the sum of its elements is the largest. For example, row matrix 0 - 2 - 7 0 - 2 11 - 4 13 - 5 - 2, the maximum sum of submatrixes is 11 + (- 4) + 13 = 20
input data
Multiple groups of test data. The first row of each group of data is an integer N (N < = 100), and the second row contains N integers, which are N elements of the row matrix, and each element is between - 127 and 127.
output data
The sum of the largest submatrix, one row for each group.
sample input
10 0 -2 -7 0 -2 11 -4 13 -5 -2
sample output
20
Solution 1
#include <stdio.h>
int N;
int a[105];
int main(){
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++ ){
scanf("%d",&a[i]);
}
int sum=0;
int max=a[0];
for(int i=0;i<N;i++){
sum+=a[i];
if(sum<0)
sum=0;
if(sum>max)
max=sum;
}
printf("%d\n",max);
}
}
Problem B. multi row maximum submatrix and problem
Time limit 1000 ms
Memory limit 64 MB
Title Description
Given n × N matrix, matrix elements are integers between - 127 and + 127. Please find a sub matrix so that the sum of its elements is the largest. For example, given a 4 * 4 matrix 0 - 2 - 7 0 9 2 - 6 2 - 4 1 - 4 1 - 1 8 0 - 2, the maximum submatrix is 9 2 - 4 1 - 1 8, and the sum of the maximum submatrix is 9 + 2 + (- 4) + 1 + (- 1) + 8 = 15
input data
Multiple groups of test data, the first row integer N of each group of test data (N < = 100). Next, there are N lines of elements, N elements per line, and each element is between - 127 and 127.
output data
The sum of the largest sub matrix elements, and each group of test data corresponds to one row.
sample input
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
sample output
15
Solution 1
#include <stdio.h>
#include <string.h>
int n;
int a[105][105];
int temp[105];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++ ){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
int max=-32767;
for(int i=0;i<n;i++){
memset(temp,0,sizeof(temp));
for(int j=i;j<n;j++){
int sum=0; int tempmax=-32767;
for(int k=0;k<n;k++){
temp[k]+=a[j][k];
sum+=temp[k];
if(sum<0) sum=0;
if(sum>tempmax) tempmax=sum;
}
if(tempmax>max) max=tempmax;
}
}
printf("%d\n",max);
}
}
Problem C. Xiao Ming's working plan
Time limit 2000 ms
Memory limit 64 MB
Title Description
As a college student who wants to buy many games but is short of money, Xiao Ming decided to start working to make money this summer vacation. After a period of searching, he found a total of n job advertisements. The date of the i-th job started from li to ri, and he was paid ci yuan in total. Because the time of these jobs conflict with each other, Xiao Ming can participate in at most one job on the same day, and once a job starts, he must work until the end, and can't quit halfway. Now Xiao Ming wants to know how much money he can get from working this summer vacation?
input data
The first line is an integer n(1 ≤ n ≤ 10000001 ≤ n ≤ 1000000), indicating the number of recruitment advertisements. Next, there are n lines in total, and each line has 3 integers li,ri,ci(1 ≤ li ≤ ri ≤ 1000000,1 ≤ ci ≤ 1000000000,1 ≤ ci ≤ 1000000000), indicating the start time, end time and remuneration of the work.
output data
An integer k in a row indicates the maximum amount of money Xiao Ming can get.
sample input
3 1 2 3 3 4 3 2 3 5
sample output
6
Solution 1
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
struct job{
int l,r,w;
}a[1100000];
long long f[1100000];
int n,id;
bool cmp(job x,job y){
return (x.r<y.r )||(x.r==y.r && x.l<y.l);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].w;
}
sort(a+1,a+n+1,cmp);
id=1;
for(int i=1;i<=a[n].r;i++){
f[i]=f[i-1];
while(i==a[id].r&&id<=n){ // There may be multiple projects with the same end time
f[i]=max(f[i],f[a[id].l-1]+a[id].w);
id++;
}
}
cout<<f[a[n].r];
}
Problem D. design of stamp face value
Time limit 1000 ms
Memory limit 128 MB
Title Description
Given an envelope, only N stamps are allowed to be pasted at most. Calculate how to design the face value of stamps under the condition of given M (N + M < = 10) (assuming that the number of all stamps is sufficient), so as to obtain the maximum max, so that each postage value between 1 and Max can be obtained.
For example, N=3, M = 2, if the face value is 1 point and 4 points respectively, Then every postage value between l and 6 points can be obtained (of course, there are 8 points, 9 points and 12 points): if the face value is 1 point and 3 points respectively, every postage value between 1 point and 7 points can be obtained. It can be verified that when N=3 and M = 2, 7 points can obtain the continuous maximum postage value, so MAX=7 and the face value is 1 point and 3 points respectively.
Sample input: two integers in one row, divided into N and M values.
input data
One line, N and m respectively.
output data
Two lines.
The face values of the first kind of stamps are arranged in ascending order, separated by a space.
The second behavior is the maximum.
sample input
3 2
sample output
1 3 max=7
Problem solution 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n,ans,a[1005],b[1005],s[1005];
int stamp(int t)
{
int i,res;
for (i=1; i<=1000; i++) b[i]=1e6;
for (i=1; i<=t; i++) b[a[i]]=1;
res=0;
do
{
res++;
for (i=1; i<=t; i++)
if (res>a[i] && b[res-a[i]]+1<b[res])
b[res]=b[res-a[i]]+1;
}while (b[res]<=m);
return res;
}
void find(int i)
{
int k,z;
z=stamp(i-1);
if (i>n)
{
int ii;
if (z-1>ans)
{
ans=z-1;
for (ii=2; ii<=n; ii++) s[ii]=a[ii];
}
return;
}
for (k=z; k>=a[i-1]+1; k--)
{
a[i]=k;
find(i+1);
}
}
int main()
{
int i;
cin>>m>>n;
a[1]=1;
find(2);
s[1]=1;
for (i=1; i<n; i++)
cout<<s[i]<<" ";
cout<<s[i];
cout<<endl;
cout << "MAX=" << ans<< endl;
return 0;
}
Problem E. missile interception
Time limit 1000 ms
Memory limit 128 MB
Title Description
In order to defend against the missile attack of the enemy, a certain country has developed a missile interception system. However, this missile interception system has a defect: although its first shell can reach any height, each shell in the future can not be higher than the height of the previous one. One day, the radar caught the enemy's missile attack. Since the system is still in the experimental stage, there is only one system, so it may not be able to intercept all missiles.
input data
There is only one line of input data, which contains several data, separated by half angle commas, indicating the height of missiles flying in turn (there are 20 missiles at most, and their height is no more than 3) × 103).
output data
The output data has only one row, which contains two data separated by half width commas. The first data indicates the maximum number of missiles that the system can intercept; The second data indicates how many more such systems must be added to intercept all missiles.
sample input
389,207,155,300,299,170,158,65
sample output
6,1
Solution 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], d1[N], d2[N], n;
int main() {
char ch;
int n=0;
while (1){
cin >> a[++n];
ch= getchar();
if(ch=='\n') break;
};
int len1 = 1, len2 = 1; //The initial length is 1
d1[1] = a[1]; //Used to calculate the length of Non rising sequence
d2[1] = a[1]; //Used to find the length of ascending sequence
for (int i=2; i<=n; i++) { //Enumerate each number from a[2] (a[1] has been added)
if (d1[len1] >= a[i]) d1[++len1] = a[i]; //If the requirements are met (not rising), add d1
else { //Otherwise, replace a number in d1 with a[i]
int p1 = upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) - d1;
d1[p1] = a[i];
}
if (d2[len2] < a[i]) d2[++len2] = a[i]; //ditto
else {
int p2 = lower_bound(d2 + 1, d2 + 1 + len2, a[i]) - d2;
d2[p2] = a[i];
}
}
cout << len1 <<"," << len2-1; //output
return 0; //end
}
The sixth algorithm operation
Problem A. merge
Time limit 1000 ms
Memory limit 128 MB
Title Description
In an orchard, Duoduo has knocked down all the fruits and divided them into different piles according to different kinds of fruits. Dodo decided to put all the fruit into a pile.
Each time, Duoduo can merge two piles of fruits together, and the consumed physical strength is equal to the sum of the weight of the two piles of fruits. It can be seen that after n-1 times of merging, there is only one pile left. The total physical strength consumed by Duoduo in merging fruits is equal to the sum of physical strength consumed in each merging.
Because we have to make great efforts to carry these fruits home, Duoduo should save energy as much as possible when merging fruits. Assuming that the weight of each fruit is 1, and the number of types of fruit and the number of each fruit are known, your task is to design a combined sequence scheme to minimize the energy consumption, and output the minimum energy consumption value.
For example, there are three kinds of fruit, the number is 1, 2 and 9. You can merge piles 1 and 2 first. The number of new piles is 3 and the energy consumption is 3. Then, the new heap is combined with the original third heap to obtain a new heap. The number is 12 and the physical strength is 12. So Duoduo consumes a total of physical strength = 3 + 12 = 15. It can be proved that 15 is the minimum physical expenditure value.
input data
The input includes two lines. The first line is an integer n (1 < = n < 103) and n (1 < = n < 103), indicating the number of types of fruit. The second line contains n integers separated by spaces, and the ith integer AI (1 < = AI < 2 × 103) is the number of fruit type ii.
output data
The output includes a line that contains only one integer, that is, the minimum physical cost value. The input data ensures that this value is less than 231.
sample input
3 1 2 9
sample output
15
Solution 1
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int a[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
priority_queue<int, vector<int>, greater<int>> que;
for(int i = 0; i<n; i++){
cin>>a[i];
que.push(a[i]);
}
if(n==1){
cout<<0;
return 0;
}
int ans = 0;
while(!que.empty()){
int t1 = que.top(); que.pop();
int t2 = que.top(); que.pop();
ans+=t1+t2;
if(que.empty())break;
que.push(t1+t2);
}
cout<<ans;
return 0;
}
Problem B. minimum gap
Time limit 1000 ms
Memory limit 128 MB
Title Description
Given some different one digit numbers, you can select several from these numbers, arrange them in a certain order to form an integer, and arrange the remaining numbers in a certain order to form another integer. The constituent integer cannot start with 0 (unless the integer has only 1 bit).
For example, given six numbers, 0,1,2,4,6,7, you can use them to form a logarithm 10 and 2467. Of course, you can also form many other logarithms, such as 210 and 764204 and 176. Among these logarithms, the absolute value of the difference between the two numbers is 204 and 176, which is 28.
Given N different numbers between 0 and 9, please find out the absolute value of the pair (or pairs) with the smallest absolute value of the difference in each logarithm composed of these numbers?
input data
The first row includes a number T (T ≤ 1000), which is the number of groups of test data.
Each group of data includes two lines. The first line is a number N (2 ≤ N ≤ 10), which represents the number of numbers. The following line contains N different one digit numbers.
output data
Row T, a number in each row, represents the answer to the ith data. The absolute value of the smallest difference.
sample input
2 6 0 1 2 4 6 7 4 1 6 3 4
sample output
28 5
Solution 1
#include<bits/stdc++.h>
using namespace std;
int n;
int a[12];
int vis[12];
void solve(){
cin>>n;
for(int i = 1; i<=n; i++) cin>>a[i];
sort(a+1, a+n+1);
if(n==2){
cout<<a[2]-a[1]<<'\n';
return;
}
if(n&1){
if(a[1]==0) swap(a[1], a[2]);
int x = 0;
for(int i = 1; i<=n/2+1; i++) x = 10*x+a[i];
int y = 0;
for(int i = n; i>=n/2+2; i--) y = 10*y+a[i];
cout<<abs(x-y)<<'\n';
return;
}
int ret = 1e9;
for(int i = 2; i<=n; i++) {
if(a[i-1]==0) continue;
memset(vis, 0, sizeof(vis));
int x = a[i], y = a[i-1];
int l = 1, r = n;
vis[i] = vis[i-1] = 1;
for(int j = 1; j<=n/2-1; j++){
while(vis[l]) l++;
while(vis[r]) r--;
x = 10*x+a[l];
y = 10*y+a[r];
vis[l] = vis[r] = 1;
l++, r--;
}
ret = min(ret, abs(x-y));
}
cout<<ret<<'\n';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tt; cin>>tt;
while(tt--){
solve();
}
return 0;
}
Problem C. God's hobby
Time limit 1000 ms
Memory limit 128 MB
Title Description
We know that the words are filled in according to the cards. In order to test Xiaoshan, God only gave him four cards, but as long as the rhyme is consistent with the cards.
Xiaoshan has thought of N sentences with beautiful artistic conception, and each sentence has a rhyme.
The sentence patterns of qualified words should have the following four kinds of "XXYY", "XYXY", "XYYX", "XXXX", where X or Y represents rhyme.
Now Xiaoshan wants to know that from the N sentences he wants, he can pick out at most a few qualified words in order.
For example, if you choose 1 4 6 8 as a poem, then 7 you can't choose any more.
input data
Of each set of test data
The first row has a number N (N ≤ 4000).
The second line has N positive integers not exceeding 10 ^ {3}. The i-th integer represents the rhyme of the i-th sentence, and the same integer represents the same rhyme.
3030 data n ≤ 100N ≤ 100
output data
For each group of test data, output a line with only one number, indicating that Xiaoshan can pick out a few words at most.
sample input
12 1 2 4 2 3 1 2 2 1 1 2 2
sample output
2
Example description
You can pick up at most two words in the sample. One scheme is as follows:
1 2 4 6/9 10 11 12
Solution 1
#include <iostream>
using namespace std;
int a[10000];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int s=0;
int cnt=0;
int j;
int ans=0;
for(int i=0;i<n;i++){
for(j=s;j<i;j++){
if(a[i]==a[j]){
cnt++;
a[i]=a[j]=0; //Mark used
break;
}
}
if(cnt==2){ //Two pairs of identical numbers
cnt =0;
s=i;
ans++;
}
}
cout<<ans;
return 0;
}
Problem D. task scheduling problem
Time limit 1000 ms
Memory limit 128 MB
Title Description
A unit time task is a task that needs exactly one unit time to complete. Given a finite set s of unit time tasks. A schedule about s is used to describe the execution order of tasks per unit time in S. The first task in the schedule starts at time 0 and ends at time 1, the second task starts at time 1 and ends at time 2,..., and the nth task starts at time n-1 and ends at time n. The unit time task schedule problem with deadline and time delay penalty can be described as follows:
(1) Set of N unit time tasks S={1,2,..., n} (n ≤ 500)
(2) The deadline of task I is d[i], 1 ≤ I ≤ n, 1 ≤ d[i] ≤ n, that is, task I is required to end before time d[i];
(3) The delay penalty of task I is 1 ≤ w[i] < 1000,1 ≤ I ≤ n, that is, if task I does not end before time d[i], it will incur the penalty of w[i]; No penalty if completed on time.
The task schedule problem requires to determine a schedule (optimal schedule) of S to minimize the total time delay penalty.
input data
The first line is a positive integer n, indicating the number of tasks. In the next two lines, each line has n positive integers, representing the deadline and time delay penalty of each task respectively.
output data
The calculated minimum total time error penalty is output
sample input
7 4 2 4 3 1 4 6 70 60 50 40 30 20 10
sample output
50
Solution 1
#include <iostream>
#include <algorithm>
using namespace std;
struct task{
int d,w;
}a[505];
bool cmp(task t1,task t2)
{
return t1.w>t2.w;
}
int main(){
int d[505];
int w[505];
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].d;
int total=0;
for(int i=0;i<n;i++)
{
cin>>a[i].w;
total+=a[i].w;
}
sort(a,a+n,cmp);
int flag[505]={0};
int ans=0;
for(int i=0;i<n;i++){
for(int j=a[i].d-1;j>=0;j--){
if(flag[j]==0){
ans+=a[i].w;
flag[j]=1;
break;
}
}
}
cout<<total-ans;
return 0;
}
Problem E. sqy's tin foil ironing
Time limit 1000 ms
Memory limit 64 MB
Title Description
Not long ago, sqy teacher spent a lot of money to make a handsome tin foil perm. Sqy with a business vision suddenly found a big business opportunity, so he opened his own beauty salon.
sqy found the prophet cbj, who had just finished texture ironing, and predicted the future. She found that every customer only came to the hair salon during the day, and when they first came to the store, they would charge a card worth xi, and then from the next day, they would come here to take care of their hair every day. sqy only charged 1 yuan at the cost price to attract customers until they emptied the card, The customer will never come back.
The black hearted businessman sqy asked the big prophet for the time and amount of each customer's recharge. He was going to run away one night. He wanted to know how much money he could take away at most.
input data
The first line includes an integer n(1 ≤ n ≤ 105), indicating that there are n customers. Next, there are n lines. Each i+1 line includes two integers xi. yi indicates that a customer recharged yi Yuan on day xi (1 ≤ xi ≤ 106,0 ≤ yi ≤ 231 − 1).
output data
The output line includes an integer ans, indicating how much sqy can take away at most.
sample input
5 1 5 2 5 3 5 4 5 5 5
sample output
15
Example description
On the fifth day, the first person's consumption of 4 yuan left 1 yuan, the second person's consumption of 3 yuan left 2 yuan, the third person's consumption of 2 yuan left 3 yuan, the fourth person's consumption of 1 yuan left 4 yuan, and the fifth person ran away with money before he began to consume.
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX 1000010
using namespace std;
long long my_min(long long a,long long b){
if(a<b) return a;
else return b;
}
long long my_max(long long a,long long b){
if(a<b) return b;
else return a;
}
long long in[MAX];//profit
long long out[MAX]; //spend
long long ans =0;
int main(){
for (int i=0;i<1000010;i++)
in[i] = out[i] = 0;
long long n;
scanf("%lld",&n);
long long day,income;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&day,&income);
in[day]+=income;
out[day+1]--;
long long leave=my_min(day+income+1,MAX);
out[leave] ++;
}
long long cur_out=0;//Number of barbers in the day
long long cur_in=0;//Day earnings
for(int i=1;i<=MAX-10;i++){
cur_out+=out[i];
cur_in=cur_in+in[i]+cur_out;
ans=my_max(ans,cur_in);
}
printf("%lld",ans);
return 0;
}
The seventh algorithm operation
Problem A. naval warfare
Time limit 1000 ms
Memory limit 128 MB
Title Description
In this famous game, a fixed number and shape of ships are placed on a square plate, but each ship can't touch other ships. In this problem, we only consider that ships are square, and all ships are square composed of graphics. Write a program to calculate the total number of ships placed on the chessboard.
input data
The first line of the input file consists of two integers R and C separated by spaces, 1 ≤ R,C ≤ 1000,, 1 ≤ R,C ≤ 1000. These two numbers represent the number of rows and columns of the game board respectively. Each of the following r lines contains C characters. Each character can be "#" or ".", "#" means part of a ship, "." Indicates water.
output data
Output one line of solution for each paragraph. If the position of the ship is correct (that is, there are only squares on the chessboard that cannot be contacted with each other. If two "#" ships are adjacent up and down or left and right, but belong to two different ships, they are said to be in contact with each other). Output a paragraph "There are S ships.", S indicates the number of vessels. Otherwise, "Bad placement." is output.
sample input
6 8 .....#.# ##.....# ##.....# .......# #......# #..#...#
sample output
There are 5 ships.
Method 1
- Traverse from left to right and from top to bottom. If it is "#" (indicating that square may appear), take this point as the reference point S(i,j) to enter the next step of judgment
- Scan the single row and column to the right with the reference point and find the maximum length y and width x of "#" in succession.
- Judge whether the region with (i,j) as the top left corner and x,y as the length and width is square and adjacent to other regions, that is, whether the following two conditions are met
- Traverse rows i+1~i+x-1, the continuous width of each row = = x and the value of column j-1 of this row! = '#‘
- Traverse the j~j+x-1 column, the continuous length of each column = = y and the value of the j-1 column! = '#‘
- If not, Bad Placement is output, otherwise ans++
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int m,n;
int x=0, y=0;//Row, number
for (m = i; m < r && a[m][j] == '#'; m++) {
if (j > 0 && a[m][j - 1] == '#')
break;
x++;
}
for (n = j; n < c && a[i][n] == '#'; n++) {
if (i > 0 && a[i - 1][n] == '#')
break;
y++;
}
for (m = i; m < i + x; m++) {
int tx = 0;
for (n = j; n < c && a[m][n]=='#'; n++) {
tx++;
}
if (tx != y)
return 0;
}
for (n = j; n < j + y; n++) {
int ty = 0;
for (m = i; m < r&&a[m][n]=='#'; m++) {
ty++;
}
if (ty != x)
return 0;
}
for (m = i; m < i + x; m++)
for (n = j; n < j + y; n++)
a[m][n] = '.';
ans++;
return 1;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
Method 2
The check function of method 1 has high complexity, and each row and column must be traversed. Method 2 simplifies the judgment by looking for substructures. It can be found that in any 2 * 2 area, if there are 3 #, there must be adjacent ships. Method 2: optimize check.
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
Method 3
In method 3, the dfs algorithm is adopted, that is, all points connected with # are changed to * because they are the same ship during each deep search
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int r,c;
char map[1010][1010];
int fx[4]={0,-1,1,0};
int fy[4]={-1,0,0,1};
int dfs(int x,int y){
map[x][y]='*';
for(int i=0;i<4;i++){
if(x+fx[i]>0 && x+fx[i]<=r && y+fy[i]>0 && y+fy[i]<=c && map[x+fx[i]][y+fy[i]]=='#') dfs(x+fx[i],y+fy[i]);
}
} //Change all points connected with # to * because they are the same ship
int check(int i, int j) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main(){
scanf("%d%d",&r,&c);
int i,j;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
cin>>map[i][j];
}
}
int s=0;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(i<r&&j<c&&check(i,j)==0){
printf("Bad placement.");
return 0; //It's illegal. There's no need to continue later
}
}
}
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(map[i][j]=='#'){
s++;
dfs(i,j);
}//Because it has been ensured that it is legal, now we only need to count the number of ships
}
}
printf("There are %d ships.",s);
return 0;
}
Problem B. class assignments - 9-2
Time limit 1000 ms
Memory limit 64 MB
Title Description
On a plain divided into n*n grids, there are iron ores in some grids. If the two grids are adjacent, they are considered to belong to the same deposit. Each deposit contains one or more iron ores. How many deposits are there in total.
Two grids are adjacent as long as they have common edges or common points.
input data
The first line is a positive integer n, n < = 1000, followed by N lines, each line has n characters, indicating whether there is iron ore at the corresponding position of the plain, * represents no, # represents yes
output data
Number of deposits
sample input
6 *#*### ###*#* *##*** *#**** ***### ******
sample output
2
Example description
The bottom three iron ores belong to one deposit and the other iron ores belong to one deposit, so there are two deposits in total
Method 1
Typical dfs searches around 8 points at a time
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int n;
string a[maxn];
int di[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dj[] = {1, -1, 0, 0, 1, -1, 1, -1};
bool inB(int i, int j){
return 1<=i&&i<=n&&1<=j&&j<=n;
}
void dfs(int i, int j){
a[i][j] = '*';
for(int k = 0; k<8; k++){
int ii = i+di[k], jj = j+dj[k];
if(!inB(ii, jj)||a[ii][jj]=='*') continue;
dfs(ii, jj);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i<=n; i++){
cin>>a[i];
a[i] = " "+a[i];
}
int cnt = 0;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(a[i][j]=='*') continue;
cnt++;
dfs(i, j);
}
}
cout<<cnt;
return 0;
}
Problem C. class assignments - 9-4
Time limit 1000 ms
Memory limit 64 MB
Title Description
As we all know, the eight queens problem is a very classic algorithm problem. Now change the problem to put min(n,m) queens who do not attack each other on the n*m chessboard and ask how many kinds of playing methods there are.
input data
Two positive integers n,m, N and M do not exceed 12
output data
Number of schemes
sample input
2 3
sample output
2
Method 1
Idea: put it row by row, and use the for loop to determine the number of columns in each row. Use check to judge that the placement position of line j does not conflict with lines 1~j-1.
#include <iostream>
using namespace std;
int n, m;
int a[15];
int res = 0;
int check(int i, int j) {
int j1 = j, i1 = i, ok1 = 1;
while ((j1 > 1) && ok1) {
j1--;
if (a[j1] == i)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1 > 1) && (i1 > 1) && ok1) {
j1--; i1--;
if (a[j1] == i1)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1>1) && (i1 < n) && ok1) {
j1--; i1++;
if (a[j1] == i1)
ok1 = 0;
}
return ok1;
}
void queue(int j) {
if (j > m)
{
res++;
}
else {
for (int i = 1; i <= n; i++) {
if (check(i, j)) {
a[j] = i;
queue(j + 1);
}
}
}
}
int main() {
cin >> n >> m;
int temp;
if (n < m) {
temp = n;
n = m;
m = temp;
}
queue(1);
cout << res;
}
Method 2
Idea: dfs
Row by row is placed. Use the for loop to determine each column. Because it is placed row by row, it is impossible to go together. We just need to mark the same column and diagonal. We will find that the sum of rows and columns on a diagonal of the main diagonal is equal to the same constant, and the difference of rows and columns on a diagonal of the sub diagonal is equal to a constant, but it will be negative, To prevent the subscript from being negative, we can add + n.
#include<bits/stdc++.h>
using namespace std;
#define maxn 50
int n, m;
int a[maxn][maxn];
const int bias = 25;
int visc[maxn], vis1[maxn], vis2[maxn];//Indicates whether there is a queen in the main diagonal and negative diagonal of this column
int cnt;
void dfs(int i){
if(i>n){
cnt++;
return;
}
for(int j = 1; j<=m; j++){
if(visc[j]||vis1[i+j]||vis2[i-j+bias]) continue;
visc[j] = vis1[i+j] = vis2[i-j+bias] = 1;
dfs(i+1);
visc[j] = vis1[i+j] = vis2[i-j+bias] = 0;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
if(n>m) swap(n, m);
dfs(1);
cout<<cnt;
return 0;
}
Problem D. class assignments - 8-4
Time limit 1000 ms
Memory limit 64 MB
Title Description
For an undirected graph with n points, m edges, and a starting point s and an ending point t, ask if you can go through some edges from s to T. If you can, output Yes, otherwise output No
Points are numbered from 1 to n
input data
The first line is two positive integers n, m, n < = 1E5, m < = 1E5, and the next M lines are two positive integers t1, t2 for each line, representing that there is an undirected edge from t1 to t2, and the last line is two positive integers s and t
output data
Yes or No
sample input
3 2 1 2 2 3 1 3
sample output
Yes
Method 1
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, m;
vector<int> G[maxn];
int vis[maxn];
void dfs(int u){
if(vis[u]) return;
vis[u] = 1;
for(auto v:G[u]){
dfs(v);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i<=m ;i++){
int u, v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
int s, t; cin>>s>>t;
dfs(s);
cout<<(vis[t]?"Yes\n":"No\n");
return 0;
}
Problem E. 24 point game
Time limit 1000 ms
Memory limit 128 MB
Title Description
A digital poker game was popular all over the world decades ago, and some people still enjoy it. In China, we call this game "counting 24 points". As a player, you will get 4 natural numbers between 1-13 (a instead of 1, J instead of 11, Q instead of 12 and K instead of 13 in playing cards) as operands, and your task is to perform appropriate arithmetic operations on these 4 operands (you can use +, -, *, /, parentheses) to judge whether the operation result is equal to 24. You can output 1 but not 0.
input data
Four cards face value. The face value of the card is separated from the face value of the card by a space.
output data
Output 0 or 1.
sample input
3 8 10 Q
sample output
1
Example description
Q×(10/(8-3))=24
Method 1
#include <iostream>
#include <vector>
using namespace std;
double nums[4];
int vist[4] = {0};
bool dfs(double res) {
double num;
bool last = true;
for (int i = 0; i < 4; ++i) {
if (!vist[i]) {
vist[i] = true;
num = nums[i];
if (res) {
if (dfs(res + num) || dfs(res - num) || dfs(num - res) ||
dfs(res * num) || dfs(res / num) || dfs(num / res)) {
return true;
}
}
else {
if (dfs(num)) {
return true;
}
}
vist[i] = false;
last = false;
}
}
return last && res == 24;
}
int main() {
string tmp;
for (int i = 0; i < 4; ++i) {
cin >> tmp;
if (tmp == "A") {
nums[i] = 1;
} else if (tmp == "J") {
nums[i] = 11;
} else if (tmp == "Q") {
nums[i] = 12;
} else if (tmp == "K") {
nums[i] = 13;
} else {
nums[i] = atoi(tmp.c_str());
}
}
if (dfs(0)) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
return 0;
}