暑假集训Day3

#计划和一些无用的碎碎念

——————————————集训队—————————————

1. 我的挑战程序设计和算法导论都到啦！
2. 深搜剪枝的问题感觉原理不难，难题也需要水题打基础吧。
3. 暑假坚持打了cf，虽然最近都没计分，希望能尽快组队！！

——————————————前 端——————————————

1. 继续学习JS，果然JS比HTML和CSS实现的东西都要高级点。
2. 总是放心不下，如果把前端学到能谋生的地步，可能会放心。

——————————————Unity——————————————

1. 已经入门编了点东西出来，真的好好用。

——————————————————————————————

• 可能确实是一个没有什么安全感的人，从很早开始，生活对于我来说就变得像一团迷雾，无法确定选择是否正确，也不知道所有的可能性通往何处，希望能把未来牢牢地掌控在自己手中。有时候会想自己是不是太贪心了，因为精力是有限的，不能什么都尝试，但是我真的怕路不通，还是希望自己能狡兔三窟。
• 如果能通过前端外包做网页达到赚点小钱，acm能组队，压力会减轻很多。这么一看现在的焦虑大概是因为生活没有步入正轨，一定要说的话有时候会感觉生活像一匹马车，一开始我拉着他跑，后来我跟着他跑，再后面感觉缰绳拖着我走，一路拖过去现在膝盖都快磨没了。
• 发现不放弃还真的是自己唯一值得称道的特质。有人说过“喜欢你努力的样子。”听起来像是喜欢那种飞蛾扑火的样子。也许很多时候不放弃真的是没有什么用的，除非现实世界也能存档，那我有那个韧性一次次达成best。
• 我喜欢和别人说问题的解决方案就像一个圆，但有时候他也许更像一个胡乱缠绕的线团，时刻都在恐惧，事情是混乱复杂的，世界是混乱复杂的，但是没有人喜欢混乱复杂，在裹挟中的痛苦大概是必然会有的。
• 高中的时候第一次接触到波德莱尔的《恶之花》，有强烈的共鸣，我知道我和他本质上是同一种人。因为知道自己迟早会倒霉反而无所顾忌，被不知来处的原罪感压得喘不过气来，只不过他选择了保持放飞自我，我在释放本性的时候，偶尔觉得自己还能抢救一下。虽然丧，但是也能丧的有力量，比强撑着积极。

---

我在这里向我的博客倾诉，顺便发个誓：
我一定会成为很了不起的人的，我不会消失，也不会毁灭。

毕竟创造和毁灭都是原始欲望，这么看前者可比后者简单多啦，所以我一定可以做到的。

---

最后：

没有人会不喜欢David Bowie，真的相见恨晚！
长得像吉良吉影的zongyu系摇滚歌星。

Strange infatuation seems to grace the evening tide
无法言喻的痴恋仿佛使夜色更为迷人
I’ll take it by your side
我在你身边欣赏着
Such imagination seems to help the feeling slide
这种幻觉似乎促使着感情的转变
I’ll take it by your side
我在你身边感受着
Instant correlation sucks and breeds a pack of lies
速食般的关系很恶心，不断孕育出大量的谎言
I’ll take it by your side
我在你身边忍受着
Oversaturation curls the skin and tans the hide
过于了解你的一切，我的心被不断打击着
I’ll take it by your side
我在你身边承受着
tick - tock
滴答滴答
tick - tock
滴答滴答
tick - tock
滴答滴答
tick - tick - tick - tick - tick - tock - tick
滴答滴答滴答滴答滴答滴答滴答滴答
I’m unclean, a libertine And every time you vent your spleen
我放荡不洁
I seem to lose the power of speech
每次你一发脾气
Your slipping slowly from my reach
我便无话可说
You grow me like an evergreen
你渐渐的远离我
You never see the lonely me at all
你只把我当作常青植物那样养着，不管不顾
I…
从没留意过我的孤单
Take the plan, spin it sideways
这种想法，不断盘旋在我脑海
I…
我却依旧沉沦
Fall

Without you, I’m Nothing
没有你，我算什么
Without you, I’m nothing
没有你，我什么也不是
Without you, I’m nothing
没有你，我什么也不是
Take the plan, spin it sideways
想法不断在脑海盘旋
Without you, I’m nothing at all
没有你，我根本什么也不是

---

#深搜和剪枝

