果子acwing 148
Acwing.第126场周赛
Acwing.第126场周赛 比赛链接 之前忘记整理上传了,不能有遗留问题 A.蜗牛爬井 蜗牛在 n米深的井底往上爬,每天清晨到傍晚向上爬 5米,夜间又滑下来 4米,请问像这样从某天清晨开始,第几天爬到井口? 输入格式 一个正整数 n。 输出格式 一个整数,表示爬到井口的天数。 思路: 就是一个比较 ......
acwing367证明
首先,\(max(p,q)\)是下界,因为连一条边最多只能减少一个零入度点和一个零出度点,而最终的图不可能有哪怕一个零出度点或者零入度点(最后的图刚好就是一个点) 根据这个下界,我们也很容易可以构造出来一种方法,让零出度点和另一个SCC的零入度点相连即可,就像下面一样(红色边是添加的边) ......
acwing318 划分大理石
有价值分别为 1..6 的大理石各 a[1..6] 块,现要将它们分成两部分,使得两部分价值之和相等,问是否可以实现。 其中大理石的总数不超过 20000 。 输入格式 输入包含多组数据! 每组数据占一行,包含 6 个整数,表示 a[1]∼a[6] 。 当输入为 0 0 0 0 0 0 时表示输入结 ......
对acwing355异象石引理的证明
首先我们抽象一下这道题的模型,然后把引理记住 模型:对于一棵树上选定的一些点,把他们连通起来的最小边数 我们先考虑一种朴素做法,对于任何一种方案,任取其中两个点,那么这个方案一定包含这两个点之间的路径 就是说,我们依次添加每个点,对于每一个新添加进来的点,让这个点与其已经添加的点求路径,然后把路径上 ......
Acwing 最长上升子序列
题目 给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N。 第二行包含 N 个整数,表示完整序列。 输出格式 输出一个整数,表示最大长度。 数据范围 1≤N≤1000 −10^9≤数列中的数≤ 10^9 输入样例: 7 3 1 2 1 8 5 6 ......
Acwing 800.数组元素的目标和,双指针初步
Acwing 800.数组元素的目标和 给定升序的有序数组A(长度为n),B(长度为m)以及目标值x,求出满足\(A[i] + B[j] = x\)的数对\((i,j)\),题目保证仅有 唯一解 输入样例: 4 5 6 1 2 4 7 3 4 6 8 9 输出样例: 1 1 双指针来做 定义指针i, ......
题解 AcWing 1272. 与众不同
题目描述 定义完美序列:若一个序列内没有重复的数,称这个数列为完美数列。 每次给定一个区间 \([l,r]\),求这个区间内最长的完美序列长度。 具体思路 设 \(len_i\) 表示从 \(i\) 出发往右的最长完美序列长度。 我们定义一个指针 \(st\),表示当前枚举的区间左端点,同时定义多一 ......
Acwing.第125场周赛
比赛链接 数量 给定一个正整数 n,请你计算[1,n]范围内一共有多少个正整数满足能被 2整除,但不能被 3整除。 输入格式 一个正整数 n。 输出格式 一个整数,表示满足条件的整数的数量。 数据范围 前 3个测试点满足 1≤n≤100。 所有测试点满足 1≤n≤10000。 思路: 一个比较简单的 ......
题解 AcWing 359.创世纪
题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图,若选了当前节点,那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树,因此考虑基环树 dp。 我们先不管环的条件,先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选,最多 ......
acwing322消木块
这个题目就当一个见识吧 设f[i][j][k]表示当前的状态是[i,j]并且j后面还有k个与j颜色相同的木块的最大价值 第一种情况,当第j块和第j-1块颜色相同时,f[i][j][k]=f[i][j-1][k+1] 第二种情况,当第j块和第j-1块颜色不同时,考虑最后那一堆颜色相同的怎么消去的 如果 ......
题解 AcWing 1078 旅游规划
题目描述 给你一棵树,让你判断树上每个节点是否在树的直径上。 树的直径:树上最远的两个点之间的距离。 树的直径可能不止一条。 具体思路 对于树的直径,我们有三种求法。 树形dp 设 \(d_x\) 表示 \(x\) 往下走能够到达最远距离,\(f_x\) 表示经过 \(x\) 的最长链的长度。 那么 ......
AcWing 126. 最大的和
\(AcWing\) \(126\). 最大的和 关键字 最大子段和,有一维和二维两种情况 一维:\(O(N)\) 二维:\(O(n^3)\) 一、题目描述 给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为 \(1×1\) 或更大的连续子阵列。 矩形的总和是该矩形中所有元素的总和。 在 ......
Acwing.第123场周赛
Acwing.第123场周赛 比赛链接 回家休息了五天调整好状态继续出发!!!! A.队列 一共有三个队列,当前分别已有 a,b,c个人。 现在有 n个人尚未进队,每个人都需要被安排到一个队列当中。 为了队形整齐,我们希望所有人被安排进队后,三个队列包含的人数均相等。 请你判断,是否可能做到。 输入 ......
AcWing_1_1_785_快速排序
一、题目描述 给定你一个长度为 n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n。 第二行包含 n 个整数(所有整数均在 \(1∼10^9\) 范围内),表示整个数列。 输出格式 输出共一行,包含 n 个整数, ......
Go每日一库之148:base64Captcha(多种形式验证码)
[Base64captcha](https://github.com/mojocn/base64Captcha) 几行代码就可以定义自己内容的图形验证码库,支持任意unicode字符的内容. ## 1. 文档&Demo - [English](https://godoc.org/github.com ......
《看了受制了》第二十九天,7道题,合计148道题
2023年9月28日 好尴尬啊,好尴尬啊,怎么就想不到呢?今天的C、D思路都是来源于知乎大佬。 【 >此篇博客解析< 】 Acwing1275 最大数 题目理解 线段树,板子题。但是需要转化!! 每次添加一个数,看作在flag + 1的位置上,修改一个数 然后query是求l 到 flag的最大值 ......
AcWing 431. 守望者的逃离
\(AcWing\) \(431\). 守望者的逃离 一、题目描述 恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。 守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。 为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。 到那时,岛上的所有人都会遇难 ......
AcWing 414. 数字游戏
\(AcWing\) \(414\). 数字游戏 一、题目描述 丁丁最近沉迷于一个数字游戏之中。 这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。 游戏是这样的,在你面前有一圈整数(一共 \(n\) 个),你要按顺序将其分为 \(m\) 个部分,各部分 ......
[Go 夜读 第 148 期] Excelize 构建 WebAssembly 版本跨语言支持实践
本期分享将对 Excelize 的 2023 年部分更新背后的技术点、Go 1.21.0 版本中 XML 标准库的兼容性问题,以及如何构建 WebAssembly 版本跨语言支持展开讨论。 ......
AcWing 463. 求和
\(AcWing\) \(463\). 求和 一、题目描述 一条狭长的纸带被均匀划分出了 \(n\) 个格子,格子编号从 \(1\) 到 \(n\)。 每个格子上都染了一种颜色 \(color_i\)(用 \([1,m]\) 当中的一个整数表示),并且写了一个数字 \(number_i\)。 定义一 ......
第九十八场周赛. AcWing 4949. 末尾连续0
第九十八场周赛. AcWing 4949. 末尾连续0 给定一个正整数 \(m\),请你统计一共有多少个正整数 \(n\) 满足,\(n\) 的阶乘的末尾连续 \(0\) 的数量恰好为 \(m\)。 输出满足条件的 \(n\) 的数量以及所有满足条件的 \(n\)。 例如,当 \(m=1\) 时,满 ......
第九十八场周赛. AcWing 4948. 大乘积
第九十八场周赛. AcWing 4948. 大乘积 我们规定,如果一个非负整数 \(a\) 满足以下两个条件之一,则称 \(a\) 为美丽数: \(a=0\) \(a=10^x\),其中 \(x\) 为任意非负整数。 给定 \(n\)个非负整数 \(a_1,a_2,…,a_n\),这其中有至少 \( ......
Acwing 周赛110 5046
Acw 5046 思路 dp,\(dp_i\) 表示前i种药且吃第i种药使智商达到\(r_i\)的方案,根据题意可知 \[dp_i = \sum dp_j,(r_j\in [l_i,r_i-1]) \]先将各区间按右端点排序, 求j的区间可用二分. 代码 //9.24 int n,m,k; int ......
Acwing. 第122场周赛
比赛链接 A简单输出 题目链接 简单的模拟一下就好了,注意是多组样例就行。 #include<bits/stdc++.h> using namespace std; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cout<<i<<" "; } ......
acwing 299. 裁剪序列
原题 考虑朴素\(dp\),设\(dp_i\)表示前\(i\)个数划分后的最小答案 可以得到转移: \[dp_i = \min_{j=1}^{i-1}\{dp_j + \max_{k=j+1}^{i}\{a_k \} \} \]计算复杂度\(O(n^2)\),会超时 我们发现对于可能成为答案的状态是 ......
容斥原理应用Acwing890借鉴题解
参考文献 简单的容斥原理介绍请看下图: C++ 代码 简单的容斥原理介绍请看下图: 本题思路: 将题目所给出的m个数可以看成是m位的二进制数,例如 当p[N]={2,3}时,此时会有01,10,11三种情况 而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3 所以当i=1时 ......
AcWing.5151.程序调用
AcWing.5151.程序调用 有 \(n\) 个程序,编号 \(1∼n\)。 初始时,这 \(n\) 个程序都在一个调用队列当中,位于队列第 \(i\) 位的是编号为 \(a_i\) 的程序。 每个程序都有一个调用级别,根据程序在队列中的排位,排在第 \(1∼k\) 位的程序属于 \(1\) 级 ......
AcWing.5150. 顶牛
AcWing.5149.简单计算 约翰的农场有\(n\)头奶牛,编号 \(1∼n\)。 为了决出谁才是牛中强者,它们之间决定来一场顶牛大赛。 已知,每两头奶牛之间都会有一场一对一对决,对决可能产生以下几种结果:没有牛被顶翻、一头牛被顶翻、两头牛都被顶翻。 所有对决的结果已经用一个 \(n×n\) 的 ......
AcWing.5149.简单计算
AcWing.5149.简单计算 给定三个整数 \(x,y,z\),请你计算并输出 \(⌊(z-y)/x⌋*x+y\) 的值。注意,⌊ ⌋ 表示向下取整。 输入格式 第一行包含整数 T,表示共有 T组测试数据。 每组数据占一行,包含三个整数 \(x,y,z\)。 输出格式 每组数据输出一行结果。 数 ......
acwing 294 计算重复
原题 首先\(conn(conn(s_2,n_2),m) = conn(s_2,n_2 \times m)\),因此我们可以找一个最大的\(m'\)满足\(conn(s_2, m')\)能由\(conn(s_1, n1)\)生成,然后再通过\(m = \lfloor \frac{m'}{n_2} \ ......