Acwing 2022 daily question

Week 1 Friday Sexy prime ( Selection structure + Prime judgment )

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

bool judge(int n)
{
    
	if(n<2) return 0;
	for(int i=2;i*i<=n;i++)
		if(n%i==0)	
			return 0;
		return 1;
}// Prime judgment 
int main()
{
    
	cin>>n;
	
	if(judge(n)&&judge(n-6))
	{
    
		puts("Yes");
		cout<<n-6;
		return 0;
	}// Find the small matching sexy prime first 
	
	if(judge(n)&&judge(n+6))
	{
    
		puts("Yes");
		cout<<n+6;
		return 0;
	}// Can't find a small matching sexy prime number 
	
	for(int i=n+1;;i++)
	{
    
		if(judge(i)&&judge(i+6)||judge(i)&&judge(i-6))
		{
    
			cout<<"No"<<endl<<i;
			break;
		}
	}// Can't find it. Search later to find a sexy prime 
	
}

Week 4 Sunday The problem of pouring water ( Violent search )

Original link ：
The problem of pouring water

Ideas ：

At the beginning of reading, I naturally thought of bezu theorem and extended Euclid , But after reading the question carefully, I found that it was not the case , After reading the solution carefully, I'll come back to make up the problem .

It's a search question , Violent search All States are ok ;

A,B,C It's all about 0 ~ 4000 It seems that the number of States has 4001³ There are so many ( It's going to explode ), But it's not , Because every transfer must guarantee A cup is empty or a cup is full , In this way, the worst complexity is reduced to $3\ast 2\ast 4000\ast 4000$ It's about 9.6*10⁷ That is to say 1e8

At first, the state of three glasses of water is (0,0,C)

Start pouring water, that is, after the state begins to shift , The transfer direction is

a - b
a - c
b - a
b - c
c - a 
c - b

These six directions , We can transfer according to the meaning of the topic

Note that duplicate states are not counted , The status of each time is (a,b,c),a,b,c Satisfy a+b==c Therefore, as long as we write down the state of two numbers, it is equivalent to indicating the state of these three numbers , We use it set To save the status , When the state is different C It could be the same , Let's use another set Come and save All different C, Statistics C The answer .

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int N = 1e5+7; 

int A,B,C;

typedef pair<int,int>  PII;
set<PII>st;
set<int>ans; 

/* a - b a - c b - a b - c c - a c - b */

void dfs(int a,int b,int c)
{
    
	if(st.count({
    a,b})) return ;
	st.insert({
    a,b});// Record status 
	ans.insert(c);// Record the answers in the current state 
	
	int x;
	
	x=min(a,B-b);
	dfs(a-x,b+x,c);//a - b
	
	x=min(a,C-c);
	dfs(a-x,b,c+x);//a - c
	
	x=min(b,A-a);
	dfs(a+x,b-x,c);//b - a
	
	x=min(b,C-c);
	dfs(a,b-x,c+x);//b - c
	
	x=min(c,A-a);
	dfs(a+x,b,c-x);//c - a
	
	x=min(c,B-b);
	dfs(a,b+x,c-x);//c - b
	
}
int main()
{
    
	while(cin>>A>>B>>C)
	{
    
		ans.clear();
		st.clear();
		
		dfs(0,0,C);
		
		cout<<ans.size()<<endl;
	}
}

summary

Read the questions carefully in the future , You can't look like using a certain idea , The small details of this question are particularly clever , Including its search method ( The transfer of state ), Method of recording , We should study this problem well .

Week 5 Monday Tree search ( Selection structure )

Ideas ：

The first k The left serial number of the layer l yes 2^k-1 Right serial number r yes 2^k-1
Determine whether it is null Judgment n And l Of Size relationship
And when it is not empty , Also pay attention to whether this layer is complete
Attention format
Move left k That is to say × 2^k

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e4+10;

int n,k;
int a[N];

int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	cin>>k;
	
	int r=(1<<k)-1;
	int l=1<<(k-1); 
	
	if(n<l)
	{
    
		cout<<"EMPTY";
	}
	else
	{
    
		r=min(r,n);
		for(int i=l;i<=r;i++)
		{
    
			if(i!=r) cout<<a[i]<<" ";
			else cout<<a[i];
		}
	}
	
}