搜索结果
查询Tags标签： times，共有 215条记录-
优化dp
单调队列优化dp 单调队列单调队列是一种特殊的双端队列，其内部元素具有单调性。常见有最大队列和最小队列两种单调队列，其内部元素分别是单调递减和单调递增的。 支持两种操作 -插入：如果新元素从队尾插入后会破坏其单调性，则删除队尾元素，直到插入后不再破坏单调性为…
2022/9/8 23:53:18 人评论 次浏览 -
乘法逆元
乘法逆元 例题1 小凯的数字一串数字l(l+1)(l+2).......(r-1)r，例如l=2,r=5,数字为2345，小凯很喜欢数字9，所以写下的数字除以9的余数是多少\[2345=2\times 10^3+3\times 10^2+4\times 10^1+5\times 10^0\\ \forall x \geqq 0,10^x\mod 9=1\\ (2\times 10^3)\%9=(2\%9\ti…
2022/9/5 23:25:38 人评论 次浏览 -
2022.09.02
Codeforces Round #818 (Div. 2) 赛时：476+904+1176+930+0+0 补题：476+904+1176+930+600+0A. Madoka and Strange Thoughts求满足 \(a,b\leq n\) 且 \(\frac{lcm(a,b)}{gcd(a,b)}\leq 3\) 的个数。 \(n\leq 10^8,t\leq 10^4\) 。赛时打表 \(1\) 分钟看出规律，设差分序列…
2022/9/3 23:25:11 人评论 次浏览 -
人物交互算法（HOI）学习笔记之 ——QPIC
论文简介 QPIC: Query-Based Pairwise Human-Object Interaction Detection with Image-Wide Contextual Information [论文地址][https://arxiv.org/abs/2103.05399] [代码地址][https://github.com/hitachi-rd-cv/qpic] 背景与摘要 HOI（Human Object Interaction）检测…
2022/8/28 14:24:27 人评论 次浏览 -
CF1715B 题解
前言 题目传送门！ 更好的阅读体验？ 看起来挺难，其实一分钟就能想出来。 思路 首先考虑什么时候无解。由于 \(k \times \left\lfloor\dfrac{a}{k}\right\rfloor \le a \le \left\lfloor\dfrac{a}{k}\right\rfloor + (k - 1)\)，\(a\) 与 \(k\) 是自然数。 所以可得下式。…
2022/8/27 23:22:54 人评论 次浏览 -
好用的东西2
合并果子(加强版) 有若干堆果子，每次合并两堆果子 \(S_1,S_2\) 需要付出 \(|S_1|+|S_2|\) 的代价，问合并为一堆的最小代价。\(n\le 10^7\) 我们开两个队列，一个存初始每个果子并升序排序，另一个存合并后的若干堆果子。每次比较两个队首，取出最小和次小，并把合并后的…
2022/8/24 23:26:28 人评论 次浏览 -
01分数规划
01分数规划 经典例题：POJ2976 给定 \(n\) 个物品的价值 \(a\) 和 花费 \(b\) ，取其中的 \(k\) 个物品，求 \(\sum a[i] / \sum b[i]\) 的最大值。 题解： 假设 \(\sum a[i] / \sum b[i] = x\) ,则： 当 \(x\) 不是最优解时，\(\sum a[i] / \sum b[i] \ge x\) 成立，则存…
2022/8/24 6:53:08 人评论 次浏览 -
数学知识
相关证明参考数学部分简介 - OI Wiki (oi-wiki.org) 数论 质数 在大于 \(1\) 的整数中，只包括 \(1\) 和它本身的约数，又称作素数 质数的判定——试除法 \(O(\sqrt n)\) bool is_prime(int n) {if (n < 2)return false;for (int i = 2; i <= n / i; i++)if (n % i …
2022/8/11 6:24:58 人评论 次浏览 -
2022.8.2 颓废记录
Preface 之前有看别人写过每天的做题记录，今天准备写题解时突然想起来了这个。 感觉一题一个题解太占空间了QAQ，不如以后都以这样的形式记录我的训练生活。 今天还是挺开心的，切了三道题，然后愉快地颓了一天。 Content [CF980D]Perfect Groups题意：对于一个长度为 \(…
2022/8/3 6:23:54 人评论 次浏览 -
CF1710E Two Arrays
*2400？*24000！题意 用两个数组 \(a_1,a_2,\ldots,a_n\)、\(b_1,b_2,\ldots,b_m\) 描述一个 \(n\times m\) 的网格图，\((i,j)\) 的权值为 \(a_i+b_j\)。 一开始有个车位于 \((1,1)\)，Alice 和 Bob 轮流操作，一次操作可以选择：横向移动车至与其同一行的任意一个格子；…
2022/8/1 23:26:00 人评论 次浏览 -
P1516 青蛙的约会
题目传送门 思路 因为两个青蛙同时跳到同一个点上才算碰面，设 $ t $ 为跳的次数， $ p $ 为两个青蛙跳的圈数之差，有如下式子： \[(x+m \times t ) - ( y+n \times t ) = p \times L \]整理得： \[(n-m) \times t + L \times p = x - y \]首先，要判断 $ \gcd ( n-m ,…
2022/7/31 23:39:32 人评论 次浏览 -
[NOIP2021]方差 题解
传送门QAQ Preface 现在看来当时的我还是太菜了啊QAQ（虽然现在也很菜 Analysis 显然，原序列中每个数都减去同一个数后，方差也不会有任何改变。 为了方便，这里我们先让原式中每个 \(a_i\) 减去 \(a_1\)。 考虑将题中要求的这个式子化简（很简单，过程省去）： \[n\time…
2022/7/29 23:23:04 人评论 次浏览 -
【牛客网235422 区间最大值】题解
题目地址 题目思路 以下分数皆表示整除 \[\Large\max(n\bmod i)\\\Large=\max(n-\frac n i\times i)\\\Large=n+\max(-\frac n i\times i)\\\Large=n-\min(\frac n i \times i) \]显然，当 \(\frac n i\) 一定时，\(i\) 越小越好，所以可以把每个 \(\frac n i\) 求出来，然…
2022/7/28 23:30:35 人评论 次浏览 -
扩展欧几里得算法exgcd基本运用 与 exgcd求逆元
基础用法 给定 $ n $ 对正整数 $ a_i, b_i $，对于每对数，求出一组 $ x_i, y_i $，使其满足 $ a_i \times x_i + b_i \times y_i = gcd(a_i, b_i) $。 裴蜀定理 对于任意正整数\(a, b\)，那么一定存在非零整数\(x,y\)使得\(ax + by = gcd(a , b )\)假设\(ax + by = d\)…
2022/7/24 14:23:15 人评论 次浏览 -
筛法求欧拉函数之和
题目描述 求\(1\sim n\)每个数欧拉函数之和 想法如果\(i\)是质数 \(\varphi (i) = i - 1\)质数\(i\)只有\(1\)和\(i\)两个因数，\(i\)不和\(i\)本身互质，因数只有一个\(1\)，所以互质的数就有\(i-1\)个如果\(i\)不是质数\(i \% j = 0\) \(j\)是质数 则\(j\)即\(i\)的一个…
2022/7/24 6:24:07 人评论 次浏览
