ARC 073
C - Sentou
直接线段覆盖即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,T;
int ans;
void Solve() {
read(N);read(T);
int t,r;
r = 0;
for(int i = 1 ; i <= N ; ++i) {
read(t);
ans += t + T - max(t,r);
r = t + T;
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
D - Simple Knapsack
把每个背包的体积改成(w_i - w_1)
然后记录(dp[i][j])为选了i个体积为j的最大值
对于答案枚举i然后取剩余(W - i imes w_1)部分能取最多的即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int64 dp[105][305],w[105],v[105],W;
void Solve() {
read(N);read(W);
for(int i = 1 ; i <= N ; ++i) {
read(w[i]);read(v[i]);
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = i ; j >= 1 ; --j) {
for(int k = w[i] - w[1] ; k <= 3 * N ; ++k) {
dp[j][k] = max(dp[j][k],dp[j - 1][k - (w[i] - w[1])] + v[i]);
}
}
}
int64 ans = 0;
for(int i = 1 ; i <= N ; ++i) {
if(W < i * w[1]) break;
ans = max(dp[i][min(W - i * w[1],1LL * 3 * N)],ans);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
E - Ball Coloring
我们认为这2n个数最大为(MAX)，最小为(MIN)
发现(R_{max})和(B_{max})里一定有一个(MAX)
(R_{min})和(B_{min})里一定有一个(MIN)
然后不失一般性，认为有两种情况
(R_{max} = MAX,B_{min} = MIN)
这个时候我们要(B_{max})最小，(R_{min})最大，我们只需要两个球里选最大的涂红，最小的涂蓝即可
(R_{max} = MAX,R_{min} = MIN)
我们把所有袋中数值小的球涂成蓝色，然后排序，逐个把蓝色红色互换，求每次蓝球间的最小值
发现这两种方式处理方式其实在第二种都包含了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 400005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
pii p[MAXN];
multiset<int> sb,sr;
void Solve() {
read(N);
int x,y;
for(int i = 1 ; i <= N ; ++i) {
read(x);read(y);
if(x > y) swap(x,y);
p[i] = mp(x,y);
sb.insert(x);sr.insert(y);
}
sort(p + 1,p + N + 1);
int64 ans = 1e18;
for(int i = 1 ; i <= N ; ++i) {
int a = *(--sr.end()) - *sr.begin();
int b = *(--sb.end()) - *sb.begin();
ans = min(ans,1LL * a * b);
sr.erase(sr.find(p[i].se));
sr.insert(p[i].fi);
sb.erase(sb.find(p[i].fi));
sb.insert(p[i].se);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
F - Many Moves
记录状态(dp[x[i]][a])为两个块分别在(a)和(x[i])时最小的价值
我们相当于对于(dp[x[i]][x[i - 1]])特殊处理，只要求(dp[x[i - 1]][1,x[i - 1] - 1])和(dp[x[i - 1]][x[i - 1] +1,N])的后一维到(x[i])的距离加dp值
然后其余位置都直接加上(abs(x[i] - x[i - 1]))
直接线段树优化转移
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 400005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int64 val[2],lz;
int L,R;
}tr[MAXN * 4];
int N,Q,A,B,x[MAXN];
void addlz(int u,int64 v) {
tr[u].lz += v;
for(int i = 0 ; i < 2 ; ++i) tr[u].val[i] += v;
}
void pushdown(int u) {
if(tr[u].lz) {
addlz(u << 1,tr[u].lz);
addlz(u << 1 | 1,tr[u].lz);
tr[u].lz = 0;
}
}
void update(int u) {
for(int i = 0 ; i < 2 ; ++i)
tr[u].val[i] = min(tr[u << 1].val[i],tr[u << 1 | 1].val[i]);
}
void build(int u,int l,int r) {
tr[u].L = l;tr[u].R = r;
if(l == r) {
tr[u].val[0] = 1e16 - l;
tr[u].val[1] = 1e16 + l;
return;
}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
update(u);
}
void Change_pos(int u,int p,int64 v) {
if(tr[u].L == tr[u].R) {
tr[u].val[0] = v - tr[u].L;
tr[u].val[1] = v + tr[u].L;
return;
}
pushdown(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(p <= mid) Change_pos(u << 1,p,v);
else Change_pos(u << 1 | 1,p,v);
update(u);
}
void Add_Range(int u,int l,int r,int64 v) {
if(l > r) return;
if(tr[u].L == l && tr[u].R == r) {
addlz(u,v);return;
}
pushdown(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) Add_Range(u << 1,l,r,v);
else if(l > mid) Add_Range(u << 1 | 1,l,r,v);
else {Add_Range(u << 1,l,mid,v);Add_Range(u << 1 | 1,mid + 1,r,v);}
update(u);
}
int64 Query(int u,int l,int r,int id) {
if(l > r) return 1e16;
if(tr[u].L == l && tr[u].R == r) return tr[u].val[id];
pushdown(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) return Query(u << 1,l,r,id);
else if(l > mid) return Query(u << 1 | 1,l,r,id);
else {return min(Query(u << 1,l,mid,id),Query(u << 1 | 1,mid + 1,r,id));}
}
int64 Getans(int u) {
if(tr[u].L == tr[u].R) return tr[u].val[0] + tr[u].L;
pushdown(u);
return min(Getans(u << 1),Getans(u << 1 | 1));
}
void Solve() {
read(N);read(Q);read(A);read(B);
build(1,1,N);
x[0] = A;
Change_pos(1,B,0);
for(int i = 1 ; i <= Q ; ++i) {
read(x[i]);
int64 trans = 1e18;
trans = min(x[i] + Query(1,1,x[i],0),trans);
trans = min(Query(1,x[i] + 1,N,1) - x[i],trans);
Change_pos(1,x[i - 1],trans);
Add_Range(1,1,x[i - 1] - 1,abs(x[i] - x[i - 1]));
Add_Range(1,x[i - 1] + 1,N,abs(x[i] - x[i - 1]));
}
out(Getans(1));enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}