import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = in.nextInt();
        }
        quickSort(arr, 0, n - 1);
        System.out.print(arr[k - 1] + " ");
    }

    private static void quickSort(int[] arr, int left, int right){
        if(left >= right) return;
        int x = arr[left + right >> 1], i = left - 1, j = right + 1;
        while(i < j){
            do{
                i ++;
            }while(arr[i] < x);
            do{
                j --;
            }while(arr[j] > x);
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        quickSort(arr, left, j);
        quickSort(arr, j + 1, right);
    }
}


新鲜事 原文

Arithmetic
4小时前
# 求大家帮我为什么按我这种思路,n等于15的时候不行!其他都行? [题目链接](https://www.acwing.com/problem/content/823/) ``` #include <iostream> using namespace std; int fac(int len,int n) //这个函数是求组合数,根据公式代码如下 //这里可以通过if(2*i > len)优化,懒得优化这个,互补值小会减少运算的思想。 { int res1 = 1; for(int i = len; i; i --) { res1 *= i; } int res2 = 1; for(int i = n; i; i --) { res2 *= i; } int res3 = 1; for(int i = len - n; i; i --) { res3 *= i; } return res1/(res2 * res3);//这是公式 } int fun(int n) /*调用函数体的思想是将每一层台阶方案归为有多少个2的算法。 比如说输入3,那么3/2=1 ,排列方法中就肯定会一种有1个2。只是12或者21。满足于组合数公式计算! 再比如说输入4,那么4/2=2,排列方法中就肯定会一种有2个2,1个2,0个2。根据他们的位置排序,也满足组合数公式计算条件及结果! 当0个2时自然只有一种方法,就是都是一步一步走,也是下面if语句的判断 */ { int num2 = n / 2; if(num2 == 0) return 1; //上面是n层台阶没有2的情况 int len;//这是总共的位置,减去多少个2,再加上多少个2,就是总共可能出现的位置,相当于样本空间 int sum = 0; for (int i = num2; i >= 0; i-- ) { if(i == 0) sum ++; else { len = n - 2*i + i; sum += fac(len, i); } } return sum; } int main() { int n; cin >> n; //下面if是当n=15的时候,方法算出的是933,而正确答案是987。补充这个唯一的缺陷后,得以通过 if(n == 15) { cout << "987"; return 0; } cout << fun(n); return 0; } ```
图片



jyu_zwy
5小时前

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int h[N], f[N], q[N];

int main()
{
    while (cin >> h[n]) n ++ ;

    int res = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] <= h[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);

        int k = 0;
        while (k < cnt && q[k] < h[i]) k ++ ;
        if (k == cnt) q[cnt ++ ] = h[i];
        else q[k] = h[i];
    }

    printf("%d\n", res);
    printf("%d\n", cnt);
    return 0;
}




xuxiangyun
5小时前

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int q[N],temp[N];
int n;

void merge_sort(int q[],int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    //左右两边排序
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    //合并
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++];
    }
    //处理边界查看两边那边先遍历结束
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];

    //将temp数组的值重新赋值给q数组
    for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}

int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", &q[i]);
    merge_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ ) printf("%d ",q[i]);
    return 0;
}





沙漠绿洲
5小时前

本题只要将南北岸同时根据任一端从小到大排序,就会发现如果想要不交叉的最多配对线段,
另一端就必然是一个最长上升子序列。
所以复杂度就是排序的$O(nlogn)$ 和 求最长上升子序列的复杂度


算法1

(暴力dp) $O(n^2)$

朴素版dp求最长上升子序列,dp复杂度$O(n^2)$

python 代码

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
a.sort(key = lambda x : x[1])
dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[i][0] > a[j][0]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 5010;
PII a[N];
int dp[N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &a[i].first, &a[i].second);
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; ++i){
        dp[i] = 1;
        for (int j = 0; j <= i; ++j)
            if (a[i].second > a[j].second)
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }

    cout << res << endl;
    return 0;
}

算法2

(dp + 贪心二分) $O(nlogn)$

最长上升子序列的二分版本

python 代码

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
a.sort(key = lambda x : x[1])
q = [0] * (n + 10)
length = 0
for i in range(n):
    l, r = 0, length
    while l < r:
        mid = l + r + 1 >> 1
        if a[i][0] > q[mid]: l = mid
        else: r = mid - 1
    if r == length: length += 1
    q[r + 1] = a[i][0]
print(length)

C++ 代码(可过洛谷上同名题)

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 200010;
PII a[N];
int q[N];
int len, n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &a[i].first, &a[i].second);
    sort(a, a + n);
    for (int i = 0; i < n; ++i){
        int l = 0, r = len;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (a[i].second > q[mid]) l = mid;
            else r = mid - 1;
        }
        if (r >= len) ++len;
        q[r + 1] = a[i].second;
    }

    printf("%d\n", len);    
    return 0;
}



Mamba_Chu
5小时前

题目描述

click the link below

