怀着一腔热血来华师读书结果自己陷入“大学很轻松”的泥潭，沉溺了一年半，在大二下学期这个不迟不早的时间点，我终于解锁成就“挂科”。挂科只差一道大题的分数，刚好是那道我花了半个小时画图的地址分配题（计算机组成原理）。内存算多一倍，所以即使完成了整道题目，没有分数。当然挂科并没有给我多沉重的打击，它只是一个触发点，让我回顾思考我大学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: <img src="https://static-img.0xffff.one/mKt9HtNgkm7SbqFJKlh7PTmkKLaPFikdpdtGk_J77xM/q:90/w:800/rt:fit/aHR0cHM6Ly9zdGF0/aWMuMHhmZmZmLm9u/ZS9hc3NldHMvZmls/ZXMvMjAxOS0wMS0y/MC8xNTQ3OTUyMTEz/LTkyNTA4Ny1kMWVh/MjUxZS1mMDU5LTRj/ZWMtYjM2Yi1jYTMw/YmVjZGQ4YTkucG5n.jpg" data-orig-src="https://static.0xffff.one/assets/files/2019-01-20/1547952113-925087-d1ea251e-f059-4cec-b36b-ca30becdd8a9.png" width="845" height="371" title="" alt=""> 题意的意思是：给定一串字符串，字符串中‘\’表示下坡，‘/’表示上坡，'_'表示平坡，以此表示某一地形。持续降雨后，求其总积水量，积水处的数量和各积水处的积水量。思路：第一个思路：利用栈储存。栈中元素类型为整型，只储存每个积水处的积水量。但由于判断某个积水处是否独立（即不与其他积水处联通或者说是被更大的积水处包含）较为麻烦，所以经过多次钻牛角尖，以失败告终。第二个思路：利用栈储存。栈中元素储存积水处面积与积水边中靠近前面的边的位置。当后面的积水处的前面的积水边比前面的积水处的前面的积水边要前，即合并两个积水处。草稿：心得：一、再一次被输出坑了。最后的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; if(window.hljsLoader && !document.currentScript.parentNode.hasAttribute('data-s9e-livepreview-onupdate')) { window.hljsLoader.highlightBlocks(document.currentScript.parentNode); } }

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

加油！有时候觉得，我们可能缺了一些安静与专注的氛围。（贴代码要注意一下观感哇，可以编辑帖子的

引用： #include<iostream> using namespace std; int main(){ int a=0; a++; return 0； } if(window.hljsLoader && !document.currentScript.parentNode.hasAttribute('data-s9e-livepreview-onupdate')) { window.hljsLoader.highlightBlocks(document.currentScript.parentNode); } preformatted： #include<iostream> using namespace std; int main(){ int a=0; a++; return 0； } if(window.hljsLoader && !document.currentScript.parentNode.hasAttribute('data-s9e-livepreview-onupdate')) { window.hljsLoader.highlightBlocks(document.currentScript.parentNode); } 怀疑那一段代码触发了引用

[未知用户] 怎么弄来着.....不大清楚

[未知用户] 我很少发帖，也没用过Markdown。。。。。贴代码我也很困扰怎么贴......

[未知用户] 可能是我无疑触发的，我真滴不会。

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

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

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

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

LiQiang

第六天

先写个总结：最近在训练二分查找的题目，但还是不熟悉二分查找
最大连续子列和的求法

题目来源：计蒜客-二分查找-园艺布置

题目描述：

思路：

选定一个区间，在这个区间内二分查找其满意度平均值。
每猜一个平均值，利用贪心算法其其最大子列和,子列的每个元素应该减去平均值
最大子列和为正,代表平均值过大，则令 left = mid，否则令 right = mid

参考链接

