Soda Machine
求一个数列上的一个点最多被多少个区间覆盖。
非常简单的一道题，直接差分+离散化就可以了。
1 |
|
细胞分裂
要求最小的正整数$K$使得存在$i$满足$S_i ^ {K} | M_1 ^ {M_2}$
直接质因数分解。
要想满足条件，那么显然$S_i$必须包含$M_1$的所有的质因数。
于是先判断这个事情。如果可以继续，那么设$F[A][B]$表示$A$的质因数中的$B$的数量，$M_1$的质因子$i$的出现的次数为$B_i$
那么$\frac {M_2 \times B_j}{F[S][j]} \leq K$，那么根据$K$和时间的单调性关系，可以得到
$K = max(k, \lceil \frac {M_2 \times B_j}{F[S][j]} \rceil)$
直接上代码了。
1 |
|
Making Money
FJ又经营起了古董生意，买卖一些像奶牛圣诞树上的装饰之类的小玩意。他知道他会将他能存储的N(1<=N<=100)件不同的奶牛古董每件都卖出。
而且如果他的钱足够多他可以买他想要的任意数量的古董（即他可以购买的古董数量没有限制）。他只有M(1<=M<=100,000)元钱来买古董，但他想要在他经商的第一年年末最大化他的利润（这有点难以解释）。
第i种古董采购需要花费Ci(1<=Ci<=100,000)元钱，每卖掉一件可以获得Ri(1<=Ri<=100,000)元钱(每卖一件的利润为Ri-Ci)。FJ可以以任意顺序卖出他的货物。他并不需要花光他所有的钱来购买古董。
FJ在他经商的第一年年末能得到的最大总利润（利润=初始钱数-总花费+总收入）是多少呢？输入数据保证这个数字不会超过1,000,000,000.
假设FJ只有3种古董而且开始时有M=17元钱。下面是三种古董的花费和收入。
完全背包直接上就是了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;
const int INF = 0x7fffffff ;
int N, M, W[MAXN], V[MAXN], Dp[MAXN], Ans ;
inline int Read() {
int X = 0 ; bool F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0')
F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9')
X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;
return X * F ;
}
int main() {
N = Read() ; M = Read() ;
for (int i = 1 ; i <= N ; i ++) {
W[i] = Read(), V[i] = Read() ;
V[i] -= W[i] ;
}
for (int i = 1 ; i <= N ; i ++)
for (int j = W[i] ; j <= M ; j ++)
Dp[j] = max(Dp[j], Dp[j - W[i]] + V[i]) ;
for (int i = 1 ; i <= M ; i ++)
Ans = max(Ans, Dp[i] - i + M) ;
printf("%d\n", Ans) ;
return 0 ;
}
道路游戏
链接：https://ac.nowcoder.com/acm/contest/1106/D
来源：牛客网小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有n个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n 个机器人工厂编号为1~n，因为马路是环形的，所以第n个机器人工厂和第1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这n段马路也编号为1~n，并规定第i段马路连接第i个机器人工厂和第i+1个机器人工厂（1≤i≤n-1），第n 段马路连接第n个机器人工厂和第1个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在i（1≤i≤ n）号机器人工厂购买了一个机器人，这个机器人会从i 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过i 号马路，到达i+1号机器人工厂（如果i=n，机器人会到达第1个机器人工厂），并将i号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在2个或者2个以上的机器人，并且每个机器人最多能够在环形马路上行走p次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为1~p之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
\1. 游戏从小新第一次购买机器人开始计时。
\2. 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
\3. 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
\4. 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
\5. 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过m 个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。
这道题是真的难。优先队列优化动态规划。
状态表示就比较难想，你在真正比赛的时候不一定敢信这是一个一维的。设$Dp[i]$表示在时间$i$的时候的最优答案。
那么我们利用一下二维前缀和就大概可以写出来$Dp$的式子。
然后这个$Sum$表示的是时间和工厂这两维的前缀和。上面这相当于是一个$O(N^3)$的暴力$DP$，但是我们可以用优先队列进行优化。
首先把没有$k$的一项提出来，就变成：
于是你就发现$max$里面全部都是$i - k,j - k$，因此你可以预处理一下一个$Rec[i][j]$表示$Dp[i] - Sum[i][j] - Cost[j]$，那么$Dp$方程就变成了
那么如果我们能够简化对于$Rec[i][j]$的枚举，就可以做到$O(N^2)$，这就非常优秀，那么显然这个时候就可以使用优先队列来进行优化。
1 |
|
Lake Counting
一个八联通的$N \times M$的方格图，$W$代表水池，$.$代表空地，常识确定一共有多少个水坑。
直接搜索。（这都是些什么垃圾题啊。。。
1 |
|
多项式输出
一元nn次多项式可用如下的表达式表示：
输入系数，输出这个式子。
哈，模拟好题。
1 |
|
Dinner Time
农民约翰的$N（1≤N≤1000）$奶牛(编号1..N)在保加利亚参加$IOI$。奶牛们喜欢保加利亚的太阳，并享受他们的假期。一切
似乎都很好。
这在晚餐时间发生了变化。餐厅很小，只有$M（1 <= M = N）$个牛的座位（编号1 .. M）.每头奶牛开始在一个位置
$cx_i，cy_i（1000000 <= cx_i≤1000000；1000000≤cy_i <= 1000000）$；可以在$sx_j，sy_j$
$（1000000 < = sx_j≤1000000；1000000≤sy_j < = 1000000）$找到座位。
奶牛有一个非常有效的（虽然很原始）的方法来分配座位。只要一头母牛可以确定她会先坐到座位上，她会尽快地
赶到那里（所有的母牛都跑得一样快）。
农民约翰的奶牛跳过座位、桌子、其他的牛不成问题，所以他们可以在一条直线上跑。当多
个奶牛可以在同一时间达到一个座位，最老的牛（在输入数据中出现得早）将会得到座位。同样，当一头母牛可
以到达多个座位时，她也会选择最早在输入数据中出现的一个。
有些牛不能吃晚饭（没有座位），那些饥饿的奶牛集体计划偷农民约翰的食物。农夫约翰想要一个他应
该警惕的牛的名单。（在没有饥饿的奶牛的情况下，输出0）。你能帮他吗？
语文好题。
直接枚举座位和牛，然后就直接让最近的牛做到这个座位上就可以了。
1 |
|
Counting Beads
给你一个序列，让你求出有多少个$A[j], A[i + 1]$满足01相间
我透了这真是连普及都不到啊。
1 |
|
Barn Allocation
大概就是给你一个序列和一堆序列，然后让你选择一些序列保证任意序列不相重，最大化序列数。
这个题也算是比较经典的贪心了，直接排序右端点，然后从左往右能选就选就可以了。
1 |
|