# A short break during the application season

While it comes, the application seasion, full of tension, sadness and happiness. At this time, just after finsihing submitting all UC applications, I decided to join this competiton held in Foshan, Guangdong, which is a prosperous city around the Guangzhou. It is a short break for me, for I have some time to reflect the early application season including EA and UC and better think how could I improve in the future. Also, I haven’t taken any VEX competition for almost a year due to the COVID. It is the best time for me to catch up with this brand new season and implement my new-learned knowledge in real match.

# Geography Final Exam

Do you think Donald Trump will win the presidential election with Biden (Democratic candidate) in November 2020? Why?

# History Final Exam

2020年，发生了很多事件。我一直在思考，真的是2020年的大事件比2019，2018多出很多吗？因为今年所发生的无论是国内、国际、政治、经济、文化、历史遗留等等重大事件，从我个人的观感来说，比往年都要多出一个数量级的感觉。究竟是疫情导致了这些事件，还是因为人们在疫情期间更加有精力和时间去挖掘信息，我一直在思考。历史告诉我们，事情具有两面性，不具有绝对性。一部分事件，是因为疫情爆发给人们心理上带来的压力所导致的；而另一部分事件，则是必然会发生的，无论是否有疫情的刺激。

# Chinese Final Exam

“老师好，我叫李昊锦，在西安高新第一中学国际班就读，我喜欢计算机，我是……”，他像是背顺口溜一样，一个绊子都没有，非常流利地在母亲和老师面前做了自我介绍。与其说是他在说话，不如说他的嘴巴在发声。这一番话他不知讲了多少遍，在多少个局促的教室里，对着多少初次见面的老师，当然还有每次都陪着的他的母亲，不，他陪着的母亲。他明白自己不能惹母亲生气，每一次都极不情愿地答应与母亲去各种中介办公室交流谈话，而母亲每次都会说这是最后一次，以后他都不用去了。像极了小时候父母哄孩子喝苦涩的中药，但最终都是为了孩子好。

# The Honest Theif

• meet the theif in the bar, offer him a drink
• drink all night
• move to the new house
• sell his breeches, lost
• fight
• go away
• come back

# 05/31/20

## Summary

Today we officially began our new season robotics development. To be honest, I have less time available this season due to my SAT and TOEFL exam and college application stuff. However, I want to insist on this activity which I’ve already participated since my middle school. My job will gravitate mainly on programming.

Plus, we move to a brand new activity room with double area and completely new equipment and match field. Hope I can achieve some accomplishments that I left as pities last season.

So sad that today I am alone in my team. They are all busy preparing AP makeup exams, although I also need to retake.

• Get started and familiar with code formatting and competition template again.
• Recode and design my code format and template.
• Finish the entire base program with optimization

# Student Based Online Community

## Background: Under the Epidemic

According to Wikipedia, 2019 (COVID-19) is an infectious disease caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). The disease was first identified in December 2019 in Wuhan, the capital of China’s Hubei province, and has since spread globally, resulting in the ongoing 2019–20 coronavirus pandemic.

# Why I chose this book to read

I get an inexplicable feeling about my life recently and books help me a lot in most cases. I browsed the online bookstore on my kindle and chose the one with highest evaluation.

# My real feeling about the book

To be honest, it’s not surprise for me. I thought I would suddenly realize something after reading but I didn’t. Closing my eyes, I got the same picture over and over again: the author Tara was shocked by the fact of world and was bullied by her family. It told me almost the whole life that Tara has been going through, but I didn’t get it. I was not moved after all.

I try to connect plots in the book with my real life or experience but I failed. I cannot have a resonance with the author since I never had a family background like her. Maybe I take all granted or maybe I should read again when I go to college, go to work and gain more thoughts about it.

# Educated

The name of the book is Educated, so let’s talk about its meaning. I believe it’s a suitable name for the book. Tara uses her own experience revealing us the path her grown up under different educations. Education means learning different opinions, views, perspectives of an object or event and have the ability to accept and tolerate it.

# 基础的神经单元

$x_i$ 输入的n维度的向量
$w_i$ 加权的系数
$b$ 偏置
$z$ $\Sigma_{i=1}^{n} w_ix_i+b$ 的值
$h(z)$ 经过激活函数得到的一个范围在0-1之间的数
$a$ 作为输入向量x传给下一个神经元

# — 空 —

