金源走读营-XP03A汇总

YJCH_002

2026-08-09 15:19:32

发布于：北京

30阅读

0回复

0点赞

充满希望的拼接质数1

#include <bits/stdc++.h>
using namespace std;
#define int long long
int isprime(int x){//判断x是否为质数  
	if(x<=1)return 0;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
int a[15];
int n;
int ans;
void dfs(int x,int sum){//第x个水晶选或者不选，得到的总魔力值 
	if(x>n){//n次全部判断完， 
		if(isprime(sum)){
			ans++;
		} 
		return ;
	}
	dfs(x****um+a[x]);//选了
	dfs(x****um); 
}
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	dfs(1,0);
    cout<<ans;
	return 0;
}

质数防护罩

#include <bits/stdc++.h>
using namespace std;
#define int long long
int isprime(int x){//判断x是否为质数  
	if(x<=1)return 0;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
int a[15];
int n;
int ans;
map<string ,int>mp; 
void dfs(int x,int sum,string s){//第x个水晶选或者不选，得到的总魔力值 
	if(x>n){//n次全部判断完， 
		
		if(isprime(sum)&&mp[s]==0){
			mp[s]=1;//如果没有，存起来 
			ans++;
		} 
		return ;
	}
	dfs(x****um+a[x],s+to_string(a[x])+"+");//选了
	dfs(x****um,s); //不选  
}
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
    sort(a+1,a+n+1);//前提条件 
	dfs(1,0,"");
	cout<<ans;
	return 0;
}

迷路的小猫

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int d[100010];//到达每个位置所需要的最小时间 
int vis[100010];//标记到达的所有点 
void bfs(){
	queue<int>q;
	d[n]=0; 
	q.push(n);
	vis[n]=1;
	
	while(q.size()){
		int r = q.front();
		q.pop();
		if(r+1<=100000&&!vis[r+1]){//往右走一格 
			d[r+1]=d[r]+1;
			vis[r+1]=1;
			q.push(r+1);
		}
		if(){//往左走一格 
		}
		if(){//往右*2 
		}
	}
	
}
signed main() {
	cin>>n>>k;
	cout<<d[k]; 
	return 0;
}

彩灯染色

//三叉树有n个结点，求最小高度：
// (1)用第i层节点数量：pow(3,i-1)    需要累加
// (2)log3(2*n+1)  直接套公式


推导(2)
n = 1+3+pow(3,2)+pow(3,3)+pow(3,4)...+pow(3,h-1)  等比求和
n = (pow(3,h)-1)/2;

链路效能极值

注意前缀和与前缀最值的区别
    //1.
	for(int i=1;i<=n;i++){//a[i]+i的前缀和 
		s[i]=s[i-1]+a[i]+i;
	}

    //2.
	//a[i]+i+(a[j]-j) 
	d[0]=INT_MIN;
	for(int i=1;i<=n;i++){//a[i]+i的前缀最值 
		d[i]=max(d[i-1],a[i]+i);
	}


    
	int maxn=INT_MIN;
	for(int j=1;j<=n;j++){
		//从1到j-1中a[i]+i的最大值 
		//for(int i=1;i<=j-1;i++){//a[i]+i的最大值;O(n)
		//	maxn=max（maxn,a[i]+i） 
		//}
		maxn=max(maxn,a[j]-j+d[j-1]);//前缀最值优化O(1) 
	}