各组调研方案汇总

水文

调查内容

课上提到

1.水岸形态（码头，栅，洗衣平台…..)
2.塘，沼泽，荡
3.涨落
4.地理位置
5.内容
6.污染情况
7.水路交通
8.有无死河
9.填河水域

补充

10.水产养殖基地
11.台风后丁栅的水情（有无泛滥，倒灌）

调查方法

将丁栅的核心区分成被水系分割的12个岛。
从每个岛的某个点出发，逆时针绕岛沿岸拍摄，大概每隔100m拍一张。遇到特殊的则在地图上标记，并且拍摄
这样可以解决上述的（1/2/4/5/6/7/8/9）。
也就是还有(3/10/11)需要调查。
3的解决方法是一开始找一个平台记录下当时的水位，然后下次去的时候再看一下。
10/11，需要再绕完每个岛后对特殊的情况继续深入了解。

人员分配

最大的一个岛大概边长四公里。绕一圈半小时，结合调查大概一个半小时。
结合上述的问题。一个人负责六个岛的全貌，剩下两个人各负责三个岛的全貌。但是三个岛的两位在绕完边后
需要对于10与11以及2进行一个继续的调查。

能帮别的小组做的

1.每个桥梁可以拍到。
2.水域旁的养殖基地,可以与产业的小组沟通。
3.水路交通对于交通是一个补充。

另

原来商业的可能没有太多时间去做。
只能大家看到了在地图上标记出来。

===================================

交通

一.步行交通

1.步行道宽
2.斑马线分布
3.街道人数计数
4.街区穿行用时步数计数

二.车行交通

1.街道宽高比
2.街道停车
3.公交系统线路
4.无回头路状况
5.红绿灯情况
6.路灯位置
7.特定时期交通状况

三.街道市容

1.垃圾桶分布
2.街道绿化节点
3.街墙控制
4.转角
5.绿化植物种类

===================================

地块

调查内容

自己总结

1.大区编号
2.大区域类型
3.大区域边界
大区域边界标号
大区域边界类型
4.小群编号
5.小群类型
6.小群入口设置
7.小群边界
小群边界标号
小群边界类型
8.小群的照片记录

课上提到

1.边缘
2.内核
3.转角
4.入口
5.特点(米粉加工厂 嵌 厂房)

调查方法

将丁栅的核心区分成被水系分割的14个岛。
将这14个岛屿作为14个大区块。
在这14个大区块标号命名为A、B、C、D…N
将这些大区分类，给予其大致的区域类型(如0.工业区；1.农业区；2.居住区…具体参见调查记录表)
将大区的边界(根据其形状定下几边形，并按照顺时针方向给每条边界标号1、2…)
将上述标号的边界，定下边界类型(如:0.步行街；2.机动车道…具体参见调查记录表)
以上除了手动的记录(可以当场记录，可以之后总结)，更重要的是按着调查顺序拍照记录，记录分区分

人员分配

两人，一人拍照一人记录

能帮别的小组做的

1.大部分商业区会走遍，可以帮助拍照记录
2.大部分道路会走到，帮助拍照记录
3.途中和当地人交流和观察到的当地特点可以反映给问卷组

另

原来商业的可能没有太多时间去做。只能大家看到了在地图上标记出来。

===================================

商业

原来商业的可能没有太多时间去做。
只能大家看到了在地图上标记出来。

===================================

文教

查阅中心学校简介.pdf

调研方案

基础要求：
·学校与居住地的交通距离
·各级学校的情况
·教育特点
·人口年龄特征（中年劳动力比重）
·操场使用，开放程度
·图书馆

需了解的情况：

1. 各级学校（幼儿园、小学、初高中）的数量（前期确定）
2. 各级学校（幼儿园、小学、初高中）的位置（前期确定）
3. 丁栅镇居民对当地的教学状况是否满意？或者对学校（幼儿园）有什么期望
4. 丁栅镇居民更倾向送孩子在当地（丁栅镇）学校上学，还是到更远的城镇上学？（统计数据%）

