头像

心有远方从未止步




离线:2天前


最近来访(49)
用户头像
数论贪心图论DP通通不会
用户头像
麦小蓝
用户头像
yxc
用户头像
陌上花开Charlie
用户头像
Q_Chivalrous
用户头像
Sakura1
用户头像
Radium_98
用户头像
bi_nian
用户头像
O_30
用户头像
用户头像
zhaoyige2007
用户头像
prism
用户头像
OneSemeserToOneThousand
用户头像
acwing_1482
用户头像
zjc2001
用户头像
chmffwn1
用户头像
追星星的人_6
用户头像
见微
用户头像
Kitebin
用户头像
Jackle


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int n;
struct Segment
{
    int l, r;
    bool operator < (const Segment& t) const 
    {
        return r < t.r;
    }
}seg[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d %d", &seg[i].l, &seg[i].r);

    sort(seg, seg + n); //排序,默认按结构体前面的数据排序

    int ans = 0, last = -2e9;
    for(int i = 0; i < n; i ++)
    {
        if(last < seg[i].l) //直接判断边界,前面的右端点小于后面的左端点,即ans加一
        {
            ans ++;
            last = seg[i].r;
        }
    }
    cout << ans << endl;
    return 0;
}



#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int n;
struct Segment
{
    int l, r;
    bool operator < (const Segment& t) const 
    {
        return r < t.r;
    }
}seg[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d %d", &seg[i].l, &seg[i].r);

    sort(seg, seg + n); //排序,默认按结构体前面的数据排序

    int ans = 0, last = -2e9;
    for(int i = 0; i < n; i ++)
    {
        if(last < seg[i].l) //直接判断边界,前面的右端点小于后面的左端点,即ans加一
        {
            ans ++;
            last = seg[i].r;
        }
    }
    cout << ans << endl;
    return 0;
}



#include<iostream>
using namespace std;

const int N = 1010;
int T;
typedef long long LL;

//神奇海螺公式:相遇问题 :路程和 = 时间 + 速度和;
//因此,回到本题,相遇需要多少秒: 路程和除以速度和
int main()
{
    cin >> T;
    while(T --)
    {
        LL x, y, a, b;
        cin >> x >> y >> a >> b;
        LL sum = y - x;
        if(sum % (a + b) == 0)
           cout << sum / (a + b) << endl;
        else
           cout << "-1" << endl;
    }
}



#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了,输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用,修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯,取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
}




算法1

(暴力枚举) 过9个样例
#include<iostream>
using namespace std;

const int N = 100010;
int n, a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];

    for(int i = 0; i < n; i ++)
    {
       if(i == 0) cout << "-1" << " ";
       for(int j = i - 1; j >= 0; j --)
       {
          if(j == 0 && a[j] >= a[i]) cout << "-1" << " ";
          else
              if(a[j] < a[i])
              {
                cout << a[j] << " ";
                break;
              }
       }
    }
    return 0;
}

算法2

(单调栈)
#include<iostream>
using namespace std;

const int N = 100010;
int n;           
int stk[N], tt;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt--; //如果tt下标为真而且栈顶元素大于给定的x元素,则pop
        if(tt) cout << stk[tt] << ' '; //如果还有栈内元素,则栈顶就是x左边第一个比x小的数字
        else cout << "-1" << ' '; //反之,没有元素,则-1

        stk[++ tt] = x; 
    }

    return 0;
}



#include<iostream>
using namespace std;

