挂科之后，我决定重新开始。

LiQiang

怀着一腔热血来华师读书结果自己陷入“大学很轻松”的泥潭，沉溺了一年半，在大二下学期这个不迟不早的时间点，我终于解锁成就“挂科”。

挂科只差一道大题的分数，刚好是那道我花了半个小时画图的地址分配题（计算机组成原理）。内存算多一倍，所以即使完成了整道题目，没有分数。当然挂科并没有给我多沉重的打击，它只是一个触发点，让我回顾思考我大学3/8的时间都用来干嘛了。正是这回顾让我觉得焦虑与不安，我告诉自己不能再继续这样下去了。

于是我决定从头开始，希望接下来的时间可以弥补遗憾。
我开始学习ACM基础，并决定从数据结构开始重新学。
在此记录一下每天的学习过程。?

第一天我决定从最基础的栈开始,题目来源：AOJ ALDS_3_D
链接：https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_3_D

INPUT:
A string, which represents slopes and flatlands by '/', '\' and '' respectively, is given in a line. For example, the region of the above example is given by a string "\///_/\/\\//\///__\_\/\//\".
OUTPUT:

题意的意思是：给定一串字符串，字符串中‘\’表示下坡，‘/’表示上坡，'_'表示平坡，以此表示某一地形。持续降雨后，求其总积水量，积水处的数量和各积水处的积水量。

思路：
第一个思路：利用栈储存。栈中元素类型为整型，只储存每个积水处的积水量。但由于判断某个积水处是否独立（即不与其他积水处联通或者说是被更大的积水处包含）较为麻烦，所以经过多次钻牛角尖，以失败告终。
第二个思路：利用栈储存。栈中元素储存积水处面积与积水边中靠近前面的边的位置。
当后面的积水处的前面的积水边比前面的积水处的前面的积水边要前，即合并两个积水处。
草稿：

心得：
一、再一次被输出坑了。最后的cout<<endl;不加就是 Presentation error
二、万事先打草稿

代码：

#include<stack>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
struct thepair
{
int first;
//int second;
int data;
thepair():data(0) {}
void set(int a,int b)
{
first = a;
data = b;
}
};
int main()
{
int totals = 0;
stack<thepair> s;
stack <int> s1;
string a;
cin >> a;
stack<int> down;
thepair work;//记录面积与位置的临时变量
int len = a.length();
bool status = false;//判断tmp是否增加过,true时为压入栈标志
for (int i = 0; i < len; ++i)
{
//是否将积水处面积及其位置压入栈,work.data为面积不为零
if (status&&work.data)
{
if (!s.empty())
{
//当当前积水处较以往积水处位置靠前
while (!s.empty()&&s.top().first > work.first)
{
work.data += s.top().data;
s.pop();
//s.push(work);
}
}
s.push(work);
work.data = 0;
}
status = true;
if (a != '/'&&a != '') {
down.push(i);
continue;
}
else if (a == '')continue;
else
{
/solve/
if (down.empty())continue;
work.first = down.top(); down.pop();
work.data += i - work.first;
status = false;
}
}

if (work.data) 
{
	if (!s.empty())
	{
		//当当前积水处较以往积水处位置靠前
		while (!s.empty()&&s.top().first > work.first)
		{
			work.data += s.top().data;
			s.pop();
			//s.push(work);
		}
	}
	s.push(work);
}

len = s.size();
for (int i = 0; i < len; ++i) 
{
	s1.push(s.top().data);
	totals += s1.top();
	s.pop();
}

cout << totals<< endl;
cout << len;
for (int i = 0; i < len;++i)
{
	cout << " "<< s1.top() ;
	s1.pop();
}
cout << endl;

}

0xdeadbeef

首先，很难想象一个知道在Markdown里怎么用preformatted的人，在贴自己的代码的时候居然不会把所有的代码都括在里面。

0x0001

加油！有时候觉得，我们可能缺了一些安静与专注的氛围。

（贴代码要注意一下观感哇，可以编辑帖子的

LiQiang

0x0001 邹老哥加把劲修

wood-mirror

引用：

      #include<iostream>
      using namespace std;
      int main(){
              int a=0;
              a++;
              return 0；
      }

preformatted：

 #include<iostream>
 using namespace std;
 int main(){
          int a=0;
           a++;
           return 0；
}

怀疑那一段代码触发了引用

0x0001

LiQiang
LiQiang
尝试一下就会啦，指南有介绍，Markdown 本身不是什么很高深的东西，不过是一些标记，然后取了个名字

