皆非的万事屋 - 算法
type: channel
link: http://makeyourchoice.cn/category/algorithm/
description: 记录做的算法题和算法比赛
items: 【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
items: 【leetcode】SQL编程题题解
items: 【leetcode】shell编程题题解
items: 【leetcode】多线程编程题题解
items: 【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
items: 【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
items: 【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
items: 【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解
items: 第十二届蓝桥杯——Java软件开发（国赛）总结（20210605）
items: 【ACM】第十三届ACM国际大学生程序设计竞赛感想

【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
type: item
date: 2021-11-20T13:37:00+00:00
description: 更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 153.寻找旋转排序数组中的最小值 二分查找的变种，想这些二分查找变种相关的题目我掌握的实际并不好，需多次练习理解 public int findMin(int[] nums) { int l = 0; int h = nums.length - 1; while (l < h) { int mid = (l + h)/2; if (nums[mid] < nums[h]) { h = mid; }else { l = mid + 1; } } return nums[l]; } 排序 （纯排序题目，这里就不放代码了，之前有） 128. 最长连续序列 题目要求O(n)的时间复杂度，这里先使用Set把元素放入并去重，开始遍历，遍历数为x 如果存在x-1，跳过此次（因为要避免重复计算，要每次从连续数列的第一个开始计算） 存在x+1，继续查找更大的 更新结果 public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } Set<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { set.add(nums[i]); } int res = 0; for (int i = 0; i < nums.length; i++) { int x = nums[i]; if (!set.contains(x-1)) { int cur = 0; while (set.contains(x)) { cur++; x++; } res = Math.max(res, cur); } } return res; } 62.不同路径 经典动规，不多说了 public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } 136.只出现一次的数字 要求时间O(n)，空间O(1)，则使用异或！ 因为0^a=a，a^a=0，所以一个数字连续两次和0异或之后为0 又因为异或操作满足分配律，所以一个数组里的数字连续异或之后，剩余的结果即为只出现一次的数字！ public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } return res; } 240.搜索二维矩阵 II 从右上角开始，向左下开始寻找 public boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length - 1; while (col >= 0 && row < matrix.length) { if (matrix[row][col] == target) { return true; } if (target < matrix[row][col]…

【leetcode】SQL编程题题解
type: item
date: 2021-11-18T02:02:00+00:00
description: 本文将记录力扣SQL下的题目： 除了较多的连接题目以外，有很多的排序题目，需要用到窗口函数 175.组合两个表 很基本的两表关联 SELECT p.FirstName AS firstName, p.LastName as lastName, a.City AS city, a.State AS state FROM Person p LEFT JOIN Address a ON p.PersonId = a.PersonId 176.第二高的薪水 考查LIMIT的使用，同时考虑记录只有一条的情况 SELECT (SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1,1) AS SecondHighestSalary 177.第N高的薪水 这道题给了一个mysql的脚本 CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT BEGIN SET N:=N-1; RETURN ( # Write your MySQL query statement below. SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT N,1 ); END 178. 分数排名 这道题使用窗口函数会很方便 row_number() 在排名是序号连续、不重复，即使遇到表中的两个一样的数值亦是如此 rank() 函数会把要求排序的值相同的归为一组且每组序号一样（序号可能会间断） dense_rank() 排序是连续的，也会把相同的值分为一组且每组排序号一样 ntile(group_num) 将所有记录分成group_num个组，每组序号一样 select Score, dense_rank() over(order by Score desc) 'Rank' from Scores 179.连续出现的数字 数字连续出现三次以上，将同一张表自关联三次 SELECT DISTINCT l1.Num AS ConsecutiveNums FROM Logs l1,Logs l2,Logs l3 WHERE l1.Id = l2.Id - 1 AND l2.Id = l3.Id - 1 AND l1.Num = l2.Num AND l2.Num = l3.Num 181.超过经理收入的员工 自关联作比较 SELECT a.NAME AS Employee FROM Employee AS a JOIN Employee AS b ON a.ManagerId = b.Id AND a.Salary > b.Salary 182.查找重复的电子邮箱 分组之后根据count判断 SELECT Email FROM Person GROUP BY Email HAVING count(Email) > 1 183.从不订购的客户 使用NOT IN SELECT Name Customers FROM Customers WHERE Id NOT IN (SELECT CustomerId FROM Orders) 184.部门工资最高的员工 关键在于WHERE之后的限定，使用两个字段IN一个子查询（ID和最大薪资） SELECT Department.name AS 'Department', Employee.name AS 'Employee', Salary FROM Employee JOIN Department ON Employee.DepartmentId = Department.Id WHERE (Employee.DepartmentId, Employee.Salary) IN (SELECT DepartmentId, MAX(Salary) FROM Employee GROUP BY DepartmentId)

【leetcode】shell编程题题解
type: item
date: 2021-11-18T01:50:00+00:00
description: 本文将记录力扣shell下的题目： shell脚本需要熟悉常见的awk、grep等命令 词频统计 写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率： # 输入 the day is sunny the the the sunny is is # 输出 the 4 is 3 sunny 2 day 1 首先cat命令查看words.txt tr -s ' ' '\n'将空格都替换为换行 实现分词 sort排序将分好的词按照顺序排序 uniq -c 统计重复次数（此步骤与上一步息息相关，-c原理是字符串相同则加一，如果不进行先排序的话将无法统计数目） sort -r 将数目倒序排列 awk '{print $2,$1}' 将词频和词语调换位置打印出来 cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{print $2,$1}' 有效电话号码 给定一个包含电话号码列表（一行一个电话号码）的文本文件 file.txt，写一个单行 bash 脚本输出所有有效的电话号码。 你可以假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字） 你也可以假设每行前后没有多余的空格字符。 解法就是正则匹配 grep -P '^xxxxxxxxx$' file.txt。其中 ^ 是正则的开始，$是正则的结束 (a|b)代表a或者b都可以 对于特殊字符前面要加上\ [0-9]{3}代表数字0-9需要连续出现3次 grep -P '^([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}$' file.txt 转置文件 给定一个文件 file.txt，转置它的内容。 你可以假设每行列数相同，并且每个字段由 ' ' 分隔。 法1： # 获取第一行，然后用wc来获取列数 COLS=`head -1 file.txt | wc -w` # 使用awk依次去输出文件的每一列的参数，然后用xargs做转置 for (( i = 1; i <= $COLS; i++ )) do # 这里col就是在代码里要替换的参数，而它等于$i awk -v col=$i '{print $col}' file.txt | xargs done 法2： awk '{ for (i=1;i<=NF;i++){ if (NR==1){ res[i]=$i } else{ res[i]=res[i]" "$i } } }END{ for(j=1;j<=NF;j++){ print res[j] } }' file.txt awk是一行一行地处理文本文件，运行流程是： 先运行BEGIN后的{Action}，相当于表头 再运行{Action}中的文件处理主体命令 最后运行END后的{Action}中的命令 有几个经常用到的awk常量：NF是当前行的field字段数；NR是正在处理的当前行数。 注意到是转置，假如原始文本有m行n列（字段），那么转置后的文本应该有n行m列，即原始文本的每个字段都对应新文本的一行。我们可以用数组res来储存新文本，将新文本的每一行存为数组res的一个元素。 在END之前我们遍历file.txt的每一行，并做一个判断：在第一行时，每碰到一个字段就将其按顺序放在res数组中；从第二行开始起，每碰到一个字段就将其追加到对应元素的末尾（中间添加一个空格）。 文本处理完了，最后需要输出。在END后遍历数组，输出每一行。注意printf不会自动换行，而print会自动换行。 第十行 打印第十行 ：sed -n '10p' file.txt 打印一到十行 ：sed -n '1,10p' file.txt 查找指定字符 ：grep -n 'KeyWord' file.txt

【leetcode】多线程编程题题解
type: item
date: 2021-11-15T07:53:00+00:00
description: 本文将记录力扣多线程下的题目： 每道题基本都有很多种解法，基本都可以使用变量、Semaphore、CountDownLatch等手段来控制。 1114.按序打印 1.变量控制 class Foo { private volatile int flag = 1; public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); flag = 2; } public void second(Runnable printSecond) throws InterruptedException { while (flag != 2); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); flag = 3; } public void third(Runnable printThird) throws InterruptedException { while (flag != 3); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } 2.Semaphore class Foo { public Semaphore seam_first_two = new Semaphore(0); public Semaphore seam_two_second = new Semaphore(0); public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); seam_first_two.release(); } public void second(Runnable printSecond) throws InterruptedException { seam_first_two.acquire(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); seam_two_second.release(); } public void third(Runnable printThird) throws InterruptedException { seam_two_second.acquire(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } 3.CountDownLatch class Foo { private CountDownLatch second = new CountDownLatch(1); private CountDownLatch third = new CountDownLatch(1); public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); second.countDown(); } public void second(Runnable printSecond) throws InterruptedException { second.await(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); third.countDown(); } public void third(Runnabl…

【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
type: item
date: 2021-11-10T12:59:00+00:00
description: 更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 155.最小栈 使用 辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中 class MinStack { ArrayDeque<Integer> stack; ArrayDeque<Integer> minStack; public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack.push(val); minStack.push(Math.min(val, minStack.peekFirst())); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peekFirst(); } public int getMin() { return minStack.peekFirst(); } } 41.缺失的第一个正数 缺失的正数一定在[1, nums.length+1]中，由于题目限制空间复杂度为O(1)，我们需要修改原数组，结合数组下标的特性来替代哈希表。 public int firstMissingPositive(int[] nums) { int l = nums.length; //将所有小于等于0的数置为l+1 for (int i = 0; i < l; i++) { if (nums[i] <= 0) { nums[i] = l+1; } } for (int i = 0; i < l; i++) { int temp = Math.abs(nums[i]); if (temp <= l) { nums[temp-1] = -Math.abs(nums[temp-1]); } } //寻找下标对应的第一个正数，返回该下标 for (int i = 0; i < l; i++) { if (nums[i] > 0) { return i+1; } } return l+1; } 718.最长重复子数组 这里要注意是连续子数组，不同于字符串的子序列，所以状态转移方程中不相等的情况下：dp[i][j] = 0; 动规：时间O(MN)，空间O(MN) 滑动窗口： O((N+M)×min(N,M)) ，空间 O(1) public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length+1][nums2.length+1]; int res = 0; for (int i = 1; i <= nums1.length ; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i-1] == nums2[j-1]) { dp[i][j] = 1 + dp[i-1][j-1]; } else { dp[i][j] = 0; } res = Math.max(res, dp[i][j]); } } return res; } 234.回文链表 时间…

【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
type: item
date: 2021-11-03T07:50:00+00:00
description: 更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 8.字符串转换整数 (atoi) 自动机 我的代码就是根据题意一步一步判断的，所以非常臃肿，但是根据官方给的自动机解法暂时还没看懂 public int myAtoi(String s) { int j = 0; for (; j < s.length();) { if (s.charAt(j) == ' ') { j++; }else { break; } } s = s.substring(j); if (s.length() <= 0) { return 0; } boolean isNegative = false; int i = 0, res = 0; if (s.charAt(0) == '-' || s.charAt(0) == '+') { if (s.charAt(0) == '-') { isNegative = true; } i = 1; } for (; i < s.length();) { if (s.charAt(i) == '0') { i++; }else { break; } } StringBuilder sb = new StringBuilder(""); for (; i < s.length(); i++) { if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { sb.append(s.charAt(i)); }else { break; } } String str = sb.toString(); if (str.length() != 0) { if (str.length() > 10) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { long l = Long.valueOf(str); if (l > Integer.MAX_VALUE) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { if (isNegative) { return -1*Integer.valueOf(str); } return Integer.valueOf(str); } } } return res; } 2.两数相加 话说真快被链表题搞懵了呀，这个我也是按照纯模拟加法的思路写的，先去判断哪个链表长，然后哦就把短的依次加到长的上面，还要注意进位问题。 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode cul1 = l1; ListNode cul2 = l2; int l1_len = 0; int l2_len = 0; while (cul1 != null || cul2 != null) { if (cul1 != null) { l1_len++; cul1 = cul1.next; } if (cul2 != null) { l2_len++; cul2 = cul2.next; } } ListNode lon = l1; ListNode shor = l2; if (l2_len > l1_len) { lon = l2; shor = l1; } int yu = 0; while (shor != null) { …

【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
type: item
date: 2021-10-29T13:01:00+00:00
description: 更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 92.反转链表II 思路是记录反转部分的前一个节点和后一个节点，将其反转后再连接，思路是这个，但是我在实现上可能麻烦一些： class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode curr = head; ListNode prev = null; ListNode next = curr; int flag = 1; while (flag < right) { if (flag == left - 1) { prev = curr; } curr = curr.next; flag++; } next = curr.next; if (prev == null) { head = reverse(head, left, right); prev = head; }else { prev.next = reverse(prev.next, left, right); } while ( prev.next != null && left <= right) { prev = prev.next; } if (next != null) { if (prev.next != null) { prev.next.next = next; }else { prev.next = next; } } return head; } public ListNode reverse(ListNode head, int left, int right) { if (left == right) { return head; } ListNode prev = null; ListNode curr = head; while (left <= right) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; left++; } return prev; } } 200.岛屿数量 广搜、深搜都可以，这里是深搜+剪枝，不用回溯： class Solution { public int numIslands(char[][] grid) { int res = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { res++; dfs(grid, i, j); } } } return res; } public void dfs(char[][] grid, int x, int y) { grid[x][y] = '0'; if (x < grid.length - 1 && grid[x+1][y] == '1') { dfs(grid, x+1, y); } if (x > 0 && grid[x-1][y] == '1') { dfs(grid, x-1, y); } if (y < grid[0].length - 1 && grid[x][y+1] == '1') { dfs(grid, x, y+1); } if (y > 0 && grid[x][y-1] == '1') { dfs(grid, x, y-1); } } …

