f(sixleaves) = sixleaves

重剑无锋 大巧不工

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  95 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks

置顶随笔 #

     摘要: 1.掌握@property方法的四类参数设置,现在重点掌握与setter方法内存管理相关的参数。  阅读全文
posted @ 2015-05-08 20:41 swp 阅读(156) | 评论 (0)编辑 收藏

     摘要: 掌握自定义构造方法需要注意的规范。  阅读全文
posted @ 2015-05-02 14:29 swp 阅读(110) | 评论 (0)编辑 收藏

     摘要: 1.总结了@property与@synthesize和最新的@property新特性。  阅读全文
posted @ 2015-05-01 23:14 swp 阅读(125) | 评论 (0)编辑 收藏

 铁轨

PopPush城市有一座著名的火车站。这个国家到处都是丘陵。而这个火车站是建于上一个世纪。不幸的是,那时的资金有限。所以只能建立起一条路面铁轨。而且,这导致这个火车站在同一个时刻只能一个轨道投入使用,因为它缺少空间,两列火车将无路可走。具体看下图。

当地的惯例是每一列火车从A方向驶向B方向时候,会用某种方式将车厢重组。假设火车将要到达A方向,拥有N个车厢(N<=1000),这些车厢按照递增顺序标记为1到N。负责从组车厢的领导,必须知道是否能从组车厢让它驶出B,而这个重组的序列就是a1\a2\a3...aN.帮组他并且写一个程序来判断是否可能按照所要求的车厢顺序。你可以假设,单个的车厢可以从列车上分离出来,在他们进入站台之前。并且他们可以自由移动,知道它们上了B轨道。你也可以假设在任意时候站台可以放下无数的车厢。但是只要一个车厢进入站台,它就不能返回A轨道,同时如果它离开了站台驶向B轨道,它就不能返回站台。

输入:
这个输入文件由多个行块组成。每一个块描述的是多个要求的重组车厢的序列。在这每个块中的第一行是一个整数N,被用来说明上面每行的车厢个数。这个快的最后一行仅仅是一个数字0要来标记该快的结束
最后一个块仅仅是一个0独占一行。

输出:
这个输出文件包含多行,这些行和排列车厢的行数一一对应。日过该排列可行,则输出Yes,否则输出No。另外存在一个空行在每个相对应的块后面。输出文件中不存在于最后一个什么数据都没有的响应输出。

输出
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

Output
Yes
No

Yes

 1 /*
 2 由于station符合后进先出规则,所以可以用一个stack<int>来表示station。
 3 然后采用模拟的规则来写,因为进入station是按照编号递增进入,所以可以用aId变量表示。
 4 接下来就是模拟时候应该注意的条件,我们知道有以下两种情况,一种是一进来station,就出station
 5 也就是 aId == coaches[lenB]; 一种是进来时还不出站,那么这时候就要s.push(aId),但是这一种的条件呢?
 6 我们如果可以排除掉第一种,那么无非就是第二种了。但是我们要知道,在进站之前,如果站台里有车它是可以先出站的
 7 ,这种状态就条件就是 !s.empty() && s.top() == coaches[lenB].所以只要按照顺序判断这几个条件
 8 就可以写出这个模拟程序了。
 9 
10 
11 总结:
12 解决问题的关键点,在于构建问题的模型、大部分都是可以用现有的基础数据结构。构造完对应的数据结构,特别是对于模拟题
13 无非就是状态见的转移处理,这是就要在基于模型的基础上、先写出映射到个个状态的唯一条件,然后按照问题逻辑一一先后判断
14 即可。
15 */
16 #include <iostream>
17 #include <stack>
18 
19 using namespace std;
20 const int len = 1024;
21 int coaches[len];
22 
23 int main() {
24 
25     int n;
26     while (cin >> n, n) { 
27         stack<int> s;
28         // read the required permutaion
29 
30         while (    cin >> coaches[0], coaches[0]) {
31 
32             for (int i = 1; i < n; i++) {
33                 cin >> coaches[i];
34             }
35             int lenB = 0, aId = 1;
36             bool ok = true;
37             while (lenB < n) {
38 
39                 if (aId == coaches[lenB]) {  aId++; lenB++; }
40                 else if(!s.empty() && s.top() == coaches[lenB]) { s.pop(); lenB++; }
41                 else if(aId <= n) s.push(aId++);
42                 else { ok = falsebreak; }
43 
44             }
45 
46             cout << (ok ? "Yes" : "No") << endl;
47         }
48         cout << endl;
49     }
50     
51     return 0;
52 }
2015/3/30下午3:03:52
posted @ 2015-03-30 16:17 swp 阅读(1354) | 评论 (0)编辑 收藏

