长春网站建设外包,wordpress管理员表,网址申请注册,wordpress文章时间插件A 滑板上楼梯
贪心
要求最少次数#xff0c;尽量多跳三阶的#xff0c;不能连续跳三阶#xff0c;三阶后面一定要跟着一个一阶#xff0c;相当于直接跳四阶 每次跳四阶都是两步#xff08;3、1#xff09;#xff0c;如果 % 4 之后#xff0c;正好剩下 3 #xff0c…A 滑板上楼梯
贪心
要求最少次数尽量多跳三阶的不能连续跳三阶三阶后面一定要跟着一个一阶相当于直接跳四阶 每次跳四阶都是两步3、1如果 % 4 之后正好剩下 3 则直接跳一个三阶否则要一阶一阶跳
import java.util.Scanner;public class Main {private static int N;private static long n;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextLong();long ans 0;ans n / 4;ans * 2;n % 4;if (n 3) ans 1;else ans n;System.out.println(ans);}
}B 牛牛的加法
字符串模拟加法
两个字符串分别存储两个数字因为没有进位直接从最长的字符串的最后倒序处理即可每次取和的模
/*** author :Changersh* date : 2023/1/14 15:44*/import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N (int) 2e5 10;private static String s;private static int[] a new int[N], b new int[N];public static void main(String[] args) {s sc.next();int x s.length();for (int i 0, j x - 1; j 0; j--, i) {a[i] s.charAt(j) - 0;}s sc.next();int y s.length();for (int i 0, j y - 1; j 0; j--, i) {b[i] s.charAt(j) - 0;}int len Math.max(x, y);for (int i 0; i len; i) {a[i] (a[i] b[i]) % 10;}while (len 0 a[len - 1] 0) len--;for (int i len - 1; i 0; i--) out.print(a[i]);if (len 0) out.println(0);out.close();}
}C 石子合并
贪心
两堆合并得到的价值是两堆价值的和并且拿走少的那堆求最大价值 把所有的都和最大的那个合并即可 注意会溢出要用 long
import java.util.*;public class Main {private static int N (int) 2e5 10, n, m, k;private static int[] a;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();a new int[n];for (int i 0; i n; i) a[i] sc.nextInt();Arrays.sort(a);long ans 0, t a[n - 1];for (int i 0; i n - 1; i) ans (t a[i]);System.out.println(ans);}
}D 黑白边
kruskal 并查集
用 0 代表黑边我们就按这个排序优先选择所有的黑边然后按大小遍历所有的边。 如果该边的两个端点不在同一个集合就用并查集到同一个集合cntcnt记录下该集合中的点的个数 ans记录白边个数因为黑边0白边1直接ansedge.w 即可
import java.io.*;
import java.util.*;
import java.lang.*;class Edge {public Edge(int x, int y, int w) {this.x x;this.y y;this.w w;}int x, y, w;
}public class Main {private static int N (int) 2e5 10, n, m;private static int[] f new int[N];private static Edge[] edges;public static void main(String[] args) {n sc.nextInt();m sc.nextInt();for (int i 0; i n; i) f[i] i; // 初始化edges new Edge[m];for (int i 0; i m; i) {int x sc.nextInt();int y sc.nextInt();int w sc.nextInt();edges[i] new Edge(x, y, w);}Arrays.sort(edges, (a, b) - (a.w - b.w));int cnt 0, ans 0;for (int i 0; i m; i) {int fx find(edges[i].x);int fy find(edges[i].y);if (fx ! fy) {ans edges[i].w;cnt;f[fx] fy;}if (cnt n - 1) break;}if (cnt n - 1) out.println(ans);else out.println(-1);out.close();}private static int find(int x) {if (x ! f[x]) f[x] find(f[x]);return f[x];}
}E 滑板比赛
贪心
将两个人的动作值分别从小到大排序双指针就行计算 牛牛大于牛妹的次数
import java.util.*;public class Main {private static int N (int) 2e5 10, n, m;private static int[] a;private static int[] b;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();a new int[n];b new int[m];for (int i 0; i n; i) a[i] sc.nextInt(); // niufor (int i 0; i m; i) b[i] sc.nextInt(); // meiArrays.sort(a);Arrays.sort(b);int ans 0, l 0, r 0;while (l n r m) {if (a[l] b[r]) {ans;l;r;} else {l;}}System.out.println(ans);}
}F 最好的宝石
不会线段树
G GCD
线性筛求素数
求长尾 k 的最小子集每个长为 k 的子集中都至少有一对 x ygcd(x,y) 1 k 肯定大于所有素数的个数且要包括 1统计素数的时候把 1 也统计上得到ans 这个是所有最大公因数是 1 的此时只要加上一个非素数即可满足条件
结果 ans 1 如果ans n 不满足输出 -1 否则输出 ans
import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N (int) 1e5 10, n, tot;private static int[] p new int[N];private static boolean[] vis new boolean[N];/*** ans 素数个数 1* ans n 时 返回 -1*/public static void main(String[] args) {n sc.nextInt();euler(); // 筛素数int ans 1;for (int i 1; i n; i) {if (!vis[i]) ans; // 素数 }if (ans n) out.println(-1);else out.println(ans);out.close();}private static void euler() {for (int i 2; i n; i) {if (!vis[i]) p[tot] i;for (int j 0; j tot p[j] n / i; j) {vis[i * p[j]] true;if (i % p[j] 0) break;}}}
}H 第k小
堆
只存储最小的 k 个即可
import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N (int) 1e5 10, n, m, k;private static PriorityQueueInteger pq new PriorityQueue((a, b) - (-(a - b)));/*** 发现只需要存储前 k 个即可* 倒序存储 只要 size k 就一直 pop*/public static void main(String[] args) {n sc.nextInt();m sc.nextInt();k sc.nextInt();for (int i 0; i n; i) pq.add(sc.nextInt());int opt;while (m-- 0) {while (pq.size() k) pq.poll();opt sc.nextInt();if (opt 1) {int x sc.nextInt();pq.add(x);}else {if (pq.size() k) out.println(pq.peek());else out.println(-1);}}out.close();}
}I 小游戏
dp
拿和不拿两种状态 选择拿只能拿前面不拿的 选择不拿在前一个 拿和不拿之间取一个 max
import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N (int) 2e5 10, n, m;private static int[] a new int[N];private static long[][] f new long[N][2]; // 选 / 不选/*** dp因为范围小所以遍历整个范围a[i] 存储的是 值为 i 的数的个数*/public static void main(String[] args) {n sc.nextInt();for (int i 0; i n; i) {int x sc.nextInt();a[x];}for (int i 1; i 200000; i) {f[i][0] Math.max(f[i - 1][0], f[i - 1][1]); // 不选前一个可选可不选f[i][1] f[i - 1][0] a[i] * i;}out.println(Math.max(f[200000][0], f[200000][1]));;out.close();}
}J 区间异或
二分
区间长度是 3000可以预处理出来每个区间的异或和放到b中 b[i] 存的是区间长度为 i 的最大的异或和
因为要求异或和大于 x 的最小区间则小区间的异或值如果大于大区间则是覆盖了大区间的我们两两取最大值可以构造出来一个递增的序列满足了二分答案的条件对于每此询问二分答案即可。
import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N (int) 2e5 10, n, m;private static int[] a new int[N];private static int[] b new int[N];/*** 预处理区间的异或和*/public static void main(String[] args) {n sc.nextInt();m sc.nextInt();for (int i 1; i n; i) a[i] sc.nextInt();// 预处理for (int i 1; i n; i) {int ans 0;for (int j i; j n; j) {ans ^ a[j];b[j - i 1] Math.max(b[j - i 1], ans);}}// 取自己和前面的最大值得到一个非递减的序列for (int i 2; i n; i) b[i] Math.max(b[i], b[i - 1]);while (m-- 0) {int x sc.nextInt();if (x b[n]) {out.println(-1);continue;}int l 1, r n;int ans -1;while (l r) {int mid l ((r - l) 1);if (b[mid] x) {r mid - 1;ans mid;}else l mid 1;}out.println(ans); // 长度从 0 开始了}out.close();}
}
