NOIP模拟测试22「位运算」
归档于 2019-08-16 07:09
范围n—–$100000$ m $30$
输出方案
这是一个很好的$dp$题
首先我们应该看出来一条性质只要你最后有方案达到$n$个$1$，那么你可以达到任何`一种$n$个$1$的情况
例如
你最后可以达到$3$个$1$
那么你可以达到$11100 $ $ 01110$ $01011$ $01101$等方案
证明：题目里说的操作和优美值都是一的个数相关，只要我们可以达到$n$个一，我们可以通过变换$1$的位置得到多种方案
于是题目里给的$C$我们并不关心，我们只关心$1$的个数，我们把1都放到最右面,另外这也给我们下面dp提供方便
我们先看各个运算意义
假设你$x$和$y$中有$s$个重复的$1$求各个运算之后一的个数，
$&$后$1$的个数就是$s$，
对于$|$我们如果都加的话重复的多加一次
$|$后$1$的个数就是$x+y-s$
重复变为0
^后$1$的个数就是$x+y-s-s$
然后我们可以尝试列一个$dp$
设$f[x][j]$表示第$x$个操作有$j$个$1$的情况，我们当有这种情况就设为$1$，设最后$C$中一的个数为$x$,我们只需要看$f[n][x]$,若$f[n][x]$为$1$递归找解(后面会说到,其实递归找解是这个题最难的地方),若为$0$就是无解
根据上面得出结论我们可以列出
枚举这次操作后重复个数为w,设这次优美值为$G[i]$,枚举之前1的个数为$j$
若这次操作为$&$则$f[x][w]=max(f[x-1][j],f[x][w])$
若为$|$ 则$f[x][G[i]+j-w]=max(f[x][G[i]+j-w],f[x-1][j])$
类似的若为^则$f[x][G[i]+j-w2]=max(f[x][G[i]+j-w2],f[x-1][j])$
注意一下边界以及循环枚举
for(ll w=max(0ll,G[i]+j-m);w<=min(j,G[i]);w++)
看这句max,因为当它比m大时一定有重叠部分,且重叠部分至少为$G[i]+j-m$
然后就到了这个题难点记录方案
思考我们已知条件
我们从后往前搜,我们目前知道的是最终值,我们每一次都把前一位的值算出来,再搜前一位
那么我们已知运算符号已知运算前后1的个数,和运算后的值,我们现在要做的就是求出前一位值,且我们知道这一定能找到一组合法解
三个运算符号分开考虑,
假设符号为$|$,我们已知当前1个数(G[i]),和这次操作之后1的个数,这次操作之前1的个数
我们只需要让这次操作之前数,这次操作数二进制下1完美覆盖掉这次操作1的个数即可
因为我们符号$|$,我们只需要一个从前扫,一个从后扫,类似ST重复无所谓
例如操作前$3$个$1$,这次操作$3个1$操作后$11011$,我们一个从前扫得到$11010$另一个得到$01011$
假设符号为$&$,&只会让数值变小,我们可以断定操作前1的个数和这次操作1一定>=操作后
我们先保证这些操作后上有值的位一定有$1$,然后我们分开放剩下的$1$
例如操作前$4$个$1$,这次操作$3$个$1$,操作后$10001$,我们先得到$10001$
$10001$,再分开放1得到$11101$和$10011$
假设我们当前符号^,思考^运行他会使相同的位置变成0,不同变为1
那么我们重复的地方可以算出是(之前1的个数+这次1的个数-操作后1的个数)/2
然后先给不重复地方赋值,再分别给重复地方赋1
例如操作前$4$个$1$,这次操作$2$个$1$,操作后$11101$,我们先得到重复长度1,然后得到$11100$和$00001$,最后给重复赋值$11110$,$00011$
void dfs(ll pos,ll now)
{
if(pos==1)
{
printf("%lld ",now);
return ;
}
ll cnt_1=0;
// printf("pos=%lld\n",pos);
for(ll i=1;i<=m;i++)
if(now&(1<<(i-1)))
cnt_1++;
if(ch[pos][1]=='A'){
ll nowk=now,tot=cnt_1,pr=pre[pos][cnt_1],nxtk=now;
//知道目前的数，知道目前cnt，知道之前cnt，求之前数
//因为是&所以在满足k条件下尽量差开，分开放最优
//例如10001
//先放11001再放10111
for(ll i=1;i<=m;i++){
if(tot==G[pos]) break;
if(!(now&(1<<(i-1))))
nowk|=(1<<(i-1)),tot++;
}
tot=cnt_1;
for(ll i=1;i<=m;i++){
if(tot==pr) break;
if(!(nowk&(1<<(i-1))))
nxtk|=(1<<(i-1)),tot++;
}
// printf("nxtk=%lld nowk=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
if(ch[pos][1]=='O')
{
ll nowk=0,tot=0,pr=pre[pos][cnt_1],nxtk=0;
//知道目前的数，知道目前cnt，知道之前cnt，求之前数
//那么向kmp一样或无所谓
for(ll i=1;i<=m;i++)
{
if(tot==G[pos])break;
if(now&(1<<(i-1)))
nowk|=(1<<(i-1)),tot++;
}
tot=0;
for(ll i=m;i>=1;i--)
{
if(tot==pr)break;
if(now&(1<<(i-1)))
nxtk|=(1<<(i-1)),tot++;
}
// printf("nx=%lld no=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
if(ch[pos][1]=='X'){
ll nowk=0,tot=0,pr=pre[pos][cnt_1],nxtk=0,lst=0;
ll chong=(pr+G[pos]-cnt_1)/2;
//计算出重合部分，重合部分就是第一个长度+第二个长度-总1数/2
for(ll i=1;i<=m;i++)
{
if(tot==G[pos]-chong)break;
if(now&(1<<(i-1)))nowk|=(1<<(i-1)),tot++,lst=i;
}
tot=0;
for(ll i=m;i>=lst+1;i--)
{
if(tot==pr-chong)break;
if(now&(1<<(i-1)))nxtk|=(1<<(i-1)),tot++;
}
tot=0;
for(ll i=1;i<=m;i++)
{
if(tot==chong)break;
if(!(now&(1<<(i-1))))nowk|=(1<<(i-1)),nxtk|=(1<<(i-1)),tot++;
}
// printf("nxk=%lld nok=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
}
求方案代码
总代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1010101
ll f[A][32],pre[A][32],G[A],dl[A];
ll x,n,m,c;
char ch[A][6];
bitset<36> b;
void dfs(ll pos,ll now)
{
if(pos==1)
{
printf("%lld ",now);
return ;
}
ll cnt_1=0;
// printf("pos=%lld\n",pos);
for(ll i=1;i<=m;i++)
if(now&(1<<(i-1)))
cnt_1++;
if(ch[pos][1]=='A'){
ll nowk=now,tot=cnt_1,pr=pre[pos][cnt_1],nxtk=now;
//知道目前的数，知道目前cnt，知道之前cnt，求之前数
//因为是&所以在满足k条件下尽量差开，分开放最优
//例如10001
//先放11001再放10111
for(ll i=1;i<=m;i++){
if(tot==G[pos]) break;
if(!(now&(1<<(i-1))))
nowk|=(1<<(i-1)),tot++;
}
tot=cnt_1;
for(ll i=1;i<=m;i++){
if(tot==pr) break;
if(!(nowk&(1<<(i-1))))
nxtk|=(1<<(i-1)),tot++;
}
// printf("nxtk=%lld nowk=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
if(ch[pos][1]=='O')
{
ll nowk=0,tot=0,pr=pre[pos][cnt_1],nxtk=0;
//知道目前的数，知道目前cnt，知道之前cnt，求之前数
//那么向kmp一样或无所谓
for(ll i=1;i<=m;i++)
{
if(tot==G[pos])break;
if(now&(1<<(i-1)))
nowk|=(1<<(i-1)),tot++;
}
tot=0;
for(ll i=m;i>=1;i--)
{
if(tot==pr)break;
if(now&(1<<(i-1)))
nxtk|=(1<<(i-1)),tot++;
}
// printf("nx=%lld no=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
if(ch[pos][1]=='X'){
ll nowk=0,tot=0,pr=pre[pos][cnt_1],nxtk=0,lst=0;
ll chong=(pr+G[pos]-cnt_1)/2;
//计算出重合部分，重合部分就是第一个长度+第二个长度-总1数/2
for(ll i=1;i<=m;i++)
{
if(tot==G[pos]-chong)break;
if(now&(1<<(i-1)))nowk|=(1<<(i-1)),tot++,lst=i;
}
tot=0;
for(ll i=m;i>=lst+1;i--)
{
if(tot==pr-chong)break;
if(now&(1<<(i-1)))nxtk|=(1<<(i-1)),tot++;
}
tot=0;
for(ll i=1;i<=m;i++)
{
if(tot==chong)break;
if(!(now&(1<<(i-1))))nowk|=(1<<(i-1)),nxtk|=(1<<(i-1)),tot++;
}
// printf("nxk=%lld nok=%lld\n",nxtk,nowk);
dfs(pos-1,nxtk);
printf("%lld ",nowk);
}
}
int main(){
scanf("%lld%lld%lld",&n,&m,&c);
for(ll i=2;i<=n;i++){
scanf("%s",ch[i]+1);
}
b|=c;
x=b.count();
// printf("x=%lld\n",x);
for(ll i=1;i<=n;i++){
scanf("%lld",&G[i]);
}
f[1][G[1]]=1;
for(ll i=2;i<=n;i++)
for(ll j=0;j<=m;j++){
if(!f[i-1][j]) continue;
for(ll w=max(0ll,G[i]+j-m);w<=min(j,G[i]);w++){
if(ch[i][1]=='A'){
if(f[i-1][j]==1)
f[i][w]=1,pre[i][w]=j/*,printf("A pos=%lld pre[%lld][%lld]=%lld\n",i,i,w,pre[i][w])*/;
}
if(ch[i][1]=='O'){
if(f[i-1][j]==1)
f[i][j+G[i]-w]=1,pre[i][j+G[i]-w]=j/*,printf("O pos=%lld pre[%lld][%lld]=%lld\n",i,i,j+G[i]-w,pre[i][j+G[i]-w])*/;
}
if(ch[i][1]=='X'){
if(f[i-1][j]==1)
f[i][j+G[i]-2*w]=1,pre[i][j+G[i]-2*w]=j/*,printf("X pos=%lld pre[%lld][%lld]=%lld\n",i,i,j+G[i]-2*w,pre[i][j+G[i]-2*w])*/;
}
}
}
dfs(n,c);
}
View Code