题解3175 2015 haoi
P2679 [NOIP2015 提高组] 子串
注意 \(A\) 中取相同位置子串划分方式不同也算作不同的方案。 令 \(f_{i,j,l,0/1}\) 表示 \(A\) 中前 \(i\) 个字符,取出 \(l\) 个子串,拼成了 \(B\) 中前 \(j\) 个字符,第 \(i\) 个字符取/不取的方案数。 不取直接累加 \(A\) 中上一个字 ......
CF70D Professor's task 题解 & 动态凸包板子
CF70D Professor's task 题解 前言 此篇题解用的是 \(Andrew\),不想看这种做法的可以绕道。 题意 动态凸包板子题。 维护动态凸包。两种操作,加一个点或查询一个点是否在凸包内。 题解 首先你得会静态二维凸包。 维护二维凸包的方法挺多的,比如什么 \(Andrew\) 算 ......
[ABC320E] Somen Nagashi题解
2023-09-16 题目 题目传送门 翻译 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 优先队列 解题思路 水题一道。 需要两个优先队列: 因为每一次是队首的人拿到面条,即队列中编号最小的拿面条,就用一个优先队列用来维护当前队列中的编号最小的人。 由于每一次拿了面条后再 ......
【题解】AtCoder-ABC320
AtCoder-ABC320A Leyland Number 依题意计算。 提交记录:Submission - AtCoder AtCoder-ABC320B Longest Palindrome 直接 \(O(n^2)\) 枚举,\(O(n)\) 判断。 提交记录:Submission - AtC ......
[ABC320F] Fuel Round Trip 题解
题意 在坐标轴上给定 \(N\) 个点,坐标依次为 \(X_1, X_2, \cdots, X_N\),你需要从原点前往 \(X_N\) 并折返,其中在第 \(1\) 个到第 \(N - 1\) 个点上有加油站,其中第 \(i\) 个加油站可以花费 \(P_i\) 购买 \(F_i\) 升汽油,汽油 ......
合并果子题解-C++ STL priority_queue容器的使用
说明:本博文关于priority_queue容器的说明来源于www.cnblogs.com/fusiwei/p/11823053.html 本人是刚刚接触算法竞赛的萌新,如果有大佬发现了错误,还望指出(真的有人会看本蒟蒻的博文吗) 这是我的第一篇博文,更多是作为测试 以后会将博客作为笔记记录学习的体 ......
P2669 [NOIP2015 普及组] 金币
题目背景 NOIP2015 普及组 T1 题目描述 国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当 ......
CF1542E1 Abnormal Permutation Pairs (easy version) 题解
CF1542E1 Abnormal Permutation Pairs (easy version) 题解 不会 Hard version 对于第一个限制字典序,我们可以考虑枚举前 \(i\) 位相同,然后考虑后 \(n-i\) 位。我们只需要保证 \(p_{i+1} < q_{i+1}\) 即可。 ......
CF1852B Imbalanced Arrays 题解
CF1852B Imbalanced Arrays 题解 Links 洛谷 Codeforces Description 对于一个给定的长度为 \(n\) 的数组 \(A\),定义一个长度为 \(n\) 的数组 \(B\) 是不平衡的当且仅当以下全部条件满足: \(-n \leq B_{i} \le ......
LeetCode-Java题解 209. Minimum Size Subarray Sum
题目地址:209. Minimum Size Subarray Sum 解题思路: 看到这道题,心里本身是有双指针这个概念的,但是不知道怎么用,脑子里第一反应就是暴力解法,双for一把梭,然后时间就超时了...看了题解才知道滑动窗口这个解法,不禁直呼妙啊!感觉和双指针非常类似,其核心点在于避免了暴力 ......
题解 UVA1566 John
题目描述 两个人轮流取石子,每人每次可以 \([1,a_i]\) 个石子,最后取完石子的人为负。问最终谁会赢。 具体思路 若堆数为 \(1\) 且该堆数量为 \(1\),先手必败。 若堆数不为 \(1\) 且每堆数量都为 \(1\),若有奇数堆,先手比败,否则,先手必胜。 若堆数不为 \(1\),转 ......
洛谷题解 | P5660 数字游戏
目录 题目描述 输入格式 输出格式 输入输出样例 说明/提示 题目简化 题目思路 AC代码 题目描述 小 K 同学向小 P 同学发送了一个长度为 8 的 01 字符串来玩数字游戏,小 P 同学想要知道字符串中究竟有多少个 1。 注意:01 字符串为每一个字符是 0 或者 1 的字符串,如“101 ......
洛谷题解 | P1046 陶陶摘苹果
目录 题目描述 输入格式 输出格式 输入输出样例 说明/提示 题目思路 AC代码 题目描述 陶陶家的院子里有一棵苹果树,每到秋天树上就会结出 10 个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个 30 厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。 现在已知 10 个 ......
洛谷题解 | P1051 谁拿了最多奖学金
目录 题目描述 输入格式 输出格式 输入输出样例 提示 题目思路 AC代码 题目描述 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条件各自不同: 1. 院士奖学金,每人 8000 元,期末平均成绩高于 80 分(>80),并且在本学期内发表1篇或1篇以上论文的学生均可 ......
[ABC313F] Flip Machines 题解
题意 有 \(N\) 张卡片,第 \(i\) 张卡片正面印着一个数 \(A_i\),反面印着一个数 \(B_i\)。一开始所有数正面朝上。 有 \(M\) 种操作,第 \(i\) 种操作表示为: \(50\%\) 的概率将卡片 \(X_i\) 翻转,否则将 \(Y_i\) 翻转。 求一个集合 \(S ......
题解 P8920 『MdOI R5』Variance
题目描述 给你两个长度为 \(n\) 的序列 \(a\) 和 \(b\),让你选 \(n\) 个 \(c_i \in [a_i,b_i]\),使得 \(\frac{1}{n} \sum_{i=1}^n (c_i- \overline c)^2\) 最大。 具体思路 首先我们从方差的定义出发,方差代表 ......
Fox and Minimal path 题解
Fox and Minimal path 题目大意 构造一张无向图,使得从 \(1\) 到 \(2\) 的最短路数量为 \(k\)。 思路分析 我们首先可以发现当 \(k = 2^t\) 时的构造方式: 其中只有 \(O(\log k)\) 个点。 当 \(k\not = 2^t\) 时,我们可以将 ......
CF1599J 题解
题意 给定一个长度为 \(n\) 的数组 \(b\),判断是否存在一个长度为 \(n\) 的数组 \(a\),使得 \(b\) 中每一个元素都可以由 \(a\) 中两个位置不同的元素相加得到。若存在,输出任意一个 \(a\)。 \(2\le n\le 10^3,1\le b_i\le 10^6\)。 ......
P2501 [HAOI2006] 数字序列
原题 是思路非常值得学习的一道题 第一问: 首先我们感性上觉得这题应该和LIS有一点关系,但里面有一点问题: 17 50 50 50 18 如果我们求LIS的话,我们会认为只需要改掉50 50 50即可,但其实我们只改掉这些数,我们是无法做到让数单增的 我们发现这个限制写成数学语言即为:\(a_i ......
NOI 2023 题解
Copper Loser 的题解…… Day1 T1 方格染色 有一个 \(n\times m\) 的网格,有 \(Q\) 次操作,每次形如有三种:将 \((x_i+j,y_i)\)/\((x_i,y_i+j)\)/\((x_i+j,y_i+j)\) 染色,其中 \(j=0,1\dots L_i-1 ......
CF1867F 题解
一、题目描述: 给你一颗 $n$ 个点的有根树 $S$,你需要构造一颗 $n$ 个节点的有根树 $T$, 使得 $T$ 的 $n$ 颗子树中不与 $S$ 的任意一颗子树同构的数量最大。 注意,这里是有根树,旋转树之后的同构不算同构。输出 $T$ 的所有边。 数据范围:$1\le n\le 1\tim ......
『题解』P6055
给出 \(N\),求: \[\sum _ {i = 1} ^ N \sum _ {j = 1} ^ N \sum _ {p = 1} ^ {\lfloor\frac{N}{j}\rfloor} \sum _ {q = 1} ^ {\lfloor\frac{N}{j}\rfloor} [\gcd(i, ......
9.11CF1819 题解
9.11CF1819 题解 A. Constructive Problem 简单题,上链接: 链接 B. The Butcher 题意 有一张 \(h \times w\) 的纸片,现在对这张纸片进行 \(n−1\) 次裁剪。每次裁剪后会将其中一半收归(即这一半不会再被裁剪)。 保证纸片不会被旋转。 ......
P6076 [JSOI2015] 染色问题
原题 题解里大部分做法要做两次二项式反演,不知为何有点喜感 老规矩,先说我的做法: 方法1: 我一开始也想到了要做两次二项式反演,但感觉好麻烦,于是把一个二项式反演换成了\(dp\),复杂度就差了一些 首先我们发现行列的限制不好容斥,因此我们考虑容斥颜色的限制。具体的,设\(f_i\)表示有至少\( ......
【dfs基础题】洛谷P1219题解
题目大意 给定棋盘的规格为 \(n×n\),现在要摆 \(n\) 个皇后,使得每个皇后不能互相攻击。 题目解答 由题意可知,如果两个皇后在同一行或同一列或同一对角线,那么就会互相攻击。 那么就简单了,若当前要摆的是第 \(i\) 个皇后,那么只需要 for 循环一遍前面的 \(i-1\) 个皇后,判 ......
[COCI2020-2021#4] Janjetina 题解
题目链接 题目大意: 给定一棵树,求满足路径最大值减路径长度大于等于 \(k\) 的点对 \((u,v)\) 的数量。 分析: 求树上满足条件的点对数量,很容易想到点分治可以做。 设当前根为 \(root\),\(g[x]\) 表示 \(x\) 到 \(root\) 之间的最大值,\(d[x]\) ......
visual studio community 2015 clodelens功能
关于community版本中增加codelens功能, 网上能搜索到不少安装ssdt后出现该功能的文章, 之前我也是参照这些文章来安装codelens功能的, 但前几天重装系统后, 再次安装ssdt时codelens功能并没有像预期那样出现, 经过一系列的折腾, 发现是ssdt版本的问题, 在最新版 ......
AtCoder Beginner Contest 319 全部题解
AtCoder Beginner Contest 319 全部题解 A Legendary Players 该题只需使用判断来写出所有的答案,注意不要复制错。 #include <bits/stdc++.h> using namespace std; string s; int main(){ ci ......
Codeforces Round 882 (Div. 2) 题解
Codeforces Round 882 (Div. 2) 这题很简单的吧,比较脑抽的就是D,下面详细说,我nloglogn过不去2e5说实话有点不应该,感觉有更聪明的办法搞这个。 很奇怪的一点是,yongwham究竟是怎么只做出来A的???? A. The Man who became a God ......
Codeforces 1868C/1869E Travel Plan 题解 | 巧妙思路与 dp
题目链接:Travel Plan 题目大意:\(n\) 个点的完全二叉树,每个点可以分配 \(1 \sim m\) 的点权,定义路径价值为路径中最大的点权,求所有路径的价值和。 对于任意长度(这里主要指包括几个节点)的路径 \(t\),最大点权不超过 \(k\) 的方案数有 \(k^t\) 个, 因 ......