LiQiang

0x0001 谢谢，看到了发帖指南了，我用了三个浏览器点击编辑发现网页都崩溃了。Edge提示脚本时间运行过长，谷歌和360显示无法显示。

0x0001

LiQiang 恭喜，新成就【触发0xFFFF网站bug】达成
(这就去修

0x0001

LiQiang ? 看一看当初立下的 flag 还是蛮有意思的，比如说我鸽到现在还没修的bug（逃 0x0001

LiQiang

首先表示抱歉，很少发帖子，因此代码都是直接放的。看到了发帖指南才知道什么是正确的姿势。然后因为触发了某个bug，我的帖子编辑不了，一编辑网页就崩溃，所以只能等管理员修好啦。

第二天

上了PTA，看到数据结构与算法题目集（中文）
于是直接撸第一题：
原文链接：https://pintia.cn/problem-sets/15/problems/709

而后看到了时间限制，感觉这题是给我这种新手设置的，限制达到了50s,目测暴力解法就可以做出来了。

接下来是思路：

考虑数据结构的使用：
栈，思量一番后，构建不出关于栈的有效算法。
图或树，思量一番后，觉得构建出来的图或者树就是数组。

于是决定用数组

考虑算法
暴力双for循环

for i 从 0 到 k:求最大的以dataa[i]为开头的连续子序列的和

其中result为所求数据，dataa[]为保存输入数据的数组，tmp为保存临时连续子序列之和的变量。
当tmp>result时，更新result为tmp
把数组中每个元素都作为开头都进行遍历
暴力解法代码：


#define max 100000
int dataa[max];

int main()
{

	int k;
	cin >> k;
	int result;
	for (int i = 0; i < k; ++i)cin >> dataa[i];
	result = dataa[0];
	int tmp;
	for (int i = 0; i < k; ++i) 
	{
		tmp = 0;
		for (int p = i; p < k; ++p) 
		{
			tmp += dataa[p];
			result = result > tmp ? result : tmp;
		}
	}
	cout << result;
    return 0;
}

结果：

意料之中，暴力解法是可以过的，但这样就达不到训练自己的目的了。可以看到测试点4耗费了3000+ms，应该有改进的方法。
暴力解法时间复杂度为O(N²)
2. 图形结合
思路大概是这样的:
把输入的所有数据看成以0为开头的数列的增长值或者削减值，并把数列画成图像，可以看出，子序列就是把图像对应的图像就是把图像上下移动，子序列最大和就是每个移动的图像中的最高点的最大值。
不难看出子序列最大和的图像必然包括最高点。

”图形结合“方法的代码：


int max(int data[], int n) 
{
	int M = data[0];//子序列之和
	int tmp = 0;//临时变量
	int record=0;//记录最大和下标
	for (int i = 0; i < n;++i) 
	{
		tmp += data[i];
		if (M < tmp) 
		{
			M = tmp;
			record = i;
		}
	}
	if (n == 1)return M;//仅有一个元素则返回一
	//向左扫描
	tmp = 0;
	for (int i = record; i > 0; --i) 
	{
		tmp += data[i];
		if (tmp > M)M = tmp;
	}
	//向右扫描
	tmp = 0;
	for (int i = record; i < n; ++i) 
	{
		tmp += data[i];
		if (tmp > M)M = tmp;
	}
	return M;
}

运行结果：

可以看出速度快了不少，已经可以过1000ms的限制了，时间复杂度为O(N)
3. 分治法
这个是在CSDN上看到的，目前我还想不出这种方法。研究了一下，很受用。
作者：Alex1996a
链接：https ://blog.csdn.net/jimtrump/article/details/72782852
运行结果：

原文作者说时间复杂度为O(N)

今日收获：
1. 分治的思想
2. 强行复习了图形结合

0x0001

LiQiang 其中result为所求数据，dataa[]为保存输入数据的数组，tmp为保存临时连续子序列之和的变量。
当tmp>result时，更新result为tmp

行内的代码用一组反引号圈起来，不然指针的 * 号会触发 Markdown 的斜体字语法?

LiQiang

0x0001 感谢阅读

LiQiang

第三天

今天刷的题是二分查找的，以前只知道用求平方根公式一直迭代求平方根，今天尝试用二分查找求平方根。

题目来源

题目描述：

题目限制： 1000ms 65536K

题目样例

输入
1
2
3
4
5
6
7
8
9
输出
1
1
1
2
2
2
2
2
3

思路：

输入n
利用二分查找，在区间[0,n]上查找n的平方很
主要比较当前元素的平方与n的大小之间的关系
利用无符号整数
注意到n/2的平方可能溢出，所以当当前元素的值大于65536时，直接进入下一次二分搜索。

代码：

#include<iostream>
using namespace std;

int main() {

	unsigned int tmp;
	unsigned int mid;
	unsigned int left;
	unsigned int right;
	while (cin >> tmp)
	{
		left = 0;
		right = tmp;
		mid = tmp / 2;

		while (true)
		{
			//防溢出
			if (mid > 65536) 
			{
				right = mid;
				mid = (left + right) / 2;
				continue;
			}

			if (mid*mid>tmp)
			{
				//mid-1的平方小于等于tmp,则mid-1为所求平方根
				if ((mid - 1)*(mid - 1) <= tmp)
				{
					cout << mid - 1 << endl;
					break;
				}
				else
				{
					right = mid;
					mid = (left + right) / 2;
				}
			}
			else if (mid*mid<tmp)
			{
				//恰好大于，则mid为平方根
				if ((mid + 1)*(mid + 1)>tmp)
				{
					cout << mid << endl;
					break;
				}//恰好等于，则mid+1为平方根
				else if ((mid + 1)*(mid + 1) == tmp)
				{
					cout << mid + 1 << endl;
					break;
				}
				else
				{
					left = mid;
					mid = (left + right) / 2;
				}

			}
			else
			{
				//不大不小即是等于
				cout << mid << endl;
				break;
			}

		}

	}
	return 0;
}

结果：

iwktd1220

好强……真的不会(;´༎ຶД༎ຶ`)膜拜大佬

LiQiang

iwktd1220
我只是个挂科仔
（盯~）真正的大佬总是善于装萌新（手动滑稽）

0x0001

LiQiang 不要被这两个字限制了想象力?

LiQiang

0x0001
不会的，谢谢你哈

0x0001

LiQiang 嗯，就是有点点“标签效应”的感觉

LiQiang

0x0001
当然不是因为挂科才开始努力，只是突然之间意识到了一些东西。一个师兄说到了大三就会焦虑，我了解了其他学校的情况和一些公司招聘的情况后，就开始焦虑了。我觉得这种焦虑是好事，起码是我看清事实的表现。至于挂科这件事情，其实我心里有点数，知道现在开始也还有救，起码不会堕落至极。

讲个小故事，隔壁宿舍大佬至大二上学期已经完成两个项目，一个OJ项目已经弄好雏形了。但是绩点是真的低（大概是因为不爱交作业），不过他学习的热情依然没有降低，目前能力杠杠滴。
希望自己也能像他那样坚持下去，以后试着做个算法工程师。

LiQiang

第四天

先写个今日总结：
二分查找，不要瞎搞。

本来还是二分查找的题目，想试着暴力破解。后来发现不行，超时间了。

题目来源

题目描述

蒜头是个爱学习的孩子，他总喜欢在生活中做一些小实验，这次蒜头想研究一下光合作用。

蒜头的实验材料有如下几样：神奇的种子，普通的纸箱和一些光源。一开始，蒜头将种子均匀的种在了箱子底部，你可以将其看成 X 轴，种子的位置为 X 轴上的点。然后蒜头用纸板将箱子盖住，并在纸板上安装了一些光源（具体见图）。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在蒜头想知道当实验结束时每颗种子的高度是多少？

题目图片

顶上的为光源，光源两边与顶部的夹角都为 45°，黄色部分为光照，绿色的为植物。

样例输入

2
7 1 2
4
4 4 1
1
2
3
4

样例输出

0
0
1
2
1
0
0
1
1
1
1

思路

错误思路：

本思路即暴力扫描


以test[100000]为标记数组,根据输入的n确定上限
输入T
while(T--)
   输入n,m,H;
   for i 从0 到 n: test[i]=0;
   for i 从0 到 m:
        输入 tmp
        在tmp附近扫描，并判断是否在边界内，根据H进行赋值，若赋值后不大于原来数值，则不不赋值
   for i 从1 到 n: 输出test[i];

该思路遇到的困难：

没有考虑上下限的越界，导致多次程序数组越界

该思路的结果：

据估计，单组运算的时间复杂度达O(mH+2n)
即O(m*H + n)
不过还是有可能解决的，考虑好各个灯泡之间的位置关系是有可能更进一步降低时间复杂度的

错误思路代码

#include<iostream>
#include<algorithm>
using namespace std;
#define max 100010
int mark[max];//灯泡位置数组
int cmp(const void *a, const void *b)
{
	return *(int *)b-*(int *)a ;
}

int main()
{

	int n, m, H;
	int T;
	cin >> T;
	int tmp;
	bool status = false;//标记越界处理用
	while (T--)
	{
		cin >> n >> m >> H;
		//初始化
		int test[max]={0};

		for (int i = 0; i<m; ++i)
		{
			cin >> mark[i];
		}
		qsort(mark, m, sizeof(int), cmp);

		for (int i = 0; i < m; ++i)
		{
			status = false;
			tmp=mark[i];	
			//当可能越界
			if ((tmp + H - 1>n)||(tmp-H+1<1))
			{
				status = true;
				//扫描
				for (int k = 1 - H; k < H; ++k)
				{
					if (tmp + k > n)break;
					if (tmp + k < 1)continue;
					if (H - abs(k) > test[tmp + k])test[tmp + k] = H - abs(k);
				}
			}
			//处理越界情况后，跳过本次正常处理
			if (status)continue;
			
			//正常扫描
			for (int k = 1 - H; k < H; ++k)
			{
				if (H - abs(k) > test[tmp + k])
				test[tmp + k] = H - abs(k);
			}
		}
		//output
		for (int i = 1; i <= n; ++i)
		{
			cout << test[i] << endl;
		}
	}
	return 0;
}

正确思路

以下是用二分查找的正确姿势......
参考链接

代码：


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

const int maxn = 1e5+5;
int x[maxn];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,h;
        scanf("%d %d %d",&n,&m,&h);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x[i]);
        }
        sort(x+1,x+m+1);
        for(int i=1;i<=n;i++)
        {
            int ans = 0;
         //找到第一个大于等于i的元素，利用二分查找
            int cnt = lower_bound(x+1,x+m+1,i)-x;
         //当查找到的元素为第一个元素
            if(cnt==1&&m!=0)
            {
                ans = max(ans,h-x[cnt]+i);
            }
         //当查找到的元素为最后一个元素
            else if(cnt==m+1&&m!=0)
            {
                ans = max(ans,h-i+x[cnt-1]);
            }
         //当查找到的元素为中间部分的元素
            else if(m!=0)
            {
                ans = max(0,max(h-i+x[cnt-1],h-x[cnt]+i));
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

收获：

二分查找函数使用
快排函数使用

散列表习题

题目来源

题目描述：
Your task is to write a program of a simple dictionary which implements the following instructions:
- <b>insert str</b>: insert a string str in to the dictionary
- <b>find str</b>: if the distionary contains str, then print 'yes', otherwise print 'no'
Input
In the first line n, the number of instructions is given. In the following n lines, n instructions are given in the above mentioned format.
output
Print yes or no for each find instruction in a line.
Constraints
- A string consists of 'A', 'C', 'G', or 'T'
- 1 ≤ length of a string ≤ 12
- n ≤ 1000000
Sample Input 1
5
insert A
insert T
insert C
find G
find A
Sample Output 1
no
yes

Sample Input 2
13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T
Sample Output 2
yes
no
no
yes
yes
yes
题目限制：
- 2 sec
- 131072 KB

思路：
书上说用散列表做，然后调皮了一下,比较了一下4¹² *sizeof(bool) b跟131072kb的大小关系，于是决定直接用数组标记就好了。后面补充一下散列表的做法。

代码：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define max 16777216
bool mark[max]={false};

unsigned int find(string b)
{
	unsigned int result = 0;
	unsigned int tmp = 1;
	unsigned int len = b.length();
	for (int i = 0; i < len; ++i) 
	{
		switch (b[i]) 
		{
		case 'A':
			result += tmp * 1; break;
		case 'C':
			result += tmp * 2; break;
		case 'G':
			result += tmp * 3; break;
		case 'T':
			result += tmp * 4; break;
		}
		tmp *= 4;
	}
	return result;
}
int main()
{
	string a="abc";
	int n;
	cin >> n;
	if (!n)return 0;
	while (n--) 
	{
		cin >> a;
		if (a == "insert")
		{
			cin >> a;
			mark[find(a)] = true;
		}
		else 
		{
			cin >> a;
			if (mark[find(a)])cout << "yes" << endl;
			else cout<<"no"<<endl;
		}
	}
    return 0;
}

结果

看了一下差0.03s突破1s,有点悬。

LiQiang

第五天

今天摘橘跑步，然后做题。写得有些迟了。

两数相除

题目描述

给定两个 int 类型的数，不用乘法、除法和取模运算，计算他们的商。

输入格式

多组输入，输入到文件结尾。

每组数据依次输入被除数和除数，中间以空格间隔开。

输出格式

每组数据用一行输出一个整数，表示它们的商。

样例输入

-1060849722 99958928
110 11

样例输出

-10
10

第一个思路

这道题目是我从二分查找选的，然后.....我一直在想如何实现二分查找的“除以2”
最后放弃了，想不出什么快速的方法。
模拟手工除法，判断输出的两个树的大小关系和位数的多少
不能用乘法，所以采用if...else if... 判断位数大小，根据int 类型上限即可判断最高位
如果被除数比除数大，两个相差n位数，则先让result=1^{(n-1)，节省加减法步骤}

关键代码：


int V(int tmp) 
{
	int i = 1;
	tmp = abs(tmp);
	if (tmp <10)return 1;
	else if (tmp < 100)return 2;
	else if (tmp < 1000)return 3;
	else if (tmp < 10000)return 4;
	else if (tmp < 100000)return 5;
	else if (tmp < 1000000)return 6;
	else if (tmp < 10000000)return 7;
	else if (tmp < 100000000)return 8;
	else if (tmp < 1000000000)return 9;
	else return 10;

}

但是做着做着.....我突然想到了另一个方法，于是放弃了这个方法。

第二个思路

利用栈
利用多次“+=”运算，达到“指数爆炸”的效果，以快速逼近被除数

主要的伪代码：

//已经确认好b<a，且符号已经先存在bool status,false 为 相同，true为相异
a = abs(a);
b = abs(b);
result = 1;
while(true){

if(b<a) 
{
压(b,result)入栈
b+=b;
result+=result;
}
else
{
出栈，栈顶值赋值b和result

while(栈不为空)
{
if(b+栈顶对应数值<a)
{
b+=栈顶对应值；
result+=栈顶对应值；
}
else 出栈；
}

}
if(栈空)break;
}
if(status)输出-result
else 输出result

下面的代码还可以简化和改进
代码：

#include<iostream>
#include<stack>
using namespace std;
struct record 
{
	int num;
	int data;
	void set(int tdata, int tnum) 
	{
		num = tnum;
		data = tdata;
	}
};
//a*b>0? false:true
inline bool ZF(int a,int b) 
{
	if (a > 0) 
	{
		if (b < 0)return true;
		return false;
	}
	else 
	{
		if (b > 0)return true;
		return false;
	}
}
int main()
{
	int a, b;
	int tmpb,tmpnum;
	stack<record> s;
	record work;
	//当前指数
	int num = 1;
	//当前结果
	int result;
	//两数正负状态
	bool status;
	while (cin >> a >> b) 
	{
		//clear the stack
		while (!s.empty())s.pop();

		//a=0,|a|<|b|
		if (!a || (abs(a) < abs(b)))
		{
			cout << 0 << endl;
			continue;
		}
		//a*b>0? false:true
		status = ZF(a, b);
		a = abs(a);
		b = abs(b);
		
		if (a == b) 
		{
			if (status)cout << '-' << 1 << endl;
			else cout << 1 << endl;
			continue;
		}

		tmpb = b;
		num = 1;
		result = 1;

		while(true)
		{

			if (b < a) 
			{
				work.set(b, num);
				s.push(work);
				tmpb = b;
				tmpnum = num;

				result += num;
				b += b;
				num += num;
			}
			else 
			{
				b = tmpb;
				num = tmpnum;
				result = tmpnum;
				while (!s.empty())
				{
					if (b + s.top().data <= a)
					{
						b += s.top().data;
						result += s.top().num;
					}
					else s.pop();
				}
			}
			if (s.empty())break;
		}
		if(status)cout <<'-'<< result << endl;
		else cout << result << endl;

	}
    return 0;
}

结果

继续改进

我输入了 INT32_MAX / 1 然后明白了......这是临时变量上溢了 INT32_MAX = 2147483647

一怒之下把int 改成了 long long int

结果

后来想了一下，其实这是变相的二分查找。

草稿

今日收获：

进一步熟悉二分查找

可改进之处

利用 <<x 代替 tmp*2^x
利用好1<< x
利用好以上两点则可不用栈