catalogue
1. Enumeration - Full Permutation
2. Simulation - (3n+1) conjecture
3. Enumeration - clumsy fingers
4. Enumeration - find the number of prime numbers
5. Enumeration - longest non repeating subsequence
8. Simulation happiness derivation
1. Enumeration - Full Permutation
Title: after arranging the N integers 1 ∼ n into a line, randomly disrupt the order and output all possible orders.
Input format:
An integer n.
Output format:
Output all schemes in the order from small to large, one for each line.
First, two adjacent numbers in the same row are separated by a space.
Secondly, for two different lines, the number of corresponding subscripts is compared one by one, and the one with smaller dictionary order is in the front.
Data range 1 ≤ n ≤ 9
Input example:
A set of inputs is given here. For example:
3
Output example:
The corresponding output is given here. For example:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Source code:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
///Retrospective model
int n,m;
int mem[maxn]={0};
int mark[maxn]={0};
void traceback(int pos)
{
if(pos>n)
{
for(int i=1;i<=n;i++)
{
cout<<mem[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
{
if(mark[i]==1)
{
continue;
}
mem[pos]=i;
mark[i]=1;
traceback(pos+1);
mark[i]=0;
}
}
int main()
{
cin>>n;
traceback(1);
return 0;
}
2. Simulation - (3n+1) conjecture
Title: karaz conjecture: for any natural number n, if it is even, cut it in half; If it is odd, cut (3n+1) in half. This has been repeatedly cut down, and finally get n=1 in a certain step. Here, it is not required to prove the theorem, but for any given positive integer n not exceeding 1000, how many steps does it take to get n=1?
Input format:
Each test input contains one test case, which gives the value of the natural number n
Output format:
Output the number of steps required to calculate from n to 1
Input example:
A set of inputs is given here. For example:
3
Output example:
The corresponding output is given here. For example:
5
Source code:
#include<iostream>
using namespace std;
int main(){
int n,step=0;
cin>>n;
while(n != 1){
if(n%2 == 0){
n = n/2;
step++;
}
else{
n = (3*n+1)/2;
step++;
}
}
cout<<step;
return 0;
}3. Enumeration - clumsy fingers
Title: Bessie the cow is learning how to convert numbers between different hexadecimals.
But she always makes mistakes because she can't easily hold the pen with her two front feet.
Whenever Bessie converts a number to a new base and writes down the result, she always writes one of the numbers wrong.
For example, if she converts the number 14 to a binary number, the correct result would be 1110, but she might write 0110 or 1111.
Bessie will not add or delete additional numbers, but may write down numbers with leading zeros due to wrong numbers.
Given the result of Bessie's conversion of the number N to binary and ternary digits, please determine the correct initial value of N (decimal representation).
Input format:
The first line contains the binary representation of N, one of which is wrong.
The second line contains the ternary representation of N, one of which is wrong.
Output format:
Output the correct value of N. 0 ≤ N ≤ 10 ^ 9, and there is a unique solution.
Input example:
A set of inputs is given here. For example:
1010 212
Output example:
The corresponding output is given here. For example:
14
Source code:
#include<iostream>
#include<cstring>
#include <unordered_set>
using namespace std;
int get(string s,int b){
int res =0;
int len =s.size();
for(int i=0;i<len;i++){
int c =s[i]-'0';
res =res*b+c;
}
return res;
}
int main(){
string str,str1;
cin>>str>>str1;
unordered_set<int> S;
int len1 =str.size();
int len2 =str1.size();
for(int i=0;i<len1;i++){
str[i] =str[i]^1;
S.insert(get(str,2));
str[i] =str[i]^1;
}
for (int i = 0; i <len2; i ++ ){
char c =str1[i];
for(int j=0;j<3;j++){
if(c!=j+'0'){
str1[i] =j+'0';
int ans =get(str1,3);
if(S.count(ans)){
cout<<ans<<endl;
return 0;
}
}
}
str1[i] =c;
}
return 0;
}4. Enumeration - find the number of prime numbers
Title: given a positive integer n, please find the number of prime numbers in 1 ∼ n.
Input format:
A total of one line, including integer n.
Output format:
A total of one line, including an integer, representing the number of prime numbers in 1 ∼ n.
Input example:
A set of inputs is given here. For example:
8
Output example:
The corresponding output is given here. For example:
4
Source code:
#include<iostream>
using namespace std;
int ans;
bool isPrime(int a){
if(a<2) return false;
for(int i=2;i<=a/i;i++){
if(a%i==0)
return false;
}
return true;
}
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
if(isPrime(i))
ans++;
}
cout<<ans<<endl;
return 0;
}5. Enumeration - longest non repeating subsequence
Title: given a sequence of integers with length n, please find the longest continuous interval that does not contain repeated numbers and output its length.
Input format:
The first line contains the integer n. The second line contains n integers (all within the range of 0 ∼ 10 ^ 5), representing the sequence of integers.
Output format:
There is one row in total, including an integer, indicating the length of the longest continuous interval that does not contain repeated numbers. Data range 1 ≤ n ≤ 10 ^ 5
Input example:
A set of inputs is given here. For example:
5 1 2 2 3 5
Output example:
The corresponding output is given here. For example:
3
Source code:
#include<iostream>
using namespace std;
const int N=10010;
int n;
int a[N],b[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int kes=0;
for(int i=0,j=0;i<n;i++)
{
b[a[i]]++;
while(b[a[i]]>1)
{
b[a[j]]--;
j++;
}
kes=max(kes,i-j+1);
}
printf("%d",kes);
return 0;
}
6. Simulation - code run time
Title: to get the running time of a C language program, the common method is to call the header file time h. The clock () function is provided to capture the time spent from the beginning of the program to the time when clock () is called. This time unit is clock tick, or "clock strike". There is also a constant CLK_TCK, which gives the number of clock ticks taken by the machine clock per second. Therefore, in order to obtain the running time of a function f, we only need to call clock () before calling f to obtain a clock count C1; After the f execution is completed, call clock() to obtain another clock count C2; The difference (C2-C1) between the clock beats obtained twice is the clock beats consumed by F operation, divided by the constant CLK_TCK, you get the running time in seconds. Here we might as well simply assume the constant CLK_TCK is 100. Given the clock count obtained by the tested function before and after, please give the running time of the tested function.
Input format:
The input gives two integers C1 and C2 in order in one line. Note that the clock points obtained twice must be different, that is, C1 < C2, and the value is [0,10 ^ 7].
Output format:
Output the running time of the tested function in one line. The running time must be output in hh:mm:ss (i.e. 2-bit hour: minute: Second) format; Time less than 1 second is rounded to seconds.
Input example:
A set of inputs is given here. For example:
123 4577973
Output example:
The corresponding output is given here. For example:
12:42:59
Source code:
#include<iostream>
#include<cstdio>
using namespace std;
const int CLK =100;
int main(){
int c1,c2;
scanf("%d%d",&c1,&c2);
int ans =c2-c1;
if(ans%100>=50){
ans =ans/CLK+1;
}
else{
ans =ans/CLK;
}
printf("%02d:%02d:%02d",ans/3600,ans%3600/60,ans%60);
return 0;
}7. Simulation - Happy boxing
Title: Grey Wolf and Jiao wolf meet for the new year and make an appointment to drink together. The method of two people's boxing on the wine table is to shout out a number in each population and draw a number with their hands at the same time. If the number drawn by one is exactly equal to the sum of the numbers shouted by the two, the one who wins will be fined a glass of wine. If two people win or lose together, they will continue to the next round until the only winner appears. Here are the boxing records of Grey Wolf and Jiao wolf. Please count how many glasses of wine they drank in the end.
Input format:
Each test input contains one test case, which gives the value of the natural number n.
Output format:
The first line of input gives a positive integer N (≤ 100), and then N lines. Each line gives a record of one round of boxing. The format is: Grey Wolf calls grey wolf, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana, banana.
Input example:
A set of inputs is given here. For example:
5 8 10 9 12 5 10 5 10 3 8 5 12 12 18 1 13 4 16 12 15
Output example:
The corresponding output is given here. For example:
1 2
Source code:
#include <cstdio>
int main()
{
int n;
scanf("%d", &n);
int a[2], b[2];
int counta = 0, countb = 0;
for(int i = 0; i < n; i++){
scanf("%d%d%d%d", &a[0], &a[1], &b[0], &b[1]);
int temp = a[0] + b[0];
if(a[1] == temp && b[1] == temp){
continue;
}
if(a[1] == temp){
counta++;
}
if(b[1] == temp){
countb++;
}
}
//For the winning times calculated above, the penalty for alcohol is the penalty for the other party
printf("%d %d\n", countb, counta);
return 0;
}8. Simulation happiness derivation
Title: solving the derivative of univariate polynomial.
Input format:
Enter the coefficients and exponents of non-zero terms of polynomials in the way of exponential descent (the absolute values are integers not exceeding 1000). Numbers are separated by spaces.
Output format:
The coefficients and exponents of the nonzero terms of the derivative polynomial are output in the same format as the input. Numbers are separated by spaces, but there must be no extra spaces at the end. Note that the exponent and coefficient of "zero polynomial" are 0, but expressed as 0.
Input example:
A set of inputs is given here. For example:
3 4 5 6
Output example:
The corresponding output is given here. For example:
30 5 12 3
Source code:
#include <iostream>
using namespace std;
int main()
{
int count = 0;
int x, n;
while(cin >> x >> n)
{
if (count == 0)
{
if (n != 0)
{
cout << x*n << " " << n-1;
}
else
{ /* If you start with a polynomial of degree 0 */
cout << "0 0";
}
count ++;
}
else
{
if (n != 0)
{ /* 0 The derivation of degree polynomial will disappear. You only need to operate on polynomials that are not 0 */
cout << " " << x*n << " " << n-1;
}
}
}
return 0;
}#include<stdio.h>
int main()
{
char ch = 0;
int fac[1000] = {},exp[1000] = {};
int i = 0,count = 0;
do
{
scanf("%d %d",&fac[i],&exp[i]);
i++;
}while((ch = getchar()) != '\n');
for(int j = 0 ; j < i;j++ )
{
if(j < i-1)
{
if(exp[j] && 0 != exp[j+1])
{
printf("%d ",fac[j] * exp[j]);
printf("%d ",exp[j] -1);
}
else if(exp[j] && 0 == exp[j+1])
{
printf("%d ",fac[j] * exp[j]);
printf("%d",exp[j] -1);
}
}
else if(j == i -1 && 0 != i-1)
{
if(exp[j])
{
printf("%d ",fac[j] * exp[j]);
printf("%d",exp[j] - 1);
}
}
else
{
if(exp[j])
{
printf("%d ",fac[j] * exp[j]);
printf("%d",exp[j] - 1);
}
else
{
printf("0 0");
}
}
}
return 0;
}