做题和算法整理QwQ

发表于 更新于

这算是之前的旧文章了,现在不这么记了   

之前做的题比较少，也没有怎么整理，但是现在不同往日了。在不出点成绩就要退役了，QwQ，AFO

在上者中寻找最长连续有序序列长度

P1434 [SHOI2002] 滑雪

题目描述

Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子： 

1
2
3
4
5
1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 \(24\)－\(17\)－\(16\)－\(1\)（从 \(24\) 开始，在 \(1\) 结束）。当然 \(25\)－\(24\)－\(23\)－\(\ldots\)－\(3\)－\(2\)－\(1\) 更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 \(R\) 和列数 \(C\)。下面是 \(R\) 行，每行有 \(C\) 个数，代表高度(两个数字之间用 \(1\) 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

样例 #1

样例输入 #1

1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出 #1

1
25

提示

对于 \(100\%\) 的数据，\(1\leq R,C\leq 100\)。

  开始的时候写错了，写了个伪代码，然后过来6个点， （什么水数据）   这个是记忆化搜索实现的，思想可以迁移……嗯，学习学习

code

QwQ 
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
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0;
int MAP[105][105]; //start, over;
int f[205][205] = {0}, temp;
int xx[4] = {1, -1, 0, 0}, yy[4] = {0, 0, -1, 1};
int search(int x, int y) {
	if (f[x][y])return f[x][y];
	f[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		if ((x + xx[i] > 0) && (y + yy[i] > 0) && (x + xx[i] <= n) && (y + yy[i] <= m)) {
			if (MAP[x][y] < MAP[x + xx[i]][y + yy[i]]) {
				search(x + xx[i], y + yy[i]);
				f[x][y] = max(f[x][y], f[x + xx[i]][y + yy[i]] + 1);
			}
		}
	}
	return f[x][y];
}
int main() {
	freopen("in.txt", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &MAP[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//start=MAP[i][j];
			temp = search(i, j);
			ans = max(ans, temp);
			//ans=max(ans,over-start);
			//start=0,over=0;
		}
	}
	printf("%d\n", ans);
	return 0;
}
/*神仙伪算法竟然过了6个点
void search(int x,int y){
	over=MAP[x][y];
	int maxn=MAP[x][y],max_x=0,max_y=0;
	for(int i=0;i<4;i++){
		if (maxn<MAP[x+xx[i]][y+yy[i]]){
			maxn=MAP[x+xx[i]][y+yy[i]];
			max_x=x+xx[i];max_y=y+yy[i];
		}
	}
	if (maxn==0)return ;
	if (max_x==0||max_y==0)return ;
	search(max_x,max_y);
	return ;
}
*/

偏序序列在线序列中项

P1168 中位数

题目描述

给出一个长度为\(N\)的非负整数序列\(A_i\)，对于所有\(1 ≤ k ≤ (N + 1) / 2\)，输出\(A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}\)的中位数。即前\(1,3,5,…\)个数的中位数。

输入格式

第\(1\)行为一个正整数\(N\)，表示了序列长度。

第\(2\)行包含\(N\)个非负整数\(A_i (A_i ≤ 10^9)\)。

输出格式

共\((N + 1) / 2\)行，第\(i\)行为\(A_1, A_3, …, A_{2k - 1}\)的中位数。

样例 #1

样例输入 #1

1
2
7
1 3 5 7 9 11 6

样例输出 #1

1
2
3
4
1
3
5
6

## 提示

对于\(20\%\)的数据，\(N ≤ 100\)；

对于\(40\%\)的数据，\(N ≤ 3000\)；