代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 1000000+5
long long a[maxn];
double b[maxn],sum[maxn];
double dp[maxn];//求最大子段和
#define INF 1<<29
long long start, maxnum;
bool judge(double x,long long n,long long k)
{
	for (int i = 1; i <= n; i++)
	{
		b[i] = a[i] - x ;//代价为1，变
		sum[i] = sum[i-1]+b[i];
		if (i == 1)
			dp[i] = sum[1];
		else
		dp[i] = min(sum[i], dp[i - 1]);//前i项中最小的sum[i]
	}
	
	double ans = -INF; 
	    maxnum = 0;
	for (int i = k; i <= n; i++)//寻找长度大于K的子段。
	{
		if (ans < sum[i] - dp[i - k])
		{
			ans = sum[i] - dp[i - k];
			maxnum = i; //子段的尾巴
		 }
 
	}
	double s = 0;
	for (int i = maxnum; i > 0; i--)
	{
		s += b[i];
		if (s == ans)
		{
			start = i;
			break;
		}
	}
	return ans >= 0;
}
long long cal(long long a, long long b)
{
	return b ? cal(b, a%b) : a;
}
void f(long long m,long long n)
{
	long long fenzi=0, fenmu=0;
	double ans=0,left=0,right=10000000,mid;
	while (right - left > 0.000001)
	{
		mid = (left + right) / 2;
		if (judge(mid, n, m))
			left = mid;
		else
			right = mid;
	}
	
	for (long long i = start; i <= maxnum; i++)
 		fenzi += a[i];
	fenmu = maxnum - start + 1;
	long long yue = cal(fenzi, fenmu);
	if (fenzi%fenmu == 0)
		cout << fenzi/fenmu;
	else
		cout << fenzi / yue<<"/" << fenmu / yue;
        
}
int main()
{
	long long  n, m, x;
	scanf("%lld%lld", &n,&m);
	for (long long i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
 
	f(m, n);
	return 0;
 
}

0x0001

LiQiang 记得《编程珠玑》有一节讲二分法蛮透彻的，一语中的的那种感觉

LiQiang

0x0001
个人觉得还是题刷得少，所以不熟悉。之前一位师兄也有说过这本书。
在我看来，算法题有一点套路的意思，虽然说也要思考，但是需要熟悉技巧更重要，一个类型题刷个四五道内容不同的题，可以大概了解这个算法的应用。

LiQiang

第七天

继续二分搜索

在前一天继续熟悉了二分搜索的应用之后，决定今天再撸一道二分搜索的题目。
题目来源：AOJ

题目描述

大意如下：

传送带依次传来n个货物，第i个货物的重量为Wi，现在把这些货物装载到K辆卡车上，卡车最大运载量为P，所有卡车最大运载量一致。写一个程序，输入n,k,Wi，求其能装载全部货物所需的最大运载量P的最小值。
输入
第一行依次给出n,K
接下来n行,第i行依次给出 wi
输出
输出P的最小值，占一行
输入样本：
5 3
8
1
7
3
9
输出样本：
10

思路：

设二分左右初始边界为0和INT32_MAX (注：微软家的才有这个宏定义，g++貌似没有？)
定义"临时答案"int mid = (left+right)/2;
模仿上一天的题目，对答案进行二分，然后把“临时答案”模拟进行装车.
当装车成功时，标记信息true，否则标记false
当标记信息为true时，right = mid,否则 left = mid
一直执行到right = left+1,此时停止二分
输出 right

代码：


#include<iostream>
//#include<algorithm>
using namespace std;
#define max 100010
#define INT32_MAX 2147483647
int n, k;
int mark[max];
int mid;

bool find()
{
	int i;
	int f = 0;
	int tmp;
	for (i = 0; i < k; ++i)
	{
		tmp = 0;
		while (tmp + mark[f] <= mid)
		{
			tmp += mark[f];
			++f;
			if (f == n)return true;
		}

	}
	return false;
}
int main()
{
	//cout << INT32_MAX;
	cin >> n >> k;
	int right = INT32_MAX;
	int left = 0;
	//int mid;
	for (int i = 0; i < n; ++i)
	{
		cin >> mark[i];
	}
	//sort(mark, mark + k);
	while (right != left+1 )
	{
		mid = (right + left) / 2;
		if (find())
		{
			right = mid;
		}
		else
		{
			left = mid;
		}
	}
	cout << right << endl;
	return 0;
}

LiQiang

第八天

今天懈怠了，刚躺下突然想起还有题没做.....于是乎起床。
在床上纠结了一会儿，还是觉得事情不能有一，否则就有二三四五六，所以起来继续坚持
晒一下知网研学坚持的天数。坚持63天就有奖品拿。

题目链接：AOJ:穷举法判断某数是否是某子列和

输入：第一行输入n,第二行给出 n个整数，第三行输入 p,第四行给出 p个整数
输出：对于第四行的每个整数Pi，如果存在第二行的某个子列之和恰好为Pi则输出“yes”,否则输出“no”
样例
思路
直接穷举递归，总算法复杂度为O(P * 2ⁿ⁾

直接上代码：

#include<iostream>
using namespace std;
#define max 2010
int mark[max];
int n, q;
//穷举法递归验证是否满足解
bool solve(int i,int m) 
{
	//为 0 ，问题解决
	if (!m)return true;
	//负数，不满足解
	if ((m - mark[i]) < 0)return false;
	//最后一个数据，k++=i+1=n，不会进入循环，所以可能出问题
	if (i == n-1 &&!(m - mark[i]))return true;

	for (int k = i+1; k < n; ++k) 
	{
		//循环递归解决问题
		if (solve(k, m - mark[i]))
			return true;
	}
	return false;
}

void result() 
{
	int tmp;
	cin >> n;
	//++n;
	for (int i = 0; i < n; ++i)
		cin >> mark[i];
	//mark[0] = 0;
	cin >> q;
	for (int i = 0; i < q; ++i) 
	{
		cin >> tmp;
		for(int p=0;p<n;++p)
			if (solve(p, tmp)) 
			{
				cout << "yes" << endl;
				//跳出二层循环
				goto loop;
			}

	     cout << "no" << endl;
	 loop:;;;
	}
}

int main()
{
	result();
    return 0;
}

hsxfjames

第五天那道题应该比入门难一点，其他好像都是二分答案。。二分答案比较简单，不用花太多时间死磕的（逃

LiQiang

hsxfjames 基本都是二分查找，最近在做这个专题

LiQiang

第九天

科赫曲线

题目描述：

Sample Input 1
1
Sample Output 1
0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000

思路：

将“单条边”按规则三等分，用扫描法进行求解
利用向量推导出等边三角形的三个点关于边的端点的表达式


#include<iostream>
#include<iomanip>
using namespace std;
//科赫曲线
//根号三
#define SD3 1.732050808
#define max 4100

struct Node
{

	double x;
	double y;
	void set(double a, double  b)
	{
		x = a;
		y = b;
	}
	Node &operator=(Node rex)
	{
		rex;
		1 + 1;
		this->x = rex.x;
		this->y = rex.y;
		return  *this;
	}

};
//等边三角形右下角
inline Node P1(Node &A,Node &B)
{
	Node tmp;
	tmp.x = 1.0 / 3 * A.x + 2.0 / 3 * B.x;
	tmp.y = 1.0 / 3 * A.y + 2.0 / 3 * B.y;
	return tmp;
}
//等边三角形左下角
inline Node P3(Node &A, Node &B)
{
	Node tmp;
	tmp.x = 1.0 / 3 * B.x + 2.0 / 3 * A.x;
	tmp.y = 1.0 / 3 * B.y + 2.0 / 3 * A.y;
	return tmp;
}
//等边三角形最上面
inline Node P2(Node &tmpA,Node &tmpB) 
{
	Node tmp;
	Node A = P3(tmpA, tmpB);
	Node B = P1(tmpA, tmpB);
	tmp.x = (B.x - A.x)*0.5-(B.y-A.y)*SD3*0.5+A.x;
	tmp.y = (B.x - A.x)*SD3*0.5 + (B.y - A.y)*0.5 + A.y;
	return tmp;
}
//两个标记数组，用于轮流推导下一层的科赫曲线
Node mark1[max];
Node mark2[max];
int main() 
{
	//cout << fixed<<setprecision(9)<<sqrt(3);
	//cout << endl << pow(4, 6);
	Node work;
	work.set(0, 0);
	mark2[0] = work;
	mark1[0] = work;
	work.set(100, 0);
	mark2[1] = work;
	mark1[1] = work;
	double tmp;
	int len1 = 2;
	int len2 = 0;
	int h;
//h为输c出第h层科赫曲线
	cin >> h;
//若h为0
	if (!h) 
	{
		cout <<fixed << setprecision(9)<< 0.00000000 <<' '<< 0.00000000 << endl;
		cout << fixed << setprecision(9)<<100.00000000 << ' ' << 0.00000000 << endl;
		return 0;
	}
	for (int i = 0; i < h; ++i) 
	{
	if(i%2)
	{
		tmp = (mark1[1].x - mark1[0].x)*0.25;
		len1 = (len2 - 1) * 4 + 1;
		for (int k = 0; k < len2 - 1; ++k)
		{
			if (4 + k * 4 >= max) 
			{
				mark1[0]=work;
			}
			mark1[1 + k * 4] = P3(mark2[k], mark2[k + 1]);
			mark1[2 + k * 4] = P2(mark2[k], mark2[k + 1]);
			mark1[3 + k * 4] = P1(mark2[k], mark2[k + 1]);
			mark1[4 + k * 4] = mark2[k + 1];
		}
		if(i==h-1)
		for (int k = 0; k < len1; ++k)
			cout << fixed << setprecision(9)<< mark1[k].x << ' ' << mark1[k].y << endl;
		//cout << "*******************************" << endl << endl << endl;
	}
	else 
	{
		tmp = (mark1[1].x - mark1[0].x)*0.25;
		len2 = (len1 - 1) * 4 + 1;
		for (int k = 0; k < len1-1; ++k) 
		{
			if (4 + k * 4 >= max)
			{
				mark1[0] = work;
			}
			mark2[1 + k * 4] = P3(mark1[k],mark1[k+1]);
			mark2[2 + k * 4] = P2(mark1[k], mark1[k + 1]);
			mark2[3 + k * 4] = P1(mark1[k], mark1[k + 1]);
			mark2[4 + k * 4] = mark1[k + 1];
		}
		if (i == h-1)
		for (int k = 0; k < len2; ++k)
			cout << fixed << setprecision(9)<< mark2[k].x<<' '<<mark2[k].y << endl;
		//cout << "*******************************" << endl << endl << endl;

	}
	}

	return 0;
}

今日收获
复习了矩阵的一些内容

不小心踏进去一个bug，如下


struct Node
{

	double x;
	double y;
	void set(double a, double  b)
	{
		x = a;
		y = b;
	}
	Node &operator=(Node& rex)
	{
		rex;
		1 + 1;
		this->x = rex.x;
		this->y = rex.y;
		return  *this;
	}

};
inline Node &P1(Node &A,Node &B)
{
	Node tmp;
	tmp.x = 1.0 / 3 * A.x + 2.0 / 3 * B.x;
	tmp.y = 1.0 / 3 * A.y + 2.0 / 3 * B.y;
	return tmp;
}

调用以下语句会出现bug，原因在于返回了临时变量的引用。

Node A,B,C;
/*B,C已经赋值*/
A = P1(B,C);

LiQiang

第十天

AOJ:逆序数

题目描述：

输入
第一行给出一个数n ，第二行给出 n 个整数
输出
输出为一行，输出输入的第二行的逆序数
限制
1000ms 131072 KB

样例输入1：
5
3 5 2 1 4
样例输出1：
6
样例输入2：
3
3 1 2
样例输出2：
2

思路一：直接根据定义用扫描法暴力解决，但是算了一下时间复杂度，行不通。
思路二：用冒泡排序法。算了一下时间复杂度，行不通。
思路三：

采用分治法
类比归并排序（升序）
假设有一个递归函数可以完成逆序数的统计，把数组Array分为左右两部分LAraay,RArray，统计这两部分的逆序数Lans,Rans。然后再根据逆序数的定义以及左右两部分数组，RArray每先有一个元素回到Array，则LArray中剩余的元素数量比该元素都大，所以LArray中剩余的元素数量即为该元素对应增加的逆序数。
计算由这两部分数组生成的逆序数。三个逆序数加起来即为该数组的逆序数。

代码：


#include<iostream>
using namespace std;
#define MAX 200005
unsigned long long int mark[MAX];
unsigned long long int l[MAX];//left array
unsigned long long int r[MAX];//right array
unsigned long long int merge(unsigned long long int left, unsigned long long int right)
{
	unsigned long long int lf = 0;//左起
	unsigned long long int rt = 0;//右起
	unsigned long long int ans = 0;

	unsigned long long int mid = (left + right) / 2;
	//赋值左数组
	for (unsigned long long int i = 0; i < mid - left; ++i)
	{
		l[i] = mark[left + i];
	}
	//赋值右数组
	for (unsigned long long int i = 0; i < right - mid; ++i)
	{
		r[i] = mark[mid + i];
	}
	//类似归并排序
		for (unsigned long long int i = 0; i < right - left; ++i)
		{
			//如果左右数组均未被读完
			if (lf < mid - left && rt < right - mid)
			{
				if (r[rt] < l[lf])
				{
					mark[left + i] = r[rt];
					++rt;
					//加上左数组剩余元素数量
					ans += mid - left - lf;
				}
				else
				{
					mark[left + i] = l[lf];
					++lf;
				}
			}//左数组还未被读完
			else if (lf < mid - left)
			{
				while (lf < mid - left)
				{
					mark[left + i] = l[lf];
					++lf;
					++i;
				}
				break;
			}//右数组还未被读完
			else
			{
				while (rt < right - mid)
				{
					mark[left + i] = r[rt];
					++rt;
					++i;
				}
				break;
			}
		}
		return ans;
	}

unsigned long long int mergesort(unsigned long long int left, unsigned long long int right) 
{
	//返回左数组逆序数，右数组逆序数，左右数组产生的逆序数之和
	if (left + 1 < right)
		return mergesort(left, (left + right) / 2) + mergesort((left + right) / 2, right) + merge(left, right);
	return 0;
}

int main()
{
	unsigned long long int n;
	cin >> n;
	for (unsigned long long int i = 0; i < n; ++i)
		cin>>mark[i];
	cout << mergesort(0, n)<<endl;
	return 0;
}

Ariacx

hey加油~

LiQiang

Ariacx ?谢谢

LiQiang

第十一天

水题依旧
题目来源：POJ:中国剩余定理

题目描述：

人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。

输入

输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。所有给定时间是非负的并且小于365, 所求的时间小于21252。

当p = e = i = d = -1时，输入数据结束。

输出

从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。

采用以下格式：
Case 1: the next triple peak occurs in 1234 days.

注意：即使结果是1天，也使用复数形式“days”。

样例输入

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

##样例输出

Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.

思路

暴力解决，用一个数组标记每个高峰日，当该日为三峰时，相应数组元素标记为3，再打表扫描。
用中国剩余定理求解参考链接

思路二代码：

#include<iostream>
using namespace std;
//23,28,33

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int t1, t2, t3, t4;
void slolve() 
{
	int tmp = 23 * 28 / gcd(28, 23);
	t3 = tmp;
	while (t3 % 33 != 1)t3 += tmp;
	tmp = 28 * 33 / gcd(28, 33);
	t1 = tmp;
	while (t1 % 23 != 1)t1 += tmp;
	tmp = 23 * 33 / gcd(33, 23);
	t2 = tmp;
	while (t2 % 28!= 1)t2 += tmp;
	tmp = 23 * 28 / gcd(28, 23);
	t4 = 33 * tmp / gcd(tmp, 33);
}
int main()
{
	slolve();
	//cout << t1 << ' ' << t2 << ' ' << t3 << ' '<<t4;
	int p, e, i, d;
	int cnt = 1;
	int sum;
	while (cin >> p >> e >> i >> d) 
	{
		if (p + 1)
		{
			sum = (t1*p + t2 * e + t3 * i - d) % t4;
			sum = (sum + t4 - 1) % t4 + 1;
			cout << "Case " << cnt << ": the next triple peak occurs in " << sum << " days." << endl;
		}
		else break;
		cnt++;
	}
    return 0;
}

今日收获：

中国剩余定理

Ariacx

LiQiang

吼吼可以啊上来就CRT

LiQiang

Ariacx
其实一开始是因为要训练

这个的使用方法。
但是想不出来怎么使用。求问：你有没有根据以上方程的其他解法。

Ariacx

LiQiang

这个是扩展欧几里得（egcd）

数论一般从同余、快速幂、素数筛选、唯一分解等开始
gcd和egcd、乘法逆元、费尔马小定理、欧拉定理、欧拉函数blablabla
然后crt，二次剩余、大步小步等。。。。
先把这些了解一下在做题会好很多

kuangbin 数论专题（入门）
https://vjudge.net/contest/70017

0x0001

LiQiang 扩展欧几里得(egcd)算法

LiQiang

Ariacx 嗯嗯，我是在看俞勇的书，上面也有提及。

0x0001

Ariacx 才发现你已经回了(つ°ヮ°)つ

LiQiang

第十二天

今天被老师给的视频“带”去做了水题。
今日收获：（好像没收获）强化了格式化输出信息的能力

第一题：POJ1005

题目描述（看原题好一点）：

一个在被河水侵蚀的河岸住一辈子的人要我计算出他家什么时候被河水吞没。河水吞没的面积形状呈半圆形扩散，每年增加50平方英里。
题目图片

输入：

第一行给出整数M,接下来输入M行坐标。以半圆中心为原点，河岸为x轴，每行给出两个浮点数，此为他家的坐标（单位为英里）

输出：

至少经过N年后，他家被吞没。输出对于每个坐标，像样例输出那样输出至少经过N年,他家被吞没。
最后一行输出END OF OUTPUT.

样例输入：

2
1.0 1.0
25.0 0.0

样例输出：

Property 1: This property will begin eroding in year 1.
Property 2: This property will begin eroding in year 20.
END OF OUTPUT.

思路：根据坐标求半径，然后算面积，再用面积除以50，向上取整。

代码：

//POJ1005
 #include<iostream>
 #include<cmath>
 using namespace std;
 double area(double x,double y)
 {
 	double tmp = sqrt(x*x+y*y);
 	return tmp*tmp*3.14159*0.5;
 }
 int main()
 {
 	int n;
 	cin>>n;
 	double x,y;
 	for(int i =1;i<=n;++i){
	 cin>>x>>y;
	 cout<<"Property "<<i<<": This property will begin eroding in year "<<ceil(area(x,y)/50)<<'.'<<endl;
	 }
	 cout<<"END OF OUTPUT."<<endl;
 	return 0;
 }

第二题：POJ1003

题目描述：

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.

第二题题目图片

输入

The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.

输出

For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.

样例输入

1.00
3.71
0.04
5.19
0.00

样例输出

3 card(s)
61 card(s)
1 card(s)
273 card(s)

来源：Mid-Central USA 2001
思路
输入的数据最大才5.20，首先求出超出5.0时所用的最大板块数，发现没有超过300.
输出所有在题目范围内的总板块长度，打表
利用二分法对答案进行搜索

#include<iostream>
 using namespace std;
 //test() 用来打表，提交代码时不用执行
 void test()
 {
  int i = 2;
  //double m = 1;
  double result = 0;
  for(;i<278;++i)
  {
  result+=1.0/i;
  cout<<result<<',';
  }
  //cout<<result<<' '<<i<<endl;
 return;
 }
 int main()
 {
 	double result[] = {0.0,0.5,0.833333,1.08333,1.28333,1.45,1.59286,1.71786,1.82897,1.92897,2.01988,2.10321,2.18013,2.25156,2.31823,2.38073,2.43955,2.49511,2.54774,2.59774,2.64536,2.69081,2.73429,2.77596,2.81596,2.85442,2.89146,2.92717,2.96165,2.99499,3.02725,3.0585,3.0888,3.11821,3.14678,3.17456,3.20159,3.2279,3.25354,3.27854,3.30293,3.32674,3.35,3.37273,3.39495,3.41669,3.43796,3.4588,3.47921,3.49921,3.51881,3.53804,3.55691,3.57543,3.59361,3.61147,3.62901,3.64625,3.6632,3.67987,3.69626,3.71239,3.72827,3.74389,3.75928,3.77443,3.78935,3.80406,3.81855,3.83284,3.84692,3.86081,3.87451,3.88802,3.90136,3.91451,3.9275,3.94032,3.95298,3.96548,3.97782,3.99002,4.00207,4.01397,4.02574,4.03737,4.04886,4.06022,4.07146,4.08257,4.09356,4.10443,4.11518,4.12582,4.13635,4.14676,4.15707,4.16728,4.17738,4.18738,4.19728,4.20708,4.21679,4.22641,4.23593,4.24536,4.25471,4.26397,4.27314,4.28223,4.29124,4.30017,4.30902,4.31779,4.32649,4.33511,4.34366,4.35213,4.36053,4.36887,4.37713,4.38533,4.39346,4.40152,4.40952,4.41746,4.42533,4.43315,4.4409,4.44859,4.45622,4.4638,4.47132,4.47878,4.48619,4.49354,4.50084,4.50809,4.51528,4.52243,4.52952,4.53656,4.54355,4.5505,4.55739,4.56424,4.57105,4.5778,4.58451,4.59118,4.5978,4.60438,4.61092,4.61741,4.62386,4.63027,4.63664,4.64297,4.64926,4.65551,4.66172,4.6679,4.67403,4.68013,4.68619,4.69221,4.6982,4.70415,4.71007,4.71595,4.7218,4.72761,4.73339,4.73914,4.74486,4.75054,4.75619,4.76181,4.76739,4.77295,4.77847,4.78397,4.78943,4.79487,4.80027,4.80565,4.811,4.81631,4.82161,4.82687,4.8321,4.83731,4.84249,4.84765,4.85278,4.85788,4.86296,4.86801,4.87303,4.87803,4.88301,4.88796,4.89288,4.89778,4.90266,4.90752,4.91235,4.91716,4.92194,4.9267,4.93144,4.93616,4.94085,4.94553,4.95018,4.95481,4.95942,4.964,4.96857,4.97311,4.97764,4.98214,4.98663,4.99109,4.99554,4.99996,5.00437,5.00875,5.01312,5.01747,5.0218,5.02611,5.0304,5.03467,5.03893,5.04316,5.04738,5.05159,5.05577,5.05994,5.06409,5.06822,5.07233,5.07643,5.08051,5.08458,5.08863,5.09266,5.09668,5.10068,5.10466,5.10863,5.11258,5.11652,5.12044,5.12434,5.12824,5.13211,5.13597,5.13982,5.14365,5.14747,5.15127,5.15506,5.15883,5.16259,5.16634,5.17007,5.17378,5.17749,5.18118,5.18485,5.18852,5.19217,5.1958,5.19943,5.20304};
 	double tmp;
 	int left = 0;
 	int right = 279;
 	int mid;
 	while(cin>>tmp&&tmp-0.0>1e-6)
	 {
	 	left = 0;
	 	right = 276;
	 	while(left+1<right)
		 {
		 mid = (left+right)/2;
		 if(result[mid]>tmp)
		 {
		 	right = mid;
		 }
		 else{
		 	left = mid;
		 }
		 }
		cout<<left+1<<" card(s)"<<endl;
		 
	 }
	 return 0;
 }

第三题：POJ1004-求平均数

题目简化描述：

给定十二个浮点数，求其平均数

输入

给出十二行，每行一个包含小数点后两位的浮点数

输出

先输出‘$’，再输入的十二个浮点数的平均数，要求四舍五入到小数点后两位

思路：
小数点定点输出+判断是否需要四舍五入（可能我忘了有四舍五入的函数）

代码：

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
	double a;
	double tmp = 0;
	for(int i =0;i<12;++i)
	{
	cin>>a;
	tmp+=a;
	}
	tmp/=12;
	if(int(tmp*1000)%10>4)
	cout<<'$'<<fixed<<setprecision(2)<<tmp+0.01<<endl;
	else cout<<'$'<<fixed<<setprecision(2)<<tmp<<endl;
	
	return 0;
}

LiQiang

补一题，看视频后去做的
* 递归回溯法
红黑格子

题目描述

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

输入

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

'.' - a black tile
'#' - a red tile
'@' - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.

输出

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input

样例输入：

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

样例输出

45
59
6
13

题目来源:Japan 2004 Domestic
思路
递归回溯，标记已走格子，走完所有能走的方格即可。

代码

//poj 1979
#include<iostream>
using namespace std;
struct Node
{
	char data;
	bool status;
	
	bool begin(){
	return data=='@';
	}
	bool go(){
		return !(data-'.');
	}
};

Node mark[21][21];
int n ,m;
int result = 0;
void count(int x,int y){
result++;
for(int i=0;i<4;++i){
	switch(i){
		//up
		case 0:{
			if(x-1>-1&&mark[x-1][y].go()&&!mark[x-1][y].status){
				mark[x-1][y].status = true;
				count(x-1,y);
			}
			break;
		}
		//right
		case 1:{
			if(y+1<n&&mark[x][y+1].go()&&!mark[x][y+1].status){
				mark[x][y+1].status = true;
				count(x,y+1);
			}
			break;
		}
		//down
		case 2:{
			if(x+1<m&&mark[x+1][y].go()&&!mark[x+1][y].status){
				mark[x+1][y].status = true;
				count(x+1,y);
			}
			break;
		}
		//left
		case 3:{
				if(y-1>-1&&mark[x][y-1].go()&&!mark[x][y-1].status){
				mark[x][y-1].status = true;
				count(x,y-1);
			}
			break;
		}
		default:cout<<"error"<<endl;break;
	}
}
	
}

int main(){

	int a,b;
	char oo;
	while(cin>>n>>m&&n&&m){
	result = 0;
	for(int i =0;i<m;++i){
		for(int k=0;k<n;++k){
		cin>>oo;
		mark[i][k].data=oo;
		mark[i][k].status = false;
		if(mark[i][k].begin()){
			a = i;
			b = k;
		}	
		}
	} 
	count(a,b);
	cout<<result<<endl;
}
	
	return 0;
}