练习Day——9
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
package 前170题;
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
上一篇: 熊孩子的最高境界
下一篇: excel 数据有效性全程详解