从对学校调查中可以了解的问题：

1. 该学校有多少学生？（前期确定）
2. 学生来自哪里？丁栅镇或周边地区?
3. 学生的家庭条件如何？（模糊数据%）（很难调查）
4. 该学校有多少教师？（前期确定）
5. 教师的年龄结构？
6. 教师是否是本地人，如不是，来自哪里？（模糊数据%）
7. 教师的资质如何？（前期确定一部分）

8. 师生上下班（课）使用什么交通方式？到达学校需要多少时间？是否方便？

9. 校舍的新旧程度（年代）

10. 校舍的使用面积是否满足日常教学的需求？
11. 教学设备（投影仪、实验器材等）是否完善？
12. 学校是否有图书馆？如果有，有多少藏书？
13. 学生是否有足够的课外活动场地？
14. 学校的活动场地是否对外开放？
15. 学校的教学特色？（如为适应当地条件实施的规定、特别教学活动等）

16.幼儿园学生和低年级学生的上下学安全情况，通勤时间，交通工具
17.幼儿园的位置（地图上看周围较多工地，空气污染可能是问题）
18.校园周围景观

从对图书馆调查中可以了解的问题：

1. 图书馆的新旧程度（年代）
2. 图书馆的藏书量
3. 图书馆的藏书种类配比
4. 图书馆的开闭馆时间
5. 图书馆的人流量大小、座位使用率
6. 进入图书馆需要什么证件？
7. 体育场（馆）的新旧程度及保养条件
8. 体育场（馆）各个时间段的使用人数（我觉得不太可能测的出来。。改成使用频率怎么样？但是怎样定量分析？）

可调查地点
丁栅镇文化中心 姚庄镇图书馆丁栅分馆
丁栅镇中心学校 https://jsxdszxxx.jsxjyj.cn/
姚庄镇丁栅幼儿园 2014年9月开园
丁栅社区卫生服务中心
继续寻找一些比较有历史的，成为当地文脉一部分的建筑……

补充

1.对校园周边地块拍照，内部尽量拍照
2.在中心区中寻找一些小孩活动的“小领地”
3.图书馆周围的文具店

===================================

行为调查

一、地点

学校区、商业区、汽车站、住宅区……

二、访谈内容

1,人（整体）：

人口结构，人流（早中晚……）……

2,人与人的关系：

交集、矛盾，特定关系及特定行为发生的时间地点……

3,人与丁栅的关系：

吸引人的地方、打发时间的地点及理由，当地人心中的标志物（老街、制高点……）……

三、访谈目标

1,了解当地人的生活情况等……
2,对其他组调研不到的内容进行补充（住宅、生活情况等……）
3,尽可能找出“地”与“人”之间的联系。

===================================

产业

产业调研方案

1,农贸市场

去农贸市场了解下农贸价格, 分布, 来源

2,中午找个吃饭的地

3,实地走访产业

有那么多工厂如何解决？

• 1, 结合地形
• 2, 选择区块结点
• 3, 选择道路

确定地图上某些产业具体是什么。
实地调研完成后, 在地图上标记剩余产业.

4,去看下地图里标出来的较老的工厂

5,设计编号系统:

• 划分区块:Block, 道路Road
• 主要类型: a-工业, b-农业, c-混合型
• 细分类型: 01-水泥构件、02-建材、03-造纸、04-玩具、05-木业、06-纺织; 07-番茄, 08-甲鱼, 09-大米、10-蔬菜、12-莲藕

要跟地块, 交通, 水文组确定一下。包括拍照的编号。然后打印成一份直观的图, 大家相互通气。

6,拍照重点:

拍摄内容：
外部
1.工厂的大门形态（与地图标号相对应）
2.工厂大门与道路的交接情况
3.工厂开门形式
内部（可以的话）
1.工厂大致的厂房分布
2.厂房之间的道路（宽度等）
3.厂房的大开门口
4.厂房内部的基本结构（桁架 框架…）
5.厂房与河岸的关系
6.运送船和厂房和河岸和道路的联系
7.整个厂房里新建与老标记出来
8.不同商家工厂间的分隔形式（墙？ 铁栅栏？ 臭狗？ 草？ 河岸？）

