题解computational geometry p9702
[ABC329D] Election Quick Report 题解
题目翻译 有一场选举,要从 \(N\) 名候选人中选出一名获胜者,候选人编号为 \(1, 2, \ldots, N\),共有 \(M\) 张选票。 每张选票正好投给一位候选人,其中 \(i\) 票投给了候选人 \(A_i\)。 选票将按照从第一张到最后一张的顺序进行统计,每张选票统计完毕后,将更新并 ......
AT_abc329_e [ABC329E] Stamp 题解
题目翻译 给你两个字符串:\(S\) 由大写英文字母组成,长度为 \(N\);\(T\) 也由大写英文字母组成,长度为 \(M\),小于 \(N\)。有一个长度为 \(N\) 的字符串 \(X\),它只由 # 字符组成。请判断是否有可能通过执行以下任意次数的操作使 \(X\) 与 \(S\) 匹配: ......
[ABC328D] Take ABC 题解
题目大意: 给你一个字符串 \(s\)。你要在其中找到多少个 ABC 的子串,例如 AABCBC 算两个,删掉中间的 ABC 后,前面的和后面的加起来也是一个 ABC,所以就算两个。 思路分析: 首先很容易写出暴力,把一个 ABC 提取出来后把后面的元素往前移,然后再重复操作,但是我们发现时间复杂度 ......
[ABC327D] Good Tuple Problem 题解
分析: 这一道题很容易发现可以用并查集来维护 (不知道为什么其他人都用了图论),\(a_i\) 与其对应的 \(b_i\) 代表着 \(a_i\) 这个集合里不能存在着 \(b_i\)。 根据只有存在两个集合,所以我们会发现,若 \(x\) 与 \(y\) 不在一个集合且 \(x\) 与 \(z\) ......
AT_abc324_e [ABC324E] Joint Two Strings 题解
题目大意 给你 \(n\) 个字符串 \(s\),和一个字符串 \(t\)。 问你,有多少组是 \(s_j\) 拼在 \(s_i\) 后面所组成的新字符串中,\(t\) 是其子序列。 思路 分析:\(5 \times 10^5\) 的数据肯定需要 \(O(n)\) 或 \(O(n \log n)\) ......
洛谷 P4872 OIer们的东方梦 题解
前言 一个下午,一个晚上,一个早上,可以算是一天了吧,终于调出了这道题,纪念一下吧!!! 食用更佳。 这道题其实就是一道简简单单的 BFS 模(du)板(liu)题。 说难不难,简单不简单,虽然没有难的算法,但是就是码量一百多行,比较难调。 题目难度绿,思维难度橙,代码难度蓝。真是个绝世好题。 题目 ......
洛谷 P6239 [JXOI2012] 奇怪的道路 题解
P6239 [JXOI2012] 奇怪的道路 首先,拿到题面,\(n \le 30\),\(k \le 8\),这不就暴搜吗。再想想,紫题会给你暴搜的机会吗?所以进一步思考,发现这其实是一道 DP,而且数据这么小,肯定是给状压 DP 的样子。 经过一定思考,发现我们可以直接线性枚举 \([1,n]\ ......
洛谷P3161 [CQOI2012] 模拟工厂题解
P3161[CQOI2012]模拟工厂题解。题目 其实发现这是一道状压,发现这道题是一道数学题,其实就很简单了。对于每一次的订单我们可以设: \(time\) 为距离下一个订单的时间。 \(num\) 为这个订单要生产的数量。 \(x\) 为生产能力。 \(y\) 的时间可以用来提高工厂的生产力。那 ......
[ARC117E] Zero-Sum Ranges 2题解
题解 前言 个人认为官方题解写得最为详细、干净、清楚,如果有意向阅读外文版的题解的话,还是推荐去读一读: Editorial - AtCoder Regular Contest 117 本文属于转载(?),有一些自己的思考过程,希望有帮助。 题意 有多少个长度为 \(2N\) 的序列 \(A\) 满 ......
P9779_[HUSTFC 2023] 不定项选择题_题解
# [rt](https://www.luogu.com.cn/problem/P9779)# 题目##### 有一道共 n 个选项的不定项选择题,它的答案至少包含一个选项,由于题目与选项的内容晦涩难懂,你打算通过尝试每一种可能的答案来通过这道题。##### 初始时所有选项都没有被勾选,你可以执行任 ......
【题解 P2839】 middle
[国家集训队] middle 题目描述 一个长度为 \(n\) 的序列 \(a\),设其排过序之后为 \(b\),其中位数定义为 \(b_{n/2}\),其中 \(a,b\) 从 \(0\) 开始标号,除法下取整。 给你一个长度为 \(n\) 的序列 \(s\)。 回答 \(Q\) 个这样的询问:\ ......
P8737 题解
定义 \(path(x,y,z)\) 表示 从 \((0,0,0)\) 走到 \((x,y,z)\) 的方案数。 显然的经过容斥得到,若 \(r1\le r2,c1\le c2,h1\le h2\),则 \(ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1 ......
CF1864D 题解
我们注意到对如图倒三角形上的所有点操作都会影响到目标点。 那么我们可以维护两个前缀和,第一个前缀和表示如下的点是否操作 第二个前缀和表示这些点是否操作 这样我们求出了前缀和之后,将两个前缀和异或一下就知道该点是否要操作了。 #include<bits/stdc++.h> using namespac ......
P6326 Shopping 题解
非常好题目。 思路 考虑题目需要求一个连通块的背包。 点分治是平凡的,很容易想到,因为要统计的东西恰好可以把树分成几段。 但点分治操作时的背包确实卡了一下。 以前也没有见过这样的做法。 我们考虑如果直接做树上背包的话。 复杂度是绝对受不了的。 因为合并两个多重背包是基于值域的。 无法体现在树上的优势 ......
题解 NOIP2021 方差
原题 我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃 题意 题意概述: 给定非严格递增序列 \(a_{n}\) 可以进行若干次操作,求序列方差的最小值的\(n^2\)倍 方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2 ......
ARC168(A-C)题解
比赛链接:arc168 A 题意: 读入一个由<和>构成的字符串,在最开始,最后,字符之间可以填上任意数字,任意两个相邻数字之间必须满足字符代表的大小关系。求问最后填入的数字组成的数组最少有多少对逆序对。 题解: 签到。 <可以不去考虑,因为不会对答案造成影响。 >如果不是在连续段内,也可以不去考虑 ......
[Codeforces] CF1475C Ball in Berland 题解
Ball in Berland - 洛谷 题意 在毕业典礼上,有个男孩和个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。 现在你知道个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。 思路 暴力 最朴素,也是简单的方法,就是通过暴力组合进行配对。 #incl ......
vue中watch、computed、methods的执行顺序
一、默认加载情况 如果watch不加immediate:true属性(页面初加载的时候,不会执行watch,只有值变化后才执行),则只执行computed(在mounted后执行); 如果watch添加immediate:true属性(在beforeCreate后created前执行),则先执行wa ......
【题解】HD2016.X1,HD2016.X3,HD2016.X4,HD2016.X5
[HD2016.X1] 价钱统计 题目描述 夏天到了,超市里摆满了各种各样的应季水果。现在知道:西瓜的价钱是每斤 1.2 元;桃子的价钱是每斤 3.5 元;葡萄的价钱是每斤 4.5 元;苹果的价钱是每斤 5 元。 现在分别给出上述四种所购买的斤数(均不超过 20),请你编写程序帮助售货员阿姨计算并依 ......
ISOM 3029 - Computer Programming Using C++
以下是C++程序的问题。 作业的硬拷贝和软拷贝都应按时提交。全部的 程序(.cpp文件)将被压缩并上传到 “提交作业1”按钮。压缩文件应与您的学生一起命名 编号,例如“ba12345_Ass1.zip”。 问题1:彩票计划(50%) 编写一个C++程序,在开始时输出一条问候信息,然后生成6个肯定 ......
PostGIS的geometry类型及使用方法
转:https://blog.csdn.net/supermapsupport/article/details/123573338 作者:WuMY PostGIS中矢量数据如何存储和构造,有哪些注意事项?其空间数据模型体系又遵循哪些标准规范?本文进行了详细介绍,并提供实操内容供读者参考。 此外,Yu ......
CF1898 E Sofia and Strings 题解
Link CF1898 E Sofia and Strings Question 给出两个由小写字母组成的序列 \(t\) ,\(s\) 我们有两种操作, 删去 \(t\) 中的任意一个字母 \(t_i\) 把 \(t\) 的任意一个区间 \(t_l\sim t_r\) 按从小到大排序 可以操作任意 ......
【luogu题解】P5461 赦免战俘
一、题目 现有 \(2^n\times2^n\ (n≤10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵,每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免,剩下 3 个小 ......
P8907 [USACO22DEC] Making Friends P 题解
明明看着不难的题目,却意外的卡人。 思路 考虑两头奶牛可以成为朋友条件是什么。 存在一条路径连接这两头奶牛。 且除去端点外的路径上的所有点的编号小于两端点的较小值。 充分必要性都比较显然。 如何维护。 我们可以从小到大加入点,维护这些路径。 对于每个点维护一个 \(\text{set}\)。 表示这 ......
【luogu题解】P9749 [CSP-J 2023] 公路
\(Meaning\) \(Solution\) 这道题我来讲一个不一样的解法:\(dp\) 在写 \(dp\) 之前,我们需要明确以下几个东西:状态的表示,状态转移方程,边界条件和答案的表示。 状态的表示 \(dp[i]\) 表示到达第 \(i\) 个站点所需要的最少钱数, \(w[i]\) 表示 ......
[IOI2015] Teams 题解
妙妙题。 不难发现,我们对于每个 \(k\) 取出的人都是满足 \(a_i \leq k \leq b_i\) 的。 经典的,我们直接将 \((a_i, b_i)\) 转化到二维平面上,将它转化成一个二维数点问题。 我们对于每一个询问,都使 \(k\) 有序,从小到大贪心的选择,也就相当于 \(x\ ......
【模板】最小度限制生成树 题解
其他的题解感觉都好高级,分享一种好想且好实现的方法。 我们可以先把点 \(s\) 和与其相连的边都删除,我们发现剩下的部分变成了一些连通块。 我们不难发现,当要求与 \(s\) 点相连的边的个数为 \(k\) 时,我们的连通块个数显然是 \(k\) 的。 接下来这个问题就转化成了:\(n - 1\) ......
使用Geotools合并多个Geometry成一个图形
合并Geometry针对初始geometry的个数不同,可选取多种方法: 一、在geometry数量少的情况下可以直接循环调用geometry的union方法: // 合并图形: geometryDefault为初始图形,polygon为待合并的图形 Geometry geometry = geom ......
P9870 题解
blog。NOIP2023 T3,特殊性质题。 什么是特殊性质题?就是题目给出了你极其神秘的性质,从而引导你想出正解。 本篇题解将从部分分的角度,一步步讲述部分分与正解的关系。这样看的话,本题会变得十分简单。 \(\text{Task }1\sim7\),\(O(Tnm)\) 首先转换题意。\(\f ......