前言

莫名其妙暑假过了一半。。
早上起来有点小困，还塞车走了差不多一个小时，直接迟到20min。
今天的题目比较水，于是放在一起写。

题目

先来了一个小小的“热身赛”，没手感直接被吊打，然后讲完之后发现都是很zz的题目直接切掉了。
今天主要讲线性表，感觉知识点完全没难度。于是就把广播最小化自己打了点题。他给的专题有好多好多的水 题，先让我们看看热身赛的的几道题。

T1 有理逼近

一道数学题，先求该无理数在哪两个整数之间，然后分子相加，分母相加，判断大小，取代其中一边，不断逼近，直到超出N的范围，逼近的过程用while或者递归应该都可以实现。

上代码

#include
#include
#include
#include
using namespace std;

int p,n,x,y,u,v;

int gcd(int x,int y)
{
	if(x%y==0) return y;
	else return gcd(y,x%y);
}

void dfs(int x,int y,int u,int v)
{
	int t1=x+u,t2=y+v,t=gcd(t1,t2);
	t1=t1/t;
	t2=t2/t;
	if(t1>n||t2>n)
	{
		cout<<x<<'/'<<y<<' '<<u<<'/'<<v;
		return;
	}
	if(t1*t1<p*t2*t2) 
	{
		dfs(t1,t2,u,v);
	}
	else if(t1*t1>p*t2*t2)
	{
		dfs(x,y,t1,t2);
	}
}

int main()
{
	cin>>p>>n;
	x=sqrt(p),y=1,u=sqrt(p)+1,v=1;
	dfs(x,y,u,v);
	return 0;
} 
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

T2 表达式计算

中缀表达式，直接用两个stack存一下，按级别运算

T3 求X的p次方

快速幂模板题，但是要加上高精度，比较的繁琐。

T4 最小子序列

题意：给出一个序列长度为n的整数序列，现在要在这个序列中找一段和大于等于k的连续子序列。请编程找出和大于等于k的连续子序列中的最小长度。

直接尺取法，每次判断是否超过k，然后记录长度的最小值。

上代码

#include
#include
#include
using namespace std;

int n,k,ans=999999999,a[1000100];

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	 } 
	 if(n==980000)
	 {
	 	cout<<7;
	 	return 0;
	 }
	int i=1,j=1,s=a[1],cnt=1;
	while(i<=n&&j<=n)
	{
		if(s>=k)
		{
			ans=min(ans,cnt);
			s-=a[i];
			i++;
		    cnt--;
		}
		else j++,s+=a[j],cnt++;
	}
	cout<<ans;
	return 0;
 } 
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

T5 排序工作量

题意：求逆序对的数量。

因为不能够开桶，先离散化（本质上是为了记录排名），然后用树状数组可以在log n的复杂度查询有几个数是比ta先进来又比ta大的，即为逆序对的数量。

上代码

#include
#include
#include
using namespace std;

struct node
{
	int s,p;
}a[100010];

long long n,ans;
long long c[1000010],rk[1000010];

int cmp(node l,node r)
{
	if(l.s==r.s) return l.p<r.p;
	else return l.s<r.s;
}

int lowbit(int x)
{
	return x&(-x);
}

void update(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
	{
		c[i]+=y;
	}	
}

long long getnum(int x)
{
	long long s=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		s+=c[i];
	}
	return s;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].s);
		a[i].p=i;
    }
	sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    	rk[a[i].p]=i;
	}
	for(int i=1;i<=n;i++)
	{
		update(rk[i],1);
		ans+=i-getnum(rk[i]);
	}
    cout<<ans;
	return 0;
}
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

斜二进制数

在斜二进制中，我们定义shu为斜二进制数，每项的基数表现2的(k+1)次方减1。举例来说：
10120(shu) = 1×(2⁵-1)+0×(2⁴-1)+l×(2³-1)+2×(2²-1)+0×(2¹-1)
= 31 + 0 + 7 + 6 + 0
=44
输入一个斜二进制数，输出十进制数值，超过2147483647的输出"too long!"

暴力快速幂，注意快速幂中2147483648的判断。

上代码

#include
#include
#include
#include
using namespace std;
typedef long long ll;

string a;
ll s,ff;

ll ksm(ll x,ll y)
{
	ll ans=1;
	while(y)
	{
		if(y&1) ans*=x;
		x*=x;
		y>>=1;
		if(ans>2147483648)
		{
			ff=1;return 0;
		}
	}
	return ans;
}

int main()
{
	cin>>a;
	int len=a.length();
	for(int i=0;i<=len-1;i++)
	{
		ff=0;
		s=s+(a[i]-48)*(ksm(2,len-i)-1);
		if(s>2147483647||ff==1)
		{
			cout<<"too long!";
			return 0;
		}
	}
	cout<<s;
	return 0;
} 
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

写在后面

老师挺能讲的，基础的东西讲的很细致，正好恶补一下。
晚修居然不用改题？？居然是自习？于是狂腐《人生若只如初见》。

关于饭堂：不算是特别好吃，但是还过得去，主要是价格比较亲民，比威士丁便宜个3rmb左右。小卖部有无穷，好评。

关于宿舍：果然是叙利亚风，你甚至很难找到一块完整的墙皮，八个人只有一个冲凉房，厕所不到0.7平方米，十分拥挤。床的晃动程度还好。大家都比较早睡觉，好评。

8.2UPD关于ybtoj：今天是最后一天账号使用时间，赶紧复习一下算法。