377A Maze
大意: 给定棋盘, 保证初始所有白格连通, 求将$k$个白格变为黑格, 使得白格仍然连通.
$dfs$回溯时删除即可.
#include <iostream>
#include <functional>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head const int N = 1e3+;
int n,m,s,px,py;
int vis[N][N];
char a[N][N];
const int dx[]={,,-,};
const int dy[]={-,,,}; int main() {
scanf("%d%d%d", &n, &m, &s);
REP(i,,n) cin>>a[i]+;
REP(i,,n) REP(j,,m) if (a[i][j]=='.') px=i,py=j;
function<void(int,int)> dfs = [&](int x, int y) {
if (x<=||y<=||x>n||y>m||vis[x][y]||a[x][y]=='#') return;
vis[x][y] = ;
REP(k,,) dfs(x+dx[k],y+dy[k]);
if (s) --s,a[x][y]='X';
};
dfs(px,py);
REP(i,,n) puts(a[i]+);
}
377B Preparing for the Contest
大意: $m$道题, $n$个学生, 每个学生每天做一道题, 每个学生只能做难度不超过他的能力的题, 雇第$i$个学生做题需要花费$j$元, 求最短时间做完所有题的情况下的最少花费, 输出方案.
二分答案, 维护一个堆贪心
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <functional>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;} int main() {
int n=rd(),m=rd(),s=rd();
vector<pii> f(m);
int id = ;
for(auto &t:f) t.x=rd(),t.y=id++;
sort(begin(f),end(f),greater<pii>());
vector<pair<int,pii> > g(n);
id = ;
for(auto &t:g) t.x=rd();
for(auto &t:g) t.y.x=rd(),t.y.y=++id;
sort(begin(g),end(g),greater<pair<int,pii>>());
vector<int> ans(m);
auto chk = [&](int x) {
auto now = g.begin();
auto pos = f.begin();
int sum = ;
priority_queue<pii,vector<pii>,greater<pii>> q;
while (pos!=f.end()) {
while (now!=g.end()&&now->x>=pos->x) q.push((now++)->y);
if (q.empty()) return ;
auto mi = q.top(); q.pop();
if (!mi.y||sum+mi.x>s) return ;
sum += mi.x;
int t = x;
while (pos!=f.end()&&t--) ans[(pos++)->y]=mi.y;
}
return ;
};
int l=,r=m,ret=-;
while (l<=r) {
int mid = (l+r)/;
if (chk(mid)) ret=mid,r=mid-;
else l=mid+;
}
if (ret==-) return cout<<"NO"<<endl,;
cout<<"YES"<<endl;
chk(ret);
for (auto &t:ans) cout<<t<<' ';
cout<<endl;
}
377C Captains Mode
大意: $n$个英雄, 给出两个队伍的操作序列, 操作$(p,x)$表示第$x$队选一个英雄, 操作$(b,x)$表示第$x$队禁一个英雄. 一个英雄被选过或被禁过就不能再选, 禁英雄操作可以跳过. 第一个队想要最大化两个队英雄属性和的差, 第二个队想要最小化. 求最优情况下的差值.
只需考虑属性前$m$大的英雄即可, 那么很容易有$O(m^22^m)$的$dp$
但是可以注意到禁英雄一定会比不禁英雄更优, 那么每个阶段可用英雄数是固定的, 所以第$i$个阶段状态数是$\binom{m}{m-i}$, 这样复杂度可以达到$O(m2^m)$.
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head const int N = 2e6+;
int n, m, a[N], f[N];
int dp[N]; void chkmin(int &a, int b) {a>b?a=b:;}
void chkmax(int &a, int b) {a<b?a=b:;}
int main() {
scanf("%d", &n);
REP(i,,n-) scanf("%d",a+i);
scanf("%d", &m);
sort(a,a+n,greater<int>());
REP(i,,m-) {
char op;
int x;
scanf(" %c%d", &op, &x);
f[i] = (op=='p')<<|(x==);
}
int mx = (<<m)-;
REP(S,,mx) {
int i = m-__builtin_popcount(S);
int &r = dp[S];
if (f[i]==) {
r = INF;
REP(j,,m-) if (S>>j&) {
chkmin(r,dp[S^<<j]);
}
}
else if (f[i]==) {
r = -INF;
REP(j,,m-) if (S>>j&) {
chkmax(r,dp[S^<<j]);
}
}
else if (f[i]==) {
r = INF;
REP(j,,n-) if (S>>j&) {
chkmin(r,dp[S^<<j]-a[j]);
}
}
else if (f[i]==) {
r = -INF;
REP(j,,n-) if (S>>j&) {
chkmax(r,dp[S^<<j]+a[j]);
}
}
}
printf("%d\n",dp[mx]);
}
O(m2^m)
377D Developing Game
大意: $n$个工人, 第$i$个工人属性$v_i$, 只能和属性范围$[L_i,R_i]$的人一起工作, 求最多选出多少工人.
这道题还是挺有意思的, 刚开始想了一个$dp$的做法, 用树套树优化, 但是数据范围太大了, 很难卡过.
实际上可以直接考虑最终确定的区间$[L,R]$, 那么一个工人$(L_i,v_i,R_i)$会对所有$L_i\le L\le v_i,v_i\le R\le R_i$的区间产生贡献. 这样就转化为二维区间加, 最终查询所有点最值, 可以用线段树扫描线很容易实现.
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head const int N = 1e6+;
int n, cnt, mx;
struct {
int l,v,r;
} e[N];
struct _ {
int l,r,h,v;
} a[N];
struct node {
int mx,tag,pos;
void upd(int x) {mx+=x,tag+=x;}
node operator + (const node &rhs) const {
node ret;
ret.mx = max(mx,rhs.mx);
ret.pos = ret.mx==mx?pos:rhs.pos;
ret.tag = ;
return ret;
}
} tr[N<<]; void pd(int o) {
if (tr[o].tag) {
tr[lc].upd(tr[o].tag);
tr[rc].upd(tr[o].tag);
tr[o].tag=;
}
}
void add(int o, int l, int r, int ql, int qr, int v) {
if (ql<=l&&r<=qr) return tr[o].upd(v);
pd(o);
if (mid>=ql) add(ls,ql,qr,v);
if (mid<qr) add(rs,ql,qr,v);
tr[o] = tr[lc]+tr[rc];
}
void build(int o, int l, int r) {
tr[o].mx=tr[o].tag=,tr[o].pos=l;
if (l!=r) build(ls),build(rs);
} int main() {
cin>>n;
REP(i,,n) {
cin>>e[i].l>>e[i].v>>e[i].r;
a[++cnt] = {e[i].l,e[i].v,e[i].v,};
a[++cnt] = {e[i].l,e[i].v,e[i].r+,-};
mx = max(mx, e[i].r+);
}
sort(a+,a++cnt,[](_ a,_ b){return a.h<b.h;});
build(,,mx);
int now = , ans = ;
pii pos;
REP(i,,mx) {
while (now<=cnt&&a[now].h<=i) add(,,mx,a[now].l,a[now].r,a[now].v),++now;
if (tr[].mx>ans) {
ans = tr[].mx;
pos = pii(tr[].pos,i);
}
}
printf("%d\n", ans);
REP(i,,n) {
if (e[i].l<=pos.x&&pos.x<=e[i].v&&e[i].v<=pos.y&&pos.y<=e[i].r) {
printf("%d ",i);
}
}
puts("");
}
377E Cookie Clicker
大意: $n$种建筑, 第$i$个花费$c_i$个曲奇, 每秒生产$v_i$曲奇. 每秒钟只能选一个建筑工作. 初始时刻$0$, 曲奇数$0$, 若$t$时刻选择一个建筑工作, 那么$t+1$时刻得到收益. 求得到$s$块曲奇最少用时.
斜率优化dp
include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}
ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}
//head const int N = 1e6+;
int n;
ll s, dp[N];
struct _ {
ll c, v;
bool operator < (const _ &rhs) const {
return c<rhs.c||c==rhs.c&&v<rhs.v;
}
} a[N]; ll slope2(int i, int j) {
return (a[j].v-a[i].v-+dp[i]-dp[j])/(a[j].v-a[i].v);
}
ll chk(int i, int j, int k) {
return slope2(i,j)>=slope2(j,k);
}
ll slope(int i, int j) {
return (dp[i]-dp[j])/(a[j].v-a[i].v);
} int main() {
cin>>n>>s;
REP(i,,n) cin>>a[i].v>>a[i].c;
sort(a+,a++n);
memset(dp,INF,sizeof dp);
deque<int> q;
ll ans = 1e18;
REP(i,,n) {
if (q.size()&&a[q.back()].v>=a[i].v) continue;
while (q.size()>&&slope(q[],q[])*a[q[]].v+dp[q[]]<a[i].c) q.pop_front();
if (i==) dp[i] = ;
else if (q.size()) {
ll t = (a[i].c-dp[q[]]+a[q[]].v-)/a[q[]].v;
ll rem = t*a[q[]].v+dp[q[]]-a[i].c;
dp[i] = rem-t*a[i].v;
}
else continue;
ans = min(ans, (s-dp[i]+a[i].v-)/a[i].v);
while (q.size()>&&chk(q[q.size()-],q.back(),i)) q.pop_back();
q.push_back(i);
}
printf("%lld\n", ans);
}