这是一道很好的模拟题,用vector<int> p[maxn],建立模型,映射为maxn个堆。主要要掌握vector模拟堆操作的简单方法。
接下来得思路是自顶向下的方式,逐步完善程序。首先根据提议列出下表。
1.move a onto b
clear_above(a) && clear_above(b);
insert a above b;

2.move a over b
clear(a)
insert a above bs

3.pile a onto b
clear(b)
insert as above b

4.pile a over b
insert as above bs

观察可以提取出move的话必有clear_above(a)、onto必有clear_above(b).
而insert 动作不管b是在p[b]的顶部还是外部。都是p[b].push_back(a或a以上的木块)
所以可以抽取成pile_into(pa, ha, pb);

考虑完这些,开始写框架。如下
 1 
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <string>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 64;
 9 int n;
10 vector<int> a[maxn];
11 int find_block(int a, int& h);
12 void clear_above(int p, int h);
13 void pile_into(int pa, int ha, int pb);
14 void print();
15 int main() {
16 
17     
18     
19     string s1, s2;
20     scanf("%d", &n);
21     for (int i = 0; i < n ; i++) {
22         a[i].push_back(i);
23     }
24     
25     while (cin >> s1, s1 != "quit") {
26         int ba,bb;
27         cin >> ba >> s2 >> bb;
28         int ha = 0,hb = 0;
29         int pa = find_block(ba, ha);
30         int pb = find_block(bb, hb);
31         if (pa == pb) continue;
32         
33         if (s1 == "move") clear_above(pa, ha);
34         if (s2 == "onto") clear_above(pb, hb);
35         pile_into(pa, ha, pb);
36     }
37     
38     print();
39     return 0;
40 }
 
