3 oopscyc

尚未进行身份认证

暂无相关描述

等级
TA的排名 1w+

ACM-ICPC 2018 南京赛区网络预赛 G. Lpl and Energy-saving Lamps (线段树)

https://nanti.jisuanke.com/t/30996  题意:有n个房间,里面分别有ai盏灯需要更换,Lpl每月都会买m盏灯,如果刚好能更换一个房间就会把灯都更换掉,如果不能就会继续找下一个房间看是否能全部更换,剩余的灯就会被留到下个月使用,最后输出她每月最多能更换的房间数和所剩余的灯的数量。 思路:直接线段树找到最左边小于一个数的位置,然后把可以换的更新成...

2018-09-11 13:02:21

ACM-ICPC 2018 南京赛区网络预赛 B. The writing on the wall (暴力)

https://nanti.jisuanke.com/t/30991 题意:方格矩形中不包括一些点,能形成多少个子矩形 思路:我们可以将每个点当做矩形的右下角,看能形成多少个矩形,先预处理每个点最多能往上连续几个点,然后往左查询,最多能构成几个矩形 代码:#include<bits/stdc++.h>usingnamespacestd;#d...

2018-09-11 12:11:47

ACM-ICPC 2018 南京赛区网络预赛 E. AC Challenge (状压dp)

https://nanti.jisuanke.com/t/30994题意:有n道题,每道题可以得到t*a+b,有些题必须要在一些题做出后才能做,问最高得多少分思路;最多20道题,那么就可以用状压dp写。dp[i]表示状态为i时的最大值。代码:#include<bits/stdc++.h>usingnamespacestd;#definelllong...

2018-09-10 22:44:42

ACM-ICPC 2018 南京赛区网络预赛 J. Sum (欧拉筛法+规律)

https://nanti.jisuanke.com/t/30999题意:f(i):能拆成两个数的乘积,并且这两个数要求没有平方因子。最后求f(1)+f(2)+f(3)+...f(n)。 思路:我们可以发现素数的f为2,每个大于2的数都能拆成若干个素数相乘,如果一个素数出现三次,那这个数的f肯定为0,没有相同素数时为(p为因数个数),否则为(n为不同因子的个数,p为相同因...

2018-09-10 21:23:14

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze (拆点+最短路)

https://nanti.jisuanke.com/t/31001题意:有n个城市,m条有向路,最多选取k条路的权值为0,求1到n的最短路。 思路:我们可以当每个点分成k层,同一层的点的权值为w,到下一层的权值为0,这样建图,就能保证最短k条边的权值为0,然后跑最短路。 代码:#include<bits/stdc++.h>usingnamesp...

2018-09-10 20:02:20

2018中国大学生程序设计竞赛 - 网络选拔赛 1007 Neko's loop (线段树+循环节)

http://acm.hdu.edu.cn/showproblem.php?pid=6444题意:给出一个n个元素的环、可以任意选择起点、选完起点后、可以行走m步、每次前进k个单位、所走到的点将产生正或负贡献、问你一开始得准备多少才能使得初始资金加上在环上获取最大利益不少于给定的s思路:把循环节扒出来,把m归约到循环节长度大小,然后跑长度小于某个值的最长子段和就可以了...

2018-08-27 21:49:01

2018中国大学生程序设计竞赛 - 网络选拔赛 1009 Tree and Permutation (树形dp)

http://acm.hdu.edu.cn/showproblem.php?pid=6446题意:给出一颗树,按节点进行全排列,然后求根节点到每个节点的最短距离之和。 思路:对每条边单独计算贡献,一条边EE将树分成两侧,假设其中一侧大小为M,则另一侧大小为N-M。在N!条路线中每条都分为N-1段,对每段单独计算贡献,例如某一段从X到Y,则该段经过E当且仅当X与Y在E的两侧,对...

2018-08-27 17:21:35

2018中国大学生程序设计竞赛 - 网络选拔赛 1010 YJJ's Salesman (线段树+dp)

http://acm.hdu.edu.cn/showproblem.php?pid=6447 题意:给你n个点,你只能向右,向下,向右下走,当你向右下走恰巧走到某个点时,你可以获得收益,问最大收益是多少思路:先离散化到1e5*1e5的格点,dp[i][j]表示走到(i,j)为止的得到的最大金钱,显然dp[i][j]=max{dp[i-1][j],dp[i][j-1],d...

2018-08-27 16:42:39

2018中国大学生程序设计竞赛 - 网络选拔赛 1003 Dream (费马小定理)

http://acm.hdu.edu.cn/showproblem.php?pid=6440题意:给定一个素数p,要求定义一个加法运算表和乘法运算表,使的成立。思路:根据费马小定理 那么则代码:#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintmaxn...

2018-08-27 15:30:43

