\[\text{暑假NOIP模拟赛-6} \]
终于没挂分了
T1 打工
有 \(n\) 个工作，做一个工作要消耗一个时间单位，可以获得价值 \(a_i\)，截止日期 \(b_i\)，求 \(T\) 单位时间内最多获得多少价值
\(1\leq n\leq 10^6\)，\(1\leq a_i,b_i\leq T\leq 10^9\)
先按照时间从小到大排序，然后倒序枚举，将两个时间点的所有工作压入堆里，然后从大到小暴力计算即可，时间复杂度 \(O(n\log n)\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1000010;
int T,n,cnt,b[N];
LL ans;
struct node{int t,val;}a[N];
vector <int> g[N];
priority_queue <int> q;
bool cmp(node x,node y)
{
if(x.t==y.t)
return x.val>y.val;
return x.t<y.t;
}
int main()
{
scanf("%d%d",&T,&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&a[i].t,&a[i].val);
sort(a+1,a+1+n,cmp);
a[0].t=-1;
for(int i=1; i<=n; i++)
{
if(a[i].t==a[i-1].t)
g[cnt].push_back(i);
else
b[++cnt]=a[i].t,g[cnt].push_back(i);
}
b[0]=0;
for(int i=cnt; i>=1; i--)
{
int len=g[i].size();
for(int j=0; j<len; j++)
q.push(a[g[i][j]].val);
int len2=q.size();
int m=min(b[i]-b[i-1],len2);
while(m--)
{
int x=q.top(); q.pop();
ans+=(LL)x;
}
}
printf("%lld",ans);
return 0;
}
T2 购物
其实就是P2851 [USACO06DEC] The Fewest Coins G
一眼背包，但是发现背包体积 \(V\) 要达到 \(\sum v_ic_i\)？？？？其实不用，因为 \(v_i\leq 200\)，所以背包体积上界 \(V\leq 10^5+200\)，做一次 \(\rm 01\) 背包和多重背包即可
#include<bits/stdc++.h>
using namespace std;
const int N=210,NN=4010,C=20010,M=100210,maxn=100200;
int n,m,c[N],v[N],tot,tot2;
int t[N],w1[NN],v1[NN],w2[N];
int f[M],g[M];
void divide(int cnt,int val)
{
int x=1;
while(cnt>=x)
{
w1[++tot]=x*val;
v1[tot]=x;
cnt-=x;
x<<=1;
}
if(cnt)
w1[++tot]=cnt*val,v1[tot]=cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&v[i]);
for(int i=1; i<=n; i++)
{
scanf("%d",&c[i]);
t[v[i]]+=c[i];
}
for(int i=1; i<=200; i++)
if(t[i])
divide(t[i],i),w2[++tot2]=i;
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
f[0]=0;
for(int i=1; i<=tot; i++)
for(int j=maxn; j>=w1[i]; j--)
f[j]=min(f[j-w1[i]]+v1[i],f[j]);
g[0]=0;
for(int i=1; i<=tot2; i++)
for(int j=w2[i]; j<=maxn; j++)
g[j]=min(g[j-w2[i]]+1,g[j]);
int ans=1e9;
for(int i=m; i<=maxn; i++)
ans=min(ans,f[i]+g[i-m]);
if(ans==1e9)
printf("-1");
else
printf("%d",ans);
return 0;
}
T3 魔法
真的用了魔法，\(O(qn\log m)\) 卡过了，（不开 \(\rm O_2\) \(1.12s\)）
一眼线段树，一个字符串包含 \(\{0,1,?\}\)，是三进制，我不会转化，于是直接每个线段树节点都存一个字符数组 \(a\) 代表这个区间的字符串，一个二进制数 \(s\) 表示哪些位置是不确定的（不确定为 \(1\)，确定为 \(0\)），还有一个标记 \(flag\) 表示这个区间是否合法。每次合并两个子区间都要 \(O(n)\) 暴力合并，时间复杂度 \(O(qn\log m)\)
放一下暴力代码
#include<bits/stdc++.h>
#define lc p*2
#define rc p*2+1
using namespace std;
const int N=35,M=100017;
struct SegmentTree
{
char a[N];
int s;
bool flag;
#define a(x,i) t[x].a[i]
#define s(x) t[x].s
#define flag(x) t[x].flag
}t[4*M];
int n,m,q,ans,pw[N];
char str[M][N];
void prework()
{
pw[0]=1;
for(int i=1; i<=n; i++)
pw[i]=pw[i-1]*2;
}
void cpy(int p,char q[])
{
for(int i=1; i<=n; i++)
a(p,i)=q[i];
}
void work(int p)
{
s(p)=0;
for(int i=1; i<=n; i++)
if(a(p,i)=='?')
s(p)+=(1<<i-1);
}
void pushup(int p)
{
flag(p)=(flag(lc)&flag(rc));
if(!flag(p))
return;
for(int i=1; i<=n; i++)
{
if(a(lc,i)==a(rc,i))
a(p,i)=a(lc,i);
else if(a(lc,i)=='?')
a(p,i)=a(rc,i);
else if(a(rc,i)=='?')
a(p,i)=a(lc,i);
else
a(p,i)='?',flag(p)=0;
}
if(flag(p))
s(p)=(s(lc)&s(rc));
}
void build(int p,int l,int r)
{
if(l==r)
{
cpy(p,str[l]);
work(p);
flag(p)=1;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
void merge(SegmentTree &x,SegmentTree p,SegmentTree q)
{
x.flag=(p.flag&q.flag);
if(!x.flag)
return;
for(int i=1; i<=n; i++)
{
if(p.a[i]==q.a[i])
x.a[i]=p.a[i];
else if(p.a[i]=='?')
x.a[i]=q.a[i];
else if(q.a[i]=='?')
x.a[i]=p.a[i];
else
x.a[i]='?',x.flag=0;
}
if(x.flag)
x.s=(p.s&q.s);
}
SegmentTree ask(int p,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r)
{
SegmentTree res=t[p];
return res;
}
SegmentTree lres,rres,res;
int mid=(l+r)>>1;
if(ql<=mid)
lres=ask(lc,l,mid,ql,qr);
if(qr>mid)
rres=ask(rc,mid+1,r,ql,qr);
if(ql<=mid && qr>mid)
merge(res,lres,rres);
else if(ql<=mid)
res=lres;
else
res=rres;
return res;
}
void change(int p,int l,int r,int pos,char rep[])
{
if(l==r)
{
cpy(p,rep);
work(p);
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
change(lc,l,mid,pos,rep);
else
change(rc,mid+1,r,pos,rep);
pushup(p);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=m; i++)
scanf("%s",str[i]+1);
build(1,1,m);
prework();
while(q--)
{
int op,l,r,pos;
char A[N];
scanf("%d",&op);
if(op==0)
{
scanf("%d%d",&l,&r);
SegmentTree tmp=ask(1,1,m,l,r);
if(!tmp.flag)
ans^=0;
else
{
int cnt=0;
for(tmp.s; tmp.s; tmp.s-=(tmp.s&-tmp.s))
cnt++;
ans^=pw[cnt];
}
}
else
{
scanf("%d%s",&pos,A+1);
change(1,1,m,pos,A);
}
}
printf("%d",ans);
return 0;
}
考虑怎么优化，其实可以先不考虑 \(?\)，对于每个节点，存储两个值 \(sa,sb\)，分别表示该位是否一定为 \(1/0\)，那如果 \(sa\&sb\ne 0\) 显然就不合法，合并两个区间时只需让它 \(sa'|sa'',sb'|sb''\) 即可
#include<bits/stdc++.h>
#define lc p*2
#define rc p*2+1
using namespace std;
const int N=35,M=100017;
struct SegmentTree
{
int sa,sb;
bool flag;
#define sa(x) t[x].sa
#define sb(x) t[x].sb
#define flag(x) t[x].flag
}t[4*M];
int n,m,q,ans,pw[N],va[M],vb[M];
char str[N];
void prework()
{
pw[0]=1;
for(int i=1; i<=n; i++)
pw[i]=pw[i-1]*2;
}
void pushup(int p)
{
flag(p)=(flag(lc)&flag(rc));
if(!flag(p))
return;
sa(p)=(sa(lc)|sa(rc));
sb(p)=(sb(lc)|sb(rc));
if(sa(p)&sb(p))
flag(p)=0;
}
void build(int p,int l,int r)
{
if(l==r)
{
sa(p)=va[l]; sb(p)=vb[l];
flag(p)=1;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
void merge(SegmentTree &x,SegmentTree p,SegmentTree q)
{
x.flag=(p.flag&q.flag);
if(!x.flag)
return;
x.sa=(p.sa|q.sa);
x.sb=(p.sb|q.sb);
if(x.sa&x.sb)
x.flag=0;
}
SegmentTree ask(int p,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r)
{
SegmentTree res=t[p];
return res;
}
SegmentTree lres,rres,res;
int mid=(l+r)>>1;
if(ql<=mid)
lres=ask(lc,l,mid,ql,qr);
if(qr>mid)
rres=ask(rc,mid+1,r,ql,qr);
if(ql<=mid && qr>mid)
merge(res,lres,rres);
else if(ql<=mid)
res=lres;
else
res=rres;
return res;
}
void change(int p,int l,int r,int pos)
{
if(l==r)
{
sa(p)=va[l]; sb(p)=vb[l];
flag(p)=1;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
change(lc,l,mid,pos);
else
change(rc,mid+1,r,pos);
pushup(p);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=m; i++)
{
scanf("%s",str+1);
for(int j=1; j<=n; j++)
{
if(str[j]=='1')
va[i]+=(1<<j-1);
if(str[j]=='0')
vb[i]+=(1<<j-1);
}
}
build(1,1,m);
prework();
while(q--)
{
int op,l,r,pos;
char A[N];
scanf("%d",&op);
if(op==0)
{
scanf("%d%d",&l,&r);
SegmentTree tmp=ask(1,1,m,l,r);
if(!tmp.flag)
ans^=0;
else
{
int cnt=0,s=(tmp.sa|tmp.sb);
for(s; s; s-=(s&-s))
cnt++;
ans^=pw[n-cnt];
}
}
else
{
scanf("%d%s",&pos,str+1);
va[pos]=vb[pos]=0;
for(int i=1; i<=n; i++)
{
if(str[i]=='1')
va[pos]+=(1<<i-1);
if(str[i]=='0')
vb[pos]+=(1<<i-1);
}
change(1,1,m,pos);
}
}
printf("%d",ans);
return 0;
}
\(100+100+100+0=300\)
标签：12,int,flag,测试,SegmentTree,sb,sa,2023.8,define From： https://www.cnblogs.com/xishanmeigao/p/17624938.html