L1
L1-1
直接输出可以, C++可能比较麻烦一点, Python和Java都有块形字符串, 语法""" 我是字符串 ! """, 再不济直接PHP复制粘贴也行 !
由于代码过长, 这里不再展示原版, 不过你可以玩玩别的hh
package GPLT_test;
/**
* @Title: L1
* @Author 李浩天
* @Date 2024/3/12 8:21
* @description:
*/
public class L1 {
public static void main(String[] args) {
System.out.println("""
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\\ = /O
____/`---'\\____
.' \\\\| |// `.
/ \\\\||| : |||// \\
/ _||||| -:- |||||- \\
| | \\\\\\ - /// | |
| \\_| ''\\---/'' | |
\\ .-\\__ `-` ___/-. /
___`. .' /--.--\\ `. . __
."" '< `.___\\_<|>_/___.' >'"".
| | : `- \\`.;`\\ _ /`;.`/ - ` : | |
\\ \\ `-. \\_ __\\ /__ _/ .-` / /
======`-.____`-.___\\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
佛曰:
写字楼里写字间，写字间里程序员；
程序人员写程序，又拿程序换酒钱。
酒醒只在网上坐，酒醉还来网下眠；
酒醉酒醒日复日，网上网下年复年。
但愿老死电脑间，不愿鞠躬老板前；
奔驰宝马贵者趣，公交自行程序员。
别人笑我忒疯癫，我笑自己命太贱；
不见满街漂亮妹，哪个归得程序员？
""");
}
}
L1-2
其实这题原来的要求更高一点, 是不允许使用数组的, 不过一般比赛不会卡内存 (除非你代码内存确实消耗太大了), 这里直接让所有数异或, 留下的结果就是答案
package GPLT_test;
import java.util.Scanner;
/**
* @Title: L2
* @Author 李浩天
* @Date 2024/3/12 8:27
* @description:
*/
public class L2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
int x = sc.nextInt();
ans = ans ^ x;
}
System.out.println(ans);
}
}
L1-3
还是比较简单的. 无论什么方法, 只要能存下来就行, 我这里采用的哈希表
这里就不多说了, 我觉得用代码比用文字阐释更清晰
package GPLT_test;
import java.util.HashMap;
import java.util.Scanner;
/**
* @Title: GPLT_test.L3
* @Author 李浩天
* @Date 2024/3/12 8:29
* @description:
*/
public class L3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n + 1];
int mi = Integer.MAX_VALUE, ma = Integer.MIN_VALUE;
HashMap<Integer, Integer> m = new HashMap<>();
for (int i = 1; i <= n; i ++ ) {
int x = sc.nextInt();
m.put(x, m.getOrDefault(x, 0) + 1);
mi = Math.min(mi, x);
ma = Math.max(ma, x);
}
System.out.println(mi + " " + m.get(mi));
System.out.println(ma + " " + m.get(ma));
}
}
L1-4
做题方法应该有很多, 我使用的双指针, 指针收缩的条件就是两边所指的字符不同
package GPLT_test;
import java.util.Scanner;
/**
* @Title: L4
* @Author 李浩天
* @Date 2024/3/12 8:33
* @description:
*/
public class L4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int ans = 0;
int left = 0, right = 0;
while (right < s.length()) {
char x = s.charAt(right);
right ++ ;
if (x != s.charAt(left)) {
ans ++ ;
left = right;
}
}
System.out.println(ans);
}
}
L1-5
诈骗题, 不要被表面所迷惑, 实际答案只存在三种情况, 我们直接面向结果编程就行了
package GPLT_test;
import java.util.Scanner;
/**
* @Title: L5
* @Author 李浩天
* @Date 2024/3/5 21:32
* @description:
*/
public class L5 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[][] ch = new char[3][3];
for (int i = 0; i < 3; i ++ ) {
String s = sc.next();
for (int j = 0; j < 3; j++) {
ch[i][j] = s.charAt(j);
}
}
int n1 = 0;
if (ch[0][0] != 'd') {
n1 ++ ;
}
if (ch[0][1] != 'f') {
n1 ++ ;
}
if (ch[0][2] != 's') {
n1 ++ ;
}
if (ch[1][0] != 'f') {
n1 ++ ;
}
if (ch[2][0] != 's') {
n1 ++ ;
}
int n2 = 0;
if (ch[0][1] != 'd') {
n2 ++ ;
}
if (ch[1][0] != 'd') {
n2 ++ ;
}
if (ch[1][1] != 'f') {
n2 ++ ;
}
if (ch[1][2] != 's') {
n2 ++ ;
}
if (ch[2][1] != 's') {
n2 ++ ;
}
int n3 = 0;
if (ch[0][2] != 'd') {
n3 ++ ;
}
if (ch[1][2] != 'f') {
n3 ++ ;
}
if (ch[2][0] != 'd') {
n3 ++ ;
}
if (ch[2][1] != 'f') {
n3 ++ ;
}
if (ch[2][2] != 's') {
n3 ++ ;
}
System.out.println(Math.min(Math.min(n1, n2), n3));
}
}
L1-6
显然, 这题是让求最多可以圈多少个鸡窝, 给鸡窝排序以后, 从左往右以每个鸡窝开始依次二分, 找到离他最远且符合条件的那个鸡窝然后尝试更新答案就行了
package GPLT_test;
import java.util.Arrays;
import java.util.Scanner;
import java.util.function.Function;
/**
* @Title: L6
* @Author 李浩天
* @Date 2024/3/12 8:44
* @description:
*/
public class L6 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
// long
long[] xi = new long[n + 1];
for (int i = 1; i <= n; i ++ ) {
xi[i] = sc.nextLong();
}
Arrays.sort(xi, 1, n +1);
Function<Integer, Integer> use = i -> {
int l = i, r = n;
while (l < r) {
int mid = l + r + 1>> 1;
if (xi[mid] <= (xi[i] + k)) l = mid;
else r = mid - 1;
}
return r - i + 1;
};
int ma = Integer.MIN_VALUE;
for (int i = 1; i <= n; i ++ ) {
ma = Math.max(ma, use.apply(i));
}
System.out.printf("%.3f\n", ma * 1.0 / n);
}
}
L1-7
这题有小贪心的成分, 如果大家线上写我相信大家可以很快的想出来答案的, 不过线下比赛的话大脑有点宕机, 再加上脑袋有点混乱可能就没写出来了, 直接说贪心结论吧, 我个人认为积累贪心的结论和模型比想贪心为什么正确得来的效率要高一些 ... (个人观点, 想看证明可以网络搜索, 应该会有证明)
结论 : 给输入的数据排序后直接计算和题目中定义的 "排序" 进行计算绝对值之差的和
package GPLT_test;
import java.util.Arrays;
import java.util.Scanner;
/**
* @Title: L7
* @Author 李浩天
* @Date 2024/3/12 8:56
* @description:
*/
public class L7 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] ai = new int[n + 1];
for (int i = 1; i <= n; i ++ ) {
ai[i] = sc.nextInt();
}
long ans = 0;
Arrays.sort(ai, 1, n + 1);
for (int i = 1; i <= n; i ++ ) {
ans += Math.abs(ai[i] - i);
}
System.out.println(ans);
}
}
L1-8
这道题有很多种解决问题的方式, 只要更写出来就行, 这里采用最笨的一种方式 -- 哈希表了
(注意. Java同学直接使用HashMap会被我卡掉, 因为哈希冲突太严重会导致HashMap时间复杂度降到O(n), 所以如果想使用哈希表要用TreeMap)
package GPLT_test;
import com.sun.source.tree.Tree;
import java.io.*;
import java.util.*;
/**
* @Title: L8
* @Author 李浩天
* @Date 2024/3/12 9:02
* @description:
*/
public class L8 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] xi = new int[2 * n + 100];
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 1; i <= 2 * n; i ++ ) {
xi[i] = sc.nextInt();
map.put(xi[i], map.getOrDefault(xi[i], 0) + 1);
}
List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
for (int x : map.keySet()) {
int nu = map.get(x);
if (nu % 2 == 1) {
System.out.println(-1);
return;
}
for (int i = 1; i <= nu / 2; i ++ ) {
l1.add(x);
l2.add(x);
}
}
l1.sort(Integer::compare);
l2.sort(Integer::compare);
Collections.reverse(l1);
Collections.reverse(l2);
for (int x : l1) {
System.out.print(x + " ");
}
System.out.println();
for (int x : l2) {
System.out.print(x + " ");
}
}
}
L2
L2-1
模拟即可, 可以用向量模拟方向, 属于是非常基础的题型
package GPLT_test.g2;
import java.util.Scanner;
/**
* @Title: L1
* @Author 李浩天
* @Date 2024/3/12 13:01
* @description:
*/
public class L1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] nums = new int[n][m];
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
nums[i][j] = sc.nextInt();
}
}
final int[] dx = new int[] {0, 1, 0, -1};
final int[] dy = new int[] {1, 0, -1, 0};
int fx = 0;
int nowX = 0, nowY = 0;
boolean[][] tag = new boolean[n][m];
for (int i = 1; i <= n * m; i ++ ) {
tag[nowX][nowY] = true;
System.out.print(nums[nowX][nowY] + " ");
int a = nowX + dx[fx], b = nowY + dy[fx];
if (a < 0 || a >= n || b < 0 || b >= m || tag[a][b]) {
fx = (fx + 1) % 4;
a = nowX + dx[fx];
b = nowY + dy[fx];
}
nowX = a;
nowY = b;
}
}
}
L2-2
非常常规的搜索问题, 大家应该有属于自己的一套板子, 这里用的深搜, 大家可以自己练习一下宽搜怎么写
package GPLT_test.g2;
import java.util.Scanner;
/**
* @Title: L2
* @Author 李浩天
* @Date 2024/3/12 12:14
* @description:
*/
public class L2 {
static int n, m;
static char[][] g;
static boolean[][] tag;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
g = new char[n][m];
tag = new boolean[n][m];
for (int i = 0; i < n; i ++ ) {
String t = sc.next();
for (int j = 0; j < n; j ++ ) {
g[i][j] = t.charAt(j);
}
}
for (int i = 0; i < n; i ++ ) {
if (i == 0 || i == n - 1) {
for (int j = 0; j < m; j ++ ) {
if (g[i][j] == 'O') {
dfs(i, j);
}
}
} else {
if (g[i][0] == 'O') dfs(i, 0);
if (g[i][m - 1] == 'O') dfs(i, m - 1);
}
}
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
if (tag[i][j]) {
System.out.print("O");
} else {
System.out.print("X");
}
}
System.out.println();
}
}
final static int[] dx = new int[] {1, 0, -1, 0};
final static int[] dy = new int[] {0, 1, 0, -1};
public static void dfs(int x, int y) {
tag[x][y] = true;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || tag[a][b] || g[a][b] == 'X') continue;
dfs(a, b);
}
}
}
L2-3
考察知识点 : 滑动窗口 , 双指针 我们手动用双指针模拟一个窗口, 判断窗口内的字符是否满足 "异位词" 的概念 !
(窗口内的字符用哈希表存, 因为 "异位词" 只关注字符的数量, 而和顺序无关)
package GPLT_test.g2;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
/**
* @Title: GPLT_test.L3
* @Author 李浩天
* @Date 2024/3/12 9:21
* @description:
*/
public class L3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
String p = sc.next();
HashMap<Character, Integer> target = new HashMap<>();
for (int i = 0; i < p.length(); i ++ ) {
char ch = p.charAt(i);
target.put(ch, target.getOrDefault(ch, 0) + 1);
}
int len = p.length();
int left = 0, right = 0;
List<Integer> ans = new ArrayList<>();
HashMap<Character, Integer> window = new HashMap<>();
while (right < s.length()) {
char add = s.charAt(right);
right ++ ;
window.put(add, window.getOrDefault(add, 0) + 1);
while (left <= right - len) {
char del = s.charAt(left);
boolean f = true;
for (char ch : target.keySet()) {
if (!window.getOrDefault(ch, 0).equals(target.get(ch))) {
f = false;
}
}
if (f) {
ans.add(left);
}
window.put(del, window.get(del) - 1);
left ++ ;
}
}
for (int x : ans) {
System.out.print(x + " ");
}
}
}
L2-4
本题的数据比较水, 因为太难的数据不好造, 建议大家去找原题进行补题, 赛时这题只要交了基本就能过 (数据比较水)
不过我们来讨论两种比较常见的思路, 然后对比一下时间复杂度
思路一 : 排序 后直接依次判断, 原题数据范围给到的是 N <= 50000, 排序的事件复杂度是O(n logn), 这种好处就是实现比较容易, 缺点就是很慢, Java同学会被卡掉, 加了快读快写也会被卡
思路二 : 转化为秒后使用差分 和 双指针 时间复杂度是O(n), 缺点很明显, 就是用Java很难实现, 不过C++应该比较容易实现
package GPLT_test.g2;
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.StringTokenizer;
/**
* @Title: L4
* @Author 李浩天
* @Date 2024/3/12 14:15
* @description:
*/
public class L4 {
static BufferedWriter qout = new BufferedWriter(new OutputStreamWriter(System.out)); // 快写
static class DDate {
int h;
int m;
int s;
public DDate(int h, int m, int s) {
this.h = h;
this.m = m;
this.s = s;
}
}
static class BandleDDate {
DDate st;
DDate ed;
public BandleDDate(DDate st, DDate ed) {
this.st = st;
this.ed = ed;
}
}
public static void main(String[] args) throws IOException {
Read sc = new Read();
int n = sc.nextInt();
String[] ss = new String[n];
// sc.nextLine(); 快读后不需要nextLine清空缓存
for (int i = 0; i < n; i ++ ) {
ss[i] = sc.nextLine();
}
BandleDDate[] bandleDDates = new BandleDDate[n];
for (int i = 0; i < n; i ++ ) {
String[] timeSeg = ss[i].split(" - ");
String[] timeDetail1 = timeSeg[0].split(":");
String[] timeDetail2 = timeSeg[1].split(":");
DDate dDate1 = new DDate(Integer.parseInt(timeDetail1[0]), Integer.parseInt(timeDetail1[1]), Integer.parseInt(timeDetail1[2]));
DDate dDate2 = new DDate(Integer.parseInt(timeDetail2[0]), Integer.parseInt(timeDetail2[1]), Integer.parseInt(timeDetail2[2]));
bandleDDates[i] = new BandleDDate(dDate1, dDate2);
}
Arrays.sort(bandleDDates, (o1, o2) -> { // o2有序, o1无序
int h1 = o1.st.h;
int h2 = o2.st.h;
int m1 = o1.st.m;
int m2 = o2.st.m;
int s1 = o1.st.s;
int s2 = o2.st.s;
if (h1 != h2) {
return h1 - h2;
}
if (m1 != m2) {
return m1 - m2;
}
return s1 - s2;
});
for (int i = 0; i < n; i ++ ) {
BandleDDate bandleDDate = bandleDDates[i];
if (i == 0) {
if (bandleDDate.st.h != 0 || bandleDDate.st.m != 0 || bandleDDate.st.s != 0) {
String format = String.format("00:00:00 - %02d:%02d:%02d\n", bandleDDate.st.h, bandleDDate.st.m, bandleDDate.st.s);
qout.write(format);
}
} else {
BandleDDate bandleDDateLast = bandleDDates[i - 1];
if (bandleDDateLast.ed.h != bandleDDate.st.h || bandleDDateLast.ed.m != bandleDDate.st.m || bandleDDateLast.ed.s != bandleDDate.st.s) {
String format = String.format("%02d:%02d:%02d - %02d:%02d:%02d\n", bandleDDateLast.ed.h, bandleDDateLast.ed.m, bandleDDateLast.ed.s, bandleDDate.st.h, bandleDDate.st.m, bandleDDate.st.s);
qout.write(format);
}
}
if (i == n - 1) {
if (bandleDDate.ed.h != 23 || bandleDDate.ed.m != 59 || bandleDDate.ed.s != 59) {
String format = String.format("%02d:%02d:%02d - 23:59:59\n", bandleDDate.ed.h, bandleDDate.ed.m, bandleDDate.ed.s);
qout.write(format);
}
}
}
qout.close();
}
static class Read { // 快读
StringTokenizer st = new StringTokenizer("");
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String next() throws IOException {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws IOException {
return Long.parseLong(next());
}
public String nextLine() throws IOException {
return bf.readLine();
}
}
}
L3
L3-1
考察大家的模拟能力, 话就不多说了, 模拟就行了, 附上我去年写的代码 ! 我也会和大家一起在写一遍练习的 !
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 10010;
/*
松针插满 : 直接输出, 然后下一个
小盒子满了但是推送器上的不符合要求 : 直接输出, 然后下一个
推送器没有松针, 而且小黑盒最上面的不符合要求 : 直接输出, 然后下一个
*/
int n, m, k; // n是推送器上的松枝的数量, m是小盒子能存放的松针片的最大数量
// k为一根松枝上能插的松针片的最大数量
stack<int> hz; // 盒子
queue<int> s; // 松枝
int t[N]; // 推送器
void printque() {
while (s.size()) {
cout << s.front() << ' ';
s.pop();
}
cout << '\n';
}
void solved() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ ) cin >> t[i];
for (int i = 1; i <= n; i ++ ) {
if (s.size() == k) printque();
while (hz.size()) {
if (s.size() == k) printque();
if (!s.size()) {
s.push(hz.top());
hz.pop();
continue;
}
if (s.size() && hz.top() > s.back()) break;
if (s.size() && hz.top() <= s.back()) {
s.push(hz.top());
hz.pop();
continue;
}
}
if (s.size() == k) printque();
if (!s.size()) {
s.push(t[i]);
continue;
}
if (hz.size() == m && s.size() && hz.top() > s.back() && t[i] > s.back()) {
printque();
i -- ;
continue;
}
if (s.size() && t[i] > s.back()) {
hz.push(t[i]);
continue;
}
if (s.size() && t[i] <= s.back()) {
s.push(t[i]);
continue;
}
}
if (s.size() == k) printque();
while (hz.size()) {
if (s.size() == k) printque();
if (s.size() && hz.top() > s.back()) printque();
if (s.size() && hz.top() <= s.back()) {
s.push(hz.top());
hz.pop();
}
if (!s.size()) {
s.push(hz.top());
hz.pop();
}
}
if (s.size()) printque();
return ;
}
signed main() {
IOS;
int t;
t = 1;
// cin >> t;
while (t -- ) solved();
return 0;
}
L3-2
贪心 : 还是老样子, 直接上原题的题解把135. 分发糖果 - 力扣（LeetCode）
package GPLT_test.g3;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
/**
* @Title: L2
* @Author 李浩天
* @Date 2024/3/12 16:49
* @description:
*/
public class L2 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] ratings = new int[n];
for (int i = 0; i < n; i ++ ) {
ratings[i] = sc.nextInt();
}
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for (int i = 1; i < n; i ++ ) {
if (ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i -- ) {
if (ratings[i] > ratings[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < n; i ++ ) {
ans += Math.max(right[i], left[i]);
}
System.out.println(ans);
}
}