37. 黑色星期五

题目

问题描述

13号又是星期五是一个不寻常的日子吗? 13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13 日落在星期一,星期二......星期日的次数.这个测试从1900年1月1日到 1900+n-1年12月31日.n是一个非负数且不大于400.

这里有一些你要知道的: 1900年1月1日是星期一. 4,6,11和9月有30天.其他月份除了2月都有31天.闰年2月有29天,平年2月有28天.

输入说明

一个整数n（1<= n <= 400）.

输出说明

七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一.....星期五的次数.

个人总结

思路

1. 题目数据范围N只有400，非常小，不需要找复杂的数学规律，直接写循环逐月模拟日期的推移即可。
2. 已知1900年1月1日是周一，加12天就是1月13日，即周一往后推12天是周六（(1+12)%7=6），所以初始计数从周六开始。
3. 下个月13号的星期数 = (本月13号的星期数 + 本月天数) % 7。利用取模运算让星期数始终保持在0-6之间。
4. 闰年判定：主要用于确定2月天数。口诀是四年一闰，百年不闰，四百年又闰。逻辑表达式为 (y%4==0 && y%100!=0) || y%400==0。

易错点

1. 循环里先利用本月天数算出下个月的星期，这样会导致循环结束时多算了一个月（算到了第N+1年的1月），所以最后一行 res[last]-- 是必须的，这一步很容易漏掉。
2. 题目要求的输出顺序很特殊，是从星期六开始，接着是日、一...五。这和通常数组下标0-6（日到六）或1-7的习惯不同，输出时要注意下标的映射关系。

代码

#include <bits/stdc++.h>
using namespace std;

// 判断闰年
bool is_leap(int y){
	return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}


// 根据年份返回本月天数
int get_days(int y, int m){
	int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
	if (is_leap(y) && m == 2){ // 是闰月
		return 29;
	}else{
		return days[m];
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	// 储存星期数，0代表周日，1代表周一
	int res[7] = {0};
	
	// 找到第一个13号作为开始
	int last = 6;
	res[last] += 1;
	
	for (int i = 0; i < n; i++){ // 逐年增加
		for (int j = 1; j <= 12; j++){ // 逐月增加
			int total = get_days(i+1900,j);
			int wd = (total % 7 + last) % 7; // 这个13号是周几
			res[wd] += 1;
			last = wd; // 更新上一个13号
		}
	}
	// 最后一年的12月多加了1，要减掉
	res [last]--;
	
	// 输出顺序：
	// 星期六,星期日,星期一.....星期五的次数
	cout << res[6];
	for (int i = 0; i < 6; i++){
		cout << " " << res[i];
	}
	cout << "\n";
	
	return 0;
}

38. 树

题目

问题描述

明明是一家地铁建设公司的职员，他负责地铁线路的规划和设计。一次，明明要在一条长L的马路上建造若干个地铁车站。

这条马路有一个特点，马路上种了一排树，每两棵相邻的树之间的间隔都是一米。

如果把马路看成一个数轴，马路的一端在数轴0的位置，马路的另一端在L的位置，那么这些树都种在数轴的整数点上，即0，1，2，…，L上都种有一棵树。

由于要设计建造地铁站的缘故，所以需要把一些树移走，明明为了移树的方便，把地铁站的区域也建在了数轴上两个整数点之间，由于有多条地铁线路，地铁车站的区域可能会有部分的重合（重合的区域明明将来会设计成一个大型的车站，移树的时候不必考虑地铁站重合区域的问题）。

现在明明想请你帮一个忙，他把车站区域的位置告诉你，即告诉你数轴上的两个整数点，在这两个整数点之间是车站的区域，请你写一个程序，计算出把所有车站区域两点之间的树移走以后，这条马路上还剩多少棵树。

例如：马路长为10，要建造2个地铁车站，车站的区域分别是2到5和3到6，原先的马路上一共有11棵树，在2到5的位置上建车站后，需要移走4棵树，在3到6的位置上建车站后，也需要移走4棵树，但是3到6这个区域和2到5这个区域有部分重合，所以只需移走1棵树即可，这样总共移走的树是5棵，剩下的树就是6棵。

明明的问题可以归结为：给你一条马路的长度和若干个车站的位置，请你用程序计算出把树移走后，马路上还剩多少棵树。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有多行，每组测试数据的第一行有两个整数L（1≤L≤10000）和M（0≤M≤100），分别表示马路的长度和地铁车站区域的个数。接下来有M行，每行有2个整数，分别表示每一座地铁车站区域的两个坐标的。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即把树移走后，马路上还剩下多少棵树。每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

个人总结

思路

由于马路长度 L 较小（最大 10000），可以建立一个大小为 10001 的数组代表马路上的每个整点。
数组初始化为 true（代表有树）。每读入一个区间 [a, b]，就通过循环将数组下标 a 到 b 的元素标记为 false（代表移走）。最后统计 0 到 L 范围内 true 的个数

易错点

注意数组的初始化问题。

之前一直用 int c[10] = {0}; 来把数组初始化为0，但在初始化为其他结果，如这题的 1 或 true 时不可以这么做。

大括号 {} 的填充规则是“缺省补零”，而不是“复制第一个数”。

当写 type arr[n] = {x}; 时，编译器的逻辑是：

1. 把第 0 个位置赋值为 x。
2. 把剩下所有没写的位置，全部赋值为 0 (false)。

我们来看这两种情况的区别：

情况 1：int c[10] = {0};

• 第 0 位：设为 0。
• 剩下 9 位：系统自动补 0。
• 结果：全是 0。
• 看起来像是“把所有数设为了0”，其实是因为人工设的值刚好和系统补的值一样。

情况 2：bool trees[L+1] = {true}; (true 在 C++ 里是 1)

• 第 0 位：设为 true (1)。
• 剩下 L 位：系统自动补 0 (false)。
• 结果：只有第一个是 true，后面全是 false。
• 这就不管用了。

只有一种情况可以用 {} 初始化整个数组： 就是想把数组全部清零（全为 0 或 false）的时候，可以写 = {0}。 其他任何值（全为 1、全 true、全 -1），请老老实实写 for 循环或 std::fill。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int L, M;
	while(cin >> L >> M){
		// 数组储存所有位置情况
		bool trees[10001];
		for (int i = 0; i < 10001; i++) trees[i] = true;
		
		// 读入数据并标记
		int a,b;
		for (int i = 0; i < M; i++){
			cin >> a >> b;
			for (int i = a; i <= b; i++){
				trees[i] = false;
			}
		}
		
		// 统计总数
		int sum = 0;
		for (int i = 0; i <= L; i++){
			if (trees[i]) sum++;
		}
		cout << sum << "\n";
		
	}
	
	
	return 0;
}

