World Robot Contest Finals

World Robot Contest Finals

This article was revised on March 5

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.

image-20210305234436333

Read more
Geography Final Exam

Geography Final Exam

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

我记得很清楚,2016年11月6日,2016美国大选的那一天,正是我初二上学期期中考试的日子。考完试兴奋地跑回家,期待大选结果的揭晓。在我的记忆里,十分清晰地记着几乎所有民调,或者说自己从国内媒体所了解到的转述过的美国国内民调都表明希拉里会以压倒性的优势赢得大选。但最后结果表明,民调错了。

Read more
History Final Exam

History Final Exam

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

Read more
Chinese Final Exam

Chinese Final Exam

局促的咨询室里,有升学指导老师、母亲和他,还有从始至终都没有动过的三杯水。

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

Read more
English Class Review
VRC Change Up 2020-2021 Dev Log

VRC Change Up 2020-2021 Dev Log

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.

Task List

  • 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
Read more
News Report

News Report

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.

Read more
Educated -- Reading Journal

Educated -- Reading Journal

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.

Neural Network

Neural Network

基础的神经单元

mark

参数 功能
$x_i$ 输入的n维度的向量
$w_i$ 加权的系数
$b$ 偏置
$z$ $\Sigma_{i=1}^{n} w_ix_i+b$ 的值
$h(z)$ 经过激活函数得到的一个范围在0-1之间的数
$a$ 作为输入向量x传给下一个神经元
Read more
基于线性回归的传染趋势预测

基于线性回归的传染趋势预测

— 空 —

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

— 数字 —

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

Read more
2019-nCoV Data Prediction

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

from https://www.cdc.gov/coronavirus/2019-ncov/about/index.html

Lead

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.

Read more
Matrix Linear Regression
Getting started with Python 2

Getting started with Python 2

For and Else

1
2
3
4
for x in range(6):
print(x)
if x==2: break
else: print("over") # this line will skip if last line exists

Pass

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

1
2
3
for x in [1,2,3,4]:
pass
print("over")
Linear Regression

Linear Regression

人工智能第一讲

定义

基于已知的函数模型预测未知的

分类

监督学习

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

无监督学习

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

有监督模型

样本二元组:(x,y)

利用样本求解模型最佳参数

线性回归

image-20200127092012971

image-20200127093925978

  • hyperparameter

image-20200127102104560

Getting started with Python 1

Getting started with Python 1

What’s new for me


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

Grammar


Assigning value to multiple variables

1
x, y, z = 1, 2, "hello"

Define a global variable in local function

1
2
3
def myfunc():
global x
x = "fantastic"

Change the value of a global variable inside the function

1
2
3
4
x = "declan"
def myfunc():
global x
x = "declan and jessica"
Read more
ACSL Diff

ACSL Diff


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Scanner;

public class Diff {
static String s1,s2;
static String[] word1;
static String[] word2;

static void input() {
Scanner input = new Scanner(System.in);
s1 = input.nextLine();
s2 = input.nextLine();
int len1 = s1.length();
int len2 = s2.length();

// for(int i=0;i<word1.length;i++) System.out.println(word1[i]);
}

static String process(String A, String B)
{
String common="";
word1 = A.split(" ");
word2 = B.split(" ");
int len1 = word1.length;
int len2 = word2.length;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
int pos = word2[j].indexOf(word1[i]);
if(pos!=-1)
{
word2[j] = word2[j].substring(0,pos) + word2[j].substring(pos+word1[i].length());
common = common + word1[i];
break;
}
}
}
return common;
}

static String declan(String c1, String c2)
{
String ans="";
int len1 = c1.length();
for(int i=0;i<len1;i++)
{
String tmp = c1.substring(i, i+1);

int pos = c2.indexOf(tmp);
if(pos==-1) continue;
ans = ans + tmp;

c2 = c2.substring(pos+1);
}
return (ans=="")?("NONE"):(ans);
}

