5月CWOI杂题
C0238 【0503 B组】模拟测试
垫底。
A 【1026 B组】bins
有一个结论：将两部分各自排序后对应装入是最优的，因为假如有交叉的选择，你交换后一定不劣。
发现 \(m\le1000\)，可以把数列丢到值域上用后缀和判断。因为需要严格大于，可以挪一位。
code:
我写了线段树，其实不用。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int m,n,a[20005];
int cntA[20005],cntB[20005],A[20005],B[20005];
struct segtree{
#define ls p<<1
#define rs p<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int mi,tag;
}c[80005];
void pushup(int p){
c[p].mi=min(c[ls].mi,c[rs].mi);
}
void pushdown(int l,int r,int p){
if(!c[p].tag)return;
c[ls].mi+=c[p].tag,c[rs].mi+=c[p].tag;
c[ls].tag+=c[p].tag,c[rs].tag+=c[p].tag;
c[p].tag=0;
}
void build(int l,int r,int p){
c[p].tag=0;
if(l==r){c[p].mi=B[l]-A[l];return;}
int mid=(l+r)>>1;
build(lson);build(rson);
pushup(p);
}
void update(int l,int r,int p,int L,int R,int k){
if(L>R)return;
if(L<=l&&r<=R){
c[p].mi+=k,c[p].tag+=k;
return;
}
int mid=(l+r)>>1;pushdown(l,r,p);
if(L<=mid)update(lson,L,R,k);
if(R>mid)update(rson,L,R,k);
pushup(p);
}
int query(int l,int r,int p,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R){
return c[p].mi;
}
int mid=(l+r)>>1,res=inf;pushdown(l,r,p);
if(L<=mid)res=min(res,query(lson,L,R));
if(R>mid)res=min(res,query(rson,L,R));
return res;
}
}Tr;
signed main(){
m=read(),n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1,j=n/2+1;i<=n/2;i++,j++)cntA[a[i]]++,cntB[a[j]]++;
for(int i=m;i>=1;i--)A[i]=A[i+1]+cntA[i];
for(int i=m-1;i>=1;i--)B[i]=B[i+1]+cntB[i+1];
Tr.build(1,m,1);
for(int k=n/2;k>=1;k--){
if(Tr.query(1,m,1,1,m)>=0)return printf("%lld\n",k),0;
Tr.update(1,m,1,1,a[k],1);
Tr.update(1,m,1,1,a[k]-1,1);
Tr.update(1,m,1,1,a[2*k-1]-1,-1);
Tr.update(1,m,1,1,a[2*k]-1,-1);
}
puts("0");
return 0;
}
B 【1026 B组】inversions
还没调出来。
C 【1026 B组】candies
有一种较为暴力的做法：枚举我们要改的位置，对剩下的做一个背包，那么加入的物品一定会使得背包为 1 的位置变为两倍（不看 0）。要最大化答案，可以先找出最大的方案，再枚举加入物品的体积，过程可以用 bitset 优化。
（注意：下文中提到“为 0/1 的位置”均指的是在最优的方案中，不考虑会改变的元素，剩余的做背包的那个数组。）
提一嘴：虽然这个做法不太能过，但加上一个强力剪枝能过：发现对于为 1 的位置的集合 \({i_1,i_2\ldots i_s}\) 和为 0 的位置的集合 \({j_1,j_2\ldots j_t}\)（满足 \(j_1>i_1\)，也就是 \(i_1\) 以前的为 0 的位置不管），\(i_k\) 在左移后必须安排到一个为 0 的位置，也就是至少为 \(j_k\)。我们枚举移动步数时可以利用这个结论跳一下，不用一个一个试。这样虽然挺玄学（我没写），但好像几乎卡不掉。
正解是你发现左移的步数 x 必须满足对于任意为 1 的位置 \(i<j\) 都要满足 \(j-i\neq x\)。有一个神奇的写法：
B.reset();B[0]=1;
for(int j=1;j<=n;++j)if(id!=j)B|=(B<<b[j]);
for(int j=1;j<=n;++j)if(id!=j)B|=(B>>b[j]);
最后 B 中不为 1 的就是可行的答案。为什么这是对的？因为 \(j-i\) 这个式子可以看作有 \(n\) 个体积为 \(b_i\) 和 \(n\) 个体积为 \(-b_i\) 的物品做背包。
虽然能过，但还是有点慢，怎么优化？你可以先对所有物品跑背包，每次在这个基础上撤销掉这个物品的影响，得到的就是其余的背包。但是我们需要记录方案数，存不下怎么办？可以对大数取模，相信概率。
code：
//每次暴力背包
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
bitset<1386005>B;int b[105],cnt[105];
signed main(){
int n=read(),id=1,s=0;
for(int i=1;i<=n;++i)b[i]=read(),s+=b[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;++i){
if(b[i]==b[i-1])continue;
B.reset();B[0]=1;
for(int j=1;j<=n;++j)if(i!=j)B|=(B<<b[j]);
cnt[i]=(int)B.count();
if(cnt[i]>cnt[id])id=i;
}
B.reset();B[0]=1;
for(int j=1;j<=n;++j)if(id!=j)B|=(B<<b[j]);
for(int j=1;j<=n;++j)if(id!=j)B|=(B>>b[j]);
for(int i=0;i<=1386000;++i)if(B[i]==0)return printf("%lld %lld\n",b[id],i),0;
return 0;
}
//优化
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int b[105],s[105],cnt[105],f[700005],g[700005];bitset<700005>B;
signed main(){
int n,id=1,all=1;scanf("%d",&n);f[0]=1;for(int i=1;i<=n;++i)scanf("%d",&b[i]);
sort(b+1,b+n+1);for(int i=1;i<=n;++i)s[i]=s[i-1]+b[i];
for(int i=1;i<=n;++i)for(int j=s[i];j>=b[i];--j){
if(f[j]!=0)all--;
f[j]=(f[j]+f[j-b[i]])%mod;
if(f[j]!=0)all++;
}
for(int i=1;i<=n;++i){
if(b[i]==b[i-1])continue;
cnt[i]=all;
memcpy(g,f,sizeof(f));
for(int j=b[i];j<=s[n];++j){
if(g[j]!=0)cnt[i]--;
g[j]=(g[j]-g[j-b[i]]+mod)%mod;
if(g[j]!=0)cnt[i]++;
}
if(cnt[i]>cnt[id])id=i;
}
B.reset();B[0]=1;
for(int j=1;j<=n;++j)if(id!=j)B|=(B<<b[j]);
for(int j=1;j<=n;++j)if(id!=j)B|=(B>>b[j]);
for(int i=1;i<=s[n]-b[id]+1;++i)if(B[i]==0)return printf("%d %d\n",b[id],i),0;
return 0;
}
D 【1026 B组】sheep
还不会。