1 _Jyq

尚未进行身份认证

暂无相关简介

等级
TA的排名 13w+

codeforces 645 Are You Fired?

链接令s[i]=a[i]+…+a[i+k-1],s[i+1]=a[i+k]-a[i],s[i+2]=a[i+k+1]-a[i+1]则转变为所有前缀和最小值 >01️⃣.k>=n/2 ----> s[1]=a[1]+.,…+a[k] , s[2]=x-a[1] , s[3]=x-a[2];把s[1]->0后取减缀和 的前缀min M[ ],则 a[1]+…+a[k]+M[n-k+1] 即为最小值2️⃣k<n/2令s[i]=a[i]+…+a[i+k-1]&g

2020-05-27 16:58:24

HDU 4912 贪心

HDU4912任选一点为根后,贪心优先填所有点对中LCA大的点。那么以LCA为根的子树的所有点都为不能再选的点#pragma GCC optimize(2)#include<bits/stdc++.h>#define ls rt<<1#define rs rt<<1|1#define fi first#define se second#defi...

2020-05-05 12:05:43

Codeforces Global Round 1 Magic Stones

链接很有意思的规律:将:b->a+c-b 之后的查分数组:a,c-b,b-a本来的差分数组:a,b-a,c-b可以发现,题目的操作就是交换 差分序列的操作,所以问题就转化为怎么交换原数组的差分序列,使其和目标序列的差分序列使相等的。那么我们只需要需处理出两个序列的差分序列,排下序后判断就可以了第一个数和最后一个数是不可以改变需要特判一下#include<bits/st...

2020-04-29 22:37:26

Educational Codeforces Round 86 (Rated for Div. 2) E - Placing Rooks

链接想使所有格子全被覆盖,要么所有行都有棋子,要么所有列都有棋子。假设现在是所有行都有棋子,那么其中k对棋子互相攻击就可以看成n-k列放n个棋子。那么答案就为2*C(n,n-k)把n个物品放n-k个集合的方案数。最后一项为第二类斯特林数,记S{n,k}为n个物品放k个集合的方案数公式:S{n,k}=sigma{C(k,i)(k-i)^n (-1)^i} 0<=i<=k递推公...

2020-04-27 11:48:57

Master of Data Structure 虚树

链接m<2000建虚树后暴力维护虚树中两点间的实际点的个数 模拟即可巨丑的代码#pragma GCC optimize(2)#include<bits/stdc++.h>#define ls rt<<1#define rs rt<<1|1#define pb push_back#define fi first#define se se...

2020-04-22 17:27:40

Codeforces Round #635 Kaavi and Magic Spell

链接考虑S串中第i个字母的贡献,那么我们就可以记录一下前i-1个字母组成的各个区间的个数dp[i] [j] 表示T串的i~j区间匹配 出现的次数,那么当加入第i个字母时,所有长度为i-1的dp区间答案已经得到,所以我们在T串中直接枚举所有长度为i的区间,即为当前字母的贡献。转移方程:dp[l][r]+=dp[l+1][r] s[i]==t[l] || l>mdp[l][r]+=dp...

2020-04-17 11:59:34

Educational Codeforces Round 85 (Rated for Div. 2) E Divisor Paths

链接最短路:x->gcd(x,y)->y然后就是一个有重复数字的错排问题,设每种数字分别出现k1,k2,k3…kp次,并假设该错排的答案为f那么f*k1!*k2!k3!…*kp!= ( sigma(ki) )!#pragma GCC optimize(2)#include<bits/stdc++.h>#define ls rt<<1#defin...

2020-04-12 10:33:36

Codeforces Round #630 (Div. 2) F. Independent Set 树形dp

