(1)题目描述 请看下面的算式: (ABCD - EFGH) * XY = 900 每个字母代表一个0~9的数字,不同字母代表不同数字,首位不能为0。 比如,(5012 - 4987) * 36 就是一个解。 请找到另一个解,并提交该解中 ABCD 所代表的整数。 请严格按照格式,通过浏览器提交答案。 (2)涉及知识点:dfs全排列+简单计算 点击查看代码public class Main04JA01 { /** * @param args */ public static int a[]={0,1,2,3,4,5,6,7,8,9}; public static void main(String[] args) { // TODO Auto-generated method stub dfs(a,0); } public static void dfs(int a[],int k){ if(k==10){ if(check()){ System.out.print(a[0]*1000+a[1]*100+a[2]*10+a[3]); System.out.println(); } }else{ for(int i=k;i<10;i++){ int temp=a[i]; a[i]=a[k]; a[k]=temp; dfs(a,k+1); temp=a[i]; a[i]=a[k]; a[k]=temp; } } } private static boolean check() { // TODO Auto-generated method stub int res1=a[0]*1000+a[1]*100+a[2]*10+a[3]; int res2=a[4]*1000+a[5]*100+a[6]*10+a[7]; int res3=a[8]*10+a[9]; return ((res1-res2)*res3)==900&&a[0]!=0&&a[4]!=0&&a[8]!=0; } } |
(1)题目描述 小明参加了少年宫的一项趣味活动:每个小朋友发给一个空白的骰子(它的6个面是空白的,没有数字),要小朋友自己设计每个面写哪个数字。但有如下要求: 1. 每个面只能填写 0 至 8 中的某一个数字。 2. 不同面可以填写同样的数字,但6个面总和必须等于24。 填好后,小朋友可以用自己填写好数字的骰子向少年宫的两个机器人挑战----玩掷骰子游戏。规则如下: 三方同时掷出自己的骰子,如果出现任何相同的数字,则三方都不计分。 0 0 0 8 8 8 请你替小明算一下,他如何填写,才能使自己得分的概率最大。 请提交小明应该填写的6个数字,按升序排列,数字间用一个空格分开。 如果认为有多个答案,提交字母序最小的那个方案。 请严格按照格式,通过浏览器提交答案。 (2)涉及知识点:dfs+概率运算 (3)分析与解答:这道题我在网上看到有剪枝,其实这道题没有必要,因为数据量很小,即使是六层循环枚举所有情况也非常小,所以直接搜索就可以了,6层循环我还没有试过,考场上没方法的时候不妨尝试一下,反正不会超时。这道题的思路是什么呢,其实很简单,首先枚举,然后只要符合条件的再把比两个机器人数字都大的情况比较出来最后再相乘就可以了,这里其实两个数字应该是要分别除以6的,但是因为不需要求最大的概率结果,所以不需要给自己增加难度。 (4)代码: 点击查看代码public class Main04JA02 { /** * @param args */ static int a[]={0,0,0,8,8,8}; static int b[]={1,1,4,5,6,7}; static int c[]=new int[6]; static int res[]=new int[6]; static int max=0; public static void main(String[] args) { // TODO Auto-generated method stub dfs(0,0,0); for(int i=0;i<6;i++){ System.out.print(res[i]+" "); } System.out.println(); } public static void dfs(int n,int cur,int sum){ if(sum>24){ return; } if(n==6){ if(sum==24){ count(); } return; } for(int i=cur;i<9;i++){ c[n]=i; dfs(n+1,i,sum+i); c[n]=0; } } private static void count() { // TODO Auto-generated method stub int m=0;int x1=0;int x2=0; for(int i=0;i<6;i++){ x1=x2=0; for(int j=0;j<6;j++){ if(c[i]>a[j]){ x1++; } } for(int j=0;j<6;j++){ if(c[i]>b[j]){ x2++; } } m+=x1*x2; } if(m>max){ for(int i=0;i<6;i++){ res[i]=c[i]; } max=m; } } } |
(1)题目描述 古埃及曾经创造出灿烂的人类文明,他们的分数表示却很令人不解。古埃及喜欢把一个分数分解为类似: 1/a + 1/b 的格式。 (2)涉及知识点:双精度运算+暴力枚举 (3)分析与解答:这道题乍看之下非常简单,但是国赛遇到这种题目千万长个心眼,后面可能暗藏着什么陷阱,其实你想想看也知道,国赛A组第三题,怎么可能出这种初学者都会做的题目,这道题目出得非常刁钻。刁钻在哪里,一开始我用的是(double)1/i+(double)1/j==(double)2/45,为了保险我还特地测了一下2/15的答案,结果2/15的答案还凑巧是对的,但是这道题目结果换成2/45就是错的,其实具体原因我也说不清楚,我唯一的理解就是double只有14位小数,运算算不到那么精准吧,当然我也不会误差排除,所以这里换个方法。怎么办呢?其实除是不精确的,但是乘法是一定精确的,所以在个人建议能用乘法尽量不要用除法,所以这里要做的是同分,转换成乘法45*j+45*i=2*i*j,其实这样double类型都不需要了,int型就可以了。 (4)代码: 点击查看代码public class Main04JA03 { private static int ans; /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub for(double i=1;i<=10000;i++){ for(double j=i+1;j<=10000;j++){ if((double)45*j+45*i==(double)2*i*j){ System.out.println(i+" "+j); ans++; } } } System.out.println(ans); } } |
(1)题目描述 闲暇时,福尔摩斯和华生玩一个游戏: (2)涉及知识点:博弈论+dfs (3)分析与解答:博弈论的题目我不太会做,毕竟没系统学过,只能借人家的代码来讲讲思路了,这道题的博弈论思路大概是这样,我们回过头来看看输入,输入数据为2行。第一行是若干空格分开的整数(每个整数介于1~100间),表示当前剩余的所有卡片。第二行也是若干空格分开的整数,表示可以选的数字。当然,第二行的数字必须完全包含在第一行的数字中。 程序则输出必胜的招法!! (4)代码: 点击查看代码import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main04JA04 { /** * @param args */ static int[]num=new int[105]; static ArrayList<Integer>g[]=new ArrayList[105]; static ArrayList<Integer>choice=new ArrayList<>(); public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); String[]s1=scan.nextLine().split(" "); String[]s2=scan.nextLine().split(" "); for(int i=0;i<=100;i++){ g[i]=new ArrayList<>(); } for(String s:s1){ if(!s.equals("")){ num[Integer.parseInt(s)]++; } } for(String s:s2){ if(!s.equals("")){ choice.add(Integer.parseInt(s)); } } for(int i=1;i<=100;i++){ if(num[i]>0){ num[i]--; for(int j=1;j<=100;j++){ if(num[j]>0&&(i%j==0||j%i==0)){ g[i].add(j); } } num[i]++; } } int flag=-1; Collections.sort(choice); for(int x:choice){ num[x]--; if(dfs(x)==1){ flag=x; break; } num[x]++; } System.out.println(flag); } private static int dfs(int u) { // TODO Auto-generated method stub for(int i=g[u].size()-1;i>=0;i--){ int v=g[u].get(i); if(num[v]>0){ num[v]--; int win=dfs(v); num[v]++; if(win==1){ return -1; } } } return 1; } } |
(1)题目描述 X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。 (2)涉及知识点:无向图构建+dfs (3)分析与解答:今年的题目是搜索专题吧,我估计是第四届出题还不熟练,总共6道题4道题考DFS,1道题考双精度运算,1道题考数论,可见DFS在蓝桥杯国赛中还是很重要的,所以必须要熟练掌握才行。这道题其实比上一道题思路简单,只要构建好无向图,对每个点搜索一下就行了,而且这道题目最简单的就是路线是固定死的,只能是两次,那么走三步就可以了,中间不能经过走过的点,也不能回到起点再来一次,那么用访问标记数组就行了,加上没有重边和自环还是很简单的。 (4)代码: import java.util.ArrayList; import java.util.Scanner; public class Main04JA05 { static int n,m,ans=0; static ArrayList<Integer>[]g; static boolean[]vis; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); g=new ArrayList[n+5]; vis=new boolean[n+5]; for(int i=0;i<=n;i++){ g[i]=new ArrayList<>(); } for(int i=1;i<=m;i++){ int a=scan.nextInt(); int b=scan.nextInt(); g[a].add(b); g[b].add(a); } for(int i=1;i<=n;i++){ dfs(i,-1,3); } System.out.println(ans); } private static void dfs(int u, int fa, int step) { // TODO Auto-generated method stub if(step==0){ ans++; return; } for(int v:g[u]){ if(!vis[v]&&v!=fa){ vis[v]=true; dfs(v,u,step-1); vis[v]=false; } } } } |
(1)题目描述 输入n, m, k,输出图1所示的公式的值。其中C_n^m是组合数,表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如图2所示。
(3)分析与解答:这道题我一时半会儿看不懂,毕竟数论没怎么学,附上大佬代码(90%的通过率) https://blog.csdn.net/u010836847/article/details/21166725?utm_source=copy (4)代码: 点击查看代码import java.math.BigInteger; import java.util.Scanner; public class Main04JA06 { /*** * @author 林梵 */ public static BigInteger lucas(BigInteger n,BigInteger m,BigInteger p){ if(m.equals(BigInteger.ZERO)) return BigInteger.ONE; return BigInteger.valueOf(f(n.mod(p).longValue(),m.mod(p).longValue())).multiply(lucas(n.divide(p),m.divide(p),p)).mod(p); } public static long f(long n,long m){ if(m>n) return 1; if(n==m|| m==0) return 1; if(m>n-m) m=n-m; long tmpi=1,tmpn=1,s1=1,s2=1,ans=1; for (int i = 1; i<=m; i++) { tmpi=i; tmpn=n-i+1; s1=s1*tmpi%999101; s2=s2*tmpn%999101; } ans = s2*pow1(s1,999099)%999101; return ans%999101; } public static long pow1(long x,long n) { if(x==1) return 1; if (n==0) return 1; else { while ((n & 1)==0) { n>>=1; x=(x *x)%999101; } } long result = x%999101; n>>=1; while (n!=0) { x=(x *x)%999101;; if ((n & 1)!=0) result =result*x%999101; n>>=1; } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); BigInteger n = new BigInteger(sc.nextLine()); BigInteger m = new BigInteger(sc.nextLine()); int k = Integer.parseInt(sc.nextLine()); long start = System.currentTimeMillis(); BigInteger md = new BigInteger("999101"); long Cnm=lucas(n, m,md).longValue()%999101; long sum = 0; if(Cnm!=0){ int[][] a = new int[k][k]; int h = 1; for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { if (j >= h) a[i][j] =0; else { if (j == 0 || j == h - 1) a[i][j] = 1; else { a[i][j] = (a[i - 1][j - 1]*(h - j)+a[i - 1][j])%999101; } } } h++; } long m1 = 1,n1 =1; long x=n.subtract(new BigInteger(k+"")).mod(md.subtract(BigInteger.ONE)).longValue(); long n3 = pow1(2,x); for (int i = k - 1; i >= 0; i--) { n1=n3*pow1(2,i)%999101; m1 = m1*(n.subtract(new BigInteger((k - 1 - i) + "")).mod(md).longValue())%999101; sum = (sum+m1*a[k - 1][i]*n1)%999101; } sum = sum*Cnm%999101; } System.out.println(sum); long end = System.currentTimeMillis(); System.out.println(end - start); } } |