头像

Jude_Zhang




离线:7小时前


活动打卡代码 AcWing 906. 区间分组

//#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

#define sync ios::sync_with_stdio ( false ); cin.tie(0); cout.tie(0)  // cin优化

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
typedef pair<PII, int> PPI;

const int N = 1e5 + 10, M = 1 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

/*-----------------以下正文-----------------*/

bool cmp ( const PII &a, const PII &b )
{
    return a.first < b.first;
}

int main ( void )
{
    int n;
    cin >> n;

    vector<PII> range(n);
    for ( PII &i : range ) cin >> i.first >> i.second;
    sort ( range.begin(), range.end(), cmp );

    priority_queue<int, vector<int>, greater<int> > q;
    for ( int i = 0; i < n; i++ )
    {
        PII t = range[i];
        if ( q.empty() || t.first <= q.top() )
        {
            q.push ( t.second );
        } else {
            q.pop();
            q.push ( t.second );
        }
    }

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

    return 0;
}



思路

1、按区间右结点升序排序。
2、从头枚举结点,当下一区间的左结点大于上一个的右结点时,说明他们不重叠,则更新右结点。

不知如何证明

瞎猜:因为是按右结点升序排序,所以每次更新结点时,它右扩的范围是最小的。

//#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

#define sync ios::sync_with_stdio ( false ); cin.tie(0); cout.tie(0)  // cin优化

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
typedef pair<PII, int> PPI;

const int N = 3e5 + 10, M = 1 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

/*-----------------以下正文-----------------*/

bool cmp ( const PII &a, const PII &b )
{
    return ( a.second < b.second || ( a.second == b.second && a.first > b.first ) );
}

int main ( void )
{
    int n;
    cin >> n;

    vector<PII> q(n);
    for ( PII &i : q ) cin >> i.first >> i.second;

    sort ( q.begin(), q.end(), cmp );

    PII m;
    int res = 1;
    m = q[0];

    for ( int j = 1; j < n; j++ )
    {
        if ( q[j].first <= m.second ) 
        {
            continue;
        } else {
            res++;
            m = q[j];
        }
    }

    cout << res << endl;
}


活动打卡代码 AcWing 905. 区间选点

//#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

#define sync ios::sync_with_stdio ( false ); cin.tie(0); cout.tie(0)  // cin优化

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
typedef pair<PII, int> PPI;

const int N = 3e5 + 10, M = 1 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

/*-----------------以下正文-----------------*/

int main ( void )
{
    int n;
    cin >> n;

    vector<PII> q(n);
    for ( PII &i : q ) cin >> i.first >> i.second;

    sort ( q.begin(), q.end() );

    int res = 0; PII m;
    for ( int i = 0; i < n; )
    {
        m = q[i];

        int j;
        for ( j = i + 1; j < n; j++ )
        {
            if ( m.second >= q[j].first ) m.second = min ( m.second, q[j].second );
            else break;
        }

        res++;
        i = j;
    }

    cout << res << endl;
}


活动打卡代码 AcWing 907. 区间覆盖

遇到后期样例wa掉了,原因是精度问题,开了long long就过了

//#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

#define sync ios::sync_with_stdio ( false ); cin.tie(0); cout.tie(0)  // cin优化

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
typedef pair<PII, int> PPI;

const int N = 3e5 + 10, M = 1 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

//----------------------------

bool cmp ( const PII &a, const PII &b )
{
    if ( a.first < b.first ) return true;
    else if ( a.first > b.first ) return false;
    else return a.second >= b.second;
}