7,调研回来后

1, 找出主要的工业农业产业
2, 爬取企业信息, 对类型进行分类, 出现的时间.
3, 地理位置标记
工商局
天眼查爬虫
天眼查

对其他组的补充

每个组大致有个活动范围, 在这个范围内也许能够为其他组提供一些调研数据。

• 方便联系
• 点铺开的广(避免死角, 想法更加分散多)

文化:

姚庄镇图书馆, 文化中心
田歌、庙会、社戏、调龙灯、串马灯

水系:

可以去渔具店, 买盒蚯蚓, 然后问问哪边钓鱼最合适, 水面宽阔

讨论

每个岛的编号初步确定。

模式语言

模式是什么?

每一个模式都描述我们周围环境中, 一再发生的某个问题(过去八年的建筑和规划实践), 叙述解决这个问题的关键所在。模式能够被反复调用, 而不会老调重弹之感。

使用模式:

模式关系

模式是有先后顺序的.

• 最大: 区域, 城镇
• 其次: 邻里, 住宅组团, 住宅, 房屋和凹室.
• 最后: 细部构造

每一种模式用于完善其前的较小的模式, 而它自身也位于其后较小模式所补充.

模式世界观:

没有任何一个模式是孤立存在的。每一个模式在世界上之所以能够存在, 是因为在某种程度上, 为其他模式所支持。每个模式又包含在较大的模式中，大小相同的模式都环绕在他周围, 而较小的模式又为他所包含.

模式是不断发展的, 希望利用这些语言, 发现更多真实深刻的不变特性.

书的概要p19

从城镇部分的概要, 可以窥见城镇部分, 设计的思路:

• 1, 划分出独立区域
• 2, 根据区域, 对土地进行保护和制定出各项政策行事
• 3, 有了政策, 形成说明城市的主要结构
• 4, 形成容易识别的社区.
• 5, 将社区之间互相联系起来. 交通, 环路, 学习, 商业, 小公共汽车
• 6, 制定社区和邻里政策, 控制环境的性质
• 7, 在社区边界内, 鼓励形成中心.
• 8, 环绕中心, 发展组团, 以面对面的人群为基础
• 9, 形成工作社区
• 10, 公路网络和小路网, 逐渐的不拘形式的发展.(城市中区域和道路的关系, 思路跟我原来想的不一样)
• 11, 提供人们能休憩, 与人交际的场所等等的公共活动场所
• 12, 社区和组团之间, 提供若干块活动用的土地.
• 13, 鼓励最小的独立社会组织: (上述)家庭, 工作, 聚会地的演变
• 14, 工作小组从车间办公室到儿童组织的各种形式发展.

(独特, 人, 制度, 规则)

建筑->构造(先省略)

几个模式:

24 珍贵的地方: 老街?..
25 通往水域,

41 工作社区
42 工业带
45 链状
46 综合商场

49 区内弯曲的道路
50 丁字形交点
52 小型路网和汽车

60 近宅绿地: 调研方法, 数据处理, 得出的结论. p671 模式68同理
70 墓地
83 师徒情谊: 学习网,
87 个体商店: 经营者自己掌管, 识别单位, 向街道开放
89 街角杂货店: 补充, 易识别邻里, 黄页调查方式, 商业网(19), 易识别邻里(14)
92 公共汽车站:
94 在公共场所打盹: 没想到的角度

p979之前..

交通模式:

49 区内弯曲的道路
50 丁字形交点
52 小型路网和汽车
92 公共汽车站:

文化模式:

24 珍贵的地方: 老街?水荡?居民区?
25 通往水域,
70 墓地

教育模式:

83 师徒情谊: 学习网,

工业模式:

41 工作社区
42 工业带
45 链状
46 综合商场

社区模式:

60 近宅绿地: 调研方法, 数据处理, 得出的结论. p671 模式68同理
83 师徒情谊: 学习网,
87 个体商店: 经营者自己掌管, 识别单位, 向街道开放
89 街角杂货店: 补充, 易识别邻里, 黄页调查方式, 商业网(19), 易识别邻里(14)
94 在公共场所打盹: 没想到的角度

调研的一些想法

1, 每个同学会搜集到一些素材(照片, 文字), 在讨论的时候, 每给出一张图片, 在坐的同学根据第一印象和介绍后的印象标记tags, 统计排序出现tags的次数.
2, 大块来讲, 可从现有的交通, 文化, 教育, 工业, 社区等方面分组调查; 观察和搜集几种特定模式所关注的问题.
3, 根据tags和几个模式下关注的问题, 一起讨论下调研问题目标, 问题设计, 处理(模式60).

1090 危险品装箱(25)

集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。

本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。

输入格式：

输入第一行给出两个正整数：N (≤10^4) 是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：
K G[1] G[2] … G[K]
其中 K (≤1000) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式：

对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。

输入样例：

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

输出样例：

No
Yes
Yes

Solution:

将每箱货物的存成hash表, 遍历每对违禁物品, 两件物品都存在这张表里就说明要爆炸, 退出遍历.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct Node {
  string a, b;
};

int main() {
  int N, M; cin >> N >> M;
  vector<Node> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i].a >> v[i].b;
  }
  unordered_map<string, int> mp;
  int n; string temp;
  while (M--) {
    cin >> n; mp.clear();
    for (int i = 0; i < n; i++) {
      cin >> temp;
      mp[temp] = 1;
    }
    int ok = 1;
    for (int i = 0; i < N; i++) {
      if (mp.count(v[i].a) && mp.count(v[i].b)) {
        ok = 0; break;
      }
    }
    if (ok) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}

1089 狼人杀-简单版(20)

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？

本题是这个问题的升级版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式：

输入在第一行中给出一个正整数 N（5≤N≤100）。随后 N 行，第 i 行给出第 i 号玩家说的话（1≤i≤N），即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式：

如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 A=a[1],…,a[M] 和 B=b[1],…,b[M]，若存在 0≤k<M 使得 a[i]=b[i] （i≤k），且 a[k+1]<b[k+1]，则称序列 A 小于序列 B。若无解则输出 No Solution。

输入样例 1：

5
-2
+3
-4
+5
+4

输出样例 1：

1 4

输入样例 2：

6
+6
+3
+1
-5
-2
+4

输出样例 2（解不唯一）：

1 5

输入样例 3：

5
-2
-3
-4
-5
-1

输出样例 3：

No Solution

Solution:

考试是没ac掉的题, 惋惜。自己的逻辑还需要锻炼, 要刷更多的题, 做更多事情, 认识更多人, 看更大的世界.

2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎

其实姥姥已经把问题写的很实质简短了, 是我真的太笨没能理解透。

分析一下, 最关键的是这两个条件:
1, 只有两个狼人, 其他都是好人.
2, 只有两个人说了假话, 一个是狼人, 一个是好人, 其他人都说真话.

正确思路是:
枚举两个狼人, 狼人如果确定了, 只要看谁说错了就是在说谎, 看谁说错的过程就是一个查Hash表的过程, 因为每个人都有一种观点talk, 另外, 每一个人都身份根据枚举的狼人建成了Hash表, 是确定的。最后只要判断说假话只有两个人, 并且只有一狼。

能想到枚举的方法, 但在考试的时候, 一直分析不出判断某次枚举成立的条件是什么。实际上回过头来看, 只要同时满足上述两个条件就好了。

我考试的时候枚举的是说谎的人, 这样枚举应该是条死路.
1, 首先, 说谎的人数是不固定的, 后面还需要根据展开的结果重新判断一次说谎人数是不是符合, 而狼人如果确定了, 只要看谁说错了就是在说谎.
2, 题目要求的就是狼人, 为什么逻辑还要嵌套一层呢?
3, 就需要先根据每个人说的, 得到所有人的身份, 然后确定是不是有两个狼人, 其中一个狼人是说谎的人.. 但问题是如果有些人的身份, 没直接提到怎么办呢? 我想这个应该是我错误的原因吧。