public static void main(String[] args)
{
for(int i=0;i<5;i++)
{
System.out.println("Please enter No."+(i+1)+" line of the input data:");
input();
String common1 = process(s1,s2);
String common2 = process(s2,s1);
System.out.println("The answer to No."+(i+1)+"line is:");
System.out.println(declan(common1,common2));
// System.out.println(common1);
// System.out.println(common2);
}
System.out.println("All output done...");
System.out.println("Thanks for your testing");

// return;
}
}
/*
The quick brown fox did jump over a log
The brown rabbit quickly did outjump the fox
How much wood would a woodchuck chuck if a woodchuck could
chuck wood He would chuck as much wood as a woodchuck could
I scream you scream we all scream for ice cream
He screams she screams they all scream for a creamery
A skunk sat on a stump and thunk the stump stunk
but the stump thunk the skunk stunk
I have got a date at a quarter to eight
I will see you at the gate so do not be late

abc defgh ijkl mnopq rstuv wxyz
ab cdefgh ijklmn opq rst uv w xy z
*/
Digital Reassembly

Digital Reassembly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
public class digitReassembly {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);

String s1 = input.next();
String s2 = input.next();

input.close();

int num = Integer.valueOf(s2);

while(s1.length()%num!=0)
{
s1 = s1 + "0";
}

int ans = 0;
int cnt = s1.length()/num;
int p = 0;
for(int i=0;i<cnt;i++)
{
ans += Integer.valueOf(s1.substring(p,p+num));
p = p+num;
}

System.out.println(ans);
}
}
ACSL CHMOD

ACSL CHMOD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.Scanner;

public class CHMOD
{
static String[] num = new String[4];
public static void input()
{
Scanner input = new Scanner(System.in);
String s = input.next();
int len = s.length();
int cnt = 0;
num[cnt++] = s.substring(0, 1);
for(int i=1;i<len;i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
num[cnt++] = Integer.toBinaryString(s.charAt(i)-'0');
}
}
input.close();
}

public static void process()
{
String[] ans = new String[]{"","","",""};
for(int i=1;i<4;i++)
{
while(num[i].length()<3) num[i] = '0' + num[i];
if(num[i].charAt(0) == '1') ans[i] += 'r'; else ans[i] += '-';
if(num[i].charAt(1) == '1') ans[i] += 'w'; else ans[i] += '-';
if(num[i].charAt(2) == '1') ans[i] += 'x'; else ans[i] += '-';
}

boolean flag1,flag2,flag3;
flag1 = flag2 = flag3 = false;

if(num[0].charAt(0)=='1' && ans[1].charAt(2)=='x') flag1 = true;
if(num[0].charAt(0)=='2' && ans[2].charAt(2)=='x') flag2 = true;
if(num[0].charAt(0)=='4' && ans[3].charAt(2)=='x') flag3 = true;

for(int i=1;i<4;i++)
{
System.out.print(num[i]+" ");
}
System.out.print("and ");


if(ans[1].charAt(2)=='x' && flag1 == true)
{
System.out.print( ans[1].charAt(0) );
System.out.print( ans[1].charAt(1) );
System.out.print("s");
}
else System.out.print(ans[1]+" ");

if(ans[2].charAt(2)=='x' && flag2 == true)
{
System.out.print( ans[2].charAt(0) );
System.out.print( ans[2].charAt(1) );
System.out.print("s");
}
else System.out.print(ans[2]+" ");

if(ans[3].charAt(2)=='x' && flag3 == true)
{
System.out.print( ans[3].charAt(0) );
System.out.print( ans[3].charAt(1) );
System.out.print("t");
}
else System.out.print(ans[3]);


}


public static void main(String[] args)
{
input();
process();
}
}

/*
0,5,2,6
1,7,3,0
2,4,1,5
4,2,3,4
4,5,6,7

*/
ACSL STRING

ACSL STRING

Question


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

Code


Read more
Data Structure

Data Structure

ArrayList


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// the data type must be a type of class
ArrayList<String> a = new ArrayList<String>();
ArrayList<Integer> b = new ArrayList<Integer>();

// the size of the ArrayList
arrayList.size();

// add data to the ArrayList
arrayList.add("DATA");

// replace data by returning the value of the replaced data
arrayList.set();

// remove data by returning the value of the removed data
arratList.remove();

How to traverse the ArrayList

Read more
My first VEX tournament of the season

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.

Read more
Our fantastic bridge -- Bridgination

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!

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

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…

img

VEX programming tips

VEX programming tips

使用万能的电机控制自定义函数

由于电机的端口是一个motor类型的变量,所以我们可以将电机当作变量传参。

模板

