B. Kefa and Company

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend …

一开始迷之wa…
先找出素数下标的上界就可以A…
然后纠结了２０分钟．．．
然后发现是预处理的素数少了一个素数．．
我预处理是处理到＜１０００５的素数．．．
最大数１００００,而超过１００００的第一个素数是１０００７
这样判断终止条件就会死循环…
sad

阅读更多

不多说，直接代码。

 1/*************************************************************************
 2	> File Name: code/poj/2100.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年09月25日 星期五 00时42分49秒
 6 ************************************************************************/
 7
 8 …

题意　：给定一个长度为n的区间．然后给k次询问，每次一个数t,求一个区间[l,r]使得这个区间和的绝对值最接近t

没办法直接尺取.

先预处理出来前缀和

如果要找一对区间的和的绝对值最最近t

Jessica’s Reading Problem

Description

Jessica’s a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to …

tags:

• codeforces
• acm
• ACM

由于顺序是可以改变的． 所以考虑是否可以映射．只要存在字母对应出现的次数都相同．那么就可以通过映射得到． 具体是开一个数组记录每个字母出现的次数… 然后sort

Rabbit and Grass

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3058    Accepted Submission(s): 2261 **

Problem Description

大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去逛公园，不去和AC男约会，两个人竟然猫在寝食下棋…… 说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的： 1、棋盘包 …

hdu 2149题目链接

题意＆思路：巴什博奕，点m是n点。。。然后往前画即可。。。

 1/*************************************************************************
 2	> File Name: code/hdu/2149.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年09月22日 星期二 20时18分02秒
 6 …

题目链接：hdu 2188题目链接

题意＆思路：巴什博奕。。画n点p点。。。

 1/*************************************************************************
 2	> File Name: code/hdu/2188.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年09月22日 星期二 20时08分08秒
 6 …

tags:

• codeforces
• 算法竞赛
• acm
• ACM

**序：**博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。 寻找必败态即为针对此类试题给出一种解题思路。

tags:

• codeforces
• 算法竞赛
• acm
• ACM

给６个矩形的长和宽（或者宽和长），问这六个矩形能否组成一个长方体．

思路比较简单，不过需要注意的地方有点多．

首先由于长和宽的顺序为止，所以要处理一下（一开始只处理了后来读入的五组，没有处理单独读入的第一组，差评）

比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫　nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护．

tags:

• codeforces
• acm
• ACM

假设有n堆石子，每堆石子的个数分别如下

a1, a2, a3, … an

定义nim-sum为a1^a2^a3…an

可以证明

1. 若a1^a2^a3…an != 0

果然dp還是弱項啊啊啊啊．． 不過比最開始的完全無從下手強了不少應該．．．

至少dp狀態表示相對了．．．．轉移方程沒想出來嗚嗚嗚

官方題解：设d(i, j)d(i,j)表示前ii个数，模pp为jj的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+sum_{j=0}^{p-1} d(i-1, (j-a[i]) mod p)d(0,0)=1,d(i,j)=d(i−1,j)+∑​j=0​p−1​​d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| le 10^9∣a​i​​∣≤10​9​​

贪心．．尽量把一样的材料放在一起．．． 然后写蠢了．．妈蛋．．． 详情见代码

 1/*************************************************************************
 2	> File Name: code/bc/#56/1001.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年09月19日 星期六 18时55分49秒
 6 …

x的二进制表示中1的个数即为答案．

原因是，每天晚上糖果数量翻倍，相当于左移１位,这时候二进制表示中1的数量不变

也就是说，二进制表示中的所有的1，一定都是添加进去的

初识分快.

引一段题解：

Let’s split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let’s number them from left to right. We’re going to pass through points rectangle by rectangle. Inside the rectangle we’re going to pass the points in increasing order of y-coordinate if the number …

因为每一个正整数可以唯一分解质因数…

要看能猜多少次，只要知道不大于n的质因子数有多少个即可（相同的算多

由于n才是１０００．所以素数表随便搞就好….不用筛也行…

背包还是理解的不够透彻．．

因为每次都是用那个一维形式的．

这道题的做法类似01背包.

此外还可以有一个优化…

当n>m的时候．．．根绝抽屉原理．．一定为yes..