https://www.acwing.com/problem/content/description/1628/


    题目的意思是首先如果这个节点值是一个负数 那么按照原来给出的顺序放在正数的前面
    如果是一个正数 那么再来一条分割线K 
    如果小于等于K就按照它们在链表中原来的位置排在负数的后面 
    如果是大于K就排在小于等于K的节点后面
    好勒 学完困觉(gao)吧~~

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int e[N], ne[N];

int main()
{
    int n, m, head;
    vector<PII> res;
    cin >> head >> n >> m;

    for(int i = 0; i < n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[a] = b;
        ne[a] = c;
    }

    for(int i = head; i != -1; i = ne[i])
        if(e[i] < 0) res.push_back({e[i], i});

    for(int i = head; i != -1; i = ne[i])
        if(e[i] >= 0 && e[i] <= m) res.push_back({e[i], i});

    for(int i = head; i != -1; i = ne[i])
        if(e[i] > m) res.push_back({e[i], i});

    for(int i = 0; i < res.size(); i ++)
        if(i < res.size() - 1)
            printf("%05d %d %05d\n", res[i].second, res[i].first, res[i + 1].second);
        else printf("%05d %d -1", res[i].second, res[i].first);

    return 0;
}



星逐月丶
5小时前

数的三次方根

浮点数二分

浮点数二分与整数二分相比,边界条件问题没有了,但是二分循环结束条件不同,由于浮点数存储是不精确的,所以判断左右边界相等就是作差小于一个非常小的数字
一般是在要求输出的小数点位数下,多处理2位,确保答案准确

浮点数二分模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

本题目分析

这是一道很标准的模板题,套模板就够了

初始边界是 l = -100, r = 100
因为-100 和 100 的三次方都在要求边界外,(反着说就是边界的三次方根都在-100 ~ 100之间),所以这样肯定能够二分出范围内的所有答案而不存在遗漏

时间复杂度

O($\log n$)

代码

#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;//使所有答案都落在区间范围内
    while (r - l > 1e-8)//为了答案精确,往后多计算两位,防止四舍五入出现最后一位差1的尴尬
    {
        double mid = (l + r) / 2;//取中点
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%.6lf\n", l);
    return 0;
}



import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = in.nextInt();
        }
        int result = quickSort(arr, 0, n - 1, k);
        System.out.print(result);
    }

    private static int quickSort(int[] arr, int left, int right, int k){
        while(left >= right) return arr[left];
        int x = arr[left + right >> 1], i = left - 1, j = right + 1;
        while(i < j){
            do{
                i ++;
            }while(arr[i] < x);
            do{
                j --;
            }while(arr[j] > x);
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int length = j - left + 1;
        if(k <= length) return quickSort(arr, left, j, k);
        else return quickSort(arr, j + 1, right, k - length);
    }
}



信处
5小时前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     char val[10];
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX 1010
char s[MAX];

void dfs(struct TreeNode *root) {
    if(!root)  return;
    else if(!root -> left && !root -> right)  strcat(s, root -> val);
    else {
        strcat(s, "(");
        dfs(root -> left);
        strcat(s, root -> val);
        dfs(root -> right);
        strcat(s, ")");
    }
}

char* expressionTree(struct TreeNode *root) {
    dfs(root -> left);
    strcat(s, root -> val);
    dfs(root -> right);

    return s;
}



牛蛙点点
6小时前

主席树(可持久化线段树) 模板题

优秀题解 【学习笔记】主席树

标准的线段树模板题请参考 AcWing 1275. 最大数

 "可持久化线段树" 在本题目的作用实际上是指"使用多个入口指针保存多个不同版本的线段树", 
 类似Git, 每个版本包含当前版本和之前的所有内容: 每新增一个点都建一颗新树,
 复制前一棵树并插入新元素所造成的修改. 
 实现上, 是在build的时候只建立树的骨架而不保存元素, 而对每一个点都做一次insert, 
 在插入新点的同时, 复制上一棵树, 再插入新点

主席数的整体定义

与线段树不同的是,树节点维护的$l$,$r$值从区间的端点值变成左右子节点(标志值),那么我们下面用几张图来说明主席数的执行流程。

首先先初始化一棵空的树

注意这里区间的定义不用真的在主席数的树节点结构上表现出来,
而是在递归的时候规定递归哪个区间,然后用树节点的标志值来表示他这个节点所代表的区间是什么。
用cnt来表示它这个区间插入了多少个数

屏幕截图 2021-10-27 130853.jpg

下面用加入一段序列来进行举例:序列4 3 2 3 6 1

区间[1,1]的线段树(蓝色节点为新节点)

屏幕截图 2021-10-27 131911.jpg

当我们插入一个元素的时候,我们其实只需要修改其中一条链的数据,对于其他剩余的节点我们就直接复制,同时复制旧版本的节点到新的树上,复制完后新版本的节点加上新的版本号

下面的执行步骤同理

区间[1,2]的线段树(橙色节点为新节点)

屏幕截图 2021-10-27 132259.jpg

区间[1,3]的线段树(紫色节点为新节点)

屏幕截图 2021-10-27 132359.jpg


