分类目录归档:数学

[BZOJ3482][COCI2013]hiperprostor

Orz Claris菊苣

对于这道题我们发现q很小,那么大概率是让你在线去做

然后我们知道n,m也很小,大概率是用n,m做一个dp

所以设f[i][j]表示从s出发,到达i,恰好经过jx边的最短路,利用spfa求出。

如果对于任意的i都有f[t][i]=\infty,则答案为无解。

继续阅读

Codeforces #388 Div.2

link

http://codeforces.com/contest/749

Solution

A. Bachgold Problem

题目大意:给你一个数,让你把它分解成尽可能多的质数的和

考虑贪心的原则,我们用这个数不断去减2

那么只可能有几种情况,减了以后是3,那就输出3

不然就是0,结束

为什么不是1呢,因为没有1,1可以改到3输出

继续阅读

[codeforces 359C] Prime Number

Description

Simon has a prime number x and an array of non-negative integers a1, a2, ..., an.

Simon loves fractions very much. Today he wrote out number on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: , where number t equals xa1 + a2 + ... + an. Now Simon wants to reduce the resulting fraction.

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (109 + 7).

继续阅读

bzoj-USACO除草计划A

我已经做了30/30


继续阅读

Codeforces Round#372 Div.2

A. Crazy Computer

ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

继续阅读

[bzoj 2667][cqoi2012] 模拟工厂

Description

有一个称为“模拟工厂”的游戏是这样的:在时刻0,工厂的生产力等于1。在每个时刻,你可以提高生产力或者生产商品。如果选择提高生产力,在下一个时刻时工厂的生产力加1;如果选择生产商品,则下一个时刻你所拥有的商品数量增加p,其中p是本时刻工厂的生产力。

n个订单,可以选择接受或者不接受。第i个订单(ti, gi, mi)要求在时刻ti给买家提供gi个商品,事成之后商品数量减少gi,而收入增加mi元。如果接受订单i,则必须恰好在时刻ti交易,不能早也不能晚。同一时刻可以接受多个订单,但每个订单只能被接受一次。要求最后的总收入最大。

例如,如果一共有两个订单(5,1,8)和(7,15,3),用如下策略是最优的:时刻0, 1, 2提高生产力(时刻3的生产力为4),然后在时刻3,4生产商品,则在时刻5时将拥有8个商品。此时接受第1个订单(还会剩下7个商品),并且在时刻5,6继续生产商品,则在时刻7时拥有7+4+4=15个商品,正好满足订单2。

继续阅读

Codeforces Round#369 Div.2

A. Bus to Udayland

ZS the Coder and Chris the Baboon are travelling to Udayland! To get there, they have to get on the special IOI bus. The IOI bus has nrows of seats. There are 4 seats in each row, and the seats are separated into pairs by a walkway. When ZS and Chris came, some places in the bus was already occupied.

ZS and Chris are good friends. They insist to get a pair of neighbouring empty seats. Two seats are considered neighbouring if they are in the same row and in the same pair. Given the configuration of the bus, can you help ZS and Chris determine where they should sit?

继续阅读

[bzoj 2563] 阿狸和桃子的游戏

Description

  阿狸和桃子正在玩一个游戏,游戏是在一个带权图G=(V, E)上进行的,设节点权值为w(v),边权为c(e)。游戏规则是这样的:
  1. 阿狸和桃子轮流将图中的顶点染色,阿狸会将顶点染成红色,桃子会将顶点染成粉色。已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色。
2. 为了保证公平性,节点的个数N为偶数。
3. 经过N/2轮游戏之后,两人都得到了一个顶点集合。对于顶点集合S,得分计算方式为

由于阿狸石头剪子布输给了桃子,所以桃子先染色。两人都想要使自己的分数比对方多,且多得越多越好。如果两人都是采用最优策略的,求最终桃子的分数减去阿狸的分数。

继续阅读

CodeForce Round#275 Div.2

A. Counterexample

Your friend has recently learned about coprime numbers. A pair of numbers {a, b} is called coprime if the maximum number that divides both a and b is equal to one.

Your friend often comes up with different statements. He has recently supposed that if the pair (a, b) is coprime and the pair (b, c) is coprime, then the pair (a, c) is coprime.

You want to find a counterexample for your friend's statement. Therefore, your task is to find three distinct numbers (a, b, c), for which the statement is false, and the numbers meet the condition l ≤ a < b < c ≤ r.

More specifically, you need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair(a, c) is not coprime.

继续阅读