2018中国大学生程序设计竞赛 - 网络选拔赛 1004 Find Integer (费马大定理+求勾股数)

http://acm.hdu.edu.cn/showproblem.php?pid=6441 思路:费马大定理:平方整数解a^2+b^2=c^2的a值奇偶数列法则可知。当a为奇数时,b=c-1当a为偶数时,b=c-2#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstint...

2018-08-27 15:13:27

2018中国大学生程序设计竞赛 - 网络选拔赛 1001 Buy and Resell (贪心+优先队列)

http://acm.hdu.edu.cn/showproblem.php?pid=6438 题意:有n个城市,你可以在一个城市买一个东西,也可以卖一个东西,也可以不买不卖,然后问获得的最大利润和最小操作数。 思路:这个博主的文章写的很详细 代码:#include<bits/stdc++.h>usingnamespacestd;#defin...

2018-08-27 14:57:30

hdu 6430 Problem E. TeaTree (合并线段树)

http://acm.hdu.edu.cn/showproblem.php?pid=6430 题意:一棵树上每个节点权值为v[i],每个节点的heard值是:以它为LCA的两个节点的GCD的最大值,要求输出每个节点的heard值 思路:因为每个点的权值不超过1e5,所以可以预处理每个点的因子,然后建n颗线段树,只要有两个节点有相同答案就维护答案,每次都把所有子节点的线段树与...

2018-08-27 14:30:01

hdu 6437 Problem L.Videos (最小费用最大流)

http://acm.hdu.edu.cn/showproblem.php?pid=6437 题意:一天有N个小时,有m个节目(每种节目都有类型),有k个人,连续看相同类型的节目会扣w快乐值每一种节目有都一个播放区间[s,t]。每个人同一时间只能看一个节目,看完可以获得快乐值。问最多可以获得多少快乐?思路:我们可以将每部电影拆成两个点来看,建立源点和汇点,还有次源点,因为要...

2018-08-25 19:40:49

hdu 6415 Rikka with Nash Equilibrium

http://acm.hdu.edu.cn/showproblem.php?pid=6415 题意:在一个矩阵中,如果某一个数字是该行该列的最大值,则这个数满足纳什均衡。要求构造一个n*m的矩阵,里面填的数字各不相同且范围是【1,m*n】,问有多少种构造方案。思路:直接公式 代码:#include<bits/stdc++.h>usingnamespac...

2018-08-21 17:47:48

2018“百度之星”程序设计大赛 - 复赛 1001 没有兄弟的舞会

http://acm.hdu.edu.cn/showproblem.php?pid=6409思路:这题直接暴力找每个点的子节点的最大值、最小值、次大值和次小值,求最大值时只加大于0的,最小值只加小于0的。 代码:#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstint...

2018-08-20 22:56:03

2018“百度之星”程序设计大赛 - 复赛 1002 序列期望

http://acm.hdu.edu.cn/showproblem.php?pid=6410  思路:数据范围l和r的最大值为10000,那我们就可以枚举每个最大值所做的贡献,因为每次只计算出了最大值小于等于最大值的,我们只要再算一下小于等于最大值减一的,两个一减就是答案了。 代码:#include<bits/stdc++.h>usingnames...

2018-08-20 22:53:09

2018“百度之星”程序设计大赛 - 复赛 1003 带劲的and和 (二进制+ 并查集)

http://acm.hdu.edu.cn/showproblem.php?pid=6411 思路:先用并查集把各个联通块整理出来,再把每个联通块点的权值按照从小到大排序,因为是&,所以只有同时满足在这个位置为1的去情况才为1,可以统计每个位置1的个数,从大到小扫一遍就可以了,记住每次都要删去扫过的,不然会重复#include<bits/stdc++.h>u...

2018-08-20 21:32:37

poj 3140 Contestants Division (树形dp)

http://poj.org/problem?id=3140题意:要删一条边使得剩余的两个分支价值差最小。 思路:先从下往上更新子树的,再从上往下更新父亲节点,然后找最小 代码:#include<iostream>#include<stdio.h>#include<string.h>#include<algorit...

2018-08-17 15:30:24

poj 2378 Tree Cutting (树形dp)

http://poj.org/problem?id=2378  题意:  给一颗n个结点的树,节点编号为1~n,把删除一个节点之后,  剩下的分支中节点数量最多的数量不大于总数量一半的编号全部按顺序输出 思路: 跟求树的重心一样的方法,先从下往上更新,在从上往下跟新即可。代码:#include<iostream>#include<stdi...

2018-08-17 14:07:09

poj 3107 Godfather (树的重心)

http://poj.org/problem?id=3107 题意:删掉某点后子树节点最多的最小思路:其实就是求树的重心代码:#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<vector>u...

2018-08-17 13:38:40

查看更多

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