对于\(100\%\)的数据，\(N ≤ 100000\)。

  这道题上各位大佬也是各显神通的，有的用两个堆性质运用到极致的（其实就是优先队列   有的用vector加lower_bound的也也可以过   更有人直接暴力sort，当然TLE就是了，嘿嘿

  ==第一种== 的思想很明确，先建两个优先队列，一个大根堆，一个小根堆，再加一个中项mid，中项前在大根堆，后在小根堆，这样把这两个优先队列夹着个mid一合并就是序列了。   然后就是愉快向里面填数了（根据中项判断）。符合条件（为奇数个数时）时输出中项mid即可，输出前检查mid是否正确（根据堆的性质和中项的性质，两边堆的元素个数大小不相等的时候，多的向通过mid向少的转移，因为输出是奇数个数，所以和上mid，两边堆的元素个数是可以相等的！） 最后就愉快的输出mid了，嘿嘿嘿 ヾ(≧▽≦*)o

  ==第二种==的找到待插入的数正确偏序位置，插入，简单粗暴，效率奇高

  ==第三种==是比较难写的树状数组写法，都是标签的锅QwQ然而什么权值线段树，树上找第K小什么的我还不会啦，等会了，再来看吧 ### code
1.优先队列解法 
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
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n;
int a[100100];
int mid,temp;
priority_queue<int,vector<int>,less<int> >q1;//大根堆
priority_queue<int,vector<int>,greater<int> >q2;//小根堆
int main(){
    scanf("%d",&n);
    scanf("%d",&temp);
    mid=temp;
    printf("%d",temp);//mid初值
    for(int i=2;i<=n;i++){
        scanf("%d",&temp);
        if(temp>mid) q2.push(temp);
        else q1.push(temp);
        if(i%2==1){//第奇数次加入
            while(q1.size()!=q2.size()){
                if(q1.size()>q2.size()){
                    q2.push(mid);
                    mid=q1.top();
                    q1.pop();
                }
                else{
                    q1.push(mid);
                    mid=q2.top();
                    q2.pop();
                }
            }
            cout<<mid<<endl;
        }
    }
    return 0;
}
2.vector直接插入法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>a;
int main()
{
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        a.insert(upper_bound(a.begin(),a.end(),x),x);//二分插入保证单调性
        if(i%2==1)
        {
        	printf("%d\n",a[(i-1)/2]);//是奇数个就输出
        }
    }
    return 0;
}
3.在树状数组上找第k小法==权值树状数组== 
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,tot;
const int maxn=1e5+10;
int bit[maxn];
int a[maxn],b[maxn];

inline int lowbit(int x)
{
    return x&-x;
}
inline void add(int pos,int x)
{
    for(int i=pos;i<=tot;i+=lowbit(i))bit[i]+=x;
}
inline int find_kth(int k)
{
    int ans=0,now=0;                //这里主要解释一下这个的原理 ans就是答案，now是比当前找到的数的小的数字的个数。 
    for(int i=20;i>=0;i--)          //2^20可以说很大了，满足我们的需求了，我们按照20倍增就可以 
    {
        ans+=(1<<i);            //先让答案加上去，试试 
        if(ans>tot||now+bit[ans]>=k)ans-=(1<<i);//如果超了总体的最大值（防止数组越界），或者是 超过了k个，就退回去，这里注意是大于等于，因为要考虑有重复元素，所以我们找的其实是一个满足小于他的个数小于k的最大数。。（可能不好理解，跑两遍样例就行了） 
        else now+=bit[ans];//能加就加上，这里不用怕加到了原来的数，因为树状数组的结构使这个新倍增出来的数就是多出来的那一条枝 
    }
    return ans+1;//然后加上1就是答案啦 
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[++tot]);      //读个入 
        b[tot]=a[tot];
    }
    sort(a+1,a+1+n);                //排个序 
    tot=unique(a+1,a+1+tot)-a-1;    //去个重 
    for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+1+tot,b[i])-a;//离散化一下 
    for(int i=1;i<=n;i++)
    {
        add(b[i],1);            //动态加点 
        if(i&1)printf("%d\n",a[find_kth((i+1)>>1)]);//查kth 
    }
    return 0;
}
🍂暂时结束,不再更新↩︎