【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解
type: item
date: 2021-10-29T12:56:00+00:00
description: 之后博主会出一个系列专门记录CodeTop高频算法题的一个详解，一次更新20道，也就是一页的数量。更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 206.反转链表 这应该是链表里最基础、最常问的一道算法题了，相比链表简单的插入删除要复杂一些，可以根据代码把图画一遍方便理解，但还是容易忘，记住要点是一个 while 循环里四行ListNode的交换操作： public ListNode reverseList(ListNode head) { ListNode prev = null, next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } 146.LRU缓存机制 这道题在Java里可以通过LinkedHashMap实现，但是面试肯定不能这么说，需要使用 哈希表 + 双向链表 ，可以说又是一道大量链表的操作题，有助于锻炼对链表操作的理解： class LRUCache { //双向链表 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; DLinkedNode() {} DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap<>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { if (size >= capacity) { removeTail(); size--; } addToHead(new DLinkedNode(key, value)); size++; }else { node.value = value; moveToHead(node); } } //加入头部 private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; node.next.prev = node; head.next = node; cache.put(node.key, node); } //移动到头部 private void moveT…

第十二届蓝桥杯——Java软件开发（国赛）总结（20210605）
type: item
date: 2021-06-05T08:23:00+00:00
description: [scode type="share"]2021年06月05日中午1点比赛结束[/scode] 第6战蓝桥杯！这应该是博主大学生涯里的最后一次比赛了，总体感觉这次国赛难度比上一次的简单吧。 [scode type="blue"]填空题[/scode] 填空题一共四道，这次做出来了三道，至少做的三道不难： 第一道是输出最大的8位二进制数的十进制————255。 第二道找纯质数，就是这个数字本身是质数，它的十进制的每一位也是质数，从1~20210605一共多少个，我暴力的结果是1903。 第三道是找完全平方数，例如2012年02月02日是2+0+1+2+2+2=9，9是平方数。那么找出2001年1月1日到2021年12月31日有多少，也是一道逻辑题，注意2月28天，闰年（4的倍数）2月29天，剩下的是30/31，最后好像是977吧我暴力的。 最后一道是日常略过，是一棵树求最小权值，赛后听是一道动态规划。（蒙错了） [scode type="blue"]程序设计题[/scode] 第一题把一行字符串全大写输出，水题。 第二题叫作123，给出一个数列112123123412345....，给出两个端点L，R（L<=R），求这个数列中[L,R]的和，灵活使用累加公式Sn = n*(n+1)/2确定出L和R分别在哪个区间，之后区分下情况再通过累加公式的加减即可求出。 第三题给一个随机数列，求特殊区间的个数，这个特殊区间中的所有数字的乘积等于所有数字之后，一开始我以为是双指针，但是发现不对，有感觉像动规，想了一会干脆直接暴力了，拿一点分也行。 第四题是巧克力，一道贪心题，把巧克力价格从小到大排列之后，先从小的吃，注意过期时间，最后求出最低价格。 第五道是括号题目，给一行字符串是一个括号序列，之后给出n个操作，操作分两种，第一种将区间[L,R]内的括号反转，第二种给出左端点L，找出最大的右端点R使得[L,R]是一个合法的括号序列，我是用的暴力，能过一点是一点吧。 第六题叫作异或三角，给一个数n，找出三个数1 <= a,b,c <= n，这三个数要满足两个条件：1. (a^b^c)==0 2.a、b、c可以组成三角形，可以找出多少组。最后时间不多了就直接写了一个三层for交了，希望对一个就行了。 [scode type="blue"]总结[/scode] 总体感觉题目似乎没有去年的国赛难吧，毕竟上次国赛大题我只写了一道，而且第一道还写错了。。。 不过5月初的集训让我感觉收获颇多，很多新的知识这次也都用到了，例如现在做大题都会先留意数据的范围，该用int还是用long，使用Scanner还是BufferedReader，还有自定义比较器。 其中判断括号序列是否合法的办法还是坤坤教给我的，使用replace把"()"替换为""，如果序列合法最后这个字符串肯定会被替换成空字符串的。 之前的3周的集训确实给我这次带来了不小的提升，希望最后的这次蓝桥杯可以完美收官吧。 [scode type="green"]2021年6月8日[/scode] 下午6点多出成绩了，这次依旧是国二 ::aru:blood:: ，可见这次题目确实简单啊，去年我只写了填空题和半道大题就拿了国二。。。 人数分布是这样，国赛JAVA B组获奖人数一共1213人，一等奖62人，二等255人，三等370人，优秀奖525人。 我处在二等的第121名，算是前50%吧，总数里排在183名，在15%，就这样吧，大学里的最后一次比赛了，收官！

【ACM】第十三届ACM国际大学生程序设计竞赛感想
type: item
date: 2021-05-25T00:59:00+00:00
description: 经过三周的算法训练，5月22日早晨我们从新乡坐高铁来到了郑州，前往位于龙子湖周围的河南农业大学，这次我们一共有六个队伍：法外狂徒、三个人的ACM、大聪明、只会心疼哥哥（我）、不写代码等于爱情、铁娘子（女队）。 观光与签到 早上9点多的郑州地铁不是那么拥挤，还有位置可坐，差不多10点左右到了河南农业大学的校门口开始进行签到，这次的队服是蓝色的，教练的衣服是粉红色的，每个参赛人员还有专门的参赛证： [album] [/album] 在校外简单签到之后就进入学校了，不得不说河农大的校门真的比河科院的高档不少，虽然新科的大门也不错，但是老大门确实比较拉跨。而且在进入校门之后有很长的一条直路，两边都是绿化的树木，看起来十分漂亮，而且学校里面交通便利，可以骑单车，学校的整体建筑风格也是偏古欧美那种的（就是有档次(๑•̀ㅁ•́ฅ)）。 [album] [/album] 校园里的街道上有专门的服务人员指路，我们很快就到了第二个签到地点，同时也是我们的比赛地点（如果说这次比赛有哪些不足，就是比赛场地没包一个室内体育馆，而是校内一个个小的实验室，拉跨了）。我们在里面换上队服，一个队站在一起拍个照片（用于最后颁奖时的屏幕展示），上午的签到工作算是结束了。 [album] [/album] 就餐与开幕式 中午在他们学校的食堂吃饭，食堂总体来说也很不错，还有露天的餐桌，我们每人发了40元的餐票，可以在指定餐厅里消费。中午饱餐一顿之后我和李老师还有光岚在室内找了一个地方休息，我同时把电脑拿出来改bug....下午两点开始举行开幕仪式，40分钟的时间暴晒在太阳下面，是真滴热啊。 [album] [/album] 热身赛 举行完开幕仪式就是模拟赛了，让每位参赛队员提前适应比赛环境。这次的比赛形式和之前我参加的ccpc一样，每次做出一道题目之后会有人员走过来给你插上一支气球，每道题都有对应的气球颜色。这次热身赛一共三道题，应该说都是热身题，但我们做的情况并不理想。 第一题就是给出一组数据，选出4个组成一个矩形，输出面积最大值，不能构成矩形输出-1。很明显是一个贪心的题，当时想也没想直接接收完全部数据后使用Arrays.sort排了个序，然后判断输出，结果超时了。行，那就不排序了，在接收的时候就比出最大的两组值，可能也是我比较紧张的问题，错误频出，第一题让我搞了一个小时，错了6次才过，直接给我心态搞炸了。 第二题是一个数论，问题说了一大堆，结果是输出一个值并对17取模，仔细一想那我可以从0试到16全部输出一遍，最坏情况是错了16遍，我便开始试，最后错了7次算是把答案试出来了。 最终我们算是A了两题。 主要还有一部分压力来自于前后两桌，半个小时后桌已经A完三道题走人了，前面那组没过多久也A完走人了（热身赛是两个小时），看着前后两桌都插满了三个气球，被夹在中间的我们着实尴尬，所以心态上有些崩。 整顿与休息 热身赛结束之后又在学校吃了顿饭就回宾馆休息了，晚上把准备好的ACM宝典打印了一份留到第二天用。晚上我们在宾馆也没怎么学习，我倒是把带的笔记本拿出来打了会游戏，要不然这个死沉死沉的玩意就白带了。 第二天早晨早早起床把房退了之后便去学校了，9点开始比赛，我们仨也只是随便吃了点煎包填填肚子。 正式赛 8点半坐在教室里，看了一下周围的墙壁上一共有13只气球，便知晓了这次比赛有13道题目。 9点钟随着哨响，比赛正式开始，我们三个人开始翻阅题册，很惊讶也很高兴的是这次的题目是全中文，不会因为英文而看不懂题目了。随着少康迅速说出某一道题特别简单之后我们开始集中看这道题。由于昨天的热身赛吃了闭门羹，我们今天的对策是三个人必须一起解题，简单题一定不能马虎，争取一遍过没有罚时。 这道题是讲给出一个坐标系（输入为几行字符串），由'*'组成的行或列代表坐标轴，'#'是目标点，求'#'相对于坐标原点(0,0)的位置，基本上可以确定为一道签到题。我们三个人不慌不忙，为了不出错花了20分钟敲出来这道题，又检查了5分钟，最后一遍过。 之后根据排行开始看做的最多的题是A，这也是一个签到题，接收完输入数据后根据题中给的公式做一些判断即可得出结果，但是我们不慌，也还是一点一点认真的敲出了这道题，最后很幸运也是一遍过，我们队的名次位于第100左右，整队的信心大涨。 接着光岚和少康开始一起看“七便士”题目，我根据排行选出另一个做出的题目最多的是最后一题“输入输出”，第一次读题我感觉这道题还是挺麻烦的，有染色端点，染色区间，最后让求最小花费，仅仅看题目给的条件和思路会感觉这道题很麻烦，但是仔细履一遍样例会发现只需把输入数据相减最后相加即可，当时我们三人还又讨论应该不会这么简单吧，但是看看过这道题的人都是一遍过，题目名字叫作“输入输出”，而且题目给的输入量确实比较大，所以当时就赌了一把，直接按一开始的简单思路…