A-迷宫问题：

定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output
左上角到右下角的最短路径，格式如样例所示。

Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

---

//
// Created by 沈宁 on 2020/7/13.
//

#include<stdio.h>
#include <iostream>
using namespace std;
struct node{
    int x;
    int y;
    int pre;
    //前一个点
};
int book[6][6];
//不能重复
int map[6][6];
//记录图
struct node queue[20];
//存储路径的队列
void print(struct node a)
//实现路径输出的函数
{
    if(a.pre==-1)//第一个点
    {
        printf("(%d, %d)\n",a.x,a.y);
        //  return ;
    }
    else
    {
        print(queue[a.pre]);
        //一直套娃上去，就能实现从先往后！！
        printf("(%d, %d)\n",a.x,a.y);
    }
}
int main()
{
    int i,j;
    int head,tail;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
    head=0;
    tail=0;
    queue[tail].x=0;
    queue[tail].y=0;
    queue[tail].pre=-1;
    book[0][0]=1;
    //出发点配置
    tail++;
    while(head<tail)
        //当队列为空时跳出，说明搜索没有找到可行路径
    {
        int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //定义出四个方向
        int flag=0;
        for(i=0;i<4;i++)  //从当前点往四周探索
        {
            int nextx=queue[head].x+next[i][0];
            int nexty=queue[head].y+next[i][1]; //实现移动
            if(nextx<0||nextx>5||nexty<0||nexty>5) 
            //超出了边界则跳出
            {
                continue;
            }
            if(book[nextx][nexty]==0&&map[nextx][nexty]==0) 
            //当点未被访问过且是可行点才入队
            {
                book[nextx][nexty]=1;//访问
                queue[tail].x=nextx;
                queue[tail].y=nexty;
                //加入队列
                queue[tail].pre=head;
                tail++;
            }
            if(nextx==4&&nexty==4)
                //到达了目的地
            {
                flag=1;
                break;
            }
        }
        if(flag) //到达目的地后调用函数输出路径
        {
            print(queue[tail-1]);
            break;
        }
        head++; //出队
    }
    return 0;
}

输出路径坐标时有先出后入特质，于是想到queue；
实现向四周探索的dfs;

