11 我是傻叉

尚未进行身份认证

暂无相关简介

等级
TA的排名 8k+

[NOI 2015复习][BZOJ 1509][NOI 2003]逃学的小孩(树的直径)

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=1509题目大意要从一棵树中找出三个点X,Y,ZX,Y,Z,使得min(dis[A][C],dis[B][C])+dis[A][B]\min(dis[A][C],dis[B][C])+dis[A][B]最大,求这个最大值思路可以发现,min里头的两个东西具体取哪个并不重要,或者说点C距离A更近还是

2015-07-13 10:25:27

[NOI 2014复习]斜率优化(BZOJ 1096、BZOJ 1010)

1.BZOJ 1096 仓库建设题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=1096思路令f[i]=[1,i]f[i]=[1,i]区间,在第i个工厂建立仓库,所需最少总花费。DP方程显然 f[i]=min1≤j<i{f[j]+w[j,i]}+C[i]f[i]=\min_{1\leq j<i}\{f[j]+w[j,i]\}+C[i] 其中

2015-07-11 11:45:31

NOI 2014简要题解

Day 1.Problem A. 起床困难综合症100分做法:把数字看成二进制数。对于初始攻击力,我们将其拆成32位,并求出每一位为0和1时经过所有防御门之后分别得到的数字。然后就是按位贪心了,我们尽量让初始攻击力的高位在经过所有防御门后变成1而不是0,根据这一贪心思想,剩下要做的就是个很简单的数位贪心问题了。#include <stdio.h>#include <stdlib.h>#inclu

2015-07-09 17:15:10

[Codeforces 55D]Beautiful numbers(数位DP)

题目链接http://codeforces.com/problemset/problem/55/D题目大意多次询问。求[L,R][L,R]中能被自己的每一位数位整除的数字个数思路像大多数的数位DP题一样,我们只需要能求出[0,x]里能被自己的每一位数位整除的数字个数就好了显然数字x能被自己的每一位数位整除,当且仅当它能被自己的每一位数位的LCM整除而1~9的子集的LCM最大值,也就是lcm(1,2.

2015-06-30 16:46:24

[Codeforces 484A]Bits(拆位贪心)

题目链接http://codeforces.com/problemset/problem/484/A题目大意求[L,R][L,R]里二进制中1的出现次数最多的数字思路首先我们把L和R拆成二进制数,然后个位对齐,形如下面这样: R:1100101000011111 L:0000101100000001 假设L和R的二进制里前缀[1,t][1,t]这部分是相同的,那么答案数字x在[1,t][1,t

2015-06-30 16:25:05

[POI 2007]Weights(拆位贪心)

题目链接http://main.edu.pl/en/archive/oi/14/odw题目大意转自BZOJ 在byteotian公司搬家的时候,他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运,并且丢弃剩下的砝码。每个容器可以装的砝码数量有限制,但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个

2015-06-30 15:59:58

Codeforces #309 Div 1 简要题解

A. Kyoya and Colored Balls题目链接http://codeforces.com/contest/553/problem/A题目大意有kk种颜色的球,每种cic_i个,要求第ii种球的最后一个球要在第i+1i+1种球的最后一个球之前放置。问有多少种合法的放置球的方案。思路我们可以初始先在这个放置序列里填入每种颜色最后一个球,然后从1号球到k号球,填入每种球,ci−1c_i-1个

2015-06-29 20:45:20

Codeforces #310 Div 1 简要题解

A. Case of Matryoshkas题目链接http://codeforces.com/contest/555/problem/A题目大意俄罗斯套娃。一套套娃的形态如一条链:1->2->3->4… 可以对一条链进行断开操作:1->2->3->4变成1->2和3->4 也可以在一条链后面套上一个新数字,但是新数字必须是链尾数字大小+1:1->2->3->4+5变成1->2->3->4->5

2015-06-29 19:49:21

[POI 2012]Kinoman(线段树)

题目链接http://main.edu.pl/en/archive/oi/22/kin题目大意共有m部电影,编号为1~m,第i部电影的好看值为w[i]。 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。 你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望

2015-06-25 21:49:54

Codeforces #263 Div 1 简要题解

A. Appleman and Toastman题目链接http://codeforces.com/contest/461/problem/A题目大意给你nn个数构成的集合SS,每次操作你可以选择当前的一个集合,将它分裂成两个非空集合,每次操作后,你将每个集合里的数字之和加起来,若出现了大小为1的集合,就将这个集合删去。问你操作的最大得分是多少。思路这样的贪心感觉比较多吧,比如NOIP的合并果子等等

2015-06-25 16:47:13

[POI 2015]Piecz(模拟)

题目链接http://main.edu.pl/en/user.phtml?op=showtask&task=pie&con=OI22题目大意一张n*m的方格纸,有些格子需要印成黑色,剩下的格子需要保留白色。 你有一个a*b的印章,有些格子是凸起(会沾上墨水)的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求: (1)印章不可以旋转。 (2)不能把墨水印到纸外面。 (3)纸