1
2
3
4
5
void m(motor motorname,int speed=100,int tor=100) //定义一个名为m的函数,三个参数分别是电机端口、速度(默认100)、力矩(默认100)。
{
motorname.setMaxTorque(tor,percentUnits::pct);
motorname.spin(directionType::fwd,speed,percentUnits::pct);
}

实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 底盘四个电机全功率向前1000ms
using namespace vex;
void test()
{
//四个电机同时以速度100,力矩100向前
m(MotorLF,100,100);
m(MotorLB,100,100);
m(MotorRF,100,100);
m(MotorRB,100,100);
//延时1000ms
task::sleep(1000);
//四个电机同时停
m(MotorLF,0);//由于在这里(一般情况下)力矩默认都为100,所以可以直接不传入力矩这个参数,跳过即可)
m(MotorLB,0);
m(MotorRF,0);
m(MotorRB,0);
}
My first debate competition

My first debate competition

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.

img

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.

img

HIT REFRESH

HIT REFRESH

It’s my first blog in English.

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!

Intro to Neural Network

Intro to Neural Network

线性回归补充

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

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

  1. 局部加权回归

人工神经网络

mark

相同的词向量表示会非常近

  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])

当然还有另外一种思路(*太强了!!!*):

  • 整张表都是向右下方走的,向下走加上数值,向右走无影响
  • 如果向下走代表花束放入花瓶,向右走无影响代表不放入
1
2
3
4
int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数


思路

  • 因为每次取头和尾,所以一定是一个连续的区间
  • 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

  • 判断不合法的状态

    1
    2
    if(i1+j1!=i2+j2) continue;
    if(i1==i2 && j1==j2 && i1+j1!=2 && i1+j1!=m+n) f[i1][j1][i2][j2]=-0x3f3f3f3f;
  • 当m,n<100m,n<100时,四维数组开不下了,因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的,并且三个数都确定时,我们可以直接算出j2j2,直接变成了三维

免费馅饼


题目

地面长度为L,高度为H,天上掉馅饼

人在地上每单位时间可以向左或向右移动0~2格,馅饼每单位时间掉落一格

求最多接到多少馅饼(馅饼有分值)

思路

  • 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])

面包


题目

有N种面包,每种面包数量无限多,有高度和价值,高度是5的倍数
将面包叠成一个面包塔,高度不得超过T
给定常数k,若一个面包高度>=k,则它下面所有面包都会被压扁
一个面包最多被压扁一次,它的高度变为原来的4/5
求最大的价值

思路

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

高精度模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
define N 1e5
struct bign
{
int len;
int v[N];

// 赋值 bign=bign
bign operator = (char* s)
{
len=strlen(s);
memset(v,0,sizeof(v));
for(int i=0;i<len;i++)
v[i]=s[len-i-1]-'0';
return *this;
}
//赋值 bign=int
bign operator = (int x)
{
char s[N];
sprintf(s,"%d",x);
return *this=s;
}

// 高精加
bign operator + (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=max(len,b.len);
for(int i=0;i<c.len;i++)
c.v[i]=v[i]+b.v[i];
for(int i=0;i<c.len;i++)
{
c.v[i+1]+=c.v[i]/10;
c.v[i]%=10;
}
if(c.v[c.len]) c.len++;
return c;
}
// 高精乘
bign operator * (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=len+b.len;
for(int i=0;i<len;i++)
for(int j=0;j<b.len;j++)
c.v[i+j]+=v[i]*b.v[j];
for(int i=0;i<len;i++)
{
c.v[i+1]=c.v[i]/10;
c.v[i]%=10;
}
while(c.len>1 && c.v[c.len-1]) c.len--;
return c;
}
// 高精加等于
bign operator += (const bign &b)
{
return *this+b;
}

// 比大小
bool operator < (const bign &b) const
{
if(len<b.len) return 1;
if(len>b.len) return 0;
for(int i=len-1;i>=0;i--)
{
if(v[i]<b.v[i]) return 1;
if(v[i]>b.v[i]) return 0;
}
return 0;//两个数相等返回flase
}

bool operator > (const bign &b) const
{
return b<*this;
}

bool operator <= (const bign &b) const
{
return !(b>*this);
}

bool operator >= (const bign &b) const
{
return !(b<*this);
}

bool operator == (const bign &b) const
{
return (b>*this)^(b<*this)
}
};

树形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]

