欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

练习Day——9

程序员文章站 2022-07-08 19:10:23
目录K好数K好数题目描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。输入输入包含两个正整数,K和L。输出输出一个整数,表示答案对1000000007取模后的值。样例输入4 2样例输出7......

K好数

(存疑)
题目描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。

输入
输入包含两个正整数,K和L。

输出
输出一个整数,表示答案对1000000007取模后的值。

样例输入
4 2

样例输出
7

package170;

import java.util.Scanner;

//K好数
public class ALGO_3 {
    public static int mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k= scan.nextInt();
        int l =scan.nextInt();
        int[][] num = new int[101][101];//num[i][j]表示L位K进制数中第i位数大小为j,这样的数有几个
        
        fun(num,k, l);
        scan.close();
    }
    public static void fun(int num[][],int k,int l){
        for (int i = 0; i < k; i++) {
            num[1][i] = 1;//目标数最低位依次初始化为0~k-1,且每一个数只出现一次
        }
        
        for(int i=2;i<=l;i++){//依次确定第2、3、4.....l位的数字
            for (int j = 0; j < k; j++) {
                for (int m = 0; m < k; m++) {
                    if(m-1!=j && m+1!=j){//两位数字不相邻
                        num[i][j]+=num[i-1][m];
                        num[i][j]%=mod;
                    }
                }
            }
        }
        int sum=0;
        for (int i = 1; i < k; i++) {//除去最高位为0的情况
            sum+=num[l][i];
            sum%=mod;
        }
        System.out.println(sum);
    }
}

结点选择

(存很大疑!!这个代码是参考的百度文库一篇答案:https://wenku.baidu.com/view/421185eba6c30c2259019efd.html?fr=search-4。但是我只搞懂了50%,最终得分也只有50%,真是令菜鸡头秃。)
题目描述
有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?

输入
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行,每行描述树上的一条边。

输出
输出一个整数,代表选出的点的权值和的最大值。

样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5

样例输出
12

样例说明
选择3、4、5号点,权值和为 3+4+5 = 12 。

数据规模与约定
对于20%的数据, n <= 20。
对于50%的数据, n <= 1000。
对于100%的数据, n <= 100000。
权值均为不超过1000的正整数。

import java.io.*;
import java.util.*;

public class Main {
	final static int MAXN=10001;
	class Tree{
		int u,v,next;
		Tree(int U,int V,int N){
			u=U;
			v=V;
			next=N;
		}
	}
	int count;
	int dp[][]=new int[MAXN][2];
	Tree t[]=new Tree[MAXN*2];
	int head[]=new int[MAXN];
	int sta[]=new int[MAXN*2];
	boolean vis[]=new boolean[MAXN];
	
	void add(int u,int v) {
		t[count]=new Tree(u,v,head[u]);
		head[u]=count++;
	}
	
	void dfs(int x,int f) {
		Arrays.fill(vis, false);
		int top=0;
		vis[x]=true;
		sta[top++]=x;
		while(top>0) {
			int u=sta[top-1];
			boolean ed=false;
			for(int i=head[u];i+1!=0;i=t[i].next) {
				int v=t[i].v;
				if(vis[v])
					continue;
				ed=true;
				sta[top++]=v;
				vis[v]=true;
			}
			if(ed)
				continue;
			--top;
			for(int i=head[u];i+1!=0;i=t[i].next) {
				int v=t[i].v;
				dp[v][0]+=Math.max(dp[u][0], dp[u][1]);
				dp[v][1]+=dp[u][0];
			}
		}
	}
	
	void run() throws IOException {
		int n=cin.nextInt();
		for(int i=1;i<=n;i++) {
			dp[i][1]=cin.nextInt();
		}
		Arrays.fill(head, -1);
		
		for(int i=1;i<n;i++) {
			int u=cin.nextInt();
			int v=cin.nextInt();
			add(u,v);
			add(v,u);
		}
		
		dfs(1,-1);
		int res=Math.max(dp[1][0], dp[1][1]);
		out.println(res);
		out.close();
	}
    public static void main(String[] args) throws IOException{
    	new Main().run();
    }
    
    Main(){
    	cin=new InputReader(System.in);
    	out=new PrintWriter(System.out);
    }
    
    PrintWriter out;
    InputReader cin;
    
    class InputReader{
    	InputReader(InputStream in){
    		reader=new BufferedReader(new InputStreamReader(in));
    		tokenizer=new StringTokenizer("");
    	}
    	private String next()throws IOException{
    		while(!tokenizer.hasMoreTokens()) {
    			tokenizer=new StringTokenizer(reader.readLine());
    		}
    		return tokenizer.nextToken();
    	}
    	public Integer nextInt()throws IOException{
    		return Integer.parseInt(next());
    	}
    	private BufferedReader reader;
    	private StringTokenizer tokenizer;
    }
}
/*第一行包含一个整数 n 。

接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行,每行描述树上的一条边。

输出格式
输出一个整数,代表选出的点的权值和的最大值。*/

本文地址:https://blog.csdn.net/qiankendeNMY/article/details/107825257

相关标签: 蓝桥杯练习