当然, 除此之外, 我前面的程序里还有很多冗杂的逻辑, 比如, copy一个vector????自己写了函数??? 比如, 自己实现的to_string和stoi不舍得丢, 分析每个人说话的时候, 还用到了string, s[0]看符号??substr提取数字???(经过, 学长的提醒, 后来改成了读整数, 判断正负…调试的时候, 还出现了溢出的情况, 回过头来想真是可怕, 只能用兵荒马乱来形容…

我考试时候没能写出的代码:

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct Talk {
  int st;
  int id;
};

int main() {
  int N; scanf("%d", &N);
  vector<Talk> talk_v(N+1);
  int st_arr[105];

  for (int i = 1; i <= N; i++) {
    int temp = 0; scanf("%d", &temp);
    int st = 0, id = temp;
    if (temp < 0) {
      st = 1; id = -1 * temp;
    }
    Talk talk; talk.st = st; talk.id = id;
    talk_v[i] = talk;
  }

  int find = 0;
  for (int i = 1; i <= N-1; i++) {
    for (int j = i+1; j <= N; j++) {
      memset(st_arr, 0, sizeof(st_arr));

      st_arr[i] = 1; st_arr[j] = 1;
      vector<int> lier_v;
      for (int k = 1; k <= N; k++) {
        int id_k = talk_v[k].id, st_k = talk_v[k].st;
        if (st_arr[id_k] != st_k) {
          lier_v.push_back(k);
        }
      }

      if (lier_v.size() == 2) {
        int cnt = 0;
        for (int k = 0; k < 2; k++) {
          if (lier_v[k] == i || lier_v[k] == j) cnt++;
        }
        if (cnt == 1) {
          find = 1;
          printf("%d %d\n", i, j);
          break;
        }
      }
    }
    if (find) break;
  }
  if (!find) printf("No Solution\n");
  return 0;
}

1088 三人行(20)

子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”

本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 2 位正整数；把甲的能力值的 2 个数字调换位置就是乙的能力值；甲乙两人能力差是丙的能力值的 X 倍；乙的能力值是丙的 Y 倍。请你指出谁比你强应“从之”，谁比你弱应“改之”。

输入格式：

输入在一行中给出三个数，依次为：M（你自己的能力值）、X 和 Y。三个数字均为不超过 1000 的正整数。

输出格式：

在一行中首先输出甲的能力值，随后依次输出甲、乙、丙三人与你的关系：如果其比你强，输出 Cong；平等则输出 Ping；比你弱则输出 Gai。其间以 1 个空格分隔，行首尾不得有多余空格。

注意：如果解不唯一，则以甲的最大解为准进行判断；如果解不存在，则输出 No Solution。

输入样例 1：

48 3 7

输出样例 1：

48 Ping Cong Gai

输入样例 2：

48 11 6

输出样例 2：

No Solution

Solution:

考试的时候， 刚开始把在[10,99]这个范围给忘记了, 2个case没过。

这里的丙一定要声明成double, 不能用取余来做, 不然case4过不了。因为丙本质上可以为小数.
丙是0.5, X = 12, Y = 4; 这是倍数是取得到的.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int db_equal(double d1, double d2) {
  return -0.0005 < d1-d2 && d1-d2 < 0.0005;
}

int main() {
  int m, x, y; cin >> m >> x >> y;
  string strs[4] = {"Cong", "Ping", "Gai"};
  int jia, yi, find = 0;
  double bing;
  for (int i = 99; i >= 10; i--) {
    jia = i;
    int second = jia % 10, first = jia/10%10;
    yi = second*10+first;
    int delta = (jia > yi) ? jia-yi : yi-jia;
    double bing = delta*1.0 / x;
    // if (!db_equal(bing, floor(bing+0.5))) continue;   // 0.5?
    if (db_equal(0, bing*y-yi)) {
      int a = jia >= m  ? jia > m ? 0:1:2,
          b = yi >= m   ? yi > m  ? 0:1:2,
          c = bing < m  ? 2 : bing > m ? 0:1;
          // c = tmp_b >= m ? tmp_ > m ? 0:1:2;
      cout << jia << " " << strs[a] << " " << strs[b] << " " << strs[c] << endl;
      find = 1;
      break;
    }
  }
  if (!find) {
    cout << "No Solution" << endl;
  }
  return 0;
}

1087 有多少不同的值(20)

当自然数 n 依次取 1、2、3、……、N 时，算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值？（注：⌊x⌋ 为取整函数，表示不超过 x 的最大自然数，即 x 的整数部分。）

输入格式：

输入给出一个正整数 N（2≤N≤10^4）。

输出格式：

在一行中输出题面中算式取到的不同值的个数。

输入样例：

2017

输出样例：

1480

Solution:

开表的时候要注意, 大小不是N的范围那么简单, 因为表中存的是值, 所以是运算后的范围, 可以严格证明, 但尽量开大点.
用max变量控制遍历的次数.

#include <cstdio>
#include <cmath>
using namespace std;

int main() {
  int N; scanf("%d", &N);
  int value[100050] = {0};
  int max = 0, cnt = 0;
  for (int i = 1; i <= N; i++) {
    int t = floor(i/2) + floor(i/3) + floor(i/5);
    value[t] = 1;
    max = t > max ? t : max;
  }
  
  for (int i = max; i >= 0; i--) {
    if (value[i]) cnt++;
  }
  printf("%d\n", cnt);
  return 0;
}

1086 就不告诉你(15)

做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着输出它们的乘积。

输入格式：

输入在第一行给出两个不超过 1000 的正整数 A 和 B，其间以空格分隔。

输出格式：

在一行中倒着输出 A 和 B 的乘积。

输入样例：

5 7

输出样例：

53

Solution1:

字符串反转字符串.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int a, b; cin >> a >> b;
  string temp = to_string(a*b);
  reverse(temp.begin(), temp.end());
  cout << stoi(temp) << endl;
  return 0;
}