代码:记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
if(t[u][k]) return f[u][k];
t[u][k]=1;
if(!k) return f[u][k]=0;
int tmp1=dp(lson[u],k-1)+v[sonl[u]];
int tmp2=dp(rson[u],k-1)+v[sonr[u]];
int tmp3=0;
for(int l=0;l<k-2;l++)
tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}

先修课


题目

课的先修关系形成一棵树的结构,每门课有一门或者没有先修课。选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条边

随机数基本使用方法

基本公式:

要取得[a,b)的随机整数,使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。
要取得a到b之间的随机整数,另一种表示:a + (int)b * rand() / (RAND_MAX + 1)。
要取得0~1之间的浮点数,可以使用rand() / double(RAND_MAX)。

四子连棋

这是我到目前为止写过最长的代码之一……


题意

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

分析

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

遇到的坑

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

  • 黑棋先走和白棋先走走到的棋局相同的情况也是两种情况,不能判重删去!!!

STL

STL

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

迭代器

1
2
set<int>::iterator it_set//一个set<int>类型的迭代器
map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

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()–返回一个用于比较元素间的值的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int tmp;
scanf("%d",&tmp);
s.insert(tmp);
}
for(it_set=s.begin();it_set!=s.end();it_set++)
{
printf("%d\n",*it_set);
}
return 0;
}

链接

容器set和multiset

三角形牧场

P1284三角形牧场


题意

现在有n段木棍,全部使用组成三角形的三条边,使三角形的面积最大

分析

  • 首先看数据范围,边长最大为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;在状态转移的过程中有可能比初始值更大,所以是大于等于

动态规划习题2

P1970 花匠


分析

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

    1
    2
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
    else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;

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

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

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

  • 动态规划

    正解:一维无法解决问题,那么就升一维。

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

    状态转移方程为

    1
    2
    3
    4
    if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
    else f[i][0]=f[i-1][0];
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
    else f[i][1]=f[i-1][1];
  • 贪心

    *为了方便我们设当前的花为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时,数列最后一个保留的数到底是多少,由此我们可以计算出应该增加的不整齐度

  • 转移方程:

    1
    f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度
  • 接下来考虑边界问题

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

    分析最清晰的一回

遇到的坑

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//与前文所使用的变量名有所不同
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留

bool operator < (const ty &a,const ty &b)
{
return a.h<b.h;
}

int main()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%d%d",&b[i].h,&b[i].w);

K=n-K;
sort(b+1,b+n+1);

//第i个数保留j个的最小整齐度,序列的最后一个数序号为i
for(int i=1;i<=n;i++)
{
for(int j=1;j<=K&&j<=i;j++)
{
if(j==1) continue;
f[i][j]=0x3f3f3f3f;
for(int t=j-1;t<i;t++)
{
f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
}
// printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
}

int ans=0x3f3f3f3f;
for(int i=K;i<=n;i++)
ans=min(ans,f[i][K]);
printf("%d\n",ans);
return 0;
}

P1429 平面最近点对(加强版)

P1429 平面最近点对(加强版)

题目

题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入输出格式
输入格式:
第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000

思路

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

  • 然后就是正解:

    分治算法

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

动态规划2-背包DP

动态规划2-背包DP

装箱问题

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述:一个整数v,表示箱子容量;一个整数n,表示有n个物品;接下来n个整数,分别表示这n 个物品的各自体积
输出描述:一个整数,表示箱子剩余空间。
样例输入: 24 6
​ 8 3 12 7 9 7
样例输出:0

状态:f[i][j]表示前i个物品能否装满j的体积

1
2
3
4
5
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
f[i][j]=f[i-1][j] || f[i-1][j-v[i]];
for(int i=v;i>0;i++)
if(f[n][i]) printf("%d",v-i);

优化

  • 01滚动

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

  • 就地滚动

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


01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

##方法1:动态规划
状态:还是一样,每一个背包只有选或者不选两种决策,这道题多了一个条件,相当于状态多了一个维度
转移方程f[i][j][k]=f[i-1][j][k]||f[i-1][j-v[i]][k-c[i]]
*i维度可以01滚动*

动态规划1

笔记

最优子结构:子结构最优,全局一定最优
无后效性:各个决策部分单独存在,不会相互影响

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

最大子串和


题意:给你一个有正有负的序列,求一个=子串(连续的一段),使其和最大!
样例输入: -5 6 -1 5 4 -7
样例输出: 14

