当前位置:网站首页>Individual game 12
Individual game 12
2022-07-05 05:37:00 【Falling spring is only inadvertently】
Individual game 12
Good night, , Theorem of arithmetic series
Title Description
Good evening , Question Maker
If a and d A positive integer for reciprocal , Then the arithmetic sequence a,a+d,a+2d,⋯ Contains an infinite number of primes
This is called Dirichlet's theorem of arithmetic series
for example , from 2 Start and add 3 Arithmetic sequence of , namely
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … ,
Contains infinite primes
2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, … .
Your task is to write a program , For a given positive integer a、d and n Find number... In this arithmetic sequence n Prime number .
Input format
The input contains multiple sets of data
Enter three positive integers for each group a d n, The meaning is as above
a≤9307,d≤346,n≤210
Output format
For each set of data , Output a number , Represents the... In the sequence n Prime number
Ensure that the number of outputs is always less than 1e6
Their thinking :
This question can be obtained by sifting out the table first 2~1e6 All the prime Numbers between , Then for each arithmetic sequence , For each of us a i a_i ai Two points to find whether it is a prime number. If so, add one to the number , If The number reaches n, Output , And stop the cycle .
Code :
#include <stdio.h>
#include <cmath>
#include <cstring>
const int N = 2E6 + 10;
int n ,d,a,cnt;
int prime[N];
bool p[N];
// The meter
void init(){
memset(p,1,sizeof p);
p[0] = p[1] = 0;
cnt = 0;
for(int i = 2;i<N;++i){
if(p[i]){
prime[cnt++] = i;
for(int j = 2*i ;j<N;j+=i)
p[j] = 0;
}
}
}
int main(){
init();
while(~scanf("%d%d%d",&a,&d,&n)){
if(!a&&!n&&!d)break;
int cou = 0,i=0 ,num;
while(1){
num = a + i*d;
int l = 0,r = cnt;
bool flag = 0;
// Two points search
while(l<r){
int mid = l+ r>>1;
if(prime[mid] == num){
flag = 1;
break;
}else if(prime[mid]>num) r = mid;
else
l = mid+1;
}
if(flag) cou ++;
if(cou == n){
printf("%d\n",num);
break;
}
i++;
}
}
return 0;
}
Railway Freight
Title Description
RJ Freight company is a Japanese railway company engaged in freight business , Recently, a switching line was built in haze, Yokohama . The line layout is shown in the figure 1 Shown .
chart 1
The freight train is from 2 to 72 The truck consists of . Yes 26 There are two types of trucks , from 26 A lowercase letter indicates , from “a” To “z”. Cars of the same type cannot be distinguished from each other , And the direction of each car is not important . therefore , The length is 2 To 72 The lowercase character string of is enough to completely represent the configuration of the train .
After arriving at the switching line , The train is divided into two sub trains at any position ( Before entering the storage line ). The direction of each sub train can be reversed ( Use reverse lines ). Last , The two sub trains are connected in any order , To form the final configuration . Please note that , The reverse operation of each sub train is optional .
for example , If the arrival configuration is “abcd”, Then the train will be divided into two sub trains , Respectively 3:1、2:2 or 1:3 Coach compartment . For each split , Possible final configurations are as follows (“+” Indicates the final connection location ):
[3:1]
abc+d cba+d d+abc d+cba
[2:2]
ab+cd ab+dc ba+cd ba+dc cd+ab cd+ba dc+ab dc+ba
[1:3]
a+bcd a+dcb bcd+a dcb+a
Remove duplicates , There may be 12 Different configurations .
Given arrival configuration , Answer the number of different configurations that can be constructed using the above switching lines .
Input format
The input contains multiple sets of data
First, enter a positive integer m It means that there are several groups of data
Next m Line one string per line ( Contains only lowercase letters ), Indicates the sequence when the train enters the station
Output format
For each set of data , Output an integer , Indicates the total number of outbound modes after reversal
Their thinking :
There may be a mathematical solution , But not , cry . But we can simulate this process , Generate all the results because the longest is 72 All stable . Simulation can be used substr() String with two parts , For this string, there are 4 In this case , One is ( double , Not turn over ),( Not turn over , Not turn over ),( Not turn over , double ),( double , double ). There are two cases when connecting, so there are probably 8 Medium condition . Whether the generated string is repeated or not, we can use map To record .
Code :
#include <stdio.h>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
int n;
string s, left, right, nowl, nowr, temp;
int sum ;
map<string, int>vis;
int main() {
while (~scanf("%d", &n)) {
while (n--) {
cin >> s;
vis.clear();
sum = 0;
for (int i = 1; i < s.size(); ++i) {
left = s.substr(0, i), right = s.substr( i );
temp = left + right ;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
temp = right + left ;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
nowl = left, nowr = right;
reverse(nowl.begin(), nowl.end()) ;
temp = nowl + right ;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
temp = right + nowl;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
nowl = left, nowr = right;
reverse(nowr.begin(), nowr.end()) ;
temp = left + nowr ;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
temp = nowr + left;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
nowl = left, nowr = right;
reverse(nowl.begin(), nowl.end()) ;
reverse(nowr.begin(), nowr.end()) ;
temp = nowl + nowr ;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
temp = nowr + nowl;
if ( vis[temp] == 0) {
sum ++;
vis[temp] = 1;
}
}
printf("%d\n", sum);
}
}
return 0;
}
Curling game 2.0
Title Description
stay MM-21 On the planet , After the Olympic Games this year , Curling games are becoming more and more popular . But the rules are somewhat different from ours . The game is played on the ice game board , There is a square grid on the board . They only use one stone . The purpose of the game is to guide the stone from the beginning to the end with the least number of moves .
chart 1 Shows an example of the game board . Some squares may be occupied by obstacles . There are two special squares , That is, the starting point and the ending point , No obstacles .( The start point does not coincide with the end point ) Once the stone starts to move , It will continue to move , Until you hit an obstacle or fall out of the game board . To bring the stone to the goal , You may need to hit a stone against an obstacle , Then throw it again
The movement of stones follows the following rules :
At the beginning of the , The stone stops at the starting point .
The movement of stones is limited to horizontal and vertical directions . Do not move diagonally .
When the stone is still , You can make it move by throwing stones . You can throw it in any direction that is not blocked ( chart 2(a)).
After throwing , The stone will continue to move in the same direction , Until one of the following happens :
A stone hits a stone ( chart 2(b)、(c)).
The stone stopped on the square next to the obstacle it hit .
Then the obstacle disappears .
The stone fell out of the board .
The game failed .
The stone reached the target square .
The stone stopped there , Game success .
In a game , You can't throw stones more than 10 Time . If the stone is 10 The goal is not achieved in the step , The game will end in failure .
According to the above rules , We want to know whether the stone at the beginning can achieve the goal , If possible , We want to know the minimum number of moves needed .
If the initial situation is as shown in the figure 1 Described , Then we move 4 You can reach the target square once , chart 3 Of a,b It represents the changes of the chessboard after the route and movement respectively
Input format
Input no more than 100 Group data , Separated by two spaces 0 End of input
For each group of data, first enter two positive integers separated by spaces w and h It represents the left and right width and upper and lower height of the chessboard respectively
2≤w≤20,1≤h≤20
Next h Every line m Number , Contains only 0 1 2 3 One of them
among
0 Indicates that the square is empty
1 Indicates that there is an obstacle on the square
2 Indicates the starting position
3 Indicates the target location
For example, figure 1 The chessboard in is described as follows
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
Output format
For each set of data , Output the minimum number of moves , If the target location cannot be reached , Output -1
Their thinking :
2 Point is the starting point , stay dfs Pay attention to the process 2 The particularity of point , It is not 1( wall ), Don't just encounter non 1 Always stop at .
Because the curler will stop when it hits the wall , Then the wall disappears . So the graph changes at any time , use dfs The backtracking of can be well solved , Although this question is a bit like bfs, But the picture changes at any time , use bfs Also back up the diagram , The complexity of time and space is greatly improved .
Code :
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f;
const int N = 100;
int dx[4] = {
0, 0, 1, -1}, dy[4] = {
1, -1, 0, 0};
int n, m, sx, sy, res;
int mp[N][N];
void dfs(int x, int y, int step) {
if (step > 10)
return ;
for (int i = 0; i < 4; ++i) {
int xx = x + dx[i], yy = y + dy[i];
if (mp[xx][yy] == 1) // If the first one is all obstacles, change the direction
continue;
// Slide in this direction without obstacles
while (mp[xx][yy] == 0 || mp[xx][yy] == 2 )
xx += dx[i], yy += dy[i];
// The grid that cannot slide is -1 It means crossing the border
if (mp[xx][yy] == -1)
continue;
// Stop when encountering obstacles
if (mp[xx][yy] == 1) {
// Remove this obstacle
mp[xx][yy] = 0;
// Because it's to the grid next to the obstacle , So go back one space
dfs(xx - dx[i], yy - dy[i], step + 1) ;
mp[xx][yy] = 1; // to flash back
}
if (mp[xx][yy] == 3) {
res = min(res, step);
continue;
}
}
}
int main() {
while (~scanf("%d%d", &m, &n)) {
if (!n && !m)
break;
memset(mp, -1, sizeof mp);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
scanf("%d", &mp[i][j]);
if (mp[i][j] == 2)
sx = i, sy = j;
}
res = INF;
dfs(sx, sy, 1);
if (res < INF)
printf("%d\n", res);
else
puts("-1");
}
return 0;
}
边栏推荐
- Sword finger offer 53 - ii Missing numbers from 0 to n-1
- Simply sort out the types of sockets
- Scope of inline symbol
- YOLOv5添加注意力机制
- lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
- Haut OJ 1243: simple mathematical problems
- Kubedm series-00-overview
- CF1634 F. Fibonacci Additions
- Maximum number of "balloons"
- EOJ 2021.10 E. XOR tree
猜你喜欢
Analysis of backdoor vulnerability in remote code execution penetration test / / phpstudy of national game title of national secondary vocational network security B module
Sword finger offer 58 - ii Rotate string left
第六章 数据流建模—课后习题
读者写者模型
Pointnet++ learning
Pointnet++学习
Acwing 4300. Two operations
object serialization
Sword finger offer 09 Implementing queues with two stacks
游戏商城毕业设计
随机推荐
剑指 Offer 53 - II. 0~n-1中缺失的数字
Haut OJ 1241: League activities of class XXX
How can the Solon framework easily obtain the response time of each request?
object serialization
F - Two Exam(AtCoder Beginner Contest 238)
【实战技能】非技术背景经理的技术管理
Sword finger offer 05 Replace spaces
After setting up the database and website When you open the app for testing, it shows that the server is being maintained
Use of room database
Improvement of pointnet++
Using HashMap to realize simple cache
YOLOv5添加注意力機制
个人开发的渗透测试工具Satania v1.2更新
剑指 Offer 53 - I. 在排序数组中查找数字 I
High precision subtraction
卷积神经网络简介
每日一题-搜索二维矩阵ps二维数组的查找
Zzulioj 1673: b: clever characters???
卷积神经网络——卷积层
Sword finger offer 53 - ii Missing numbers from 0 to n-1