​ 这个春节对于每个国人来说，都是一个不一样的春节。各大旅游景点空了，货架上的口罩品类空了，正月的拜年日程空了，城市空了，人心却没有空。全世界都在为武汉加油，为中国加油。

# — 数字 —

​ 2月4日0—24时，31个省（自治区、直辖市）和新疆生产建设兵团报告新增确诊病例3887例（湖北省3156例），新增重症病例431例（湖北省377例），新增死亡病例65例（湖北省65例），新增治愈出院病例262例（湖北省125例），新增疑似病例3971例（湖北省1957例）。
截至2月4日24时，国家卫生健康委收到31个省（自治区、直辖市）和新疆生产建设兵团累计报告确诊病例24324例（海南省核减1例），现有重症病例3219例，累计死亡病例490例，累计治愈出院病例892例（海南省、湖北省各核减1例），现有疑似病例23260例。
目前累计追踪到密切接触者252154人，当日解除医学观察18457人，现有185555人正在接受医学观察。
累计收到港澳台地区通报确诊病例39例：香港特别行政区18例（死亡1例），澳门特别行政区10例，台湾地区11例。
——援引自国家卫生健康委员会官方网站

​ 24小时实时更新的数字背后，是对患病者的祈祷，是对康复者的祝福，是对离世者的哀悼，更是对无私奉献的医护人员和支援企业及个人的敬礼。

# 2019-nCoV Data Prediction