int main ( void )
{
    sync;

    PII m;
    cin >> m.first >> m.second;

    int n;
    cin >> n;

    vector<PII> q(n);
    for ( PII &i : q ) cin >> i.first >> i.second;

    sort ( q.begin(), q.end(), cmp );

    int res = 0, pos;
    PII cur;

    ll minn = INF;
    for ( int i = 0; i < n; i++ )
    {
        if ( q[i].first <= m.first )
        {
            if ( q[i].second >= m.second )
            {
                cout << 1 << endl;
                return 0;
            }

            if ( (m.second - q[i].second) <= minn )
            {
                pos = i;
                res = 1;
                minn = m.second - q[i].second;
            }
        } else break;
    }

    if ( res == 0 ) 
    {
        cout << "-1 " << endl;
        return 0;
    }

    cur = q[pos];

    res = 1;
//    cout << cur.first << ' ' << cur.second << endl;
    for ( int i = 0; i < n; i++ )
    {
        if ( cur.second >= m.second ) 
        {
            cout << res << endl;
            return 0;
        }

        int maxx = -inf;
        for ( int j = i; j < n; j++ )
        {
            if ( q[j].first <= cur.second ) maxx = max ( maxx, q[j].second);
            else break;
        }

        if ( maxx > cur.second ) 
        {
            cur.second = maxx;
//            cout << cur.first << ' ' << cur.second << endl;
            res++;
        }
        else break;
    }

    cout << -1 << endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

#include <iostream>
#include <queue>

using namespace std;

#define sync ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;

int main ( void )
{
    sync;

    priority_queue<ll, vector<ll>, greater<ll> > q;

    int n;
    cin >> n;

    for ( int i = 0; i < n; i++ ) 
    {
        ll t;
        cin >> t;
        q.push ( t );
    }

    ll res = 0;

    while ( q.size() > 1 )
    {
        ll a = q.top(); q.pop();
        ll b = q.top(); q.pop();

        res += a + b;
        q.push ( a + b );
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 128. 编辑器

在HDU上过不掉就很烦2333

#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

#define sync ios::sync_with_stdio ( false ); cin.tie(0); cout.tie(0)  // cin优化

typedef long long ll;

const int N = 1e6 + 10, M = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;


ll stk[M], stk1[M], stk2[M];  // 栈
int hh, tt, hh1, hh2, tt1, tt2;
//----------------------------
ll sum[M], f[M];
int p = 0;  //光标

void init ( void )
{
    sync;
//  sum[0] = f[0] = -INF;
}

void insert ( void )
{
    int n;
    cin >> n;
    stk1[p++] = n;
    if ( p == 1 )
    {
        sum[p] = n;
        f[p] = n;
        ++tt1;
        return;
    }
    sum[p] = sum[p - 1] + stk1[p - 1];  //更新前缀和
    f[p] = max ( f[p - 1], sum[p] );    //更新最大前缀和
    ++tt1;
}

void del ( void )
{
    if ( tt1 == 0 || p == 0 ) return ;
    tt1--, p--;
}

void left ( void )
{
    if ( tt1 == 0 ) return;
    tt1--, p--;
    stk2[tt2++] = stk1[p];
}

void right ( void )
{
    if ( tt2 == 0 ) return;

    stk1[p++] = stk2[--tt2];
    sum[p] = sum[p - 1] + stk1[p - 1];
    f[p] = max ( f[p - 1], sum[p] );
}

void quary ( void )
{
    int n;
    cin >> n;

    cout << f[n] << endl;
}
void solve ( void )
{
    char op;

    cin >> op;

    switch ( op )
    {
        case 'I': insert(); break;
        case 'D': del(); break;
        case 'L': left(); break;
        case 'R': right(); break;
        case 'Q': quary(); break;
    }

}
int main ( void )
{
    init();

    int T;
    cin >> T;
    while ( T-- ) solve();
    return 0;
}


活动打卡代码 AcWing 900. 整数划分

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1010, mod = 1e9 + 7;

ll f[N][N];

int main ( void )
{
    int n;
    cin >> n;

    for ( int i = 0; i <= n; i++ ) f[i][0] = 1;

    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 0; j <= n; j++ )
        {
            f[i][j] = f[i - 1][j];
            if ( j - i >= 0 )
                f[i][j] = max ( f[i][j], f[i - 1][j] + f[i][j - i] ) % mod;
        }
    }

    cout << f[n][n] << endl;
}


活动打卡代码 AcWing 890. 能被整除的数

#include <iostream>

using namespace std;

const int N = 20;

typedef long long ll;

ll p[N];

int main ( void )
{
    int n, m;
    cin >> n >> m;
    for ( int i = 0; i < m; i++ ) cin >> p[i];

    ll res = 0;
    for ( int i = 1; i < (1 << m); i++ )
    {
        ll t = 1, cnt = 0;
        for ( int j = 0; j < m; j++ )
        {
            if ( (i >> j) & 1 ) 
            {
                cnt++;
                if ( t * p[j] > n ) { t = -1; break; }
                t *= p[j];
            }
        }

        if ( t != -1 ) 
        {
            if ( cnt % 2 != 0 ) res += n / t;
            else res -= n / t;
        }
    }

    cout << res << endl;
}



活动打卡代码 AcWing 891. Nim游戏

#include <iostream>

using namespace std;

int main ( void )
{
    int n;
    cin >> n;
    int res = 0;

    for ( int i = 0; i < n; i++ )
    {
        int a;
        cin >> a;
        res ^= a;
    }

    if ( res ) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



活动打卡代码 AcWing 282. 石子合并

include [HTML_REMOVED]

using namespace std;

const int N = 310;

int q[N], s[N], f[N][N];

int main ( void )
{
int n;
cin >> n;

for ( int i = 1; i <= n; i++ ) cin >> q[i];
for ( int i = 1; i <= n; i++ ) s[i] = s[i - 1] + q[i];

for ( int len = 1; len < n; len++ )
{
    for ( int i = 1; i + len <= n; i++ )
    {
        int l = i, r = l + len;
        f[l][r] = 0x3f3f3f3f;
        for ( int k = l; k <= r; k++ )
        {
            f[l][r] = min ( f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1] );
        }
    }
}

cout << f[1][n] << endl;

return 0;

}