ACZone-CSDN博客

原创 CodeForces - 963A Alternating Sum 逆元等比数列

CodeForces - 963A Alternating Sum 逆元等比数列http://codeforces.com/problemset/problem/963/A题意：求解 n∑i=0 sian−ibi∑i=0nsian−ibi mod 109+9，si表示正负，并告诉你前k个si的符号，且满足si=si−k。题解：令u= k∑i=0 sian−ibi∑i=0nsian−ibi ，z=(b/a

2018-04-18 11:56:59 320

原创 CodeForces - 898D Alarm Clock

CodeForces - 898D Alarm Clock题意：有n个闹钟，每个闹钟在第ai分钟响起并持续一分钟。如果在连续的m分钟内有至少k个闹钟响起，那么你就必须起床。现在为了不用起床，要求关闭最少的闹钟的数量。题解：进行模拟即可，另开数组存已经开启的闹钟。

2017-12-22 09:06:32 357

原创 CodeForces - 902C Hashing Trees 构造

CodeForces - 902C Hashing Trees 构造题意：给出一颗n层的树。以及从第0层开始给出每层的节点个数。求是否存在同构，若存在输出其中任意两种。题解：可以发现若存在同构：①该节点上一层的节点数大于1，②该节点所在层节点个数大于1。剩下的通过构造即可，代码的root变量是父节点。

2017-12-20 20:58:53 502

原创 CodeForces - 902B Coloring a Tree 思维

CodeForces - 902B Coloring a Tree 思维题意：给你一颗树进行染色，根节点为1。每个节点要求染成颜色xi，对于一个节点进行染色操作，那么它的所有后代都被染成这个颜色。题解：对于节点看它是否与与其父节点同色，若同色就不需要重新染色，若不同就需要进行一次染色操作。

2017-12-20 20:03:19 393

原创 CodeForces - 898C Phone Numbers STL

CodeForces - 898C Phone Numbers STL题意：给出n个人，以及每个人的号码，如果号码a是另一个号码b的后缀，那么a就要被删除。题解：STL代码实现，具体看代码实现。

2017-12-18 21:45:55 494

原创 CodeForces - 899C Dividing the numbers 思维

CodeForces - 899C Dividing the numbers 思维题意：给你1~n连续的n个数。将这n个数分成两拨，要求两拨之差的绝对值k最小。求出这个最小的绝对值，并输出其中的一拨的数字。题解：首先要想清楚这个k非零即一。先将问题分解成两类：奇数和偶数。先看最简单的偶数：由于可以组成如1，n以及2，n-1这样的数对。①如果n%4==0。那么就有偶数组上述数对，直接构造输出即可。k就等于0。②如果n%4!=0。那么两拨分完之后还剩下一个上述数对，那么一拨一个。很容易

2017-12-18 21:24:53 992

原创 CodeForces - 899D Shovel Sale 数学+思维

CodeForces - 899D Shovel Sale 数学+思维题意：给你1，2，...，n，现在要求取出一对数相加为x。x需要满足：以最多个9结尾。现在给你n，求这样的数对有几个。*例如，9099算以两个9结尾题解：设题意的x最多以k个9结尾。①先想到要求这个k是多少，可以发现一个特殊的数字5，50，500，...。当n<5时，k=0；当n>=5&&n>50时，k=1；当n>=50&&n<500时，k=2...也就是说x是这一样一个数：Z999......（0<=Z<=8，后面接上k个

2017-12-18 20:51:00 898

原创 CodeForces - 892C Pride GCD