接下来,完成程序其它部分,按照框架的意思,逐步完善。如下
 1 void print() {
 2     
 3     for (int i = 0; i < n; i++) {
 4         printf("%d:",i);
 5         for (int h = 0; h < a[i].size(); h++) {
 6             printf(" %d", a[i][h]);
 7         }
 8         printf("\n");
 9     }
10 }
11 
12 int find_block(int ba, int& h) { 
13     
14     for (int i = 0; i < n; i++) {
15         
16         int vec_size = a[i].size();
17         for (h = 0; h < vec_size; h++) {
18             if (ba == a[i][h]) return i;
19         }
20         
21     }
22     return -1;
23 }
24 
25 void clear_above(int p, int h) {
26     int vec_size = a[p].size();
27     for (int i = h + 1; i < vec_size; i++) {
28         
29         int b = a[p][i];
30         a[b].push_back(b);
31         
32     }
33     a[p].resize(h + 1);
34 }
35 
36 void pile_into(int pa, int ha, int pb) {
37     
38     int vec_size = a[pa].size();
39     
40     for (int i = ha; i < vec_size; i++) {
41         a[pb].push_back(a[pa][i]);
42     }
43     a[pa].resize(ha);
44 }
posted @ 2015-03-16 15:03 swp 阅读(167) | 评论 (0)编辑 收藏

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 
 5 int readChar();
 6 int readInt(int c);
 7 int readCodes();
 8 
 9 /*
10  1.读取字符时候如何过滤掉换行符号,兼容类unix和windows操作系统 readChar()
11  2.熟练掌握将二进制字符串映射到数组的数据结构,这个数据结构是个二元组,我们可以用该二元组唯一确定一个长度为len的二进制字符串
12  (len, value) ---- > code[len][value]
13  
14  */
15 
16 int main() {
17 
18     
19     while ( readCodes() ) { // 读编码头
20         
21         for (;;) {  // 读信息
22             
23             int len = readInt(3);
24             if (0 == len) break// 全0该信息结束
25             
26             for (;;) {  // 读信息段
27                 
28                 int v = readInt(len);
29                 
30                 if (v == (1 << len) - 1break// 全1一个信息段结束
31                 putchar(code[len][v]);
32                 
33             }
34             
35         }
36         
37         putchar('\n');
38     }
39 }
40 
41 
42 int readInt(int l) {
43     
44     int v = 0;
45     //已经读取了3 - l个字符
46     while (l--) {
47         
48         v = v * 2 + readChar() - '0';
49         
50     }
51     return v;
52     
53 }
54 
55 
56 char readChar() {
57     
58     char ch;
59     do {
60         
61         ch = getchar();
62         
63     }while ( '\n' != ch || '\r' != ch )
64     return ch;
65 }
66 
67 
68 int readCodes() {
69     
70     
71     memset(code, 0sizeof(code));
72     
73     // 因为可能读取编码头独占一行,所以我们可能读取编码头时候会读取到上一次的回车换行,所以要使用readChar函数
74     code[1][0= readChar();
75     
76     for (int len = 2; len < 8; len++) {
77         
78         for (int v = 0; v < (1 << len) - 1; v++) {
79             
80             char ch = getchar();
81             if ( EOF == ch ) return 0;
82             if ( '\n' == ch || '\r' == ch) return 1;
83             code[len][v] = ch;
84             
85         }
86         
87     }
88     return 1;
89     
90     
91 }
posted @ 2015-03-13 20:06 swp 阅读(149) | 评论 (0)编辑 收藏

2015年5月25日 #

     摘要: 1.解决数字键盘不出现问题  阅读全文
posted @ 2015-05-25 21:03 swp 阅读(978) | 评论 (0)编辑 收藏

2015年5月15日 #

     摘要: 1.NSDate与NSDateFormatter的创建 2.日期转为字符串、字符串转日期的方式 3.日期格式化的参数  阅读全文
posted @ 2015-05-15 15:19 swp 阅读(244) | 评论 (0)编辑 收藏

     摘要: 1.NSNumber、NSValue分别用于包装什么 2.如何解包装和注意事项 3.NSNumber与NSValue的关系  阅读全文
posted @ 2015-05-15 14:49 swp 阅读(160) | 评论 (0)编辑 收藏

2015年5月14日 #

     摘要: 1.掌握总结即可。 2.在掌握共同的接口特点  阅读全文
posted @ 2015-05-14 19:39 swp 阅读(438) | 评论 (0)编辑 收藏

     摘要: 1.NSString的创建 2.NSString的读与写 3.NSMutableString的创建 4.NSMutable与NSString的区别  阅读全文
posted @ 2015-05-14 16:08 swp 阅读(125) | 评论 (0)编辑 收藏

2015年5月13日 #

     摘要: 1.各结构体的含义(四个) 2.结构体的常用创建方式 3.快速打印结构体的方法 4.CGFloat的本质  阅读全文
posted @ 2015-05-13 21:13 swp 阅读(214) | 评论 (0)编辑 收藏

     摘要: 1.代理设的概念 2.代理设计模式的使用场合 3.代理设计模式的实现  阅读全文
posted @ 2015-05-13 16:39 swp 阅读(462) | 评论 (0)编辑 收藏

     摘要: 1.protocol的作用 2.protocol相关语法 3.基协议 4.限制对象类型 5.协议前置声明 6.协议也能遵守协议  阅读全文
posted @ 2015-05-13 11:09 swp 阅读(159) | 评论 (0)编辑 收藏

2015年5月12日 #

     摘要: 1.全面总结循环引用的解决方案 2.如何将工程转换成ARC项目。 3.如何让ARC与非ARC混用  阅读全文
posted @ 2015-05-12 19:39 swp 阅读(169) | 评论 (0)编辑 收藏

     摘要: 1.ARC释放对象的判断准则 2.ARC的4个特点 3.强/弱指针的概念 4.常见错误  阅读全文
posted @ 2015-05-12 16:47 swp 阅读(194) | 评论 (0)编辑 收藏

仅列出标题  下一页