2019 Novel Coronavirus (2019-nCoV) is a virus (more specifically, a coronavirus identified as the cause of an outbreak of respiratory illness first detected in Wuhan, China. Early on, many of the patients in the outbreak in Wuhan, China reportedly had some link to a large seafood and animal market, suggesting animal-to-person spread. However, a growing number of patients reportedly have not had exposure to animal markets, indicating person-to-person spread is occurring. At this time, it’s unclear how easily or sustainably this virus is spreading between people. The latest situation summary updates are available on CDC’s web page 2019 Novel Coronavirus, Wuhan, China

As everyone knows, the serious coronavirus is attacking our country especially in Wuhan while most activities are canceled. Staying at home become the daily routine. Besides working on learning stuff, I am trying to learn Python, a popular programming language which I should master long before.

After learning Matrix Linear Regression, an powerful and beginner-friendly algorithm used for predicting, I got an idea: forecasting the future trend by using a series of data including the number of people infected with virus. So I just started to do it and it’s time to share my computing results.

# 人工智能第二讲

## 矩阵形式的线性回归

x_11表示第一个样本的第一个值

T: 转制， 横竖向量转换

# Getting started with Python 2

## Pass

There cannot exist any blank within for and if else. We must use pass to avoid the mistake.

# 人工智能第一讲

## 分类

• 需要人工标记
• 预测、推荐、标注、识别等
• 回归
• 分类

### 无监督学习

• 聚类
• 社团划分
• 生成学习
• 强化学习： 根据结果回馈优化模型

## 线性回归

• hyperparameter

# What’s new for me

• Do not need to declare variables
• indentation replaces curly braces to divide code blocks

# ACSL STRING

## My thought

Nothing… The problem is pretty easy, however it troubled me for a quite long time. Just follow the instruction of the problem and simulate the whole process by coding.

## Points to note

• The conversion between String and int
• How to handle carry
• Pay attention to the additional sign
• Sometimes we can use char to simplify the process

# My first VEX tournament of the season

Now I am on the bullet train from Xi’an to Baoding, crossing one tunnel after another, passing one bridge after another. Just a few minutes ago, I was sleeping deeply, but now I think I am conscious.

## Sleepless night

From the beginning of the summer vacation, I was studying TOEFL everyday following a regular routine – getting up at 7AM, doing TOEFL practice all the day and then going to bed at 11PM.

However, Last night even didn’t close my eyes for a while because of the unfinished autonomous program. It’s a hard and harsh work putting tons of parameters and variables to my mind simultaneously. Fortunately, with my team members Tony and Jessica helping me reset the match field quickly and accurately, finally I got it. Never forget the colorful cubes leaps on the match field which seem to lose control.

## Nervous time

To be honest, I didn’t put too many efforts in the VEX competition these summer vacation. I just came to participate in training two days before our setting off. I am really awkward to my excellent team member and coach Mr. Han.

The robot that will be used in the competition hadn’t been finished two days before. Our manipulator Tony hadn’t practice controlling the robot like catching the cube and pile them up in the specific area which is not easy and definitely needs time to be familiar with the way of controlling.

Luckily, we had done everything in time under the unity of our team which is the most valuable and precious thing I got from the robot club. I saw everyone mounting screw carefully, writing engineer log amazingly… There exists many good personalities and characters that I need to learn from them.

# Our fantastic bridge -- Bridgination

So, it’s time to prepare for the final exam and enjoy the only moment we have in fundation period. In addition, it’s time for me to do some review.

## One of the colorful activities

May is the month of all kinds of colorful activities in my school. I participated in the bridge building competition which I was really reluctant to at first.

it’s our bridge: “Bridgination”, the name is given by myself！

## Hard and harsh

It was really a hard and harsh time for me to build a beautiful and strong bridge because I had no idea about any stuff about the bridge. What’s more, I have a team that I didn’t appreciate previously. Maybe I just wanted to do it with the mentality of playing.
What kind of bridge, how to build the pillar, how to connect all the parts united? I didn’t know how to deal with these massive problems. We just went forward step by step, mistake by mistake.
My teammate, Skywing (a frightening name right?), who is talented in building arches for the bridge, tried to make tons of archs used for his bow and arrow instead of being a part of our bridge. I didnot know how to persuade him at all. But luckily, he finally finshed the arch customed only for our bridge.

## Presentation

Maybe it’s a pretty sucessful presentation? I don’t know. However, it’s my first time to stand in the face of all the students from fundation class. I weared a suit because I think it’s a very formal occasion to show my respect. I was told I only had 5 minutes to present which truly makes me nervous and anxious.

At the moment standing on the stage, I saw the expecting eyes from the audience clearly. Speaking aloud with the gesture of my hand, it’s the only thing I remember. Everything including additional preparation was all forgotten behind my head.

When I finished, I heard applause one after another. I was excited and proud of my teammates and myself.

My team

## Result

We won the Design Award and Aesthetic Award finally. It really surprised my teammates and me.

## Something I learn from it

### Team spirit

We are like a loose sand at first but after the hone, we all have grown up in several aspects. I am very thankful to my teammates Skywing, Wooken and Sydeny.

### Making some friends

During the process, I was helped by many people including my classmates who was not in our team, the students from other class, the foreign teacher, the physics teacher…

# New challenge

I’ve never imagine that one day I can stand on a debate stage and speak in English. My classmate Vivian who is good at English and speaks fluently invited me to participate in a debate competition because of vacancy of her partner. Thinking that the students who are good at oral English are all in the debate club, I accept the invitation at once.

Think now, I am thankful for Vivian to give me a chance to face new challenge. We should finish our debate draft early but it lasted until three days before the official competition.

Just coming back from the VEX worlds, I was excited and felt still live in the life there. Exactly, the debate competition came. Vivian and I prepared for the debate on the whole Monday night. Both of us are students living, but we used phones and computer secretly just like thief, preventing from discovering by the teacher.

My assignment was the draft of PROS. The debate topic was about refugees. I strangled my brain to write down everything I could think about. It was hard but expanded my thinking a lot.

# A normal night

The last night before the debate competition. I got the suit and tried on in my dormitory. My dormmate helped me to adjust the tie. There exist a second, I felt very lucky to be classmates and friends with them.

I intended to review the debate draft at night, but I fell asleep quickly and unconsciously.

5:50 AM, the teacher woke me up. I got up quickly without any sleepy. To my surprise, my dormmate encouraged me and hoped me to get a good rank, even he was sleeping on the bed well.

# Exciting day

We had 4 rounds on the first day. Every time we were PROS unexpectedly. I really enjoyed the feeling and atmosphere when two sides were debating. Just like a spark collision of thinking. We even beat the Nanjing Foreign Language School because of the excellent cooperation of Vivian and me.

On the afternoon, when all the rounds ended. I heard my name from the host. We entered the top eight!

# On the bus

Because we were PROS in all four rounds, I thought we were familiar with the strategy and pace of PROS. Then, I suggested Vivian being PROS tomorrow if it was possible. But it was the divergence of us. She had finished the CONS draft but it didn’t work at all. She want to be the CONS tomorrow. I requested her on the whole way back to the school.

Finally, I gave up. I realized that I was a little impolite to treat a girl in this way. Everybody need to practice and exercise in the competition. I apologized to her and then prepare for the next day.

# Unexpected results

We are the last of the quarter-finals, which means that the first day of our first knockout opponent is the first place. We were hopeless but tried our best to compete for the top four. After the competition, we felt that we were certainly lose the game. But to our surprise, we won the game!!!

Both of Vivian and I was too excited because we defeated the group first. At that moment, I felt like my heart is jumping out!

But we lost the semifinal at last. However, we were still very happy because it’s a very perfect ranking.

# Think more deeply

First, I have made many friends through the competition. They are from Beijing, Shanghai, Shenzhen, which are more advanced than Xi’an. There are many things I can consult and learn form them. Also, I find all the competition whatever the field is, robot, computer, debate, the true meaning is meet more friends and expand my horizons.

Second, I understand and cherish my old friends more. After a competition, a few days staying together, we all made progress and became a better me. The old friends, the partners, they are different for me. We learned from each other and communicate more effectively.

# At last

At last, I want to say that thanks to Vivian, I learned a lot from her. Not only about the skills of debating, but also the truth of life.

# HIT REFRESH

There are tremendous things to say, but I deem that I don’t have enough time.

Firstly, I made a decision that maybe the first I made by myself. It’s also why I use English. I have transferred to international class. I want to go abroad.

There are many reasons cause this decision. I think the major one is that I went to Seattle, US in winter vacation. I really prefer the atmosphere there and I got a feeling of unrestrained. And now the life here is fantastic. I can talk to foreign teacher freely and meet a group of friendly classmates and teachers.

I live in the dorm. It’s unprecedented for me to sleep on time and get up on time. Every day I feel energetic and optimism.

Just like return to the primary school life. I really enjoy it. Also, it has a lot of challenges. I face to TOEFL test and many other tests.

That’s all.

By the way, I will go to Chicago in April. Hope everything will be OK!

# 线性回归补充

1. 线性回归可以对样本是非线性的，只要对参数线性

$y=\theta_0+\theta_1x+\theta_2x^2$

1. 局部加权回归

1. 把字用向量表示

2. 卷积操作

3. RNN表示

4. 平均 pool

5. 全连接

6. sigmoid

# 济南Day3 坐标型动态规划及背包

## 花店橱窗布置

### 思路

• f[i][j]f[i][j]表示前i个花瓶前j个花束的最大美学价值
• f[i][j]=max(f[i−1][k],f[i][j])f[i][j]=max(f[i−1][k],f[i][j])

• 整张表都是向右下方走的，向下走加上数值，向右走无影响
• 如果向下走代表花束放入花瓶，向右走无影响代表不放入

## 矩阵取数

### 思路

• 因为每次取头和尾，所以一定是一个连续的区间
• f[i][j]f[i][j]表示从i取到j的最大得分
• $f[i][j]=max(f[i][j-1]+a[j]*2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]*2^(i-1+n-j+1+1))$
• 指数是轮数，当前数前面有多少个数被取走，就有多少轮，注意一下1的问题