链接显然一颗树的独立集可以很容易的转移过来dp[u][0]=∏(dp[v][0]+dp[v][1])dp[u][1]=∏(dp[v][0])最后答案为dp[1][0]+dp[1][1]加上子集其实就相当于在转移的时候把当前边断开的贡献加上去就可以了,可以得到dp[u][0]=∏(dp[v][0]+dp[v][1]+dp[v][0]+dp[v][1])dp[u][1]=∏(dp[v]...

2020-04-07 12:00:10

整除分块证明

2020-04-04 21:15:10

Codeforces Round #630 (Div. 2) E. Height All the Same 思维

链接操作1可以将所有的高度变成0 or 1(像俄罗斯方块一样)并且这其中的0和1可以全局互换操作2和操作1可以移动这些1,并且将相邻的0 0 -> 1 1那么问题就转换成,放置偶数个位置0,或偶数个位置1所以当n*m%2==1时 0和1总会有一个是偶数否则,也可以简单的构造出一个组合数公式,并化简为(a+b)^c的组合形式思考问题的方向是个很重要的东西,一道题能不能快速的解出...

2020-04-01 17:44:15

The 13th Chinese Northeast Collegiate Programming Contest

文章目录B. Balanced DietC. Line-line IntersectionE. Minimum Spanning TreeG. Radar ScannerH. SkyscraperJ. Time Limit链接B. Balanced Diet贪心,假设最大天数为k,那么所有物品最大得k项都拿(再满足题意的情况下)#include <bits/stdc++.h>...

2020-03-31 00:23:39

Codeforces Round #629 (Div. 3)

第一次AK写篇题解庆祝一下~~文章目录A.Divisibility ProblemB. K-th Beautiful StringC. Ternary XORD. CarouselE. Tree QueriesF. Make k EqualA.Divisibility Problem看代码吧#include<bits/stdc++.h>#define pb push_bac...

2020-03-27 10:31:02

2019 ccpc 哈尔滨

文章目录Justifying the ConjectureFixing BannersKeeping RabbitsInteresting PermutationExchanging GiftsLRU Algorithm补Binary Numbers补Artful Paintings补Justifying the Conjecture显然,构造一个偶数和一个质数是最方便的,那么直接判断奇偶性选...

2020-03-26 00:13:33

2017 icpc 沈阳

5/13Little BoxesRabbitsHeron and His TriangleInfinite Fraction PathTree链接就这几个题目来说感觉都偏技巧性,考验思维能力。Little Boxes输出a+b+c+d JAVA就行Rabbits分析题目得到答案最多就是a[n]-a[1]-n+1 即最大值和最小值之间的空隙,那么由于每次移动一个点时,会有k个间隙被浪费...

2020-03-23 00:09:59

2017 CCPC 哈尔滨

链接Permutation根据题意构造一个A[i]-A[i-2]=1的数列即可easyA Simple Stone Game很容易想到求出N堆石子的总数量后,枚举每种因子得到一个解(将每堆石子模mid后贪心的凑出k堆)然后取最小值。但是因子的数量可能会很多会超时,那么我们在仔细想想发现其实只需要要枚举素因子就能得到正确的答案。Geometry Problem由于有N/2个点都在圆上,...

2020-03-21 13:49:19

Codeforces Round #625 World of Darkraft: Battle for Azathoth

链接Answer :可以把怪兽看成二维坐标上的一些点,每个点有一些权值。然后对于所有的x=ai(攻击)的轴上都有m个bi(防御)那么对于每一个bi它所能打死的所有怪兽就是当前的轴的左面所有y小于bi的怪兽所以问题就转化为一个区间求和+区间最大值的问题 用线段树维护就好了坑点:把握好题目给的条件,以及输入顺序(怪兽是先给的防御力 …好坑)Code:#include<bits/st...

2020-03-18 13:29:31

Codeforces Round #626 Instant Noodles

l链接Answer :本题突破口在于gcd⁡(a,b)=gcd⁡(a,a+b)\gcd(a,b) = \gcd(a,a+b)gcd(a,b)=gcd(a,a+b)然后将右部点选择性合并后 直接求gcd(c1-ck)即可坑点:遍历mp的时候注意 略过空集Code:#include<bits/stdc++.h>using namespace std;typedef lo...

2020-03-17 23:11:36

二分图

总结二分图的最大匹配:匈牙利算法二分图的最小点覆盖数 = 二分图最大匹配数二分图最大独立集 = 总点数 - 二分图最大匹配数(有向无环图)不可重叠最少路径覆盖数=原图点数 - 二分图的最大匹配前置知识:增广路:由未匹配点开始未匹配点结束,中间交错出现匹配边与未匹配边的一条路径。可以发现当我们把一条增广路的边交换性质之后,二分图的匹配数量就会➕1二分图最大匹配1匈牙利算法:枚举每个未...

2020-03-11 16:27:36

树链剖分入门

例题POJ 3237()BZOJ 3083BZOJ 3531BZOJ 3589BZOJ 3626将树上问题通过dfs序的性质转换为区间问题,从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子,重链一系列概念将时间复杂度也变成了可以接受的层次通过两次dfs求出树上一系列的信息void dfs1(int u){ sz[u]=1; dep[u]=dep[fa[...

2020-03-04 20:06:46

Codeforces Round #532 (Div. 2) E. Andrew and Taxi 二分+拓扑序

Andrew and Taxi Question:给一n个节点m条边的有向有权图 现可以改变其中一些边的方向 总代价是这些边的最大值,问使该图无环的最小花费 n,m<1e5Solution:由于代价为所有边的最大值,想到二分然后对所有大于mid的边进行拓扑排序后,如果没有环那mid这个值就是可行的。并且把不在图中的边(即权值小于mid)并且top【u】>top【v】的边翻...

2020-02-21 18:31:35

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。