Noi模拟 质数 哥巴赫猜想

质数(prime)

【题目描述】

将1~n分成尽可能少的集合,使得每个集合的元素和均为质数。

【输入数据】

一行一个正整数n。

【输出数据】

第一行一个正整数m表示最少集合数,第二行n个[1,m]中的整数,第i个整数表示i在第几个集合中。若有多种方案输出任意一种即[……]

Read more

bzoj 3675: [Apio2014]序列分割 斜率优化

首先你要发现这题有个奇妙的性质,就是说当你一个切割方案确定下来,你切的先后的顺序对最终的答案没有任何影响。

做一个简单的证明,假设a b c我们考虑先切a右侧,再切b右侧答案是

a * (b + c) + b * c

先切b右侧,再切a右侧,答案是

(a + b) * c +[……]

Read more

Noi模拟 弹球游戏 费用流

弹球游戏(bounce)

【题目描述】

妹老师引进了一个新的弹球游戏,游戏区域是一个n*m的网格,格子坐标编号从(1,1)到(n,m),每个格子里都有一个斜面,斜面有四种摆放方式:

//此处自行YY四个正方形,分别被黑白分成两半,一半是一个等腰三角。

 

灰色[……]

Read more

Noi模拟 最长路径 DP 奇妙推论

【题目描述】

在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。

Byteasar居住在1号城市,他希望从1号城市出[……]

Read more

Noi模拟 数字 打表找规律 奇妙推论

数字(num)

【题目描述】

小D喜欢的数有这样的性质:令n为正整数,S(n)为n的各位数字之和,令,若一个数能表示成x*d(x)这种形式,则这个数是小D喜欢的。

小D想知道在区间[L,R]中,有多少个数是他喜欢的。

有多组数据。

【输入数据】

第一行一个整数T,[……]

Read more

Noi模拟 矩阵 二分 上下界网络流

矩阵(mat)

【题目描述】

给定一个整数矩阵A[n*m],求一个整数矩阵B[n*m],满足,最小化。

输出任意一组合法解即可。

【输入数据】

第一行两个数n、m,表示矩阵的大小。

接下来n行,每行m个整数,描述矩阵A。

最后一行两个整数L,R。

【输[……]

Read more

Noi模拟 市场 线段树

考场上想到了以前写的这道题 :http://oi.self-jqe.win/?p=787

觉得开根号,除法之类的越整,序列越相似,那种不能批处理就暴力,能批量处理就批量处理的算法复杂度都有保证,看数据范围10^5发现貌似比正常的10^6的小一些,觉得很有可能就是这种做法,然后就写了。

具[……]

Read more