## 传纸条

### 思路

• f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)

• 一共有四种情况，上上，左左，上左，左上

• 保证两条路径不相交if(j1==j2 && i1==i2) continue

• f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])

• 步数为i+j−1i+j−1

• 判断不合法的状态

• 当m,n<100m,n<100时，四维数组开不下了，因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的，并且三个数都确定时，我们可以直接算出j2j2,直接变成了三维

## 免费馅饼

### 思路

• f[i][j]f[i][j]表示第i秒到达第j个格子的最大得分
• 该状态是从哪里转移过来的呢？ 他可以从5个地方转移过来（没有到边界的时候）
• 运动具有相对性，我们可以把该问题类比成数字三角形，相当于馅饼不动，人每次向上移动一个单位
• f[i][j]=ff[i][j]=f

## 三角蛋糕

### 思路

• 像数字三角形一样压缩成正三角形
• f[i][j]=min(f[i+1][j],f[i+1][j+1])+1f[i][j]=min(f[i+1][j],f[i+1][j+1])+1

## 金明的预算方案

### 思路：分组背包

• f[i][j]f[i][j]表示前i组物品重量不超过j的最大价值
• 一共5种转移方式
• f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5,五种情况已经重新配置的前提下

## 01/完全背包混合

• 根据物品的类型选择状态转移方程

## 二维限制的背包

• 把数组扩展成三维
• f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])

## 面包

### 思路

• 如果没有面包被压扁，就是一个完全背包问题
• 如果有大面包，肯定要放到最上面，使得压缩高度尽可能大
• 枚举最上面是哪一个大面包，然后其余所有面包的高度都变为原来的五分之四，就转化成了一半的完全背包问题