状态:f[i]表示前i个数的最大子串和,每个状态只有两种决策:1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和


给你一个有正有负的序列,求两个不重叠的子串,使其和最大!

方法一

两个不重叠的子串中间一定有一个分界点,我们可以枚举这个分界点,分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值,当前状态下有两种选择,一种是与前面组成子串,一种是单独成为一个子串,但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​
优化:可以用前缀和维护k维度,算出前k个数的最大和

最大子矩形


在一个矩阵中找到一个子矩阵,该子矩阵和最大!!输出最大和即可。

从暴力的角度考虑,这道题需要枚举矩形的两个顶点,也就是O(n^4)
我们可以只枚举两个顶点的行坐标,即找到这个矩形的高度所在的位置,然后把每一列的数之和求出来当做一个数,可以提前求出每一列前缀和,也就转化成了求最大子串和。

最长公共子序列


给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn},找出X和Y的一个最长公共子序列。

状态f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程

1
2
3
4
5
6
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词


回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而,插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路:需要添加的字符的长度为原字符串的总长度减去现有的回文串长度,所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样,那么正串与反串的最长公共子序列长度就是回文串的长度
为什么不是最长公共子串长度?* 在添加字符的时候可以在任意位置插入,所以不必要求连续。所以如果只能从左右两边加入,那么就是最长公共子串长度*

乘积最大


设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
如:有一个数字串:312, 当N=3,K=1时会有以下两种分法: 1) 312=36 2) 312=62
这时,符合题目要求的结果是:31*2=62

状态:f[i][j]表示前i位使用k个乘号的最大乘积
决策

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

*在算乘积的时候可以先算出前缀‘乘’*
转移方程:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
f[i][j]=f[i-1][j-1]*a[i];
for(int k=1;k<i;k++)
f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}

2018/12/8模拟赛

终于有一次能在考场上打出正解的模拟赛

连线游戏

题目

连线游戏(lines.cpp)
文件输入输出
时间限制:1s
空间限制:256M

【题目描述】
Farmer John最近发明了一个游戏,来考验自命不凡的贝茜。游戏开始的时候,FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板,其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000; -1,000 <= Y_i <= 1,000)。
贝茜可以选两个点画一条过它们的直线,当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分,就是她画出的直线的总条数。为了在游戏中胜出,贝茜找到了你,希望你帮她计算一下最大可能得分。

【输入格式】
第1行: 输入1个正整数:N
第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i,描述了点i的坐标

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

【输出格式】
第1行: 输出1个整数,表示贝茜的最大得分,即她能画出的互不平行的直线数

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

【输出说明】

贝茜能画出以下4种斜率的直线:-1,0,1/3以及1。

思路

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

遇到的坑

  • 考虑精度问题,考试的时候写了1e-5,结果炸了,改成1e-7就对了,甚至不加精度判断都能AC
  • 特判分母为0的情况,本来以为Inf是无限大,所有Inf表示的都是一个意思,但实际炸了……
    ###AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=210;
int x[N],y[N],n;
double ans[N*N];

int main()
{
freopen("lines.in","r",stdin);
freopen("lines.out","w",stdout);

scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);

int cnt=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
double sta;
if(x[i]-x[j]==0) sta=0x3f3f3f3f;
else sta=1.0*(y[i]-y[j])/(x[i]-x[j]);

bool flag=1;
for(int k=1;k<=cnt;k++)
{
if(ans[k]-sta<=1e-10 && ans[k]-sta>=-1e-10)
{
flag=0;
break;
}
}
if(flag) ans[++cnt]=sta;//printf("%lf\n",sta);
}
printf("%d\n",cnt);
return 0;
}

独木桥

题目

【问题描述】
战争已经进入到紧要时刻。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳一个人通过。假如有两个人相向而行在桥上相遇,那么他们两人将无法绕过对方,只能由一个人回头下桥,让另一个人先通过。但是,可以有多个人同时呆在同一个位置。
突然,你收到从指挥部发来的信息,敌军的轰炸机正朝着你所在的独木桥飞来!为了安全,你的部队必须撤下独木桥。独木桥的长度为L,士兵们只能呆在坐标为整数的位置,所有士兵的速度都为1,当一个士兵某一时刻来到了坐标为0或L+1的位置时,他就离开了独木桥。
每个士兵都有一个初始面对的方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何时间。
由于先前的愤怒,你已不能控制你的士兵。甚至,你连每个士兵初始面对的方向都不知道。因此,你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外,总部也在安排阻拦敌人的进攻,因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

