Jude_Zhang

1124

//#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;
}

//#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;
}

//#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

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;

}