# 树形DP

## 二叉苹果树

• $dp[u][j表示节点u留下j条边的最大价值，每一次决策只有三种情况：剪左子树，剪右子树，两个都不剪 • 剪左边：dp[u][j]=dp[rson][j−1]+v[rson]dp[u][j]=dp[rson][j−1]+v[rson]，同理，剪右边：dp[u][j]=dp[lson][j−1]+v[lson]dp[u][j]=dp[lson][j−1]+v[lson] • 两边都不剪：dp[u][j]=dp[lson][j]+dp[rson][k−j−2]dp[u][j]=dp[lson][j]+dp[rson][k−j−2] ## 代码：记忆化搜索 ## 先修课 ### 题目 课的先修关系形成一棵树的结构，每门课有一门或者没有先修课。选M门课，能获得的最大学分是多少？ ### 思路 • dp[u][j]dp[u][j]以u为根的子树选j门课 • 把j-1门课分配给子树，就是一个背包？ • 然后我们用f[i][j]f[i][j]表示当前树中，前i棵子树选择j门课的最大学分。这样就能够通过f算出dp[i][j]dp[i][j],相当于树上DP套背包。对于每一个状态dp[i][j]dp[i][j]都需要用f算出学分分配的最佳方案 ## K-set ### 题目 在一棵树中选出最多的点，使得这些点中每个点最多与其他点连了k条边 ### 思路 • dp[u][0/1][0/1]dp[u][0/1][0/1]表示以u为父亲，取/不取父亲,取/不取自己的最大值 • dp[u][0][0]dp[u][0][0]：自己和父亲都不取，u的儿子随便取。$f[u][0][0]=size∑i=1max( dp(vi,0,0) , dp(vi,0,1) )f[u][0][0]=∑i=1sizemax( dp(vi,0,0) , dp(vi,0,1) )\$

• dp[u][1][0]dp[u][1][0]：父亲要取，u自己不取，u的儿子同样随便取。f[u][1][0]=f[u][0][0]f[u][1][0]=f[u][0][0]

• dp[u][1][1]dp[u][1][1]

：父亲要取，自己也要取，儿子取k-1条边。

• 这时我们就要考虑取哪几条边，也就是哪几个点。
• 对于任意一个u的儿子vivi,如果取这个点，那么它的贡献就是dp(vi,1,1)dp(vi,1,1)，如果不取这个点，那么它的贡献就是dp(vi,1,0)dp(vi,1,0)
• 因此这个点取或者不取，带来的贡献就是两种情况的差，所以我们只要按两种情况的差从大到小排序就好了。最后选取差值最大的k-1个点就OK了（前提是这k-1个点带来的贡献都是正的，如果有负贡献那么就取不满k-1个点）
• dp[u][0][1]dp[u][0][1]：父亲不取，自己要取，儿子取k条边

# 题意

4*4的棋盘，一共有三种属性：白棋，黑棋，空格（有且仅有两个），每一次可以移动一颗棋子，黑白棋交替进行，只能移到空格的地方。求达成四子连棋局面（横竖斜都算）所需的最小步数

# 分析

• 广搜，和八数码问题差不多，但是更繁琐了。
• 黑白棋交替进行，那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
• 广搜要搜两遍，分别是黑棋先走或白棋先走
• 每一次需要考虑两个空格，所以从两个当前点搜状态

# 遇到的坑

• 很多都是重复的代码，只要细心就好了，但有一个*最坑的……*

# STL

C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

# SET

## set的各成员函数列表

1. begin()–返回指向第一个元素的迭代器
2. clear()–清除所有元素
3. count()–返回某个值元素的个数
4. empty()–如果集合为空，返回true
5. end()–返回指向最后一个元素的迭代器
6. equal_range()–返回集合中与给定值相等的上下限的两个迭代器
7. erase()–删除集合中的元素
8. find()–返回一个指向被查找到元素的迭代器
9. get_allocator()–返回集合的分配器
10. insert()–在集合中插入元素
11. lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器
12. key_comp()–返回一个用于元素间值比较的函数
13. max_size()–返回集合能容纳的元素的最大限值
14. rbegin()–返回指向集合中最后一个元素的反向迭代器
15. rend()–返回指向集合中第一个元素的反向迭代器
16. size()–集合中元素的数目
17. swap()–交换两个集合变量
18. upper_bound()–返回大于某个值元素的迭代器
19. value_comp()–返回一个用于比较元素间的值的函数

# P1284三角形牧场

## 分析

• 首先看数据范围，边长最大为40*40/3，并且因为要使用所有的木棍，所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i，j的情况是否成立

• f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]，相当于01背包，就不解释了……

