11
1
2015
1

【取模+枚举】NOIP2014 T6 解方程

CODEVS 3732: [NOIP2014]解方程

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

Input

输入共n+2行。

第一行包含2个整数n、m,每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数,依次为a0,a1,a2,……,an

Output

第一行输出方程在[1, m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

Hint

 

【数论噩梦系列】%%%数学省队同桌

Category: NOIP | Tags: 数论 枚举 模意义
11
1
2015
1

【map预处理+倍增优化傻逼模拟】

CODEVS 1199: 开车旅行

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小A和小B决定利用假期外出旅行,他们将想去的城市从1到N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同, 记城市 i的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即 d[i, j] = |Hi − Hj|。

旅行过程中,小A 和小B轮流开车,第一天小A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行 驶 X 公里就结束旅行。小 A 和小B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近 的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市, 或者到达目的地会使行驶的总距离超出X公里,他们就会结束旅行。

在启程之前,小A 想知道两个问题:

1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B的行驶路程为0,此 时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小A 开车行驶的路程总数与小B行驶的路程总数的比值都最小,则输出海拔最高的那个 城市。

2.对任意给定的 X=Xi和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

Input

第一行包含一个整数 N,表示城市的数目。

第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即H1,H2,……,Hn,且每个Hi都是不同的。

第三行包含一个整数 X0。

第四行为一个整数 M,表示给定M组Si和 Xi。

接下来的M行,每行包含2个整数Si和Xi,表示从城市 Si出发,最多行驶Xi公里。

Output

输出共M+1 行。

第一行包含一个整数S0,表示对于给定的X0,从编号为S0的城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值最小。

接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si和Xi下小A行驶的里程总数和小B 行驶的里程总数。

 

先黑一个:开军旅行

Category: NOIP | Tags: map 倍增 NOIP 模拟
8
8
2015
3

【差分鬼畜构图+最短路】NOIP2015 Training Contest #1 Problem C. ZCC Loves Cards III

伏地膜__shi%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

题意:一段1中有两段0= =(比如这个100111000011111)

以及n个操作:将[li,ri]上的数取反,代价为ri-li+1

求数列全变为1的最小代价。

考场上写了个25的爆搜。顺便%%%ZHL大爷160Rank1

Category: NOIP | Tags: 花式构图 最短路
8
8
2015
0

【二分+差分】NOIP2012 T5借教室

前缀&差分大法好。

SHC太大了:线段树维护区间最小值和Lazy_Tag……

本蒟蒻:%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Category: NOIP | Tags: 二分 模拟栈
8
3
2015
0

【二分+贪心+LCA】NOIP2012 T6疫情控制

2013之前TG质量还是挺高的w

题目解释不清楚w你是懒吧啊喂! CodeVS传送门

考虑到每个军队一定是往根的方向走(能控制更多的城市),那么只需计算往上走的方式。

这么屌的题目一看就是二分答案(虽然我不知道怎么看出来的=w=)

Category: NOIP | Tags: 二分 贪心 LCA
8
1
2015
1

【BFS预处理+最短路】NOIP2013 T6华容道

自古T6码农题【雾】自古六面出忠臣!

奇葩改编华容道(更TM像八数码好么)

初始思路:大力BFS!(考虑只需要记录空格与需移动点的状态)

目测60分,TLE(其实我并没有写过,SHC神犇说可以加个启发式或是双向【双向A*BFS】;老板娘说可以随机化模拟退火)

Category: NOIP | Tags: BFS 最短路
7
31
2015
2

【生成树上LCA】NOIP2013 T3货车运输

自古T3出神题!自古3面出神曲!

我觉得这次T3的题很符合我的胃口←_←

题意:给定一个图,求两点间所有路径上最小边权的最大值。

初中写只会二分答案+判断连通性(能再蠢些么= =)

Category: NOIP | Tags: LCA 倍增 生成树
7
16
2015
1

【深搜剪枝】NOIP2004 T4虫食算

codevs传送门

NOIP的深搜果然不是吃素的QAQ。

一开始按照小学奥数的姿势,从末尾数字向前枚举,写了个【真暴力·渣剪枝】。

结果TLE了最大的一个点(见最后):

Category: NOIP | Tags: NOIP 枚举

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com