• 等级
  • 48298 访问
  • 564 原创
  • 0 转发
  • 7052 排名
  • 82 评论
  • 32 获赞

欢乐纪中A组周六赛【2019.4.13】

前言做A组被虐好惨成绩RankRankRank是有算别人的RankRankRankPersonPersonPersonScoreScoreScoreAAABBBCCC222巨佬WHF巨佬WHF巨佬WHF140140140404040100100100000222巨佬ZZY巨佬ZZY巨佬ZZY14014014040404010010010...

2019-04-13 15:19:04

jzoj3171-[GDOI2013模拟4]重心【真·物理,二分】

正题题目大意若干个长2高1的长方形且有不同的质量。对于若干个矩形的重心定义为∑mi∗xi∑mi\frac{\summ_i*x_i}{\summ_i}∑mi​∑mi​∗xi​​要求每个矩形上面的所有矩形的x重心跟该矩形的x中点相距不超过1。最底下的矩阵的右下角摆放在(−2,0)(-2,0)(−2,0)的位置求最上面最右能到多远。解题思路我们二分答案,然后只要最后重心能到0或以内...

2019-04-13 15:02:16

jzoj3170-[GDOI2013模拟4]挑选玩具【容斥,状态压缩,分治】

正题题目大意有nnn个箱子放了若干个玩具,要求选择一些箱子使得mmm种玩具都有,求方案总数。解题思路设fSf_SfS​表示选择只有在集合为SSS的方案数。然后答案考虑容斥,那么答案就是∑S(2(f(∼S))−1)∗(−1)∣S∣\sum_S(2^{(f_{(\simS)})}-1)*(-1)^{|S|}S∑​(2(f(∼S)​)−1)∗(−1)∣S∣我们将集合的表示状压起来。...

2019-04-13 14:19:26

jzoj3169-[GDOI2013模拟4]生产汽车【斜率优化dp,单调队列,二分】

正题题目大意有nnn个人mmm辆车。人有tit_iti​,车有fjf_jfj​。第i个人修第j俩车时间是ti∗fjt_i*f_jti​∗fj​。一辆车要每个人都修一遍,且一个人修好后要求下一个人没有工作。对于每辆车找一个修理开始时间要求总修理时间最小(得按顺序修)。解题思路定义ti=∑i=1mtit_i=\sum_{i=1}^mt_iti​=∑i=1m​ti​设gig_igi​表...

2019-04-13 14:08:00

nssl1305-最大值【dp,数学】