• 定义初始状态f[0][0]=1f[0][0]=1

• 三条边都知道了，如何求面积呢？这里我们需要用到海伦公式

S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c)，p=12(a+b+c)p=12(a+b+c)

# P1929 迷之阶梯

## 题意

1. 如果下一步阶梯的高度只比当前阶梯高 1，则可以直接登上。
2. 除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。
3. 当你连续退下 k 后，你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现 在位于第 j 步阶梯，并且是从第 j+k 步阶梯退下来的，那么你可以跳到高度不超过当前阶 梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

## 分析

• 定义状态为f[i]表示到第i个阶梯的最小步数
• 由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

## 遇到的坑

• if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大，所以是大于等于

# P1970 花匠

## 分析

• 第一次很容易就能想到转移方程：

但是这样做有一个很大的问题，无法确定最后一个状态的转移是否合法

然后我就想找到最后一个状态是从哪里转移过来的，最后再额外判断一遍。虽然有点不像动态规划，只要用last1last2两个变量储存倒数第二个和第三个留下的点，但还是WA了2个点。

原因好像是我丢掉了一些状态：我默认了只要这棵花能选就选，不满足无后效性

• ## 动态规划

正解：一维无法解决问题，那么就升一维。

定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

状态转移方程为

• ## 贪心

*为了方便我们设当前的花为A，下一盆花为B*

• 第一盆花肯定要选，如果不选的话第二盆就成了第一盆，花的总数就会减少，一定不会比选第一盆花更优
• 如果B比A还高，那么一定会选择B，因为落差的区间变大了，能够容纳的合法的花也变多了；同理，如果BA还小，那么一定会选择B
• 通过以上两个判断不停地找波峰和波谷，记录答案就可以了

# P1020 导弹拦截

*非常恶心的一道题，我已经被搞晕了*

## 分析

• 第一问就是求最长不上升子序列，想象有一个栈，如果当前数小于等于栈顶的数，则直接入栈；否则二分查找栈内第一个大于等于当前数的数并替换它，因为与当前数相等的数是有贡献的
• 第二问就是求最长上升子序列，我不会证明，只能大概的胡诌，因为相当于我只关心子序列的长度，而只要有一个高度大于当前长度，就必须去新建一个序列，有点类似于木桶原理……

## 遇到的坑

• 最长不下降子序列 等价于 倒序的最长不上升子序列
• 最长下降子序列 等价于 倒序的最长上升子序列
• lower_bound 二分查找第一个大于等于基准数的数（涵盖的范围更广）
• upper_bound 二分查找第一个大于基准数的数

# P1103 书本整理

*很有感触的一道题*

## 分析

• 可以抽象为：给定一串数列，首先对数列进行排序然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小，输出最小的和，即最小不整齐度。好拗口

• f[i][j]表示长度为j的数列，数列最后一个的位置标号为j

• 假设当前状态数列长度为j，现在以第i位为数列的最后一个，即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留，所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时，数列最后一个保留的数到底是多少，由此我们可以计算出应该增加的不整齐度

• 转移方程：

• 接下来考虑边界问题

• j<=i 序列里的数肯定不会超过所有当前的数
• t>=j-1 由上式同理可以得出，状态中的第一维度肯定大于等于第二维度
• t<i 数列里的最后一个数肯定不可能达到现在及以后的数
• j<=n-K 由题意可得……

分析最清晰的一回

## 遇到的坑

• f[n][n-k]并不是最终答案！！！只要状态里最后一个位置编号大于n-K，并且序列里有n-K个数，就有可能成为答案，所以我们要扫一遍找到最终答案
• 赋初值！！！ 因为我们状态转移选择的是最小值，最开始所有状态都是0，无论怎么转移都是0。所以我们把所有初值赋值为无穷大？显然不可行。我们可以每当需要转移该状态时，在确定该状态一定会被改变的前提下提前赋值为无穷大****
• 真的都是很深很深的坑

3
1 1
1 2
2 2

1.0000

# 思路

• 首先考虑暴力，枚举所有点对，复杂度为O(N^2)