2015-06-24 21:21:33

[POI 2012]Well(二分+单调性)

题目链接http://main.edu.pl/en/archive/oi/19/stu题目大意给你一个长度为nn的序列AA,每次操作可以让其中一个数字减1,最多能进行mm次操作,问要使得存在某个Ai=0A_i=0的话,max{|Ai−Ai+1|}\max\{|A_i-A_{i+1}|\}的最小值是多少思路我们可以二分答案,此问题变为判定性问题:问要使得存在某个Ai=0A_i=0的话,max{|Ai−

2015-06-24 19:45:18

Codeforces #265 Div 1 简要题解

A. No to Palindromes!题目链接http://codeforces.com/contest/464/problem/A题目大意给你一个字符串SS,其中不包含任何长度大于等于2的回文子串,要你找一个长度和SS相同,且字典序比SS大的字典序最小的S′S',使得S′S'也不包含任何长度大于等于2的回文子串。思路显然S′S'的前缀是和SS相同的,而二者的后缀则不同。假设二者不相同的后缀对应

2015-06-24 16:16:11

[POI 2012]A Horrible Poem(字符串Hash)

题目链接http://main.edu.pl/en/archive/oi/19/okr题目大意给出一个字符串,多次询问其中一个子串[L,R][L,R]的最小循环节长度。思路假设∑Ri=L(S[i]==′x′)\sum _{i=L}^R(S[i]=='x')表示区间[L,R][L,R]里字母′x′'x'的出现次数。假设最小循环节长度为tt,则R−L+1t\frac{R-L+1}t(最小循环节的出现次数

2015-06-23 20:58:27

[POI 2012]Tour de Byteotia(并查集)

题目链接http://main.edu.pl/en/archive/oi/19/tou题目大意给出一个无向图,要你删除其中一些边,使得对于i∈[1,k]i\in [1,k],点ii不在环上思路水题对于所有的两个端点编号均大于kk的点,先并查集预处理维护它们的连通性。这些点构成的环上不会有点i∈[1,k]i\in [1,k]然后对于剩下的边,每条边都至少有一个端点i∈[1,k]i\in [1,k],若

2015-06-23 17:30:38

Codeforces #268 Div 1 简要题解

A. 24 Game题目链接http://codeforces.com/contest/468/problem/A题目大意给你数字1...n1...n,每次操作时,你可以从数字中选出两个数做加或减或乘操作,得到一个结果并放回数字堆中。直到最后只剩下一个数字,现在要让最后留下来的那个数字是24,问是否存在一种操作方案,并输出一组可行方案。思路显然,n<4n<4时无解。n=4,5n=4,5时可以手玩出解

2015-06-23 16:01:08

[UOJ 110][APIO 2015]Bali Sculptures(按位DP)

题目链接http://uoj.ac/problem/110思路此题如果直接用类似于NOIP乘积最大一题的那种DP做法的话,是错误的,因为此题有后效性。可以考虑拆位来做,先尽量让答案的高位为0,在答案高位尽量小的前提下,再争取让答案的低位为0。对于前4个subtask,由于A>=1A>=1,因此直接用DP求每一位的最少分组的话是不对的。可以采取O(n3logY)O(n^3logY)的做法,从最高位向最

2015-06-19 15:57:13

[POI 2012]Rendezvous(倍增LCA)

题目链接http://main.edu.pl/en/archive/oi/19/ran题目大意给定一棵内向森林,多次给定两个点a和b,求点对(x,y)满足:1.从a出发走x步和从b出发走y步会到达同一个点 2.在1的基础上如果有多解,那么要求max(x,y)最小 3.在1和2的基础上如果有多解,那么要求min(x,y)最小 4.如果在1、2、3的基础上仍有多解,那么要求x>=y思路很像LCA。

2015-06-18 16:46:15

Codeforces #272 Div 1 简要题解

比赛总结这次打得比上次稍微好点(其实主要是开了挂的缘故),三个题中只有A wa了一发,B和C都是fb。在正式和非正式选手中排名146名,在正式选手里排名120名A. Dreamoon and Sums题目链接http://codeforces.com/contest/477/problem/A题目大意定义一个数字xx是优美的,当且仅当xmodb≠0,⌊xb⌋xmodb=k,k∈[1,a]x \mod

2015-06-18 15:43:04

[POI 2012]Distance(数学)

题目链接http://main.edu.pl/en/archive/oi/19/odl题目大意给你一个序列a[]a[],定义d(i,j)=d(i,j)=a[i],a[j]a[i],a[j]每次操作可以对其中之一乘一个质数pp或除以一个数pp(pp必须为被除数的约数),让a[i]=a[j]a[i]=a[j]的最少操作步数对于每个ii,求d(i,j)d(i,j)最小的jj,若有多个解,输出最小的jj思路

2015-06-17 19:05:04

查看更多

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