Posts

题意　：给定一个长度为n的区间．然后给k次询问，每次一个数t，求一个区间[l,r]使得这个区间和的绝对值最接近t 没办法直接尺取. 先预处理出来前缀和 如果要找一对区间的和的绝对值最最近t

Jessica’s Reading Problem Time Limit Memory Limit Total Submissions Accepted 1000MS 65536K 8787 2824 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 pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.

由于顺序是可以改变的． 所以考虑是否可以映射．只要存在字母对应出现的次数都相同．那么就可以通过映射得到． 具体是开一个数组记录每个字母出现的次数… 然后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、棋盘包含1*n个方格，方格从左到右分别编号为0，1，2，…，n-1； 2、m个棋子放在棋盘的方格上，方格可以为空，也可以放多于一个的棋子； 3、双方轮流走棋； 4、每一步可以选择任意一个棋子向左移动到任意的位置（可以多个棋子位于同一个方格），当然，任何棋子不能超出棋盘边界； 5、如果所有的棋子都位于最左边（即编号为0的位置），则游戏结束，并且规定最后走棋的一方为胜者。

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 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31int n,m; 32int main() 33{ 34 #ifndef ONLINE_JUDGE 35 freopen("in.txt","r",stdin); 36 #endif 37 while (scanf("%d %d",&m,&n)!=EOF) 38 { 39 if (m<n+1) 40 { 41 printf("%d",m); 42 for ( int i = m+1 ; i <= n; i++) 43 printf(" %d",i); 44 printf("\n"); 45 continue; 46 } 47 int tmp = m%(n+1); 48 if (tmp>0) 49 { 50 printf("%d\n",tmp); 51 } 52 else 53 { 54 puts("none"); 55 } 56 57 } 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}

题目链接：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 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31void solve() 32{ 33 int n,m; 34 scanf("%d %d",&n,&m); 35 if (n%(m+1)!=0) 36 { 37 puts("Grass"); 38 } 39 else 40 { 41 puts("Rabbit"); 42 } 43} 44int main() 45{ 46 #ifndef ONLINE_JUDGE 47 freopen("in.txt","r",stdin); 48 #endif 49 int T; 50 cin>>T; 51 while (T--) 52 { 53 solve(); 54 } 55 #ifndef ONLINE_JUDGE 56 fclose(stdin); 57 #endif 58 return 0; 59}

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

给６个矩形的长和宽（或者宽和长），问这六个矩形能否组成一个长方体． 思路比较简单，不过需要注意的地方有点多． 首先由于长和宽的顺序为止，所以要处理一下（一开始只处理了后来读入的五组，没有处理单独读入的第一组，差评）

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

假设有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=0p−1d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| le 10^9∣ai∣≤109

贪心．．尽量把一样的材料放在一起．．． 然后写蠢了．．妈蛋．．． 详情见代码 代码实现 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 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31const int N=5E2+7; 32int a[N],b[N]; 33int ans,cnt; 34int p[N]; 35int n; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("in.txt","r",stdin); 40 #endif 41 int T; 42 cin>>T; 43 while (T--) 44 { 45 ans = 0; 46 cnt = 0; 47 ms(p,0); 48 scanf("%d",&n); 49 for ( int i = 0 ; i < n ; i++ ) 50 { 51 scanf("%d %d",&a[i],&b[i]); 52 p[a[i]]+=b[i]; 53 } 54 int kind = 0; 55 for ( int i = 1 ;i <= 500 ; i++) 56 { 57 if (p[i]!=0) 58 { 59 // cnt = cnt + (p[i]-1)/64 + 1; 60 cnt = cnt + (p[i]+63)/64;　//这样写不知高到哪里去了． 61 p[i] = 0; 62 } 63 64 } 65 //ans = ans + (cnt-1)/36+1; 66 ans = (cnt+35)/36; //不知高到哪里去了．．． 67 printf("%d\n",ans); 68 69 70 } 71 72 73 #ifndef ONLINE_JUDGE 74 fclose(stdin); 75 #endif 76 return 0; 77}

x的二进制表示中1的个数即为答案． 原因是，每天晚上糖果数量翻倍，相当于左移１位，这时候二进制表示中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 of rectangle is even and in decreasing if it’s odd. Let’s calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we’re passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we’re spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.

因为每一个正整数可以唯一分解质因数… 要看能猜多少次，只要知道不大于n的质因子数有多少个即可（相同的算多 由于n才是１０００．所以素数表随便搞就好….不用筛也行…

背包还是理解的不够透彻．． 因为每次都是用那个一维形式的． 这道题的做法类似01背包. 此外还可以有一个优化… 当n>m的时候．．．根绝抽屉原理．．一定为yes..