CodeForces - 892C Pride GCD题意：给你一个数列，有操作：对于相邻两个数，可以替换其中一个数为这两个数的gcd。求多少次操作后该数列全为1，不存在输出-1。题解：可以发现，①只要数列中出现了1，那么对于1相邻的数操作，将相邻的数变为1即可(操作次数是数列中剩下不为1的数)。②数列中不存在1，需要找出1(可能需要多次操作才会出现1)，那么对于原数列每个相邻的数求一次gcd，看是否出现了1。若没出现那么对于gcd再求一次gcd，知道只剩一个gcd(操作次数是反复求gcd至出现1的次数

2017-11-24 10:06:43 290

原创 CodeForces - 894C Marco and GCD Sequence 构造+思维

CodeForces - 894C Marco and GCD Sequence 构造+思维题意：有数列a[1],a[2],...,a[n]，按照方法gcd(a[i],a[i+1],...a[j]) (i<=j)，求出所有gcd放入set。现在反过来已知set，求其中一组可能的数列。题解：比赛时的想法是，①求出所有数的gcd为GCD，一定要等于最小那个数，②这个set就是其中的一组解(满足单点gcd)。后来被hack了，数据是1 3 8 12。8和12产生了新的区间gcd。所以应该加入限制，set中每

2017-11-24 09:42:43 230

原创紫书 - UVA - 1151 Buy or Build 最小生成树+状态枚举

紫书 - UVA - 1151 Buy or Build 最小生成树+状态枚举https://vjudge.net/problem/UVA-1151题意：平面上有n个点，两点间的费用为两点的欧几里得距离。另外还有m个套餐，购买第i个套餐需要花费c[i]，购买后套餐中的点均连通。题解：先对原图求一次最小生成树，将原图的其他边都去掉，仅剩下这n-1条边。然后状态枚举[0,1<<m)进行购买套餐的操作，然后再求最小生成树即可。这种思路是正确的：用Kruskal算法求最小生成树时，就是每次优先选择最小的边，而

2017-10-30 22:19:41 228

原创 CodeForces - 876D Sorting the Coins 模拟+思维

CodeForces - 876D Sorting the Coins 模拟+思维http://codeforces.com/contest/876/problem/D题意：每次执行算法：①每次都是从左向右看，②看到第i个时，如果他是非法的且第i+1是非法的就交换这两个，③最开始先看一遍不做交换。求最后没有可以交换了，需要执行算法几次。现在每次往里面放一个非法的硬币，求每次需要执行上述算法几次(第一次什么都不放)。题解：其实写几个就可以发现，每执行一次算法，非法硬币就有一个会归位到末尾且不再移动。所以

2017-10-20 18:47:20 359

原创 CodeForces - 876B Divisiblity of Differences 思维

CodeForces - 876B Divisiblity of Differences 思维http://codeforces.com/contest/876/problem/B题意：给你n个数字，要求在其中选出k个数字，要求这k个数字两两之差能被m整除。题解：这题被hack+大数据不过，好菜啊。每个数对m取余得到x，记录这个x出现的次数，大于k则存在，输出k个a[i]%m==x的a[i]即可。

2017-10-18 09:10:57 429

原创 CodeForces - 872B Maximum of Maximums of Minimums RMQ

CodeForces - 872B Maximum of Maximums of Minimums RMQhttp://codeforces.com/contest/872/problem/B题意：将一个数组连续的分成k块，每块中取最小值。求这k个最小值中的最大值。题解：①分成一个的情况：就是最小那个，②分成两个的情况：暴力即可，我用了rmq，没在意负数初始化成-1了。。。③k大于3的情况，把最大的那个数分成独立的一组即可。

2017-10-15 19:57:26 297

原创 hdu4324 Triangle LOVE 拓扑排序或强连通分量

hdu4324 Triangle LOVE 拓扑排序或强连通分量http://acm.split.hdu.edu.cn/showproblem.php?pid=4324题意：有n个人，u和v之间的关系有且仅有u喜欢v和v喜欢u中的一种。在要求其中是否存在三角关系。题解：由于每两个人之间都有关系，即有向边。那么对于环就肯定存在三角关系。比如a->b->c->d->a，根据题意，对于a和c肯定存在一条有向边，那么就是有三角关系。所以可以根据是否存在拓扑排序来判断是否有环，以及是否存在强连通分量(就是环)来

2017-10-15 11:56:59 235

原创 poj3114 Countries in War 强连通缩点+最短路

poj3114 Countries in War 强连通缩点+最短路http://poj.org/problem?id=3114题意：有n个城市和m条通道，①从u城市到y城市需要w小时，②如果两个城市相互可达属于同一个国家，属于同一个国家的两个城市之间通信不需要时间。现在给出q个询问，求u城市到v城市的最短通信时间。题解：首先tarjan求强连通分量，然后缩点进行存图。最后跑最短路即可，我用的是SPFA，刚好SPFA的代码存的是链式前向星的板子。

2017-10-14 17:04:56 281

原创 hdu3639 强连通+缩点 tarjan算法

http://acm.split.hdu.edu.cn/showproblem.php?pid=3639 题意：投票：如果A投给B，B投给C，那么C也会得到A的投票。现在要求谁的票最多，并输出这些人的编号。题解：跑tarjan求强连通分量，在强连通分量的队伍中，每个点都是相互投票的。那么对原图进行缩点，然后反向建图。选出入度为0的队伍进行dfs，求出有队伍投给了这个队伍。将总人数求和减去自己即可。最后输出在这个

2017-10-13 20:51:33 358

原创 CodeForces - 868C Qualification Rounds 思维

CodeForces - 868C Qualification Rounds 思维http://codeforces.com/contest/868/problem/C题意：有n道题目，k支队伍，现在要从n道题中取x道题(x>0)作为比赛题。要求这x道题中，每支队伍所知的题目不超过x/2。求是否存在这样的x。题解：官方的tag给出的是dp。当时我做的时候看到k最大就是4，干脆就暴力了。中间bool没有初始化，wa一发。代码打得好长，ide中间还崩溃了又得重新打。看来得养成ctrl+s的好习惯。大致思路

2017-10-05 19:47:29 289

原创 CodeForces - 868B Race Against Time 思维

CodeForces - 868B Race Against Time 思维http://codeforces.com/contest/868/problem/B题意：时针、分针、秒针将钟面分成三块，现在要从a点钟到b点钟是否可达。题解：求出每个针所指的角度范围，然后记得从小到大排序，最后我按照左闭右开去判断是否属于同一块区域。

2017-10-05 19:41:05 464

原创 CodeForces - 868A Bark to Unlock 水题

CodeForces - 868B Bark to Unlock 水题http://codeforces.com/contest/868/problem/A题意：密码为两位的小写字母，现在你可以猜n次，求这些组合中是否可以匹配原密码。题解：暴力匹配。

2017-10-05 19:38:18 326

原创 poj3352 Road Construction 边双连通分量tarjan算法

poj3352 Road Construction 边双连通分量tarjan算法http://poj.org/problem?id=3352题意：有n个城市m条道路，一开始任何两个城市相互可达。现在需要某条修路，修路时该道路不可通行。然后需要搭建临时的桥，使得任何两个城市仍是相互可达的。求最少需要搭建的桥的数量。题解：这是一个无向图，去掉一条边就不连通。那么这条边就是桥。现在要搭建临时的桥，搭建完后与原图一起，这个有向图就是边双连通的(边连通度大于1)。现在就是求加上几条边使得这个无向图是边双连通的。

2017-10-03 21:21:58 290

原创 poj1236 Network of Schools tarjan算法

poj1236 Network of Schools tarjan算法http://poj.org/problem?id=1236题意：给你一个有向图，1、求最少给多少的点发信息，可以使得所有的点都可以得到信息，2、求最少加上多少条边后，可以使图强连通。题解：1、跑完tarjan算法后，将每个强连通分量缩点，然后求出入度为0的缩点的个数，这也是最小点基的定义。2、最少加上多少条边后，可以使图强连通。可以发现找出入度为0和出度为0的缩点个数a，b。若a>b，可以从每个入度为0的点向出度为0的点连边，反之

2017-10-03 14:54:39 207

原创 CodeForces - 865A Save the problem! dp+思维

CodeForces - 865A Save the problem! dp+思维http://codeforces.com/problemset/problem/865/A题意：总面值n，以及零钱面值数m：a1，a2，...，am，可以有num种兑换方式。现在反过来告诉你num，求n，m以及a1，a2，...，am。题解：容易发现，零钱面值1和2，可以组成的面值n的兑换方式是最大的。所以只对零钱面值1和2dp即可。

2017-10-02 15:58:37 501

原创 hdu6206 Apple 2017icpc青岛赛区 java高精度类

hdu6206 Apple 2017icpc青岛赛区 java高精度类http://acm.split.hdu.edu.cn/showproblem.php?pid=6206题意：给出四个点，判断地四个点是否在其他三个点确定的圆内。题解：确定圆心和半径。double有精度损失，所以用java的BigDecimal类。设圆心(x,y)，三个点(x1,y1)，(x2,y2)，(x3,y3).有方程组：(x1-x)^2+(y1-y)^2=(x2-x)^2+(y2-y)^2(x3-x)^2+(y3-y

2017-09-29 21:26:19 312 1

原创 hihocoder1586 Minimum 2017icpc北京赛区线段树区间最值

hihocoder1586 Minimum 2017icpc北京赛区线段树区间最值https://hihocoder.com/problemset/problem/1586题意：给出2^n个数。两个操作，1：访问[x,y]，i,j∈[x,y]使得a[i]*a[j]最小，输出这个最小值。2：修改位置x的值为y。题解：很基础的线段树。比赛时题意理解出错，以为i和j是不相等的。一直想着是不是应该求出第二大和第二小，这个需要主席树。但是过的人这么多，队友说不可能是主席树。北京+南宁出现了好多失误，南宁那场甚

2017-09-28 20:48:51 231

原创计蒜客 Minimum Distance in a Star Graph 2017icpc南宁赛区字符串bfs

计蒜客 Minimum Distance in a Star Graph 2017icpc南宁赛区字符串bfshttps://nanti.jisuanke.com/t/17317题意：又是一长串阅读理解。总之，给你两个数字a，b。操作：a的第一位数字可与其它位交换。现在求最小的操作次数使a=b。题解：bfs，顺便记录已经出现过的数字(剪枝)。

2017-09-27 21:50:24 281

原创计蒜客 Weather Patterns 2017icpc南宁赛区

计蒜客 Weather Patterns 2017icpc南宁赛区https://nanti.jisuanke.com/t/17308题意：比赛最后一小时半，还一直在看没看懂。最后去做了G题计算几何。活脱脱一道阅读理解吧。一共四种天气，输入4*4的矩阵。a[i][j]表示今天i天气明天j天气的概率。接下来输入两行，每一行表示每天的天气，问这样的天气序列出现的概率。接下来还有两行，表示连续天数是i天气的期望，就是连续一天是i天气的概率+连续两天是i天气的概率+...+连续一天是n天气的概率。输出保留八位小

2017-09-27 16:03:58 254

原创计蒜客 2017icpc南宁赛区 The Heaviest Non-decreasing Subsequence Problem 最长不递减子序列

计蒜客 2017icpc南宁赛区 The Heaviest Non-decreasing Subsequence Problem 最长不递减子序列https://nanti.jisuanke.com/t/17319题意：对于每个数x，若x<0，则价值为0，x大于10000，价值为5且数值变为x-10000，反之价值为1。现在求不递减的序列使得价值最大。题解：负数没有贡献不考虑，大于10000的存五次，相当于价值为1，反之存一次。然后求一次最长不递减子序列即可，答案就是子序列长度，因为价值都是1，这样处

2017-09-26 21:39:26 281

原创 hihocoder1584 Bounce 2017icpc-北京赛区扩展欧几里德

hihocoder1584 Bounce 2017icpc-北京赛区扩展欧几里德https://hihocoder.com/problemset/problem/1584题意：在n*m的网格上，一颗小球左上方出发往右下的格子走，碰到边界就反弹，当小球到达角落就停止运动。求小球只经过一次的格子的数量。题解：如图(3*4为例)，可以把每次反弹后的线路展开，每次反弹就增加m-1(碰到上下边界)或者n-1(碰到左右边界)。因为小球是45度方向，所以最后展开一定是正方形。于是可以列出不定方程(m-1)*x+m

2017-09-23 20:06:29 318

原创 hdu3440 House Man 差分约束系统 SPFA算法

hdu3440 House Man 差分约束系统 SPFA算法http://acm.hdu.edu.cn/showproblem.php?pid=3440题意：现在有n幢房子，具有不同的高度。超人只能从矮的地方飞到刚好比当前房子高的地方。现在你可以移动房子，但是房子的相对位置不能改变，且超人每次跳跃的水平距离小于d，求最矮的房子到最高的房子的水平距离的最大值。列出两种不等式：①房子的相对位置不能改变：dis[i]-dis[i-1]>=1->dis[i-1]-dis[i]<-1②超人每次跳跃的水平距

2017-09-21 16:10:01 187

原创 poj3169 Layout 差分约束系统 SPFA算法

poj3169 Layout 差分约束系统 SPFA算法http://poj.org/problem?id=3169题意：有n头牛按序号升序拍成一列，有两个限制条件：①A牛和B牛的距离不得大于X，②C牛与D牛的距离不得小于Y。若不存在输出-1，有多种排列输出-2，反之输出1和n的距离。题解：有方程组：A-B<=X;C-D>=Y;...C-D>=y->D-C<=-y那么对于每个不等式dis[i]-dis[j]<=x，变化为dis[i]<=dis[j]+x。很像最短路的更新条件dis[i]>di

2017-09-21 14:33:35 234

原创 hdu2121 Ice_cream’s world II 最小树形图+不定根(朱刘算法)

hdu2121 Ice_cream’s world II 最小树形图+不定根(朱刘算法)题意：一个有n个节点的有向图，以其中一点vi为根建树要求花费最小。求这个最小花费和vi。题解：用朱刘算法求最小树形图，复杂度是O(n*m)，遍历每个点跑一次朱刘算法是O(n*n*m)。需要优化，这时候可以想到设一个虚拟的根v，v与每个点都可达，且权值很大为sum(原图所有边权和)。这样跑完朱刘算法后得到答案ans。如果ans-sum>=sum，说明原图不连通，因为v与原图至少连了两个点。

2017-09-19 14:48:52 517

原创 Coin 2017icpc-西安赛区牛顿二项式

Coin 2017icpc-西安赛区牛顿二项式https://nanti.jisuanke.com/t/17115题意：有一枚不均匀的硬币，正面朝上的概率是q/p。现在抛k次硬币，求其中有偶数次正面朝上的概率为X/Y，现在要求输出X*(Y对于1e9+7的逆元)。题解：for(int i=0;i<=k;i+=2){ ans+=C(k,i)*(1-q/p)^(k-i)*(q/p)^i;}可以看出这是一个牛顿二项式，但是求的是偶数项。根据牛顿二项式有：偶数项+奇数项=(a+b)^k=1偶数

2017-09-16 19:13:48 231

原创 poj1679 The Unique MST 次小生成树

poj1679 The Unique MST 次小生成树http://poj.org/problem?id=1679题意：求最小生成树是否唯一题解：求出次小生成树，如果两者相等，则不唯一(存模板)。

2017-09-16 10:22:31 197

原创算法学习之模线性同余方程组(中国剩余定理+求解同余方程组) poj1006+hdu3579

算法学习之模线性同余方程组(中国剩余定理+求解同余方程组) poj1006+hdu3579中国剩余定理中国剩余定理原文：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？解法：中国剩余定理描述的就是一元线性同余方程组(其中m1，m2，...，mn均互质)。求解同余方程组中国剩余定理就是在求解同余方程组，但是当除数两两不互质的情况。就不能用CRT的结论来解决。还是这个方程组，现在取出其中两个方程： x≡a1(mod m1) x

2017-08-23 13:10:42 2896

原创 hdu6168 Numbers 2017多校1008 map

hdu6168 Numbers 2017多校1008 maphttp://acm.split.hdu.edu.cn/showproblem.php?pid=6168题意：由一个a数组，通过ai+aj(1<=i<j<=n)构成b数组。现在给你a和b数组的混合，求a数组。题解：每次存入时，用map标记每个数字的出现次数(数据是从小到大给的，所以可以不用排序)。然后前两个数开始相加，然后更新map(感觉有点筛法的意思)。更新之后，如果map中这个数还出现，就记入答案并更新map。

2017-08-23 09:19:18 179

原创 hdu6165 FFF at Valentine 2017多校第九场1005 dfs

hdu6165 FFF at Valentine 2017多校第九场1005 dfshttp://acm.split.hdu.edu.cn/showproblem.php?pid=6165题意：给出一个有向图，要求图上任意两点是可达的(不需要相互可达)题解：dfs，每次搜索每个结点的儿子然后标记连通即可。

2017-08-23 09:14:44 210

原创 51nod1119 机器人走方格 v2 费马小定理求逆元

51nod1119 机器人走方格 v2 费马小定理求逆元题解：向右总共走n-1，向左总共走m-1，总步数就是n+m-1。所以答案就是C(n+m-1,n-1)，n+m-2步中挑其中n-1步向右。本题数据较大，不可以通过单纯求组合数的公式(杨辉三角或者单个暴力)或者dp。从组合数公式入手，由于除法不可取余，需要求逆元。根据费马小定理有：a和n互质，那么a^(n-1)=1(mod n)。所以a*a^(n-2)=1%(mod n)，即a的逆元就是a^(n-2)。

2017-08-22 13:19:04 295

原创 51nod1006 最长公共子序列Lcs dp

51nod1006 最长公共子序列Lcs dphttps://www.51nod.com/onlineJudge/questionCode.html#!problemId=1006题意：求两个串a，b的最长公共子序列。题解：子串是连续的，子序列可以是不连续的。dp[i][j]：表示以a[i]和b[j]结尾的最长公共子序列的长度。转移公式：dp[i][j]=max(dp[i][j-1]，dp[i-1][j]，dp[i-1][j-1]+(a[i]==b[j]?1:0))接下来是怎么保存答案的问题的

2017-08-21 15:08:13 197

原创 51nod1058 N的阶乘的长度+51nod1130 N的阶乘的长度 V2（斯特林近似）学习斯特林公式

51nod1058 N的阶乘的长度+51nod1130 N的阶乘的长度 V2（斯特林近似）学习斯特林公式题意：N的阶乘的长度(都是水题，只是记一下公式)。题解：由斯特林公式：n！=sqrt(2*π*n)*(n/e)^n。那么长度log一下即可，具体看代码。

2017-08-21 14:07:00 245

原创 51nod1057 N的阶乘压位

51nod1057 N的阶乘压位http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1057题意：求出N的阶乘准确值题解：一直没接触过这种类型的，以为需要大数的模板。结果看了别人的代码，用的巧妙的压位。其实也是大数的思路，大数加减乘除模板，是将一个长度为n的数划分成n位。我们这里也需要划分，如果是划分成一位。那么时间复杂度是不变的，只是解决了int的溢出问题。所以划分的大一点，即可以减少数组的开销，又可以降低时间复杂度。我还专门

2017-08-21 13:32:30 269

空空如也

空空如也