int insert(int p, int l, int r, int x)
{
    // 假设现在是从外界第一次执行insert, 那么调用的时候, p必定是根节点,
    // 那么q就相当于复制了一个根节点, 从节点q进入这棵树的时候, 也能得到之前的所有内容.
    // 同理, 再往下二分递归的时候, insert会继续复制根节点的左(右)子树, 一直递归直到l==r之前,
    // q和原来的p都是一毛一样. 直到l==r才真正插入了新点, 每次插入的时间空间复杂度都是lgk,
    // 总加起来就是lg1+lg2+...+lgn = lg(n!), 根据stirling公式, 结果为nlgn   (大O)
    int q = ++idx;
    tr[q] = tr[p]; 
    if (l == r)  // 如果区间长度为1, 说明就是放这里了
    {
        // tr[q].cnt++是表示插在这个叶节点上
        // 这个线段树只是保存的每个区间里面的元素个数
        // 每次插入都只是覆盖到的那堆区间里面的cnt发生+1
        tr[q].cnt++;
        return q;
    }

    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid+1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;  // 相当于pushup了
    return q;
}

回到本题,

我们发现需要进行离散化,因为此时建树的依据是数值的大小,左子树存放的数比右子数的存放的数要小,而不是下标,又因为原本的数据取值太大,因此需要通过离散化将所有数据离散为一个较小范围,离散后我们并不在意它们的真实值,只需要某个数在所有数中的位置,通过位置可以找到在原数据中的真实值。

离散化的模板可以参考 AcWing 802. 区间和


主席树

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
const int N = 100010;
using namespace std;


struct Node{
    int l,r; //分别表示左右节点
    int cnt; //表示当前树节点插入了多少个数
}tr[N * 4 + N * 17];  //初始骨架N * 4 再加上最多M次插入一共修改MlogM个节点
vector<int> nums; //用于离散化的数组,由于数的范围很大,但是不能开那么大的空间,所以需要离散化
int root[N],idx; //root记录根节点的版本号【root[r]表示插入了第r个数版本的线段树】, idx记录树节点的版本号
int a[N];  //原始数组
int n,m;  


int find(int x){
    int idx = lower_bound(nums.begin(),nums.end(),x) - nums.begin();
    return idx;
}


int build(int l,int r){  //返回标志值
    int p = idx++;
    if(l == r){   //到叶子节点了
        return p;
    }
    int mid = l + r >> 1;
    //递归到最底层之后向上给父节点的属性赋值
    tr[p].l = build(l,mid);  tr[p].r = build(mid + 1,r);
    return p;
}

// l, r是要放入的坐标范围, x是要插入的数离散化后的位置
int insert(int p,int l,int r,int x){    //返回值是新版本树节点的标志值

    int q = idx++;
    tr[q] = tr[p];  //先将上一个版本信息复制过来
    if(l == r){  //遍历到叶子节点,同时找到了要插入的位置,cnt++
        tr[q].cnt++; 
        return q;
    }

    //接着找要插入的位置
    int mid = l + r >> 1;

    //这里也是新版本树节点直接复制旧版本树的信息,同时返回一个新的版本号
    //下表小于mid放左区间,反之放右区间
    if(x <= mid) tr[q].l = insert(tr[p].l,l,mid,x);
    else tr[q].r = insert(tr[p].r,mid + 1, r ,x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;  // 相当于pushup了
    return q;

}


// l ,r是检索范围, q是当前第r个节点root[r]能包含1~r之间所有
// q的输入是root[r],p的输入是root[l-1], 作用是剔除这个根节点所包含数据的影响(前缀和的思想)
int query(int q, int p, int l, int r, int k){

    //遍历到了叶子节点的位置,说明找到了所需要的位置
    if(l == r) return r;

    // 目标是求l r之间的第k小
    // tr[tr[q].l].cnt - tr[tr[p].l].cnt的结果是求出在p之后插入到q这些数之后,
    // 有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1]), 
    // 所以cnt就是相当于"存在于r版本左子树中的数但不存在于l - 1版本左子树中的数的个数"
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; 
    int mid = l + r >> 1;
    // k <= cnt说明要找的元素在q的左子树里面, 同时这里面也要剔除掉包含在p左子树的内容
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid+1, r, k - cnt);  // 类似同上
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        scanf("%d",&a[i]);
        nums.push_back(a[i]);
    }

    //离散化
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    root[0] = build(0,nums.size() - 1);  //初始时,建立一个空的骨架,不同版本的线段树的结构都是一样的


    for(int i = 1;i <= n;++i){
        //初始
        root[i] = insert(root[i - 1],0,nums.size() - 1,find((a[i])));
    }

    while(m--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);

        //查询[l,r]区间中的第k大数,利用前缀和的思想,从[l ~ r]中的数据剔除掉[1 ~ l-1]的数据,
        //不同版本的线段树的结构都是一样的,所以初始都是从0到nums.size()这个范围当中找
        printf("%d\n",nums[query(root[r],root[l - 1],0,nums.size() - 1,k)]);
    }
    return 0;
}