正题题目大意求有多少个长度为nnn且由1∼p1\simp1∼p组成的序列满足在求最大值时交换了kkk次。解题思路考虑dpdpdp预处理。用fi,j,kf_{i,j,k}fi,j,k​表示长度为iii,最大的数是jjj,交换了kkk次显然有fi,j,k=fi−1,p,k−1+fi−1,j,k(p<j)f_{i,j,k}=f_{i-1,p,k-1}+f_{i-1,j,k...

2019-04-13 07:27:51

nssl1304-最大正方形【二分答案】

正题题目大意一个N∗NN*NN∗N的01矩阵,求一个面积最大的全为1的正方形解题思路先O(n2)O(n^2)O(n2)预处理hi,jh_{i,j}hi,j​表示在(i,j)(i,j)(i,j)这个位置向右有多少个连续的1。然后二分边长。时间复杂度:O(n2 log n):O(n^2\log\n):O(n2 log n)codecodec...

2019-04-13 07:19:20

P3216-[HNOI2011]数学作业【矩阵乘法,数学】

正题题目链接:https://www.luogu.org/problemnew/show/P3216题目大意求1∼n1\simn1∼n连起来%m\%m%m之后的值。解题思路我们可以考虑矩乘,但是当xxx位数时每次乘上10x10^x10x,所以我们对于不同位分开处理就好了。codecodecode#include<cstdio>#include<algor...

2019-04-12 20:24:11

P3441-[POI2006]MET-Subway【图论,贪心】

正题题目链接:https://www.luogu.org/problemnew/show/P3441题目大意求III条路径最多可以覆盖树上多少个点。解题思路我们先只考虑叶子节点,显然可以覆盖min{num叶,I∗2}min\{num_叶,I*2\}min{num叶​,I∗2}。然后网上递推,发现依旧是min{numi,I∗2}min\{num_i,I*2\}min{numi​,I∗...

2019-04-07 12:49:42

P1375-小猫【卡特兰数】

正题题目链接:https://www.luogu.org/problemnew/show/P1375题目大意东西两两绑在一起,要求绳子不能交叉,求方案数。解题思路0表示压入第i只猫,1表示弹出栈顶的猫并且和第i只猫绑在一起,这样就能保证不会交叉。也就是卡特兰数。codecodecode#include<cstdio>#definelllonglongus...

2019-04-07 10:46:56

P4562-[JXOI2018]游戏【数论,组合数学】

正题题目链接:https://www.luogu.org/problemnew/show/P4562题目大意l∼rl\simrl∼r的变化,每次访问第iii个那么iii的倍数就不用访问了。对于一个顺序sss,定义t(s)t(s)t(s)表示按这个顺序访问玩前t(s)t(s)t(s)个就都不用访问了。求所有顺序的t(s)t(s)t(s)之和。解题思路若l==1l==1l==1时那么只...

2019-04-07 10:27:41

nssl1167-桐人的约会【最短路】

正题题目大意去掉一条边使得最短路最长。解题思路这条边一定在最短路上而最短路最多只有n−1n-1n−1条边,所以直接枚举最短路上的边。复杂度O(nmK)O(nmK)O(nmK)codecodecode#include<cstdio>#include<algorithm>#include<queue>#include<cstring&g...

2019-04-07 10:07:55

P2101-命运石之门的选择【dp,离散化】

前言我切掉这道题是命运石之门的选择正题题目链接:https://www.luogu.org/problemnew/show/P2101题目大意nnn个连在一起的高度hih_ihi​盒子。一个刷子只能直着刷而且得连续都得刷。求至少刷多少次。解题思路fi,jf_{i,j}fi,j​表示前iii个已经刷完了,上一个高度为jjj的刷过来。首先我们要把jjj离散化了。然后考虑fi,j=...

2019-04-07 09:25:44

欢乐纪中A组周六赛【2019.3.30】

前言做A组被虐好惨成绩RankRankRank是有算别人的RankRankRankPersonPersonPersonScoreScoreScoreAAABBBCCC1010102017ZYC2017ZYC2017ZYC1141141142424244040405050501313132017XXY2017XXY2017XXY1001001...

2019-03-30 16:39:49

jzoj3189-解密【字符串hash】

正题题目大意一个句子有多个单词。给出了一个加密了的串。加密方法是将不同的单词转换成不同的单词。然后再给一个加密前的串,求再加密串中可能出现的最早位置。解题思路设aia_iai​表示与iii相同的前一个字母的位置。然后根据题目意思对与两个串如果aaa序列一样那么就是可以转换的加密串。所以我们可以用字符串hashhashhash进行匹配。codecodecode#include&...

2019-03-30 16:32:42

jzoj3188-找数【质数筛,数论】

正题题目大意求第nnn大的最小质因数时ppp的数。解题思路首先对于p=2p=2p=2和p=3p=3p=3时可以直接通过计算得出。然后不难发现当p=5p=5p=5时我们可以每次增加101010也就是O(n)O(n)O(n)的十分之一常数。之后再往大的我们发现是O(nln⁡np)O(\frac{n\lnn}{p})O(pnlnn​)常数是二分之一。然后可以过。codecodec...

2019-03-30 16:27:52

P3076,jzoj3187-的士【贪心】

正题luogu题目链接:https://www.luogu.org/problemnew/show/P3076题目大意有若干个请求si,tis_i,t_isi​,ti​表示一个牛要从sis_isi​到tit_iti​。一辆只能装一只牛的车,从1出发mmm结束。求最少行驶距离。解题思路首先对于每个要求一定要计算∣ti−si∣|t_i-s_i|∣ti​−si​∣的,但是考虑多行走的费用。...

2019-03-30 16:22:29

hdu3666-THE MATRIX PROBLEM【差分约束,自然对数】

正题题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3666题目大意一个n∗mn*mn∗m的矩阵CCC求有没有一个长度为nnn的aaa序列和一个长度为mmm的bbb序列使得L≤Ci,j∗ai/bi≤RL\leqC_{i,j}*a_i/b_i\leqRL≤Ci,j​∗ai​/bi​≤R解题思路首先我们将乘除转换为自然对数。所以要求变...

2019-03-29 22:15:05

POJ1275-Cashier Employment【差分约束系统】

正题题目链接:http://poj.org/problem?id=1275题目大意1∼241\sim241∼24小时中第iii个小时需要rir_iri​个出纳员有nnn个人应聘,第iii从xix_ixi​开始工作,一直工作8个小时。求至少要招募多少人应聘。解题思路numinum_inumi​表示第iii个小时有多少人招聘。设定kik_iki​表示第iii个小时放多少人这时需...

2019-03-29 20:48:16

P1081-开车旅行【倍增,链表,dp】

正题题目大意:https://www.luogu.org/problemnew/show/P1081题目大意有若干个城市有不同的海拔hhh,两个城市之间的距离定义为∣hx−hy∣|h_x-h_y|∣hx​−hy​∣小A每次走次近的,小B每次走最近的。它们轮流开车。且只会往编号更大的城市开。问一:在距离≤X\leqX≤X的情况下求一个起点是的他们两个开的距离之和最小。问二:若干个Si...

2019-03-29 20:04:53

P2568-GCD【欧拉函数,欧拉筛】

正题题目链接:https://www.luogu.org/problemnew/show/P2568题目大意求有多少个数对满足gcd(x,y)=pri(x,y≤n)gcd(x,y)=pri(x,y\leqn)gcd(x,y)=pri(x,y≤n)解题思路首先对于gcd(x,y)=pgcd(x,y)=pgcd(x,y)=p=>gcd(x/p,y/p)=1=&...

2019-03-27 16:55:44

ssl_wyc

蒟蒻OIer
关注
  • 中国
奖章
  • 专栏达人
  • 持之以恒