Solution2:

手动模拟反转计算. 比较容易出错, 不过作为练习蛮好的.

#include <cstdio>
int main() {
  int a, b; scanf("%d %d", &a, &b);
  int n = a*b;
  int arr[10] = {0}, len = 0, t = 1;
  while (n) {
    arr[len++] = n % 10; t *= 10;
    n /= 10;
  }
  t /= 10;  // debug

  int ans = 0;
  for (int i = 0; i < len; i++) {
    ans += arr[i] * t;
    t /= 10;
  }
  printf("%d\n", ans);
  return 0;
}

1082 射击比赛(20)

本题目给出的射击比赛的规则非常简单，谁打的弹洞距离靶心最近，谁就是冠军；谁差得最远，谁就是菜鸟。本题给出一系列弹洞的平面坐标(x,y)，请你编写程序找出冠军和菜鸟。我们假设靶心在原点(0,0)。

输入格式：

输入在第一行中给出一个正整数 N（≤ 10 000）。随后 N 行，每行按下列格式给出：

ID x y
其中 ID 是运动员的编号（由 4 位数字组成）；x 和 y 是其打出的弹洞的平面坐标(x,y)，均为整数，且 0 ≤ |x|, |y| ≤ 100。题目保证每个运动员的编号不重复，且每人只打 1 枪。

输出格式：

输出冠军和菜鸟的编号，中间空 1 格。题目保证他们是唯一的。

输入样例：

3
0001 5 7
1020 -1 3
0233 0 -1

输出样例：

0233 0001

Solution:

注意, 是距离小, 排名考前.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