【输入文件】
第一行:一个整数L,表示独木桥的长度。桥上的坐标为1..L
第二行:一个整数N,表示初始时留在桥上士兵的数目。
第三行:有N个整数,分别表示每个士兵的初始坐标。初始时,没有两个士兵在同一坐标。

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

【样例输入】
4
2
1 3

【样例输出】
2 4

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

思路

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

每个士兵只有两种选择,向左向右

最大值就是每个士兵的最长选择的集合中的最大值

最小值就是每个士兵的最短选择的集合中的最大值

遇到的坑

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int l,n,ans1,ans2;//max,min

int main()
{
freopen("bridge.in","r",stdin);
freopen("bridge.out","w",stdout);

scanf("%d%d",&l,&n);
while(n--)
{
int x;
scanf("%d",&x);
ans1=max(ans1,min(x,l-x+1));//min
ans2=max(ans2,max(x,l-x+1));//max
}
printf("%d %d\n",ans1,ans2);
return 0;
}

俄罗斯方块

最水的一道题,直接模拟,分七种情况,细心一点就好了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110;
int mp[N],c,p,ans;

int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);

scanf("%d%d",&c,&p);
for(int i=1;i<=c;i++)
scanf("%d",&mp[i]);

if(p==1)
{
for(int i=1;i<=c-3;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2] && mp[i+2]==mp[i+3]) ans++;
printf("%d\n",c+ans);
return 0;
}
if(p==2)
{
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]) ans++;
printf("%d\n",ans);
return 0;
}
if(p==3)
{
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]-1) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]+1) ans++;
printf("%d\n",ans);
return 0;
}
if(p==4)
{
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1]+1 && mp[i+1]==mp[i+2]) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]-1) ans++;
printf("%d\n",ans);
return 0;
}
if(p==5)
{
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]-1) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]+1) ans++;
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1]+1 && mp[i]==mp[i+2]) ans++;
printf("%d\n",ans);
return 0;
}
if(p==6)
{
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]) ans++;
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1]-1 && mp[i+1]==mp[i+2]) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]+2) ans++;
printf("%d\n",ans);
return 0;
}
if(p==7)
{
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]) ans++;
for(int i=1;i<=c-2;i++)
if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]+1) ans++;
for(int i=1;i<=c-1;i++)
if(mp[i]==mp[i+1]-2) ans++;
printf("%d\n",ans);
return 0;
}
return 0;
}

/*
5 7
2 0 3 1 2
*/
汉诺塔问题

汉诺塔问题

题面

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久,但搜索写多了至少也有一些通悟


不妨假设:

  • 当只有

    1
    1个盘子

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

    1
    2个盘子

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

    1
    3个盘子

    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

可以发现当有3个盘子时,中间就会转化成2个盘子的情况,2个盘子最后就会转化成1个盘子的情况,显然可采用递归的方法

思路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from trans end
{
if(x==1)
{
printf("move from %d to %d\n",a,c);
ans++;
return;
}
dfs(x-1,a,c,b);
printf("move from %d to %d\n",a,c);
ans++;
dfs(x-1,b,a,c);
}

int main()
{
scanf("%d",&n);
dfs(n,1,2,3);
printf("need %d steps\n",ans);
return 0;
}

自己遇到的坑

  • 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: 从后端弹出
从前端就是front
q.clear: 清空队列
q.size(): 读取队列的长度,但是好像类型不是int,只能用来判断数组是否为空


AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N=1e6+5;
int a[N];
deque<int> q;

int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);

// q.push_back(1);
//minn
for(int i=1;i<=n;i++)
{
if(q.size() && i-k>=q.front()) q.pop_front();
while(q.size() && a[i]<=a[q.back()]) q.pop_back();
q.push_back(i);
if(i>=k) printf("%d ",a[q.front()]);
}

// return 0;
printf("\n");
q.clear();
// q.push_back(1);
//maxn
for(int i=1;i<=n;i++)
{
if(q.size() && i-k>=q.front()) q.pop_front();
while(q.size() && a[i]>=a[q.back()]) q.pop_back();
q.push_back(i);
if(i>=k) printf("%d ",a[q.front()]);
}

return 0;
}