1 ddgo

尚未进行身份认证

我要认证

越菜越爱

等级
TA的排名 14w+

Euclid‘s Game (更相减损术理解)

题目地址题意:从已经得到的集合里面选取任意两个数,得到的差是以前没出现过的正数,求出集合的最大个数就可以判断对错。gcd(a,b) = gcd(b,a-b) = gcd(a,a-b) = x可以知道,所有类似于(a-b)这种两个数的差值,一定是x的倍数。所以结合里面的元素全是x的倍数,只需求出有多少个。n = max(a,b)/(__gcd(a,b)) - 2.代码:#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

2020-09-11 15:37:03

Codeforces Round #669 (Div. 2) A ~ D

A:判断1和0的个数,1的个数为cnt如果1大于0的个数,则输出 cnt%2 == 0?cnt:cnt-1 个1否则输出所有个数的0就可以。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<queue>

2020-09-09 20:24:50

acwing 239 (并查集 边带权)

用s[] 表示1的个数的前缀和1: 当s[l-r] = even,则 s[l-1] 与 sum[r]奇偶性相同2:当s[l-r] = odd,则 s[l-1] 与 sum[r]奇偶性相反故可以将l-1 和 r 合并到一个集合,并且可以判断。3种情况x1与x2 同 ,x2与x3 同,则x1与x3同同,不同,不同不同,不同,同故我们可以 令 偶数为 0,奇数为 1 它们的异或对应上面的哪些情况。儿子节点与祖先节点的情况就是路径取个异或。//判断的时候就可以用祖先节点当x2 来判断x1和x3g

2020-09-06 21:28:29

acwing 238 银河英雄传说(并查集)

题目地址维护size和距离的并查集。用d[i]表示i到父节点的距离。再合并的时候,子节点到合并的父节点的距离就是父节点的size。求两个点在不在同一列就是求是否在同一个集合,,它们之间隔的距离就是它们分别到父节点的距离之差减1.#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>#define int long longusing namespace std;

2020-09-06 20:01:45

acwing 145 supermarket (二叉堆,并查集)