struct Node{
  string id;
  double delta;
};
int main() {
  int N; cin >> N;

  Node max_n, min_n;
  max_n.delta = 0; min_n.delta = 100;
  while (N--) {
    string id; int x, y;
    cin >> id >> x >> y;
    x = abs(x); y = abs(y);
    double delta = sqrt(x*x + y*y);
    if (delta > max_n.delta) {
      max_n.delta = delta;
      max_n.id = id;
    }
    if (delta < min_n.delta) {
      min_n.delta = delta;
      min_n.id = id;
    }
  }
  cout << min_n.id << " " << max_n.id << endl;
  return 0;
}

第二遍做, 思路差不多

// 第二遍做
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int main() {
  string id, max_s = "", min_s = "";
  double max = 0, min = 100, x, y;
  int N; cin >> N;
  while (N--) {
    cin >> id >> x >> y;
    double d = sqrt(x*x + y*y);
    if (d > max) {
      max_s = id; max = d;
    }
    if (d < min) {
      min_s = id; min = d;
    }
  }
  cout << min_s << " " << max_s << endl;
  return 0;
}

1005 Number Sequence

Problem Description

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output

For each test case, print the value of f(n) on a single line.

Sample Input

1 1 3
1 2 10
0 0 0

Sample Output

2
5

Solution:

这题还没有过.

递归法

先根据给出的公式, 实现了一种递归的写法, 但是MLE了, 栈溢出了吧。

#include <cstdio>

int f(int n, int a, int b) {
  if (n == 1 || n == 2) return 1;
  return (a * f(n-1, a, b) + b * f(n-2, a, b)) % 7;
}

int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n) != EOF && a && b && n) {
    printf("%d\n", f(n, a, b));
  }
  return 0;
}

// MLE

迭代法

改成另外一种迭代法, 虽然不会造成栈溢出, 但TLE, 因为题目中1 <= n <= 100,000,000, 肯定会超时.

#include <cstdio>

int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n) != EOF && a && b && n) {
    long long int fa = 1;          // f2
    long long int fb = (a+b) % 7;  // f3
    long long int ft = 0;
    int k = n - 3;
    while (k--) {
      ft = fb;
      fb = (a*fb + b*fa) % 7;
      fa = ft;
    }
    printf("%lld\n", fb);
  }
  return 0;
}

打表法

打表, 求余; 还不是很理解.

1, 因为余数是7, f(n)在0~6之间, 根据f(1), f(2)知道, 重新回到1, 1说明是一个周期, 所以两两配对, 一个7个数据, 49种可能.
2, 既然是49种可能, 那么n % 49的余数肯定小于49, 所以利用for循环, 将f(n)的数据都存入seq数组中, 复杂度很低.

#include <cstdio>
int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n)) {
    int i;
    int seq[1000] = {0};
    seq[1] = 1;
    seq[2] = 1;
    int t;
    if (a == 0 && b == 0 && n == 0) {
      break;
    }
    for (i = 3; i <= 49; i++) {
      seq[i] = (a * seq[i-1] + b * seq[i-2]) % 7;
    }
    t = n % 49;
    printf("%d\n", seq[t]);
  }
  return 0;
}

最后一种, 参考: https://blog.csdn.net/w_linux/article/details/75449891

1004 Let the Balloon Rise

Problem Description

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges’ favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

This year, they decide to leave this lovely job to you.

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) – the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

A test case with N = 0 terminates the input and this test case is not to be processed.

Output

For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.

Sample Input

5
green
red
blue
red
red
3
pink
orange
pink
0

Sample Output

red
pink

Solution:

找到出现次数最多的string, 用string读入map, 计数输出就可以了.

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;


int main() {
  int N;
  unordered_map<string, int> mp;
  string s;
  while (scanf("%d", &N) && N) {
    mp.clear(); string max_s = ""; int max = 0;
    while (N--) {
      cin >> s;
      auto it = mp.find(s);
      if (it != mp.end()) {
        it->second++;
      } else {
        mp[s] = 1;
      }
      if (mp[s] > max) {
        max_s = s; max = mp[s];
      }
    }
    cout << max_s << endl;
  }
  return 0;
}