↓ Skip to main content
111qqz’s blog

Posts

2015

poj 2739 Sum of Consecutive Prime Numbers (尺取法)

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

poj 2100 Graveyard Design (two pointers ，尺取法)

·1 min
ACM 尺取
不多说，直接代码。 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#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; 31LL n; 32LL maxn; 33vector<LL>ans; 34 35 36void solve() 37{ 38 LL head = 1,tail = 1; 39 LL sum = 0 ; 40 41 while (tail<=maxn) 42 { 43 sum = sum + tail*tail; 44 45 if (sum>=n) 46 { 47 while (sum>n)//主要是while，因为可能要减掉多个才能小于n 48 { 49 sum -= head*head; 50 head++; 51 } 52 if (sum==n) 53 {//因为要先输出答案个数...所以必须存起来延迟输出... 54 ans.push_back(head); 55 ans.push_back(tail); 56 } 57 } 58 tail++; 59 } 60 LL sz = ans.size(); 61 printf("%lld\n",sz/2); 62 for (LL i = 0 ; i<ans.size() ; i = i +2) 63 { 64 printf("%lld",ans[i+1]-ans[i]+1); 65 for ( LL j = ans[i] ; j <=ans[i+1] ; j++) printf(" %lld",j); 66 printf("\n"); 67 } 68 69} 70int main() 71{ 72 #ifndef ONLINE_JUDGE 73 freopen("in.txt","r",stdin); 74 #endif 75 scanf("%lld",&n); 76 maxn = ceil(sqrt(n)); 77 solve(); 78 79 #ifndef ONLINE_JUDGE 80 fclose(stdin); 81 #endif 82 return 0; 83}

poj 3320 Jessica's Reading Problem (尺取法)

·3 mins
ACM 尺取法
Jessica’s Reading Problem **Time Limit:** 1000MS **Memory Limit:** 65536K **Total Submissions:** 8787 **Accepted:** 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.

poj 2159 Ancient Cipher(水)

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

acm博弈论

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

codeforces #319 div 2 E C. Points on Plane (分块)

·1 min
ACM 分块
初识分快. 引一段题解： 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.