- 博客(28)
- 收藏
- 关注
RSS订阅原创 牛客挑战赛28 C.msc的宠物
题目链接：https://ac.nowcoder.com/acm/contest/217/C题意：msc有n个小宠物，这些宠物的家是连在一起的，更有趣的是，这些宠物的家之间的连接关系形成了一个树的形态。每个小宠物的习性是不太一样的，比如说有的可能吃素，有的可能吃荤。作为直觉系女生，msc凭着自己突出的直觉对每个小宠物都有一个关于习性的评估值，对于宠物i，它的评估值是a[i]。考虑到习性...
2018-11-12 21:27:29
309
2
转载 HDU5942 : Just a Math Problem
https://www.cnblogs.com/clrs97/p/6012285.html
2018-11-12 17:21:45
161
原创 AtCoder Regular Contest 103 D.Robot Arms 构造
题目链接：https://arc103.contest.atcoder.jp/tasks/arc103_b题意：给1000个二维平面上的点，坐标值域[-1e9,1e9]，构造一个机械臂，最多40条边，每条边有长度和方向，方向可以是上下左右，你需要确定边的个数和各个边的长度，再对于每一个题目给出的点，通过改变每条边的方向，使得每个点都可以通过机械臂和(0,0)连接，注意(0,0)和每个询问点...
2018-09-30 14:32:21
218
原创 CodeForces - 891B.Gluttony
题意:给一个数组a,构造一个b数组使得b是a的一个排列,且对于所有下标的子集(除全集和空集之外),a数组对应位置的数之和不等于b数组对应位置的数之和,若不能输出-1,保证a数组无重复数字出现题解:首先，由于考虑所有下标子集，在构造出一对a，b后，将下标任意重新排列，可以保证同样成立，那么我们考虑a数组的有序排列作为a数组，在最后映射回去即可对于一个已经排序的a数组，一个可行的b是将...
2018-09-11 17:01:49
175
原创 Gym 101630G The Great Wall
题意:三个有n个正整数的数组满足a[i]<b[i]<c[i],固定一个r,根据不同的x,y生成不同的数列,每对合法的x,y(x<y)生成两个区间[x,x+r-1],[y,y+r-1],合法指生成的区间不会越界,如果一个点i被两个区间覆盖,他的值就是c[i],如果被一个覆盖就是b[i],否则a[i],一个数列的价值等于所有点的值之和,问在所有x,y生成的序列中价值第k大的是多少...
2018-09-04 22:43:26
526
原创 Manthan, Codefest 18 (rated, Div. 1 + Div. 2) F - Maximum Reduction
题意:function z(array a, integer k): if length(a) < k: return 0 else: b = empty array ans = 0 for i = 0 .. (length(a) - k): temp = a[i] ...
2018-09-03 10:19:37
165
原创 Codeforces Round #492 (Div. 1) [Thanks, uDebug!] E - Number Clicker
题意:给出u,v,p三个正整数,有三种操作u=(u+1)%p,u=(u+p-1)%p,u=pow(u,p-2)%p，找到一种方法使得200步之内通过这三种操作令u变为v，保证有解分析:相当于一个每个p个节点每个节点最多3条边的图让你找两点之间长度不大于200的路径实际上逆元这条边相当随机，好像是有人研究过这类问题的，贴一下CF官方题解的说法:We present two sol...
2018-08-23 21:19:47
357
原创 Codeforces Round #492 (Div. 1) [Thanks, uDebug!] D - Game
题意:给出一个长度为n的二进制数x和一个长度为(1<<n)的数组C，一开始x的每一位都为-1，有两位玩家A和B，每轮随机选出一名玩家将x中的一个-1改为0或1(由玩家决定)，在x确定之后游戏的结果为C[x]，玩家A想让C[x]大，玩家B想让C[x]尽量小，求C[x]的期望，此外，还会有r次更改，每次修改C数组的某个值，对于每次修改也求出C[x]的期望分析:对于二进制位的每一...
2018-08-23 20:02:41
183
原创 Codeforces Round #492 (Div. 1) C - Leaving the Bar
题意:给出n个向量，令一些向量反向使得所有向量的和的长度不超过1.5e6，其中每个向量长度不超过1e6，n <= 1e5分析:任选三个向量，他们本身和他们的反向中总能选出两个相互夹角大于120°的向量，这样就可以让向量长度减少，每次选出三个做即可，实现时用一个集合表示某些向量的和，并用带权并查集维护是否反向#include<bits/stdc++.h>#def...
2018-08-23 19:36:00
135
原创 Codeforces Round #493 (Div. 1) B - Roman Digits
题意:1,5,10,50四种硬币不限量，问用刚好n个硬币可以凑出多少种不同的数,n<=1e9分析:本题的一大难点在于同一个数可能被不同的硬币所表示，可以通过如下方法化简:由于硬币数量固定，我们可以把所有硬币的价值-1,使得价值变为{0,4,9,49}考虑如果我们选了(49+x)个4或者9，可以将其换成x个4或9，将49的倍数部分用0和49进行填充所以我们可以枚举4和9各选i,...
2018-08-21 14:01:24
126
原创 2018 牛客多校第四场B Interval Revisited
• 给出n个带权区间，选择若⼲干区间，覆盖[1, m]，使得每个位置被覆盖权值和的最大值最小• n, m <= 2000 分析:• ⼀一个显然的结论：每个位置最多被两个区间覆盖• 所有区间按照右端点从小到大排序• dp(i, j)表示最后选择的区间为i，第一个只被覆盖一次的位置是j，且[1, j]覆盖完成的权值和的最大值的最小值• 转移的过程相当于固定尾区间枚举前一个区...
2018-08-19 20:25:36
240
转载 LightOJ 1422 Halloween Costumes (区间dp)
题意和思路转自https://blog.csdn.net/yyyy_h/article/details/50557550题意：告诉有n场晚会中需要穿的衣服，衣服是可以套在其他衣服外面的，也就是说如果顺序为 1 2 1，那么可以将2套在1外面，第三场晚会需要穿1的时候把2脱掉即可，这样就只需要穿两次衣服。题目是再告诉了顺序之后需要求出在某种序列下最少需要穿多少次衣服。样例 1 2 1 2： ①穿1 ...
2018-05-16 01:26:48
116
转载 2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest 4
http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204https://wiki-ascender.icpc.camp/2016_WTC_MRS
2018-05-01 19:08:54
1136
原创 URAL 1003 并查集
有一个01串，给出K次询问，每次回答区间[l,r]中1的个数是奇数还是偶数，找出第一次产生矛盾的地方，如果没有输出K题解:把端点看成0~x的前缀和sum[x], 就可以得到向量关系sum[r]-sum[l-1]= odd/even, 转化为带权并查集处理#include #include #include #include #include #include #include
2018-01-29 14:25:01
156
转载 【codeforces 749E】 Inversions After Shuffle
原题解:https://www.cnblogs.com/MashiroSky/p/6246624.html题意 给出一个1~n的排列，从中等概率的选取一个连续段，设其长度为l。对连续段重新进行等概率的全排列，求排列后整个原序列的逆序对的期望个数。Solution 考虑对于每一对数(ai,aj),ij(ai,aj),i算贡献。 1.连续
2017-12-27 21:57:44
282
原创 Codeforces Round #403 (Div. 2) E. Underground Lab
题意:给n点m边的连通图，k个人从任意点出发至多经过 个点,求分配方式使得每个点都至少被走过一次题解：在图中以任意点为根任意dfs出一个生成树，每条边走2次（也就是每次向前走完再回头走），按dfs的顺序得出一个答案序列，总共走过2*(n-1)+1 = 2*n-1个点并且走完所有点，再把连续的 个点分配给一个人，多的人输出1 1即可#include #include
2017-12-06 23:42:59
308
转载 CF 785D Anton and School - 2
http://blog.csdn.net/zengaming/article/details/63684635
2017-12-05 13:50:55
380
原创 Codeforces 868F - Yet Another Minimization Problem (分治DP,莫队)
题意：给定一个序列要求分成k个连续子序列，使得子序列的cost之和最小，子序列的cost定义为子序列中数对的两个数相同的数对个数, 如cost(1,1) = 1, oost(1,1,1,3) = cost(1,1,1) = 3*2/2 = 1+2 = 3; 题解：对于朴素的dp[i][j]表示1~j分为i个块的最小cost，有O(k*n^2)的算法dp[i][j] = min{dp[i
2017-11-28 00:41:40
270
原创 HDU 6134 Battlestation Operational 2017多校8 莫比乌斯反演
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include using namespace std;#def
2017-11-20 11:01:53
189
原创 Codeforces Round #Pi (Div. 2) F. Mausoleum dp
题意：1~n每个数有两个，排成一个序列，要求序列先增后减(可以相等),其中上升和下降的序列长度可以为0，再给出k个条件，每个条件为某个位置>, =, 题解：dp[l][r]表示将[l,r]区间排列有多少种方法，记忆化搜索
2017-11-02 17:15:03
143
原创 Codeforces Round #318 D. Bear and Blocks DP
dp[i]表示第i列被消除需要的操作次数， dp[i] = min(i, n-i, h[i], dp[i-1]+1, dp[i+1]+1),，i、n-i表示每次消除边缘一列直到第i列的情况，h[i]表示每次消除顶端直到为0的情况，dp[i-1]+1和dp[i+1]+1表示左右两侧消除完再操作一次消除i列的情况，前三个读入的时候#include #include #include #inclu
2017-11-02 13:56:43
145
原创 uvalive7040 / cf gym 100548 Color(2014 ICPC 西安 F)
题意:n个位置m种颜色进行染色，要求相邻位置颜色不相同，切正好使用k种不同颜色题解:#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include
2017-10-30 18:59:16
212
转载 2017多校1 1003 HDU 6035 树形dp
（本文转载，原帖http://blog.csdn.net/Bahuia/article/details/76141574）题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6035 一棵n个结点的树，每个结点都有颜色，定义两点之间的路径长度为路径上出现的不同颜色数目，求树上所有路径的长度和。思
2017-10-28 13:51:17
176
原创 2013ICPC长春 HDU 4814 Golden Radio Base 乱搞
题意：给十进制数转换为黄金分割进制,要求每位为0或1，且不能出现相邻的1题解：令x为黄金分割比，1 = x^(-1) + x^(-2), n = n*(x^(-1) + x^(-2))， 题目提示了两种操作 x^1 + 1 = x^2, 2*x^2 = x^3 + 1, 最多100位数所以每次扫一遍乱搞一下就可以了，操作一可以减少总的数字的数量所以优先做1操作可以减少次数
2017-10-25 13:12:05
146
原创 2013ICPC 长春I HDU 4821 String 字符串哈希
题意:给一字符串求长度为m*l的满足条件子串个数，条件要求:子串拆成连续的m个l长的子串互不相同题意有坑，一开始以为是两个子串之间每个位置都要不一样，但是样例过不了，看了半天题才反应过来“two strings are considered as “diversified” if they don’t have the same character for every position.” 这
2017-10-25 12:57:04
205
原创 2016icpc沈阳 HDU 5955 Guessing the Dice Roll AC自动机 高斯消元
题意:n个人每人一个长为L的只包含1-6的猜测序列，一直掷骰子直到结果出现某个人的猜测序列，该人获胜，求每人获胜概率题解:随机过程里的马尔可夫过程的稳定状态，在AC自动机上做状态转移，#include #include #include #include #include #include #include #include #include #include #i
2017-10-24 12:28:09
423
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人