• 然后就是正解：

分治算法

• 每一次把平面分成两个部分，找出左边的最近点对，右边的最近点对以及穿越分割线的最近点对。
• 在求穿越分割线的最近点对时，用左右已经算出的最小值作为参考，一旦大于就停止搜索

# 装箱问题

​ 8 3 12 7 9 7

## 优化

• ### 01滚动

f[i][j]中每一次的状态转移只与上一行有关系，所以只需要一个2层的数组，可以用&1实现

• ### 就地滚动

每一次都会由左边的值转移到现在，所以每一次只要将循环从右往左就可以了

##方法1：动态规划

*i维度可以01滚动*

# 笔记

1. 确定状态
• 维度从低往高试
2. 确定转移方程
• 每一个状态的决策
• 初始值
• 边界问题
3. 是否可以降低维度或其他优化

# 乘积最大

1. 这个数与前面的数组成更大的数，需要枚举这个数的起点
2. 单独成为一个新数

*在算乘积的时候可以先算出前缀‘乘’*

# 2018/12/8模拟赛

## 连线游戏

### 题目

【题目描述】
Farmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。

【输入格式】

【输入样例】(lines.in):
4
-1 1
-2 0
0 0
1 1

【输出格式】

【输出样例】 (lines.out):
4

【输出说明】

### 思路

• 枚举两两构成直线的k值，如果k值不存在，则ans++

### 遇到的坑

• 考虑精度问题，考试的时候写了1e-5，结果炸了，改成1e-7就对了，甚至不加精度判断都能AC
• 特判分母为0的情况，本来以为Inf是无限大，所有Inf表示的都是一个意思，但实际炸了……
###AC代码

## 独木桥

### 题目

【问题描述】

【输入文件】

【输出文件】只有一行，输出两个整数，分别表示部队撤离独木桥的最小时间和最大时间。两个整数用一个空格分开。

【样例输入】
4
2
1 3

【样例输出】
2 4

【数据规模及约定】
N≤L≤1000

### 思路

两个人遇见并分别掉头两个人继续往前走是等价的，因为人与人之间不存在差异。

### 遇到的坑

• 最外一层都是max，满足木桶原理

# 汉诺塔问题

## 不妨假设：

• 当只有

1. 把盘子从A直接移到C
• 当只有

1. 将上面的盘子从A移动到B
2. 将下面的盘子从A移动到C
3. 将B上的盘子从B移动到C
• 当有

1. 将上面的盘子从A移动到C
2. 将中间的盘子从A移动到B
3. 将C上的盘子从C移动到B
4. 将下面的盘子从A移动到C
5. 将B上面的盘子从B移到A
6. 将B上的盘子从B移到C
7. 将A上的盘子从A移到C

## 思路

n-1个盘子移到B，再把最下面的盘子移到C，再把B上的n-1个盘子移到C

## 自己遇到的坑

• a,b,c三个柱子没有搞清楚，递归函数里到底四个参数分别代表什么要搞清楚

## 其他一些……

• f[n]=f[n-1]*2+1

本次的次数就等于把n-1个盘子移动了两回，加上剩下的最大的盘子移动的一次

# 滑动窗口

## 思路：单调队列

### 以求最小值为例

• 在读取每一个数 ai 的过程中，判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了，因为***它已经不可能成为现在及以后所有窗口内的最小值***，不妨弹出，重复以上操作，直到ai小于队尾的数，再把ai放到队尾
• 当现在的长度已经达到窗口的长度时，每一次都会输出最小值，因为队列是单调递减的，第一个数一定是现在窗口内最小的数，直接输出
• 在队尾添加的过程中，***要始终保证队列里的数都在窗口内***，当区间长度大于窗口长度时，要从队首弹出

## 自己遇到的坑

• ***队列内存储的是这个数的位置，不是这个数的大小***，大小通过数组类似映射表示

• *要考虑好整个过程的先后顺序*

1. 先确保队列内的数都在范围内
2. 把所有比ai小的队尾数依次弹出
3. ai入队
4. 如果达到滑动窗口范围，输出值
• *两个数的编号相减加1代表该闭区间的长度*

• 当算完最小值时队列不一定是空的，要先清空队列

## C++ STL 双端队列 deque

q.push_back: 从后端加入 q.pop_back: 从后端弹出

q.clear: 清空队列
q.size(): 读取队列的长度，但是好像类型不是int，只能用来判断数组是否为空