int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //定义出四个方向
int flag=0;
for(i=0;i<4;i++) //从当前点往四周探索
{
int nextx=queue[head].x+next[i][0];
int nexty=queue[head].y+next[i][1]; //实现移动

入队条件：未被访问过且可以到达；
总体来说思路是倒序枚举+剪枝搜索；

---

B-生日蛋糕

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）

Input
有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

Output
仅一行，是一个正整数S（若无解则S = 0）。

Sample Input
100
2

Sample Output
68

Hint
圆柱公式
体积V = πR2H
侧面积A’ = 2πRH
底面积A = πR2

---

#include <iostream>
using namespace std;
int V (int r,int h) {
    return(r*r*h);
}
int S(int r,int h){
    return(2*r*h);
}
int ans = 0;
int N, M;
void dfs( int m, int left_V, int A, int last_R, int last_H)
{
    if( m*V(last_R -1,last_H-1) < left_V && m!=M) return;
    //剪枝1：剩余体积大于最大体积
    if( left_V < 0) return;
    //剪枝2：剩余体积小于0
    //1、2：总之体积要刚刚好
    if(  A > ans&&ans) return;
    // 当前面积比最小大剪枝
    if( !m) {
        if( !left_V ) ans = A;
        return;
    }

    for( int r = last_R - 1; r >= m; r--)
        for( int h = last_H - 1; h >= m; h--){
            int curV = V(r,h);
            int curA = S(r,h);
            if( m == M) curA+=r*r;
            dfs( m-1, left_V - curV, A+curA, r, h);
        }
}


int main()
{
    cin >> N >> M;
    ans = 0;
    dfs( M, N, 0, 100, 1000);
    cout << ans << endl;
}

定义剩余体积的概念，搜索递归时使用。

dfs( m-1, left_V - curV, A+curA, r, h);

两个剪枝定义了体积不能过大或者过小
第三个剪枝保证了Smin

---

D-N皇后问题

我要吐血！！！失败了5次！！！
不过在全局变量上没栽过怎么好意思叫自己程序员！

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input
1
8
5
0

Sample Output
1
92
10

//
// Created by 沈宁 on 2020/7/13.
//

#include <algorithm>
#include <stdio.h>
#include <iostream>

int cnt[11];
int ans = 0;
int N;
int book[15];
int a[15];
using namespace std;

void dfs(int n) {
    bool flag;

    if (n == N) {
        ans++;
        //这是最后一个皇后放置也成功了
        return;

    }
    for (int i = 0; i < N; i++) {
        book[n] = i;
        //放在第N行第i列
        flag = 1;

        for (int j = 0; j < n; j++) {
            if (book[j] == i || (abs(n - j) == abs(book[j] - i))) {
                flag = 0;
                break;
            }
        }
        if (flag)
            dfs(n + 1);
    }

}

int main(){



    for( N=1;N<11;N++) {
        ans = 0;
        dfs(0);
        a[N]=ans;

    }
    while(cin>>N){
        if(N!=0)
            cout<<a[N]<<endl;
        if(N==0) break;
    }




}

通过这个剪枝筛选出斜对角的

(book[j] == i || (abs(n - j) == abs(book[j] - i)))

数组下标是行，数组存储值是列
当进行到n==N 时最后一个才放置完毕，此时算一个方案

if (n == N) {
ans++;
//这是最后一个皇后放置也成功了
return; }

最后时间限制记得打表

int main(){
for( N=1;N<11;N++) {
ans = 0;
dfs(0);
a[N]=ans;
}
while(cin>>N){
if(N!=0)
cout<<a[N]<<endl;
if(N==0) break;
}

问题总结：
我的问题出在全局变量定义上。
首先数组book应该是全局变量！
其次在main函数中不能对全局变量N进行重定义！
因此下午要特别看一下全局变量的定义。

---

关于全局变量：

定义在函数内部的变量称为局部变量，它的作用域仅限于函数内部， 离开该函数后就是无效的，再使用就会报错。

1. 在 main 函数中定义的变量也是局部变量，只能在 main 函数中使用；同时，main 函数中也不能使用其它函数中定义的变量。main 函数也是一个函数，与其它函数地位平等。
2. 形参变量、在函数体内定义的变量都是局部变量。实参给形参传值的过程也就是给局部变量赋值的过程。
3. 可以在不同的函数中使用相同的变量名，它们表示不同的数据，分配不同的内存，互不干扰，也不会发生混淆。
4. 在语句块中也可定义变量，它的作用域只限于当前语句块。

在所有函数外部定义的变量称为全局变量，它的作用域默认是整个程序，也就是所有的源文件，包括 .c 和 .h 文件。

#include <stdio.h>

int n = 10;  //全局变量

void func1(){
    int n = 20;  //局部变量
    printf("func1 n: %d\n", n);
}

void func2(int n){
    printf("func2 n: %d\n", n);
}

void func3(){
    printf("func3 n: %d\n", n);
}

int main(){
    int n = 30;  //局部变量
    func1();
    func2(n);
    func3();
    //代码块由{}包围
    {
        int n = 40;  //局部变量
        printf("block n: %d\n", n);
    }
    printf("main n: %d\n", n);

    return 0;
}

• 代码中虽然定义了多个同名变量 n，但它们的作用域不同，在内存中的位置（地址）也不同，所以是相互独立的变量，互不影响，不会产生重复定义错误。

• 对于 func1()，输出结果为 20，显然使用的是函数内部的 n，而不是外部的 n；func2() 也是相同的情况。func3() 输出 10，使用的是全局变量，因为在 func3() 函数中不存在局部变量 n，所以编译器只能到函数外部，也就是全局作用域中去寻找变量 n。

• 当全局变量和局部变量同名时，在局部范围内全局变量被“屏蔽”，不再起作用。或者说，变量的使用遵循就近原则，如果在当前作用域中存在同名变量，就不会向更大的作用域中去寻找变量。

• 由{ }包围的代码块也拥有独立的作用域，printf() 使用它自己内部的变量 n，输出 40。

• C语言规定只能从小的作用域向大的作用域中去寻找变量，而不能反过来，使用更小的作用域中的变量对于 main() 函数，即使代码块中的 n 离输出语句更近，但它仍然会使用 main() 函数开头定义的 n，所以输出结果是 30。

---

JS的学习

原来JavaScript是为了营销便利才碰瓷java的（这太好笑了
专为与网页交互而设计的客户端脚本语言。

最初是为了实现表单验证

• 用户交互（表单验证）
• 网页特效（悬浮的广告）
• 用户记住账号密码
• 网页游戏（围住神经猫）

---

JS组成：

1. ECMAScript
2. BOM 整个浏览器
3. DOM document 文档 整个文档（自<html>起至</html>终）

---

JS语法

所有代码要写在<script>``</script>标签里

1. type="text/javascript"说明当前标签中文本类型
2. 终于在前端看到要加分号的代码了。
3. 与HTML语言运行前后看代码写入顺序。
4. 为了规范，一般来说JS代码写在head标签里
5. 可以引入多个<script>，顺序执行。
6. JS代码可以外部引入<script type="text/javascript" src="XX.js">
7. 如果外部引入了！！这个标签内就不能再写代码了！！！
8. 如何输出script标签，用&lt/&gt代替</>。

<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>document</title>
	
			<script type="text/javascript">
				alert("HELLO WORLD!");
				//页面弹出警告框“hello world”
				document.write("Hello world"+"<br/>");
				//当前页面直接输出
				//+</br>实现换行
			</script>
			<script type="text/javascript" src="demo.js">
			//引入外部文件
					//如果引入了外部文件src，在这个标签内就不能写代码！！！
				</script>
				<script type="text/javascript">
					document.write("&ltscript&gt");
				</script>
				
	</head>
	<body>
	</body>
</html>

---

常量与变量

1. JS中数据分为基本数据类型``复合数据类型两类
2. 前者：数字number/字符串string（单双引号）/布尔bool/特殊null与undefined
3. 变量：
   第一步需要声明变量，通过关键词var;//var age=18;
   变量名规律：美元符号字母数字下划线组成/不能数字开头/区分大小写；
   输入当前变量/常量的数据类型：
   【格式】typeof 变量/常量；
   【注】JS是弱语言：变量如何被赋值为什么就是什么类型
   不要在后续代码中改变数据类型，容易引起代码歧义。

JavaScript 拥有动态类型。
这意味着相同变量可用作不同类型：

实例

var x; // 现在 x 是 undefined
var x = 7; // 现在 x 是数值
var x = “Bill”; // 现在 x 是字符串值

---

运算符

1. 如何类型的数据和字符串做处理都会被转化为字符串数据再进行操作，此时‘+’为字符串拼接。

---

<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>Document</title>
		<script type="text/javascript>
		/*
		转化为字符串的优先级最高，此时‘+’为字符串拼接。
		*/
		var tmp1="我是"+"欧阳小百合";
		var tmp2="1"+1;
		var tmp3="true"+true;
		var tmp4="undefined"+;undefined；
		 //document.write(tmp1);————我是欧阳小百合
		 //document.write(tmp2);——————11
		 //document.write(tmp3);——————truetrue
		 //document.write(tmp4);——————undefinedundefined
		</script>
		
	</head>
	<body>
	</body>
</html>

---

<!DOCTYPE html>
<html>
<body>

<h1>JavaScript 变量</h1>

<p>相加 "8" + 3 + 5 的结果是：</p>

<p id="demo"></p>

<script>
x = "8" + 3 + 5;
document.getElementById("demo").innerHTML = x;
</script>

</body>
</html>

输出：835
字符串后面加的都被改成了字符串。

---

<!DOCTYPE html>
<html>
<body>

<h1>JavaScript 变量</h1>

<p>相加 3 + 5 + "8" 的结果是：</p>

<p id="demo"></p>

<script>
var x = 3 + 5 + "8"
document.getElementById("demo").innerHTML = x;
</script>

</body>
</html>

输出：88

字符串前面的保持了原有性质，直到加至字符串。

---

JS的输出

JavaScript 显示方案
JavaScript 能够以不同方式“显示”数据：

• 使用innerHTML 写入 HTML 元素

<!DOCTYPE html>
<html>
<body>

<h2>我的第一张网页</h2>
<p>我的第一个段落。</p>

<p id="demo"></p>

<script>
document.getElementById("demo").innerHTML = 5 + 6;
</script>

</body>
</html>

JavaScript 可使用 document.getElementById(id) 方法如需访问 HTML 元素。id 属性定义HTML 元素。innerHTML 属性定义HTML 内容。

实例

document.getElementById(“demo”).innerHTML = 5 + 6;

更改 HTML 元素的 innerHTML 属性是HTML 中显示数据常用方法。

---

• 使用 document.write()写入 HTML 输出

<!DOCTYPE html>
<html>
<body>

<h1>我的第一张网页</h1>

<p>我的第一个段落</p>

<script>
document.write(5 + 6);
</script>

</body>
</html> 

在 HTML 文档完全加载后使用document.write() 将删除所有已有的 HTML所以document.write() 方法仅用于测试。

实例：

<!DOCTYPE html>
<html>
<body>

<h1>我的第一张网页</h1>

<p>我的第一个段落</p>

<button onclick="document.write(5 + 6)">试一试</button>

</body>
</html>

点击前：

点击后：

---

• 使用window.alert()写入警告框

<!DOCTYPE html>
<html>
<body>

<h1>我的第一张网页</h1>

<p>我的第一个段落</p>

<script>
window.alert(5 + 6);
</script>

</body>
</html> 

• 使用console.log()写入浏览器控制台

---

JS 关键词

---

JS比较运算符

---

JS算数运算符

---

JS数据类型

JavaScript 变量能够保存多种数据类型：
数值、字符串值、数组、对象等等：

var length = 7; // 数字
var lastName = “Gates”; // 字符串
var cars = [“Porsche”, “Volvo”, “BMW”]; // 数组
var x = {firstName:“Bill”, lastName:“Gates”}; // 对象

• typeof 运算符
  typeof 运算符返回变量或表达式的类型：
  对数组返回 “object”，因为在 JavaScript 中数组属于对象。

typeof ""                  // 返回 "string"
typeof "Bill"              // 返回 "string"
typeof "Bill Gates"          // 返回 "string"
typeof 0                   // 返回 "number"
typeof 314                 // 返回 "number"
typeof 3.14                // 返回 "number"
typeof (7)                 // 返回 "number"
typeof (7 + 8)             // 返回 "number"

对于复杂数据
typeof 运算符可返回function或者object。
typeof 运算符把对象、数组或 null 返回 object。
typeof 运算符不会把函数返回 object。

• 关于undefined：
  任何变量均可通过设置值为 undefined 进行清空。其类型也将是 undefined。
  Undefined 与 null 的值相等，但类型不相等：

typeof undefined // undefined
typeof null // object
null === undefined // false
null == undefined // true

---

JavaScript 对象

JavaScript 对象用花括号来书写。

var person = {firstName:“Bill”, lastName:“Gates”, age:62, eyeColor:“blue”};

对象属性是 name:value的对子，由逗号分隔。
上例中的对象（person）有四个属性：firstName、lastName、age 以及 eyeColor。

var person = {
  firstName: "Bill",
  lastName : "Gates",
  id       : 678,
  fullName : function() {
    return this.firstName + " " + this.lastName;
  }
};

this 关键词:
在函数定义中，this 引用该函数的“拥有者”。
在上面的例子中，this 指的是“拥有” fullName 函数的 person 对象。
换言之，this.firstName 的意思是 this对象的firstName属性。

return this.firstName + " " + this.lastName;
this 是什么？
JavaScript this 关键词指的是它所属的对象。

this拥有不同的值，具体取决于它的使用位置：

• 在方法中，this 指的是所有者对象。
  
• 单独的情况下，this 指的是全局对象。
  
  
• 在函数中，this 指的是全局对象。
• 在函数中，严格模式下，this 是 undefined。
  
• 在事件中，this 指的是接收事件的元素。
  
• 像 call() 和 apply()这样的方法可以将 this 引用到任何对象。
  

JS事件

• 显示时间：

<buttononclick='document.getElementById("demo").innerHTML=Date()'>现在的时间是？</button>

<button onclick="this.innerHTML=Date()">现在的时间是？</button>

<button onclick="displayDate()">现在的时间是？</button>

事件	描述
onchange	HTML元素已被改变
onclick	用户点击了HTML元素
onmouseover	用户把鼠标移动到HTML元素上
onmouseout	用户把鼠标移开HTML元素
onkeydown	用户按下键盘按键
onload	浏览器完成页面加载

这张表格是自己写的，果然自己打还是不一样的。
——————————截止JS字符串————————————
明天进行到表单。

晚上进行Unity以及挑战程序设计学习的笔记。

本文地址：https://blog.csdn.net/weixin_45849398/article/details/107332068