- 博客(32)
- 收藏
- 关注
RSS订阅
原创 POJ - 1742 Coins 背包dp变形
POJ 1742 首先多重背包有一种普通的二进制优化，然后这题还可以加一个判断如果，a[i] * c[i] >= m 的话，那就和完全背包一样，不用多重背包。这样应该能过。第二种做法，是参考了完全背包，完全背包可以用O(nm)的复杂度完成，是因为，遍历m的时候没有数量的限制。那对于这题多重背包，就要考虑在dp里面加上当前物品用掉的数量信息，从而达到完全背包的复杂度。所以用dp[i][j...
2018-08-09 21:04:37
202
原创 #539. 「LibreOJ NOIP Round #1」旅游路线
首先看到有T<=1e5T<=1e5T dp[i][j]=max(dp[i][j],dp[k][j−p[i]]+mp[i][k])dp[i][j]=max(dp[i][j],dp[k][j−p[i]]+mp[i][k]) dp[i][j] = max(dp[i][j], dp[k][j - p[i]] + mp[i][k]) ， mp[i][k]mp[i][k]mp[i][k]表示...
2018-08-06 17:01:27
388
原创 2017-acmicpc-world-finals F - Posterize
题意给n种颜色值，每种颜色值为r[i],数量为p[i]，按颜色值递增顺序给出。 现在可以任意制造k个特殊值。 每种颜色值会找到和它差最小的特殊值，然后产生一个(r[i]−k[i])2∗p[i](r[i]−k[i])2∗p[i]( r[i] - k[i] ) ^ 2 * p[i]的权值。 问总权值最小是多少？dp[i][j]表示，到第i个值，分成j段。每段都有一个特殊值。 那么转移方...
2018-08-06 13:06:32
680
原创 牛客网暑期ACM多校训练营（第五场）
E - room这题不要想太多，不应该想去怎么换人，而应该想怎么分配宿舍。 i作为原来的4人住宿，j作为新的4人住宿，那么i和j里都有的人就是不用换宿舍的。 至于不在j里的人，可以理解为他们需要换宿舍，搬出去了，但是搬到哪里不用管。 因为它们要去的地方肯定是会有人搬出来的，他们直接入住就可以。 这样就可以给i，j建边，然后跑费用流即可。#include <bits/std...
2018-08-04 18:14:04
156
原创 容斥原理练习记录
HDU 1796 How many integers can you find题意给你一个集合n，里面有1–n-1的整数，再给你一个集合m，里面有m个非负整数。 求集合n中能被集合m中某个数整除的数的个数。解很明显就是枚举因子的容斥，但是注意如果有两个因子6和9，那不能用他们相乘来容斥，应该取LCM。 正常情况下，应该是找素因子来容斥的。 这题m集合中可能会有0，要特判。...
2018-07-31 20:53:28
319
原创 ACM-ICPC 2017 Asia Urumqi A - Coins 概率dp
用dp[i][j]表示翻第i轮，有j个朝上，这题用往后推的方法比较好写。而不是在前面找。 然后用san[i][j]表示从抛i个硬币，有j个向上的概率，注意这个概率跟那i个硬币原来是正是反没关系。根据题目的要求，要尽量让向上的硬币多，所以每次尽量选朝下的硬币，但朝下的硬币可能不够，所以 dp里往后推的时候要分两种情况 1. 朝下硬币够k个，那么dp[i][j]*san[k+1][l+1] ...
2018-07-29 17:54:36
417
原创 Codeforces Round #497 (Div. 2) D - Pave the Parallelepiped
这场就不说啥了，打的很爆炸。。 漏了个return false结果函数返回值有问题，下次一定要注意。 D 题又是一个无敌容斥原理。。看来这个东西得好好补补了。 下面的题解算是对CF的editorial的理解和大致翻译吧 问你有一个(A,B,C)的平行六面体，让后让你找出(a,b,c)，能够用(a,b,c)把它填满。 问这样的(a,b,c)有几种。 首先肯定要找能整除A，B，C的，也就是找...
2018-07-28 20:25:01
214
原创 牛客网暑期ACM多校训练营（第四场）A - Ternary String 欧拉降幂
比赛的时候退出来的2的公式很麻烦。。结果根本就没想到欧拉降幂 之后看到题解里的公式竟然这么短。。 假设删去之前某个字符存在了n秒 那么删去0的时间 = 1 删去1 = n + 2 删去2 = 3∗2n+1−n−33∗2n+1−n−33 * 2 ^{n+1} - n -3 肯定是从左到右推，那么推到某个2的时候，前面的总时间在指数n+1中，因为最终时间是要模1e9+7的，也可以当做(3...
2018-07-28 20:24:45
180
原创 Benelux Algorithm Programming Contest 2014 Final
Benelux Algorithm Programming Contest 2014 FinalG - Growling Gears找−4ac−b2−4a−4ac−b2−4a \frac{-4ac - b^2}{-4a} 最大的就可以B - Button Bashing这题当时想多了，第一反应是一个背包，如果这题没有上下界的限制的话，用背包其实是可以的，可以把按键增加的...
2018-07-11 11:41:18
157
原创 Codeforces Round #493 DIV2
A - Balloons只有一堆的时候显然不可以。 两堆的时候，如果他们数量相等，也不可以。 其他情况，为了保险起见，我把他们排一下序，选择数量最少的那堆。其实只要不选数量最大的那堆就可以了。#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;using namespace std;int n;struct node{ int a,b;}p[100];...
2018-07-02 21:39:18
279
1
原创 Gym - 101201G Maximum Islands
题目链接这题题目很短，第一步的思路很快就想到了，就是把L的周围直接改成W，这是很显然的。 然后就是对剩下的C求一个能选择的最大数量，而且要互相不能碰到。 当时脑子一抽竟然用贪心来做，唉。比赛之后一想这就是个二分图最大独立集啊。。对于这类在图上选择最多的相互没有关联的点，就是经典的最大独立集问题。最大独立集 = 总点数- 最大匹配数对于无向图求最大匹配数，就是对于有关系的两个...
2018-05-14 11:56:27
234
原创 2017ICPC青岛K Our Journey of Xian Ends
Our Journey of Xian Ends 现场赛做到这题还剩1个多小时，首先心态就有些急了。 然后读题的时候比较急躁，题目又臭又长，导致没有发现，如果要在上海的两个机场之间走的话，只有一种走法。 但是由于要经过某两个特殊点，网赛有类似题，于是知道是费用流，先把板子敲上去，敲板子期间队友突然有建图的想法，然后让我来敲建图 。。。 期间一顿混乱，没能很好理解队友的意思，最后连样例都没过
2017-11-23 21:28:32
658
1
原创 HDU 4322 Candy 最大费用流+巧妙建图
单单用最大流显然是不能达到最佳分配的，应该使用费用流。 费用很显然，对于喜欢的糖，费用就是K，我一开始想的是用b[i]/kb[i]/k来表示容量上限，但后来发现这样是不对的，因为可能最后一颗糖加上之后费用超过了b[i]b[i]，但实际得到的快乐值只有b[i]b[i]，所以要对b[i]%kb[i] \% k 进行讨论 1. 若b[i]%k==0 b[i] \% k == 0 那么把连接人到超级汇
2017-10-25 23:01:52
257
原创 HDU2435 There is a war 修改一条边权值后的最小割
题目简单来说就是让你在2…(n−1)2\ldots(n-1)之间修改一条边的权值，可以是原来存在的边，也可以是原来不存在的边，只能把权值改成INF，求最大的最小割。这题就是稍微优化点的暴力，首先要能修改最小割，那么一定是改做完最小割之后，连接左右两块的边，之后再重新求一次最小割。所以做完最小割之后把左右两块的点用dfs跑出来。之后就是枚举边，我一开始是先把不存在的边也add进去，权值记为0，然后fo
2017-10-14 11:09:25
238
原创 CodeChef - COUNTARI Arithmetic Progressions FFT 分块
这题因为ijk大小关系的限制，所以不能像三个傻瓜那题一样直接FFT，排序后排出情况。所以一开始想到的是对每个位置都做一次FFT，即枚举AjA_j，用Ai和AkA_i 和 A_k做FFT，但这复杂度明显是不行的O(N∗30000∗log30000)O(N * 30000*\log30000) 然后看了题解才知道还有分块这种方法。。具体的分法就不说了，网上有一大堆，最后的复杂度就是O(N2K+k∗30
2017-09-30 18:10:45
206
原创 URAL 1996 Cipher Message 3 FFT KMP
首先还是要回到卷积的定义上 C(k)=Σi+j=kai∗bj C(k) = \Sigma_{i+j=k} a_{i}*b_{j} 这题这种做法我是看了题解之后才知道的。如果a是a1a2a3a4a_1a_2a_3a_4 ，B是b1b2b3b_1b_2b_3 ，如果我们做卷积，那么其中C5=a2∗b3+a3∗b2+a4∗b1C_5 = a_2 * b_3+a_3*b_2+a_4*b_1，这和我们的比
2017-09-29 21:25:28
228
原创 2016 香港网络赛 A题. A+B Problem (FFT)
题目地址 给你一堆数，问你满足ai+aj=ak a_i+a_j = a_k 的 (i,j,k) (i,j,k) 三元组的数量。 因为有负数，所以给每个数右移50000 然后几乎是一个裸的FFT，就这么提交，然后WA了。之后想到了忘记判不符合的情况了，只有一个地方要考虑一下。就是ai=0且j==k或者aj=0且i=ka_i = 0 且 j==k 或者 a_j=0 且 i=k 容易想到这个次数就
2017-09-28 22:45:44
315
原创 HDU 4609 3-idiots FFT入门
给你一堆数，问你组成三角形的概率是多少。首先用FFT算出可以用两个数组成的长度。把数当做权值，出现一个数就在那个权值位置加1。 然后就是用FFT计算多项式乘法。然而这样会有重复 1. 一个数自己和自己组合是不存在的，所以要删一次 2. 比如有两个数1 2 ，取(1,2)和取(2,1)是一样的，这样等于所有情况都算了两遍，除以2即可。然后算能组成三角形的情况个数。 把FFT的结果先做一个前缀和
2017-09-28 21:42:11
176
原创 HDU 6194 String String String 后缀数组 正好出现K次的子串个数 CSU1632 至少出现2次的子串个数
求正好出现K次的子串个数。 对于k≥2 k \ge 2 的时候 ，维护一个大小为k-1的区间，LCP(l,r)就是该区间内出现K次的子串个数，因为有些子串可能会在与这个区间的相邻的两端出现，所以要把他们减掉，即贡献是LCP(l,r)−max(height[l−1],height[r+1]) LCP(l,r)-\max(height[l-1],height[r+1]) 对于 k=1 k = 1 的时
2017-09-27 00:04:53
507
原创 后缀数组入门练习
rank数组建议写成rk，因为rank极有可能会和某个库函数里的东西冲突。。 要注意不同的模板里面排序的起始标号可能也会不同，有些rank和sa都是从1开始的，而有些是从0开始的。建议在做题前找一个好的模板，做题过程中熟悉模板。
2017-09-21 21:26:19
269
原创 POJ2396 Budget 上下界网络流
表示弱看了半天才能勉强看懂啊。。为什么有上下界会流量不守恒，可以看这篇文章，里面有证明。嗯。如果理解了原理的话，这题应该算是一个入门题了吧。要注意的地方就是，因为给的条件有大于和小于，所以更新low和up的时候用cap-1，cap+1，而不是cap。。调了好久才发现的。。#include <cstring>#include <iostream>#include <algorithm>#incl
2017-09-15 17:51:00
197
原创 SPOJ 839 Optimal Marks
最小割的经典题。这题的具体做法就不说了，网上一大堆说的很好的。我说一下怎么理解这题里的最小割吧。一条边如果在最小割之中，你可以理解成让这条边左边的点与右边的点矛盾所需要的代价。下面的讨论都是限定在某一个二进制位上：如果能让所有的点都在一个集合中那是最好的，因为所有XOR的结果都是0。 但这明显是不可能的，因为根据题目所给的已知数字，已经分成了两部分了，即这个二进制位是0还是1。 默认左边集合是1
2017-09-14 21:55:54
151
原创 POJ 2699 The Maximum Number of Strong Kings 最大流
题意就是给你一个完全图和每个人胜利的场数，我们知道在完全图中胜利的场数之和一定等于边数（因为一条边必定有一个人胜一个人负）。一个人是strong king，当且仅当他赢过所有分数比他高的人，问最多有几个strong king。这题主要就是胜利场数的分配问题，当strong king多起来之后，首先可以判断出当比一个人分高的人数大于他的胜场时，他一定不是strong king。并且strong kin
2017-09-12 12:01:01
246
原创 HDU 4309 Seikimatsu Occult Tonneru 状压枚举+网络流
这题其他的建模都很常见，只有一种特殊边就是第一次走过免费，之后再次走只花一次的钱就可以永久免费。 所以我下面就只说这个边怎么处理了。
2017-09-07 19:58:49
193
原创 POJ 3690 Constellations + Gym - 100783J The Big Painting 二维字符串hash
这次组队赛也出现了同样的题目，然而不会做。所以来学习一波新姿势。 二维字符串hash的原理就是先把行横着做普通的一位字符串hash，然后每一行都有一个hash值，再竖着将行与行的hash值再hash一次。原理并不复杂。然后注意横着和竖着hash取两个不同的大质数就可以了。 把x1x1 , 当做横着hash的质数，x2x2 当做竖着hash的质数。 对于这题来说。 r[i][j] 表示横着h
2017-08-29 17:12:20
523
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人