division
CF550C. Divisibility by Eight
题目大意 给你一个由阿拉伯数字组成的字符串,让你找出其中一个子序列,使其能被8整除 思路1 一个整数的末尾三位数能被8整除,则这个数能被8整除。 代码 #include <bits/stdc++.h> using namespace std; using i64 = long long; const ......
CF1916F Group Division记录
题目链接:https://codeforces.com/contest/1916/problem/F 题意 已知点双连通的图 \(G = (V, E)\)。求一种划分方式 \(V = V_1 \cup V_2\),使得 \(|V_1| = n_1\),\(|V_2| = n_2\),且 \(G\) ......
CodeForces 1916F Group Division
洛谷传送门 CF 传送门 考虑增量构造第一个集合。首先令 \(S = \{1\}\),然后不断找到下一个点 \(u\),使得它在抠掉 \(S\) 的图上不是割点,并且与 \(S\) 连通。然后令 \(S \gets S \cup \{u\}\)。 可以证明一定能找到这样的 \(u\)。 因为对于抠掉 ......
Square-free division (easy version) 题解
题意:给定一个长度为 \(n\) 的序列,求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。 一个小 Trick:如果两个数乘起来为平方数,可以先将每个数的平方因子除掉,然后这两个数必然相等。于是这道题被转化为了一个区间不能有相等的值,这就很典了。 设 \(pos_{a_{i} ......
Square-free division (hard version) 题解
题意:给定一个长度为 \(n\) 的序列,求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。你还可以将其中 \(k(k \le 20)\) 个数修改为任意的值。 一个小 Trick:如果两个数乘起来为平方数,可以先将每个数的平方因子除掉,然后这两个数必然相等。于是可以先将每个 ......
[Codeforces] CF1744E1 Divisible Numbers (easy version)
CF1744E1 Divisible Numbers (easy version) 题意 给你四个数 \(a,b,c,d\),你需要找出一组 \(x,y\) 使得 \(a<x\leq c,b<y\leq d\) 并且 \(x\cdot y\) 能被 \(a\cdot b\) 整除,如果没有输出 -1 ......
CodeForces 1497E2 Square-free division (hard version)
洛谷传送门 CF 传送门 感觉和 CF1889C2 Doremy's Drying Plan (Hard Version) 有异曲同工之妙。 显然去除每个数的平方因子后,两个数相乘为完全平方数当且仅当它们相等。 考虑若确定了分段方案,那么修改次数就是,每一段重复出现的数的个数。 那么我们设 \(f_ ......
[ARC141D] Non-divisible Set 题解
题目链接 点击打开链接 题目解法 很思维的题,需要用好所有的特殊性质 暴力的做法是建出图,然后求包含点 \(i\) 的最长反链,但这明显过不了 上面的做法没用到 \(a_i<2m\) 的性质 如何用?把 \(a_i\) 拆分成 \(q\times 2^k\;(k\) 为奇数\()\) 的形式,那么对 ......
RuCode 2020 Division A+B. I ✖ [PR #5] 和平共处
前言 认认真真学习了一下这道题相关的做法以及有关的二分图网络流理论,感觉自己又刷新了一些东西的理解。 所以说我们就从普通的二分图匹配开始吧! 二分图匹配 众所周知, 题意 给定 #include <map> #include <cstdio> #include <algorithm> using n ......
Starters 109 Division 2 (Rated)
比赛录屏 https://www.bilibili.com/video/BV1Aw411n7DP/?vd_source=9a4bbd69c77feaab80f2e4e19721de57vd_source=9a4bbd69c77feaab80f2e4e19721de57 \(Best of N Set ......
C++ signal(SIGFPE,handler) ignore division by 0 exception
#include <stdexcept> #include <chrono> #include <csetjmp> #include <ctime> #include <fstream> #include <iostream> #include <iomanip> #include <signal. ......
[ARC159F] Good Division 题解
[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下,转化为划分的每一段都没有 绝对众数,可以证明这与题目中的要求是完全等价的,证明如下: 充分性:考虑构造一种操作方法,就是每次操作都消去一个出现次数最多的数,按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......
Codeforces Round 748 (Div. 3) B. Make it Divisible by 25
给一个正整数 \(n\) ,在一步操作中可以移除 \(n\) 中的一个。当 \(n\) 只剩下一位时将不能再操作,如果过程中产生了前导 \(0\) ,则会被自动移除且不耗费操作次数。 询问最少需要多少次操作可以使得 \(n\) 被 \(25\) 整除。 显然一个正整数 \(x\) 若可以被 \(25 ......
Django报错ZeroDivisionError: division by zero
Django报错ZeroDivisionError: division by zero DJango报错:up_rate = round(upline/total*100) ZeroDivisionError: division by zero 报错代码 #报错代码 def dashboard(re ......
Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020
A - Hitachi String 满足条件的串即为串长为偶数且相邻两个均为为 hi,直接判断即可。 代码: #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=15; int ......
题解 ARC141D【Non-divisible Set】
这个题不是网络流。 problem 我们说一个集合 \(D\) 是一个好的集合,当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。 给定 \(N\) 个整数的一个集合 \(S\),值域均落在 \([1, 2*M]\) 内。 对 \(S\) 中的每个元素 \(A_ ......
abc288F - Integer Division
F - Integer Division 挺有意思的一道题, 贪心的做法就是排序之后,逐个加入,如果不能被之前的表示则加入 题解证明的话大概是这样 考虑第i个数选不选 首先加入前面选的数,如果能够表示当前的数,则必然不选 否则前面的数不能表示当前的数,假如我们不选\(p_i\) 假设最后得到一个合法 ......
1476A - K-divisible Sum
## A. K-divisible Sum https://codeforces.com/problemset/problem/1476/A ```python """ 思路: 1.k >= n, 如果能除尽, 就是每项都相同肯定是最小的, 比如2 6, 3是最小的, 其他的肯定比3要大, 所以只要 ......
CF1444A Division
## 思路 首先特判特殊情况,若 $p_i$ 本身不可被 $q_i$ 整除,那么 $x_i$ 就直接取 $p_i$ 最大。 否则的话,$p_i=q_i\times k$。所以 $q$ 的质因数,$p$ 都有,并且数量一定大于等于 $q$ 的这个质因数的数量。 那么如果 $x_i$ 的某个质因数个数小 ......
fair division for parallelsim
https://ww2.mathworks.cn/matlabcentral/fileexchange/35933-mattugames I find an algotirhtm for fair division for parallelsim. The first player choose t ......
题解:【ICPC WF 2021 C】 Fair Division
[题目链接](https://www.luogu.com.cn/problem/P9441) 记 $g = 1 - f$,即传递下去的宝藏有多少。如果一个海盗在第一轮得到了 $x$,则第二轮将得到 $g^n x$,第 $T$ 轮得到 $g^{Tn} x$,于是在极限情况下总共得到的宝藏为 $\dfr ......
Atcoder Regular Contest 114 F - Permutation Division
显然分成 $k$ 段以后,最大化形成的排列的字典序的策略是将所有段按第一个元素的大小降序排列。 由于最终排列的字典序肯定 $\ge$ 原排列的字典序,因此我们考虑最大化最终排列与原排列的 LCP,这部分就考虑二分答案,记 $dp_i$ 表示以 $p_1$ 开始 $p_i$ 结尾的 LDS 的长度,那 ......
C. Division
Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division. To improve his division skills, Oleg came up with $ ......
每日一题力扣 1262 https://leetcode.cn/problems/greatest-sum-divisible-by-three/
、 题解 这道题目核心就算是要知道如果x%3=2的话,应该要去拿%3=1的数字,这样子才能满足%3=0 贪心 sum不够%3的时候,就减去余数为1的或者余数为2的 需要注意 两个余数为1会变成余数为2的,所以可能减去2个余数为1 核心代码如下 public int maxSumDivThreeOth ......
[LeetCode] 1262. Greatest Sum Divisible by Three
Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three. Example 1: Input: nums = [3, ......
ARC114F Permutation Division
## 题意 给定一个 $1 \sim N$ 的排列,Alice 把它划分成 $k$ 段,Bob 把这 $k$ 段任意排列。Alice 想让字典序最小,Bob 想让字典序最大。请问最后的排列。 数据范围: $1\le k\le N\le 2 \times 10^5$。 ## 题解 首先 Bob 的排序 ......
AtCoder Regular Contest 114 F Permutation Division
洛谷传送门 AtCoder 传送门 这题居然是之前某场模拟赛(contest 701)的 T1……(@Vidoliga 场切但是被卡常/bx) 下面记 $m$ 为原题面中的 $K$,$a_i$ 为原题面中的 $P_i$。 不难发现后手的策略是把所有段按照段的第一个数从大到小排序接在一起。 考虑若 $ ......
ARC159F Good Division【性质,DP,线段树】
定义一个序列是好的当且仅当其可以通过每次删去一对相邻的不同的数把序列删空。 给定一个长度为 $2n$ 的序列 $a$,求有多少种划分方式使得每一段都是好的。答案对 $998244353$ 取模。 $n \leq 5 \times 10^5$,时限 $\text{5.0s}$。 先考虑什么样的数列是合 ......
CodeChef Starters 83 Division 1 解题报告
CodeChef Starters 83 Division 1 题解 $\newcommand \v \mathrm$ $\text{By DaiRuiChen007}$ Contest Link A. Construct String Problem Link 题目大意 给定长度为 $n$ 的字符 ......
Divisible Numbers
#include<iostream> #include<math.h> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+10; int n; ll gcd( ......