const int N = 100010;
int stack[N], tt;
int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        string a;
        int x;
        cin >> a;
        if(a == "push") 
            cin >> x, stack[++ tt] = x; //插入
        else if(a == "pop")
            tt --; //弹出
        else if(a == "empty")
        {
            if(tt > 0) puts("NO"); //判断是否为空
            else puts("YES");
        }
        else
            cout << stack[tt] << endl; //输出栈顶元素
    }
    return 0;
}



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
//初始化
void init()
{
    //0表示左端点,1表示右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

//在k点的右边插入x
void add(int k, int x)
{
    e[idx] = x;  //存值
    r[idx] = r[k]; //插入点的右边指针指向k点的右边指针
    l[idx] = k;   //插入点的左边指针指向k点
    l[r[k]] = idx;  //先右边再左边,这个顺序很重要,半年前理解很痛苦,不知道现在为什么理解起来没那么难了
                    //这里就是将k的右边指针的左边指向新链接点
    r[k] = idx; //再来左边连接,也就是将k点的右边指针指向新链接点
    idx ++; 
}

//删除第k的点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    cin >> m;

    init();
    while(m --)
    {
        string op;
        cin >> op;
        int k, x;
        if(op == "L")
        {
            cin >> x;
            add(0, x);
        }
        else if(op == "R")
        {
            cin >> x;
            add(l[1], x);
        }
        else if(op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if(op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x); //k + 1表示k插入的数的idx,所以l[k + 1],因此要在该点左侧插入
        }
        else if(op == "IR")
        {
            cin >> k >> x;
            add(k + 1, x); //k点的右侧插入,直接加一即可,因为add函数写的就是在右边插入的操作
        }
    }
    for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}



#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
//e[i] 表示节点的值
//ne[i] 表示下一个节点的地址
//head 表示头节点的下标
//idx存储当前已用到的点
int head, e[N], ne[N], idx;
//初始化
void init()
{
    head = -1;
    idx = 0;
}

//将x插到头节点
void add_to_head(int x)
{
    e[idx] = x; //存插入的数据
    ne[idx] = head; //将新插入的链点指向head指向
    head = idx; //将head头节点指向idx插入的链点
    idx ++; //这个链点已用,需更新
}

//将第k - 1后的位置插入x
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

//删除链点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;
    init();
    while(m --)
    {
        char op;
        cin >> op;
        int k, x;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin >> k;
            if(!k) head = ne[head];
            else remove(k - 1);
        }
        else if(op == 'I')
        {
            cin >> k >> x;
            add(k - 1, x);
        }

    }
      for(int i = head; i != -1; i = ne[i])
        {
            cout << e[i] << " ";
        }
    return 0;
}



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

using namespace std;

const int N = 100010;
typedef pair<int, int> PII;

vector<PII> segs;
int n;

void merge(vector<PII> & segs)
{
    vector<PII> res; //存储合并后的区间

    sort(segs.begin(), segs.end()); //排序pair的first,这点在区间合并很常用

    int st = -2e9, ed = -2e9; //边界

    for(auto seg : segs)
    {
        if(ed < seg.first)  //判断区间的后端点与后面区间的前端点 
        { 
            if(st != -2e9) //主要为了防止设置的边界存入
                res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else
           ed = max(ed, seg.second); //如果该区间的右端点不小于后一个区间的左端点,则于后一个区间的左端点进行比较,一边更新端点进行合并 
    }

    if(st != -2e9) res.push_back({st, ed});  //当更新到最后的区间右端点,由于没有数据进行比较无法合并最后一个区间,因此需要特判一下,
    segs = res; //最后,pair的长度就是答案
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;


    return 0;
}



题目描述

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 100010;
typedef pair[HTML_REMOVED] PII;

vector[HTML_REMOVED] segs;
int n;

void merge(vector[HTML_REMOVED] & segs)
{
vector[HTML_REMOVED] res; //存储合并后的区间

sort(segs.begin(), segs.end()); //排序pair的first,这点在区间合并很常用

int st = -2e9, ed = -2e9; //边界

for(auto seg : segs)
{
    if(ed < seg.first)  //判断区间的后端点与后面区间的前端点 
    { 
        if(st != -2e9) //主要为了防止设置的边界存入
            res.push_back({st, ed});
        st = seg.first, ed = seg.second;
    }
    else
       ed = max(ed, seg.second); //如果该区间的右端点不小于后一个区间的左端点,则于后一个区间的左端点进行比较,一边更新端点进行合并 
}

if(st != -2e9) res.push_back({st, ed});  //当更新到最后的区间右端点,由于没有数据进行比较无法合并最后一个区间,因此需要特判一下,
segs = res; //最后,pair的长度就是答案

}

int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}

merge(segs);

cout << segs.size() << endl;


return 0;

}