题目地址采用贪心的思想:1:按时间从小到大排序。让快过期的物品先卖,后面处理是否要卖它。设我们已经按当前最优的情况选出来了t个,当前处理的物品时间过期为t时,我们判断选出来的物品中是否有比它小的,如果有,则替换。当前处理物品时间过期为>t时,我们直接加入。故可以用堆去维护最小的那个。2:按利润从大到小的排序。我们尽可能在过期的时候去卖它。对于一个物品,过期的时间为t,则我们尽量在t的时候去卖它,若当前t已经被预定了,则往前面找空位去卖。止于0。可以用并查集去维护这句话(若当前t已

2020-09-06 17:46:35

acwing 237 程序自动分析(并查集)

题目地址用 并查集将所有相关的(1)都合并到相关集合里面,再去判断所有不想关的(0)是否出现在同一个集合,若出现在同一个集合内的话说明矛盾。要用离散化去离散i,j再用find去查找i,j离散后的位置。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>#define int long longusing namespace std;typedef pair<

2020-09-06 16:03:55

acwing 213 古代猪文(lucas,中国剩余定理,欧拉定理)

题目地址根据欧拉定理 ,设q上面的系数为x,模数为mod,由欧拉定理,原式等于 qx模mod−1q^{x 模 mod-1}qx模mod−1 % mod令 mod = mod - 1处理系数,暴力求解 -> 超时。分解 mod -> 2 3 4679 35617这样可以用lucas 来优化求解C(a,b).之后可以枚举n的所有约数,求出值x后对 这4个分别mod即 x mod 2 = a1x mod 3 = a2x mod 4679 = a3x mod 35617 =

2020-09-04 21:21:18

Counting swaps acwing 212 (多重集的排列数)

题目地址由题目,我们可以连接出 k 个环。单调递增排序只需拆分每个环,让每一个元素都变成自环。引理:把一个长度为n的环变成n个长度为1自环,最少需要操作n-1次。设FnF_nFn​ 表示长度为n的自环变成n个长度为1的自环 的操作数有通项公式FnF_nFn​ = nn−2n^{n-2}nn−2 可以查阅资料,化简我不会,找出前几项,贴OEIS可以得到。那么整个序列的操作数为∏l=1kFl\prod_{l=1}^kF_l∏l=1k​Fl​ 再乘 (n−k)!∏l=1k(l−1)!\frac{(n

2020-09-04 16:34:36

acwing 211 计算系数(二项式定理)

题目地址直接用二项式定理Ckn⋅an⋅xn⋅bm⋅ymC_k^n \cdot a^n \cdot x^n \cdot b^m \cdot y^mCkn​⋅an⋅xn⋅bm⋅ym则求Ckn⋅an⋅bmC_k^n \cdot a^n \cdot b^mCkn​⋅an⋅bm因为 k < 10007 所以都会有逆元,#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<iostream>#inc

2020-09-04 11:17:05

acwing 884 高斯消元解异或方程

题目地址和高斯消元解线性方程基本一致。最后return 0前面的操作中&是判断这个未知数是否对这个方程有影响#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#include<

2020-09-02 22:45:53

acwing 883 高斯消元解线性方程组

题目地址模拟初等行变换就可以了。有很多种模拟,对于此题方便,有了这个模拟。从第一列开始,枚举未处理的行找到最大的主元素。交换最大主元素的行和当前行。如果最大主元素也为0,则不处理。把主元素的系数化为1.把其他未处理行的主元素列的系数都消去。继续处理,知道最后一列。之后特判r是否把所有列处理完,没有在判断是否无解还是多解。有则把每个x算出来。代码上有许多步骤解释#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

2020-09-02 21:37:37

acwing 204 poj 2891

题目地址中国剩余定理。m序列不一定两两互质的时候。考虑前两个方程,可以得到 x = k1k_1k1​ * a1a_1a1​ + m1m_1m1​x = k2k_2k2​ * a2a_2a2​ + m2m_2m2​则k1k_1k1​ * a1a_1a1​ - k2k_2k2​ * a2a_2a2​ = m2m_2m2​ - m1m_1m1​ … 1可以知道上面就是扩展欧几里得的方程。有解条件: gcd(a1a_1a1​,a2a_2a2​) | m2m_2m2​ - m1m_1m1​对于1方程我

2020-09-02 19:54:39

acwing 245 Can you answer on these queries III【线段树】

题目地址线段树模板加维护。在build 和 change 中要维护一些东西。区间和sum,区间的最大连续子段和data,靠左最大连续区间和lmax和靠右最大连续和rmax.怎么维护:p = 父节点,l = 左节点,r = 右节点。p的sum =l的sum + r的sum.p靠左最大连续区间和 lmax = max(l的lmax,l的sum+r的lmax).同理 p靠右的最大连续区间和 rmax = max(r的rmax,r的sum+l的rmax)还有datap的data = max(ma

2020-09-02 00:01:13

acwing208 开关问题 异或高斯消元

题目地址设ai,ja_{i,j}ai,j​ 表示按j后i是否会发生变化(1是0否),xix_ixi​ 表示第i个开关是否按(1按0不按)则可以得到 一个开关变化的过程最终结果为 sa ^ en 开始的状态异或 结束的状态。即你不管怎么按,这个开关经过层层抵消,最终要按1或者不按0.而这个过程为 a1,1x1a_{1,1}x_1a1,1​x1​ xor a1,2x2a_{1,2}x_2a1,2​x2​ xor … xor a1,nxna_{1,n}x_na1,n​xn​… . . . . . . .

2020-08-31 17:17:50

acwing 207 球形空间产生器 高斯消元

题目地址题目指出有解。设球心为(x1,x2,…,xn) ,则我们可以得到∑j=0n(ai,j−xj)2\sum_{j=0}^n (a_{i,j} - x_j)^2∑j=0n​(ai,j​−xj​)2 = C。将其化简,让第一行减去第二行,依次类推。可以得到∑j=0n(ai,j−ai+1,j)=∑j=0n(ai,j2−ai+1,j2)\sum_{j=0}^n (a_{i,j} -a_{i+1,j}) =\sum_{j=0}^n(a_{i,j}^2 - a_{i+1,j}^2)∑j=0n​(ai,j​

2020-08-30 22:56:11

acwing 206 石头游戏 矩阵快速幂

题目地址构建1维数组f(num(i,j)) -> 表示第num(i,j) =((i-1)*m + j)位的石头有多少个。(i,j)表示一个位置可以知道f的长度为n*m+1.令f[0] = 1.方便后面加x个石头的操作。构造:1: 第(i,j)位置字符为’N’,且i>1,则令A[num(i,j)][num[i-1,j]] = 1.这样在矩阵相乘的时候可以让让num(i,j)位置上的石头全部转移到num(i-1,j) 上面。(转义: 当计算f(num(i-1,j))列的时候,它会加上f (

2020-08-30 18:18:40

扩展欧几里得

对于 ax + by = gcd(a,b) --> gcd(b,a%b) (由欧几里得算法知道)即ax + by = bx + (a-a/b * b)y -> x = y, y = x - a/b *y 。可以用gcd计算,回溯的时候套用这个公式即可。代码:int exgcd(int a,int b,int &x,int &y){ if(b == 0){ x = 1,y = 0; return a; } int d = exgcd(b,a%b,x,y);

2020-08-29 23:32:44

Codeforces Round #660 (Div. 2) D

由题可以构造出一个有向路径,对于一个路径,只要我们从起点开始走,我们就可以尽可能的得到最大的值。若前面一个是负数,则我们把它最后选取最为合适,因为这样继续跟着这条路径选下去,会导致后面的数越变越小。直接拓扑排序正数存到res1,负数存到res2.对于res2,为了自己的贪心成立,对于每一个负数,可能会有它前面的一个点是它的父父父结点,我们不能让这种情况发生,因为发生了,这个数还会变的更小,所以我们直接逆序输出即可。代码:#define IOS ios::sync_with_stdio(false)

2020-08-29 22:15:23

Codeforces Round #664 (Div. 2) A~D

A:回文满足条件就是最多只有一个是奇数。题上的操作可以把每一个数的奇偶性翻转。直接特殊判断一下就可。代码:#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<iostream>#include<algorithm>#include<cstring>#include<map>#define int long long#define sc scanf

2020-08-26 17:13:55

Codeforces Round #662 (Div. 2)

A:第一次操作把最外环处理,结下来每次操作会把一个环处理完,并且向里面的一个环处理。可以的出为n/2+1;#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include<bits/stdc++.h>#define int long long#define sc scanf#define pf printfusing namespace std;typedef pair<int,int>

2020-08-25 13:43:21

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。