39. 约瑟夫环

题目

问题描述

有一次，明明的公司举行忘年会。忘年会的高潮部分是最后的抽大奖环节。公司为了增加活动的气氛，并没有按传统的抽奖方式来抽，而是进行了一个游戏：逐步逐步地淘汰人，而最后剩下的人，将会得到大奖。

这个游戏的方式如下：首先公司的全部职员围成一个圈，然后确定一个淘汰数X，接着就从其中的一个人开始，从1数数，当数到X时，那个人就被淘汰出局，接着下一个人再从1开始数数，一直这样重复下去，直到剩下最后一个人，那个人就是最后的大奖得主。

例如，公司有5个人，淘汰数定为2，则一开始五个人排成一圈，依次编号为：1、2、3、4、5； 首先从编号1的人开始数数，数到2后，编号2淘汰，这样只剩下4个人：1、3、4、5； 接着从编号3的人开始数，数到2后，编号4淘汰，这样只剩下3个人：1，3、5； 接着从编号5的人开始数，数到2后，编号1淘汰，这样只剩下2个人：3、5； 最后从编号为3的人开始数，数到2后，编号5淘汰，最后编号为3的那个人就获得了最终的大奖。 （注：以上的淘汰顺序为2 4 1 5 3。）

由于明明的运气十分地差，最后第二个被淘汰，与大奖失之交臂，十分郁闷。他想知道自己被淘汰的全过程，于是他想请你帮个忙，帮他写一个程序，明明把他公司的人数告诉你，并且把那个淘汰数也告诉你，你的程序能够根据这两个数计算出淘汰人的具体顺序，即把淘汰人的编号按顺序输出。

明明的问题可以归结为：给你一个公司的人数N和一个淘汰数X，你的程序模拟上面描述的淘汰方式，输出淘汰人的编号顺序。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅一行，每组测试数据有两个整数N（1<N<100）和X（0<X<10），N表示公司的人数，X表示淘汰数，两个整数用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为N个整数，即淘汰人的编号的顺序，每个数之间用一个空格隔开。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

个人总结

思路

1. 使用一个数组记录每个人的状态，初始全标记为1代表在圈内，0代表已淘汰。
2. 总共需要淘汰N人，所以循环N次。
3. 记录上一个被淘汰者的位置last，下一轮从 (last + 1) % N 开始数。
4. 在内层寻找第X个人时，只有遇到标记为1的人计数器cnt才加1，遇到0则跳过。
5. 找到后将该位置标记为0，并更新last供下轮使用。
6. 初始状态下 last 设为 -1,既可以实现算法本身的正常运行，又因为循环过程中不会出现将 last 设为 -1 的情况，因此也可以用来作为是否是第一轮输出的判断条件，从而控制对空格的输出。

