前言
最 ez 的一集
T1 打工 原题
化简题意：有\(n\) 个工作，每个工作有固定的工资截止时间 你可以在 \(1\) 个时间单位内选择一项工作并完成它 求最后最大工资
思考：
诶 好像做个这个题？上次似乎讲过，用反悔贪心来做
思路：
首先讲原工作的截止时间从小到大排序 然后每次遍历一个工作 如果能做就做了 如果做不了就看看之前做过的所有工作中有没有工资比当前工资低的 直接选择不做那个工作 做当前的工作即可
要快速访问一段东西的最小值 用堆优化即可
时间复杂度 \(O(n\log n)\)
Code
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define mp make_pair
#define ll long long
#define N 2000005
using namespace std;
int n,m;
pair <ll,ll> a[N];
ll ans,last;
priority_queue<ll> q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%lld%lld",&a[i].first,&a[i].second),a[i].second*=-1;
sort(a+1,a+1+m);
for(int i=1;i<=m;i++)
{
ll x=-a[i].second;
last+=a[i].first-a[i-1].first;
if(last)
{
ans+=x;
q.push(-x);
last--;
}
else
{
if(q.empty()) continue;
int z=-q.top();
if(x>z) ans-=z,q.pop(),ans+=x,q.push(-x);
}
}
printf("%lld",ans);
return 0;
}
T2 购物 原题
简要题意：有 \(n\) 种货币，每种货币的价值为 \(v_i\) ,你有 \(c_i\) 个，你要支付 \(m\) 元，老板每种货币有无限个，你需要满足你支出的货币数和老板找回你钱的货币数的和最小
思考：
这是一个很容易就想到的完全背包和多重背包的结合体
最难想的问题是上界
比赛时直接猜结论过了(),上界是 \(2m\) ,时间复杂度是\(O(nm\log m)\) 差不多是 \(10^8\) 过了
代码很好写 两个背包就行
难就难在验证结论的正确性
好吧我不会证明(((
看一下第一篇题解的证明吧()
Code
#include<bits/stdc++.h>
#define N 205
#define M 400005
using namespace std;
int n,m,v[N],c[N],q;
int f1[M],f2[M],ans=1e9;
inline void bag(int x,int v)
{
for(int i=q;i>=x*v;i--)
f1[i]=min(f1[i],f1[i-v*x]+x);
}
int main()
{
scanf("%d%d",&n,&m);
q=3*m;
fill(f1,f1+q+2,1e9);
fill(f2,f2+q+2,1e9);
f1[0]=f2[0]=0;
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=q-m;j++)
f2[j]=min(f2[j],f2[j-v[i]]+1);
int t=1;
while(c[i]>t)
{
bag(t,v[i]);
c[i]-=t;
t*=2;
}
bag(c[i],v[i]);
}
for(int i=m;i<=q;i++)
ans=min(ans,f1[i]+f2[i-m]);
if(ans==1e9) ans=-1;
cout<<ans;
return 0;
}
水了()
T3 魔法 原题
简要题意：给 \(m\) 个字符长度为 \(n\) 可能有 ? 的 \(01\) 串 ?可以当成 0 或 1 来看 给定 \(q\) 次操作 每次会修改一个字符串或者查询区间 \(l\to r\)中有多少个字符串可以解释成该 \(01\) 串
吐槽一下： lgjOJ 的数据太辣鸡了 能开 \(30\) 棵线段树艹过去 真的无语(((
思考：不妨分类讨论
- 如果 \(l\to r\) 某一位同时存在 \(0\) 和 \(1\) 那么肯定不合法 答案为 \(0\)
- 如果 \(l\to r\) 某一位只有 \(0\),\(1\) 或
?说明这一位固定 对答案没有贡献 - 如果 \(l\to r\) 某一位只有
?说明这一位可以取 \(0\),\(1\) 二者之一 对答案的贡献是 \(\times 2\)
好的我们发现这道题每一位开一棵线段树或者树状数组即可 发现 \(n\leq 30\) 直接暴艹(((
然后交到原题一看 T了(((
分析一下时间复杂度 ： \(O(qn\log m) \leq 6\times 10^8\)
能艹过去就是数据水了(((
我们要考虑正解
不妨思考一下，这 \(n\) 棵线段树 每次只存 \(01\) 真的太浪费空间了
我们不妨考虑直接将他们压位压进一个 \(int\) 里
可以用这题了解压位
我们考虑 \(3\) 棵线段树：
- \(0\)树：每个字符串\(1\to 1,0\to 0,?\to 0\)
- \(1\)树：每个字符串\(1\to 0,0\to 1,?\to 0\)
- \(?\)树：每个字符串\(1\to 1,0\to 1,?\to 0\)
每棵线段树存的是他们的或值
为什么？我们把要求的数的那一位都看成 \(0\) 了 显然只有每一位都是 \(0\) 最终的或值才是 \(0\) 然后如果 \(0\) 树和一树查询的值与一下也是 \(0\) 显然方案合法 然后查一下 ? 树区间内有几个 \(0\) 即可
每次操作一次是 \(\log m\) 的 查询一次位数是 \(O(n)\) 的
时间复杂度 \(O(q(n+\log m))\)
Code
#include<bits/stdc++.h>
#define M 100055
using namespace std;
struct segtree{
int tr[4*M];
inline void Pushup(int x)
{
tr[x]=tr[x*2]|tr[x*2+1];
}
inline void updata(int l,int r,int L,int x,int v)
{
if(l>L||r<L) return;
if(l==r)
{
tr[x]=v;
return;
}
int mid=(l+r)/2;
updata(l,mid,L,x*2,v);
updata(mid+1,r,L,x*2+1,v);
Pushup(x);
}
inline int query(int l,int r,int L,int R,int x)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return tr[x];
int mid=(l+r)/2;
return query(l,mid,L,R,x*2)|query(mid+1,r,L,R,x*2+1);
}
}tr[3];
int n,m,q,ans;
string s;
inline void modify(int x,string s)
{
int s1=0,s2=0,s3=0,t=1;
for(int i=0;i<n;i++)
{
if(s[i]=='0') s2|=t,s3|=t;
if(s[i]=='1') s1|=t,s3|=t;
t*=2;
}
tr[0].updata(1,m,x,1,s1);
tr[1].updata(1,m,x,1,s2);
tr[2].updata(1,m,x,1,s3);
}
inline int ask(int l,int r)
{
int s1=tr[0].query(1,m,l,r,1);
int s2=tr[1].query(1,m,l,r,1);
int s3=tr[2].query(1,m,l,r,1);
if((s1&s2)==0)
{
int sum=0;
while(s3)
{
sum++;
s3-=s3&-s3;
}
return 1<<(n-sum);
}
else return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
cin>>s;
modify(i,s);
}
while(q--)
{
int opr,l,r,x;
cin>>opr;
if(opr==0)
{
cin>>l>>r;
ans^=ask(l,r);
}
else
{
cin>>x>>s;
modify(x,s);
}
}
cout<<ans;
return 0;
}
T4 和平
日常摆烂 稳定发挥