2023年十四届蓝桥杯国赛（JavaB组）
2023年十四届蓝桥杯国赛（JavaB组）
- 前言
- A: 互质
- B: 逆元
- C: 玩具
- D: 不完整的等式
- E: 星球
- F: 序列
- G: 电动车
- H: 游戏
- I: 非对称二叉树
- J: 数和游戏
前言
2023.6.16: 出成绩了，国一第15前排靠后，算是完成任务
先简单写写，数据范围可能有小错，等题面出来了再更新
2024.6.1：已更新体面，更新 I 题题解
A: 互质
本题总分：5分
【问题描述】
求出在 [ 1 , 202 3 2023 ] [1,2023^{2023}] [1,20232023]范围内，有多少个整数与 2023 2023 2023 互质，答案对 1 0 9 + 7 10^9+7 109+7取模。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
640720414
md考试时脑抽把 1 1 1 给减掉了，白白丢了 5 5 5 分。。
易得 2023 = 7 ∗ 17 ∗ 17 2023=7*17*17 2023=7∗17∗17，故可以先求出与2023不互质的数，然后总数减去即可。
设 a a a 为因数有7的数， b b b 为因数有17的数， c c c 为因数有7*17=119的数，显然不互质的数的总量为： a + b − c a+b-c a+b−c.
static long fpow(long a,long b) { long res = 1; a%=mod; while(b>0) { if(b%2==1) res = res*a%mod; a = a*a%mod; b/=2; } return res; } static void solve() throws IOException{ long res=fpow(2023,2023); long a = fpow(2023,2023)*fpow(7,mod-2)%mod; long b = fpow(2023,2023)*fpow(17,mod-2)%mod; long c = fpow(2023,2023)*fpow(7*17,mod-2)%mod; res = (res-a-b +c+2*mod)%mod; pw.println(res); }B: 逆元
本题总分：5分
【问题描述】
给定质数 M = 2146516019 M=2146516019 M=2146516019， 求出在 [ 1 , 233333333 ] [1,233333333] [1,233333333]内所有自然数的逆元。则所有逆元的异或和为多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1307261675
快速幂暴力求逆元，逐个异或，比赛时跑了大概10多分钟
static long fpow(long a,long b) { long res = 1; a%=mod; while(b>0) { if(b%2==1) res = res*a%mod; a = a*a%mod; b/=2; } return res; } static void solve() throws IOException{ mod = 2146516019; ans=0; for(int i=1;i long res = fpow(i,mod-2); ans ^=res; } System.out.println(ans); } 1,−⌊ip⌋(p mod i)−1,i=1i=1(mod p) mod = 2146516019; long inv[] = new long[233333335]; inv[1]=1; ans=1; for(int i=2;i inv[i] = (long)(mod-mod/i)*inv[(int)(mod%i)]%mod; ans ^=inv[i]; } pw.println(ans); } static int n,m,mod=(int)998244353,maxn=200005,inf=(int)1e9; static long ans=0,INF=(long)1e18; static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(bf); public static void main(String[]args) throws IOException{ int T = 1; while(T--0) solve(); } static int I() throws IOException{ st.nextToken(); return (int)st.nval; } static void solve() throws IOException{ n = I(); long a[] = new long[maxn]; for(int i=1;i ans += a[i]*a[j]; } System.out.println(ans); } } +,−,∗,/} 四个中的一个。 a , b , c , o p a,b,c,op a,b,c,op 四个中一个会被 ? ? ? 代替，输出被代替的那个数或符号，保证有唯一解。 static int n,m,mod=(int)998244353,maxn=200005,inf=(int)1e9; static long ans=0,INF=(long)1e18; static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(System.out); public static void main(String[]args) throws IOException{ int T = 1; //T = Integer.parseInt(S()); while(T--0) solve(); pw.flush(); } static int I() throws IOException{ st.nextToken(); return (int)st.nval; } static long c1(long a,long b,char op) { if(op=='+') return a+b; if(op=='-') return a-b; if(op=='*') return a*b; return a/b; } static long c2(long a,long b,char op) { if(op=='+') return a-b; if(op=='-') return a+b; if(op=='*') return a/b; return a*b; } static void solve() throws IOException{ String s[] = S().split("="); if(s[1].equals("?")) { long a=0,b=0; char op = ' '; int i=0; for(;i char c = s[0].charAt(i); if(c char c = s[0].charAt(i); b = b*10+(int)(c-'0'); } pw.println(c1(a,b,op)); } else { if(s[0].charAt(0)=='?') { long a=Long.parseLong(s[1]),b=0; char op = ' '; int i=1; op = s[0].charAt(i++); for(;i char c = s[0].charAt(i); b = b*10+(int)(c-'0'); } pw.println(c2(a,b,op)); } else { long a=0,b=0; char op = ' '; int i=0; for(;i char c = s[0].charAt(i); if(c for(;i char c = s[0].charAt(i); b = b*10+(int)(c-'0'); } long c = Long.parseLong(s[1]); if(a+b==c) pw.println("+"); if(a*b==c) pw.println("*"); if(a/b==c) pw.println("/"); if(a-b==c) pw.println("-"); } else { b=Long.parseLong(s[1]); pw.println(c1(a,b,op)); } } } } } p1,p2,...,pn}，小明进攻所需的能量为 E = ∑ i = 2 n d ( p i − 1 , p i ) ∗ w i E=\sum_{i=2}^n d(p_{i-1},p_i)*w_i E=∑i=2nd(pi−1,pi)∗wi，其中 d ( p i − 1 , p i ) d(p_{i-1},p_i) d(pi−1,pi) 表示 p i − 1 , p i p_{i-1},p_i pi−1,pi 两颗星球之间的直线距离。小明想知道进攻所需的最少能量是多少。 static int maxn = 200005,n,m,inf=(int)2e9; static long INF = (long)2e18,ans = 0,mod = (int)1e9+7; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st =new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws IOException{ int T = 1; while(T--0) solve(); pw.flush(); } static final int I() throws IOException { st.nextToken(); return (int)st.nval; } static long[]w=new long[20]; static int []x = new int [20],y=new int [20],z=new int[20]; static double as=INF; static double dis(int i,int j) { if(i==0) return 0; return Math.sqrt(Math.pow(x[i]-x[j], 2)+Math.pow(y[i]-y[j], 2)+Math.pow(z[i]-z[j], 2))*w[j]; } static void solve() throws IOException{ n = I(); for(int i=1;i x[i]=I();y[i]=I();z[i]=I(); } m = 1 for(int i=0;i dp[i][j] = INF; if((j(i-1))%2==1) continue; //集合有 i，跳过 for(int k=1;k if((j(k-1))%2==0) continue; if(dp[i][j] dis(i,k) + dp[k][j^(1b1=d,b2=2d,...,bn=nd}。1,2,3,4}， S 1 = 3 S_1=3 S1=3。2,4,6,8}， S 2 = 4 S_2=4 S2=4。3,6,9,12}， S 3 = 3 S_3=3 S3=3。4,8,12,16}， S 4 = 4 S_4=4 S4=4。 static int maxn = 200005,n,m,inf=(int)2e9; static long INF = (long)2e18,ans = 0,mod = (int)1e9+7; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st =new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws IOException{ int T = 1; //T = I(); while(T--0) solve(); pw.flush(); } static final int I() throws IOException { st.nextToken(); return (int)st.nval; } static int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } static long lcm(int a,int b) { return 1L*a*b/gcd(a,b); } static void solve() throws IOException{ n = I(); for(int i=1;i int a=I(); long x = lcm(a,i); ans += (1L*n*i)/x; } pw.println(ans); } } static int maxn = 200005,n,m,inf=(int)2e9; static long INF = (long)2e18,ans = 0,mod = (int)1e9+7; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st =new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws IOException{ int T = 1; while(T--0) solve(); pw.flush(); } static final int I() throws IOException { st.nextToken(); return (int)st.nval; } static class edge{ int u,v,w; public edge(int a,int b,int c) { u=a;v=b;w=c; } } static int p[] = new int [maxn]; static int find(int x) { if(p[x] == x) return x; return p[x] = find(p[x]); } static Vector Collections.sort(g,(o1,o2)-o1.w-o2.w); int cnt=0; for(edge x:g) { int a=x.u,b=x.v,w=x.w; int aa = find(a),bb = find(b); if(aa!=bb) { p[aa]=bb; ans=w; cnt++; } } if(cnt!=n-1) pw.println(-1); //不连通 else pw.println(ans); } static void solve() throws IOException{ n = I();m=I(); while(m--0) { g.add(new edge(I(),I(),I())); } krus(); } } static int maxn = 2000005,n,m,inf=(int)2e9; static long INF = (long)2e18,ans = 0,mod = (int)1e9+7; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st =new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws IOException{ int T = 1; //T = I(); while(T--0) solve(); pw.flush(); } static final int I() throws IOException { st.nextToken(); return (int)st.nval; } static int a[] = new int [maxn]; static int mi[] = new int [maxn mi[i] = Math.min(mi[i if(l==r) { mx[i]=mi[i]=a[l];return; } int mid=(l+r)/2; build(i if(ll if(ll n = I();m=I(); for(int i=1;i a[i]=I(); } build(1,1,n); long cnt=n-m+1; double ans=0; for(int i=1;i+m-1 int j = i+m-1; ans += query_mx(1,1,n,i,j) - query_mi(1,1,n,i,j); } pw.printf("%.2f\n",ans/cnt); } } hli,hri}⩾k∗min{hli,hri}，则此二叉树为一颗非对称二叉树。其中 l i , r i l_i,r_i li,ri 分别是 i i i 的左儿子和右儿子， h x h_x hx 表示以 x x x 为根的子树高度（如果结点 x x x 不存在视为高度等于 0 0 0）。hli,hri}+1]=∑max{hli,hri}⩾k∗min{hli,hri}dp[lcnt][hli]∗dp[rcnt][hri] static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535); static StreamTokenizer st = new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); static int n,m,maxn=200005,inf = 0x3f3f3f3f; static long ans=0,mod=(int)1e9+7,INF=(long)2e18; public static void main(String[]args) throws IOException{ new Task().main(); pw.flush(); } static int I() throws IOException { st.nextToken(); return (int)st.nval; } static class Task{ void main()throws IOException{ int t=1; //t=I(); while(t--0) solve(); } long [][]dp = new long[44][44]; private void solve() throws IOException { n=I();m=I(); dp[1][1]=1; dp[0][0]=1; for(int i=2;i for(int j=0;j int k=i-j-1; for(int h1=0;h1 for(int h2=0;h2 int mx = Math.max(h1, h2),mi = Math.min(h1, h2); if(mx