易错点

这题最大的问题在于，所有对于位置的处理都必须要进行取模。一旦有地方遗漏，可能会导致结果大多数时候看起来正确，但在一些特殊情况出错。

1. pos在移动时必须时刻对N取模，即 (pos + 1) % N，否则不仅无法回到起点，还会导致数组越界。
2. while循环的逻辑是数够了X个人后，pos仍执行了一次加1操作，所以循环结束后pos实际上指向了目标的下一个人，必须回退一步。
3. 回退一步时不要直接写 pos - 1，当pos为0时会变成-1导致越界。正确的写法是 (pos + N - 1) % N，利用加N再取模的方法处理循环回退。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, X;
	while (cin >> N >> X){
		// 初始化数组，每人对应一个位置，位置序号比编号小 1
		int a[105];
		for (int i = 0; i < 105; i++) a[i] = 1;
		
		// 逐轮淘汰
		int last = -1; // 上一个淘汰的人
		// 每次淘汰一人，共 N 轮
		for (int i = 0; i < N; i++){
			// 计算淘汰人选
			int cnt = 0;
			int pos = (last + 1) % N;
			while (cnt < X){
				cnt += a[pos];
				pos = (pos + 1) % N;
			}
			// pos 多前进了一格，需要回退
			pos = (pos + N - 1) % N;
			
			a[pos] = 0;
			if (last != -1){ // 不在第一轮，先输出空格
				cout << " ";
			}
			cout << pos + 1;
			last = pos;
		}
		cout << "\n";
		
	}

	
	return 0;
}

计算机英语翻译练习

More recent examples of Turing test "successes" include Internet viruses that carry on "intelligent" dialogs with a human victim in order to trick the human into dropping his or her malware guard. Moreover, phenomena similar to Turing tests occur in the context of computer games such as chess-playing programs.Although these programs select moves merely by applying brute-force techniques, humans competing against the computer often experience the sensation that the machine possesses creativity and even a personality. Similar sensations occur in robotics where machines have been built with physical attributes that project intelligent characteristics. Examples include toy robot dogs that project adorable personalities merely by tilting their heads or lifting their ears in response to a sound.

图灵测试“成功”的更近期案例包括一些互联网病毒，它们能与人类受害者进行“智能化”对话，从而诱导受害者放松对恶意软件的警惕。

此外，在国际象棋等计算机游戏领域，也存在类似图灵测试的现象。尽管这些程序仅仅通过一些简单粗暴的技术来选择移动方式，但与计算机对弈的人类往往会产生一种感觉，认为机器具有创造力，甚至拥有个性。

同样的感觉也发生在具有物理属性、模仿智能特征的机器人身上。例如，一些玩具机器人狗仅需在听到声音时歪头或竖起耳朵来响应声音，就能表现出讨人喜欢的个性。

I. Introduction

Virtual reality (VR) is becoming increasingly popular, as computer graphics have progressed to a point where the images are often indistinguishable from the real world. However, the computer-generated images presented in games, movies, and other media are detached from our physical surroundings. This is both a virtue—-everything becomes possible—and a limitation. The limitation comes from the main interest we have in our daily life, which is not directed toward some virtual world, but rather toward the real world surrounding us.

I. 引言

随着计算机图形学的发展，图像往往已达到与现实世界难辨真伪的程度，虚拟现实（VR）也随之变得越来越流行。

然而在游戏、电影和其他媒体中所呈现的计算机生成图片，与我们的现实环境是脱节的。

这既是一个优点，也是一个限制。优点在于它让一切变得可能，而限制则在于我们在日常生活中主要感兴趣的，并不是虚拟世界，而是环绕我们的真实世界。

In many ways, enhancing mobile computing so that the association with the real world happens automatically seems an attractive proposition. Augmented reality (AR ) holds the promise of creating g direct, automatic, and actionable links between the physical world and electronic information. It provides a simple and immediate user interface to an electronically enhanced physical world. AR can overlay computer-generated information on views of the real world, amplifying human perception and cognition in remarkable new ways.

在许多方面，增强移动计算以实现与现实世界的自动关联，似乎是一个极具吸引力的方案。

增强现实（AR）有望在物理世界与电子信息之间建立起直接、自动且可操作的联系。

它为电子增强的物理世界提供了一个简单且即时的用户界面。

AR 可以将计算机生成的信息叠加在现实世界的视图上，以非凡的新方式提升人类的感知与认知能力。