4 High_EnergyElectron

尚未进行身份认证

暂无相关描述

等级
博文 124
排名 4w+

解题报告: Codeforces Round #527 (Div. 3)

好久没打CF了,低迷了一段时间后又忙于搬砖和摸鱼等等0_0工作后发现有时间写写题和题解也是一种享受的,当然水平还是一如既往的菜的...C、PrefixesandSuffixes题目大意:有一个长度为n的字符串,给出分别长度为1~n-1的前缀和后缀的乱序排列,总共有(2n-2)个排列,问每个给出的排列是前缀还是后缀。思路:由最长的两个n-1的排列可以确定4种字符串,因为数据也不大...

2018-12-23 16:47:40

解题报告:Codeforces Round #432 (Div. 1) D. Tournament Construction (DP+构造)

题目链接题意:给出点的出度的去重集合,要求构造一个最小点数的竞赛图并存在一个出度序列(d1,d2,d3...dn)满足任意前缀k项和大于k*(k-1)/2(点数思路:可以确定点数的上界为61  (n*30>=n*(n-1)/2)定义:dp[n][m][l]:能否用集合的前m项(至少取一个)构造出n个点 l条边的图

2017-09-07 20:45:13

解题报告:Codeforces Round #433 (Div. 1) D. Michael and Charging Stations (DP)

题目链接题意:已知接下n天每天的消费ai若某一天只使用现金,则可以得到10%的消费作为代金券询问度过这n天的最小花费n思路:dp[x][y]:第x天手上有y金额的代金券所需的最小花费将ai除以100以缩小第二维的大小,那么可以确定y因为使用代金券会无法得到代金券,所以每次使用时要尽可能的大得到递推方程:当只使用现金时:

2017-09-07 16:43:31

解题报告:Codeforces Round #433 (Div. 2) E. Boredom ( 离线处理+树状数组)

题目链接题意:n*n的矩阵,有n个不同行列的格子染色,染色的格子两两之间组成的矩阵定义为beautiful。q组询问,每次给出一个矩阵,询问与它相交的beautiful的矩阵的数目n,q思路:每次查询分成九个矩阵,只需要知道各个矩阵中的染色的点数,即可得出答案其中五个矩阵可以由染色的性质可以直接得出答案离线处理另外四个即可代码:#include

2017-09-07 09:56:36

解题报告:HDU_6176 Function Counting (离散化DP+矩阵快速幂)

题目链接题意:求满足题目的三个要求的置换的方案思路:分析题意发现是一个多重背包设每个物品的代价为x,价值为y则物品的代价为满足(2*t+1)*x==k,t为自然数对应的价值为2^x代价为1和2的物品的价值比较特殊,为2^(x-1)另外代价为2的物品会带上一个(4,4)的物品(交叉取置换)于是就可以得到一个线性递推方程,基于n和k的范围采用不

2017-09-06 20:01:54

解题报告:Codeforces Round #432 (Div. 2) E.Arpa and a game with Mojtaba (博弈)

解题报告题意:有n个数,你每次可以选择一个素数p,和一个整数kn个数中至少存在一个数x满足:(p^k|x)然后将n个数中所有p^k能整除的数除以p^k两个人轮流进行操作,无法操作的一方输,问初始局势的胜负态思路:很明显不同素数之间的局势相互独立,O(n*sqrt(maxa))处理出后可以状压至二进制那么答案就是各个素数的局势的sg异或但是发现素数

2017-09-05 19:27:15

解题报告:Codeforces Round #432 (Div. 2) D. Arpa and a list of numbers 暴力

题目链接题意:给定一个序列含n个数,定义这个序列为good当序列里的所有数的gcd>1,你有两种操作:1:删除一个数,代价为x2:将一个数加一,代价为y求把序列变成good的最小代价思路:如果知道gcd,可以在O(n)内求出最小代价可以发现性质:当n个数中公因子越多,选这个公因子做gcd需要变动的数越少,代价可能会越低于是枚举时限内尽

2017-09-05 10:05:02

解题报告:HDU_6184 Counting Stars (三元环计数)

题目链接题意:给定一张无向图,求以下图形的方案数,点集或边集不同认为是不同方案点数和思路:考虑中间的边,它组成的三元环中任选两个都能组成不同的满足要求的图案因此跑一遍三元环统计出每条边能组成的三元环个数偷懒用unordered_map可以卡时限过,最好用hash代码:#include#defineLLlonglong#

2017-09-04 19:29:44

解题报告:HDU_6189 Law of Commutation (找规律)

题目链接题意:给定n,a,求区间[1,1的个数思路:打表发现以下规律1、若a为奇数,答案为12、若a为偶数,则对于大于n的b,满足,其中a2,b2为a,b含2的因子个数3、对于小于n的b,满足的情况有点多,直接暴力check代码:#includeusingnamespacestd;inlinelongl

2017-09-04 16:10:24

解题报告:HDU_6185 Covering (轮廓线DP+高斯消元+矩阵快速幂)

题目链接题意:给一个4*n的表格,你有两种矩阵(1*2),(2*1),询问放满的方案数。n思路:显然公式应该是一个线性递推方程,知道后可以用矩阵快速幂在O(log(n)*m^3)求得答案(m为方程的项数)为了求这个方程,我们可以用轮廓线DP求的方程的前k项然后假设一个k>m,用高斯消元求k*k的矩阵的秩,从而求得m再用高斯消元求得方程即可

2017-09-03 10:53:34

解题报告:HDU_6169 Senior PanⅡ (记忆化搜索)

题目链接题意:给定一个区间[L,R],询问区内所有最小因子(除去1)为K的数之和1官方题解:: 思路:如果数据范围小一点,应该很容易想到dp的做法数据范围很大,也可以用离散化DP去做,当然直接用map去跑会超时,需要优化考虑第一维的大小递减很快,小数据的答案用到的频率会远远多于大数据的频率那么小数据直接用数组保存,大数据直接用搜索

2017-09-02 16:25:45

解题报告:LightOJ_1406 状压DP

题目链接题意:给定一张有向图,问最少能拆成几条路径要求包含所有点且不同路径之间没有重点,同一可以重复经过同一点(点数思路:定义ok[x][y]:x集合是否存在一条以y点结尾的路径dp[x]  :x集合的最少路径数dp[x]=min(dp[i]+dp[j])     i^j==x&&i&j==0因为有环,那么每次处理出一个可行的ok

2017-09-01 08:36:55

解题报告:HDU_6123 Destroy the cube (容斥+三元环计数)

题目链接题意及官方题解:记录一下自己的做法:首先如果可以直接跑全部的黑色位置,那就很好写,但是肯定会超时,所以一定要用对称性优化。如果n为偶数,可以完美拆成八个完全一样的小正方体的子问题,很好写如果n为奇数,问题就变得复杂而且要考虑各种细节。。先不考虑最中间的面,解决八个小正方体的子问题把中间面的所有黑色位置建图跑三元环然后发现会有重

2017-08-30 20:25:12

解题报告:HDU_6129 Just do it (找规律 两种做法)

题目链接题意及官方题解:思路:看到另一种做法,要巧妙一点,记录一下解法一(官方):打出当前位对后面位的贡献表,发现是个斜杨辉三角只有组合数为奇数才用贡献,由Lucas可知组合数C(n,m)为奇数等价于(n&m)==m这样就可以枚举m(1~n-1)快速更新答案虽然复杂度看上去是O(n^2),但是满足要求的组合数并不多(不会证明。。),能

2017-08-21 21:24:32

解题报告:HDU_6122 Color the chessboard (计数)

题目链接题意及官方题解:思路:分析题意可以发现计数只需要维护2*2的矩阵满足题目要求即可将奇数格的颜色翻转发现矩阵只会有三种形式:1、每一行颜色相同2、每一列颜色相同3、全部的颜色相同然后容斥一下即可代码:#includeconstintmod=998244353;constintN=1e3+5;usingn

2017-08-21 17:25:41

解题报告:HDU_6139 Galaxy at War (阶梯博弈)

题目链接题意:一张n*m的表格上有一些格子有一些水晶球,两个人轮流进行游戏每次选择一个有水晶球的格子,选择其中至少一个水晶球将它左移或者下移,不能出界还有一些格子上有M(Meditations)或者P(pollutantsources),对应的作用为当你选择的格子上有M时,若你选择移动t个水晶球,那么会将2*t个水晶球平分到可以移动到的格子内当t个水晶被移动到有

2017-08-20 21:06:49

解题报告:HDU_6134:Battlestation Operational (莫比乌斯反演)

题目链接题意:求思路:本来出题人想考的不是反演,但是用反演做意外的简单。。原式:做反演:令易知:   (D(x)为x的因子个数)那么可在内预处理出g(),再在线性时间内得到g()的前缀和每次查询的复杂度,总复杂度代码:#includeconstintN=1e6+10;constl

2017-08-18 17:06:13

解题报告:HDU_6128:Inverse of sum (二次剩余)

题目链接题意及官方题解:思路:已知公式:转换一下:对于每个y,满足要求的x为:只需要求的y的系数在(%mod)意义下的等价式即可等同于求sqrt(-3)的等价式,也就是求p-3在(%mod)意义下的二次剩余(Cipolla'salgorithm)注意一些细节:不考虑0、mod=2、mod=3、x==y时的计数以及不存在p-3

2017-08-18 16:39:43

解题报告:HDU_6127:Hard challenge (极角排序)

题目链接题意及官方题解:补充:我是以到x负半轴的弧度进行排序,然后扫过(0~PI)的弧度,中间每扫过一个点都要可能更新答案代码:#includeconstdoublepi=acos(-1.0);usingnamespacestd;classpoint{public:intx,y,v;doubleradi

2017-08-18 10:33:52

解题报告:HDU_6136:Death Podracing (优先队列+循环链表)

题目链接题意:n个人以不同的速度在环上顺时针或逆时针移动,每次相遇,移除下标小的,问最后只剩下一个人的时间的分数形式官方题解及思路:也不是第一次写循环链表的题了,还是写了好久。。注意维护循环链表时要同时更新左右指针代码:#includeconstintN=1e5+10;usingnamespacestd;structno

2017-08-18 10:15:28
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!