当前位置:网站首页>Haut OJ 2021 freshmen week II reflection summary
Haut OJ 2021 freshmen week II reflection summary
2022-07-05 05:20:00 【hunziHang】
problem E: Prime judgement of Niuniu
Problem description :
Niuniu recently learned to judge primes , But Niuniu's friends don't believe that they want to test him , I asked him : Here are two numbers for you a,b, Judge a×b Is it a prime .
Prime numbers are greater than 1 In the positive integer of , A number with only two factors .
(PS:1e11=10 Of 11 Power )
Input :
Enter an integer in the first line T, representative T Group data . Next T That's ok (1<=T<=10), Two integers per line a,b(1<=a,b<=1e11).
Output :
For each line of input, if ,a×b If it is a prime number, output a line YES, Otherwise, output a line NO.
The sample input :
3 2 3 1 7 1 4
Sample output :
NO YES NO
Cause analysis :
Data is too natural to multiply , Also have to long long, a*b As a prime number , Prime numbers are only 1 Multiplied by itself , Therefore, it is only necessary to judge whether there is one of the two numbers 1, And whether the other is a prime number .
Solution :
#include<bits/stdc++.h>
using namespace std;
int prime (long long n)
{
long long i,k=sqrt(n);
if(n==1)
return 0;
if(n==2)
return 1;
for(i=2;i<=k;i++)
{
if(n%i==0)
{
return 0;
}
}
return 1;
}
int main()
{
long long a,b,t;
cin>>t;
while(t--)
{
cin>>a>>b;
if(a==1&&prime(b)||b==1&&prime(a))
{
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
}
}
problem G: The number of cycles of Niuniu
Problem description :
Niuniu knows , In programming , Time complexity needs to be considered , Especially for the part of the loop . for example , If there is... In the code
for(i=1;i<=n;i++) OP ;
So I did n Time OP operation , If there is... In the code
for(i=1;i<=n; i++) for(j=i+1;j<=n; j++) OP;
So I did n*(n-1)/2 Time OP operation .
Niuniu wrote the following code :
for(i=1;i<=n; i++) for(j=i+1;j<=n; j++) for(k=j+1;k<=n;k++)OP;
Now we know n, Niuniu wants to know how many times it has been done OP operation .
Input :
First line input 1 It's an integer T(1<=T<=100), On behalf of T Group data
Next T That's ok , One positive integer per line n(1<=n<=1000)
Output :
For each set of data , Output in one line OP The number of operations .
The sample input :
4 3 4 5 6
Sample output :
1 4 10 20
Cause analysis :
Three for loop , In fact, it is equivalent to 1~n Choose three numbers , That is, arrangement and combination , But pay attention to :
take 5 give an example , take 1 2 3 Only 1 2 3 No, 2 3 1, That is, the ball can only be taken from small to large , namely C(3,5) perhaps
A(3,n)/A(3,3) , C(3,5) It can be understood as the default of three numbers from small to large .
Solution :
1. Yang Hui trigonometrically asks C
#include<bits/stdc++.h>
using namespace std;
const int N = 2000;
int c[N+1][N+1];
void initc()
{
c[0][0] = 1;
for(int i=1; i<=N; i++) {
c[i][0] = 1;
for(int j=1; j<=N; j++)
c[i][j] = (c[i-1][j-1] + c[i-1][j]);
}
}
int main()
{
int t, n;
initc();
cin >> t;
while(t--) {
cin >> n;
cout << c[n][3] << endl;
}
return 0;
}
2. Simplify combinatorial operations .
There is a number for 1~5 Of 5 A little ball , take 3 A little ball , Then there are A(3,5)=60 In this case , But each group appeared 6 Time , Such as 1,2,3 This combination has A(3,3)=6 In this case , But only (1,2,3) This kind meets the requirements , So we can get the formula A(3,n)/A(3,3).
#include<stdio.h>
int main()
{
int n,T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int cnt=0;
cnt=n*(n-1)*(n-2)/6;
printf("%d\n",cnt);
}
}
Sudoku of Niuniu
Problem description :
Niuniu met a 9×9 The Sudoku of , You can help Niuniu judge whether Sudoku is effective . Just follow the rules , Verify that the numbers you have filled are valid .
1. Numbers 1-9 Only once in a row .
2. Numbers 1-9 It can only appear once in each column .
3. Numbers 1-9 Separated by thick solid lines in each 3x3 Only once in the palace .( Pictured )
Cause analysis :
The idea is simple , There are several points to pay attention to .
1. In the array i,j Swap is from row judgment to column judgment .
2. Be careful ans[i][j]==0 When directly continue;
3. When judging the Jiugongge , You can put 9*9 Approximate as 3*3, That is the two one. for from 0~3, Then there is another one in each big room 3*3 Small palace lattice of , namely Add two more cycles ,
for(ii=3*i;ii<3*i+3;ii++)
for(jj=3*j;jj<3*j+j;jj++)
Solution :
、
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,ans[10][10],ii,jj;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
cin>>ans[i][j];
}
for(i=0;i<9;i++)
{
int a[10]={0};
for(j=0;j<9;j++)
{
if(ans[i][j]==0)
continue;
if(a[ans[i][j]]==0)
{
a[ans[i][j]]=1;
}
else if(a[ans[i][j]]>0)
{
printf("no\n");
return 0;
}
}
}
for(i=0;i<9;i++)
{
int a[10]={0};
for(j=0;j<9;j++)
{
if(ans[j][i]==0)
continue;
if(a[ans[j][i]]==0)
{
a[ans[j][i]]=1;
}
else if(a[ans[j][i]]>0)
{
printf("no\n");
return 0;
}
}
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
int a[10]={0};
for(ii=3*i;ii<3*i+3;ii++)
{
for(jj=3*j;jj<3*j+j;jj++)
{
if(ans[ii][jj]==0)
continue;
if(a[ans[ii][jj]]==0)
a[ans[ii][jj]]=1;
else if(a[ans[ii][jj]]>0)
{
printf("no\n");
return 0;
}
}
}
}
}
printf("yes\n");
return 0;
}
reflection :
1. Thinking is not flexible enough , Constantly complicate the problem .
2. Too anxious AC 了 , I didn't notice the details , The first question is wa, See the question clearly .
3. Continue to strengthen the practice of strings
边栏推荐
- Download and use of font icons
- TF-A中的工具介绍
- Unity ugui source code graphic
- Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
- 一个新的微型ORM开源框架
- 2022上半年全国教师资格证下
- Page countdown
- 使用Room数据库报警告: Schema export directory is not provided to the annotation processor so we cannot expor
- 十年不用一次的JVM调用
- YOLOv5-Shufflenetv2
猜你喜欢
Embedded database development programming (VI) -- C API
win10虚拟机集群优化方案
Bucket sort
[to be continued] [UE4 notes] L2 interface introduction
C language Essay 1
The present is a gift from heaven -- a film review of the journey of the soul
小程序直播+電商,想做新零售電商就用它吧!
Merge sort
Generate filled text and pictures
[to be continued] [UE4 notes] L1 create and configure items
随机推荐
Introduction to tools in TF-A
小程序直播+电商,想做新零售电商就用它吧!
BUUCTF MISC
[turn to] MySQL operation practice (III): table connection
Data is stored in the form of table
Count sort
Download xftp7 and xshell7 (official website)
What is the agile proportion of PMP Exam? Dispel doubts
Grail layout and double wing layout
A complete attack chain
xftp7与xshell7下载(官网)
2022年上半年国家教师资格证考试
[speed pointer] 142 circular linked list II
Learning notes of "hands on learning in depth"
Solon Logging 插件的添加器级别控制和日志器的级别控制
Transport connection management of TCP
Research on the value of background repeat of background tiling
对象的序列化
C language Essay 1
2022上半年全国教师资格证下