公司网站备案需要什么,汕头app开发,nginx wordpress 管理,省交通建设质安监督局网站范围n-----$100000$ m $30$ 输出方案 这是一个很好的$dp$题 首先我们应该看出来一条性质只要你最后有方案达到$n$个$1$#xff0c;那么你可以达到任何一种$n$个$1$的情况 例如 你最后可以达到$3$个$1$ 那么你可以达到$11100 $ $ 01110$ $01011$ $01101$等方案 证明那么你可以达到任何一种$n$个$1$的情况 例如 你最后可以达到$3$个$1$ 那么你可以达到$11100 $ $ 01110$ $01011$ $01101$等方案 证明题目里说的操作和优美值都是一的个数相关只要我们可以达到$n$个一我们可以通过变换$1$的位置得到多种方案 于是题目里给的$C$我们并不关心我们只关心$1$的个数我们把1都放到最右面,另外这也给我们下面dp提供方便 我们先看各个运算意义 假设你$x$和$y$中有$s$个重复的$1$求各个运算之后一的个数 $\$后$1$的个数就是$s$ 对于$|$我们如果都加的话重复的多加一次 $|$后$1$的个数就是$xy-s$ 重复变为0 ^后$1$的个数就是$xy-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-w*2]max(f[x][G[i]j-w*2],f[x-1][j])$ 注意一下边界以及循环枚举 for(ll wmax(0ll,G[i]j-m);wmin(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(pos1){printf(%lld ,now);return ;}ll cnt_10;
// printf(pos%lld\n,pos);for(ll i1;im;i)if(now(1(i-1)))cnt_1;if(ch[pos][1]A){ll nowknow,totcnt_1,prpre[pos][cnt_1],nxtknow;//知道目前的数知道目前cnt知道之前cnt求之前数//因为是所以在满足k条件下尽量差开分开放最优//例如10001//先放11001再放10111for(ll i1;im;i){if(totG[pos]) break;if(!(now(1(i-1))))nowk|(1(i-1)),tot;}totcnt_1;for(ll i1;im;i){if(totpr) 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 nowk0,tot0,prpre[pos][cnt_1],nxtk0;//知道目前的数知道目前cnt知道之前cnt求之前数//那么向kmp一样或无所谓for(ll i1;im;i){if(totG[pos])break;if(now(1(i-1)))nowk|(1(i-1)),tot;}tot0;for(ll im;i1;i--){if(totpr)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 nowk0,tot0,prpre[pos][cnt_1],nxtk0,lst0;ll chong(prG[pos]-cnt_1)/2;//计算出重合部分重合部分就是第一个长度第二个长度-总1数/2for(ll i1;im;i){if(totG[pos]-chong)break;if(now(1(i-1)))nowk|(1(i-1)),tot,lsti;}tot0;for(ll im;ilst1;i--){if(totpr-chong)break;if(now(1(i-1)))nxtk|(1(i-1)),tot;}tot0;for(ll i1;im;i){if(totchong)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);}
} 求方案代码 总代码 #includebits/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];
bitset36 b;
void dfs(ll pos,ll now)
{if(pos1){printf(%lld ,now);return ;}ll cnt_10;
// printf(pos%lld\n,pos);for(ll i1;im;i)if(now(1(i-1)))cnt_1;if(ch[pos][1]A){ll nowknow,totcnt_1,prpre[pos][cnt_1],nxtknow;//知道目前的数知道目前cnt知道之前cnt求之前数//因为是所以在满足k条件下尽量差开分开放最优//例如10001//先放11001再放10111for(ll i1;im;i){if(totG[pos]) break;if(!(now(1(i-1))))nowk|(1(i-1)),tot;}totcnt_1;for(ll i1;im;i){if(totpr) 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 nowk0,tot0,prpre[pos][cnt_1],nxtk0;//知道目前的数知道目前cnt知道之前cnt求之前数//那么向kmp一样或无所谓for(ll i1;im;i){if(totG[pos])break;if(now(1(i-1)))nowk|(1(i-1)),tot;}tot0;for(ll im;i1;i--){if(totpr)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 nowk0,tot0,prpre[pos][cnt_1],nxtk0,lst0;ll chong(prG[pos]-cnt_1)/2;//计算出重合部分重合部分就是第一个长度第二个长度-总1数/2for(ll i1;im;i){if(totG[pos]-chong)break;if(now(1(i-1)))nowk|(1(i-1)),tot,lsti;}tot0;for(ll im;ilst1;i--){if(totpr-chong)break;if(now(1(i-1)))nxtk|(1(i-1)),tot;}tot0;for(ll i1;im;i){if(totchong)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 i2;in;i){scanf(%s,ch[i]1);}b|c;xb.count();
// printf(x%lld\n,x);for(ll i1;in;i){scanf(%lld,G[i]);}f[1][G[1]]1;for(ll i2;in;i)for(ll j0;jm;j){if(!f[i-1][j]) continue;for(ll wmax(0ll,G[i]j-m);wmin(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][jG[i]-w]1,pre[i][jG[i]-w]j/*,printf(O pos%lld pre[%lld][%lld]%lld\n,i,i,jG[i]-w,pre[i][jG[i]-w])*/;}if(ch[i][1]X){if(f[i-1][j]1)f[i][jG[i]-2*w]1,pre[i][jG[i]-2*w]j/*,printf(X pos%lld pre[%lld][%lld]%lld\n,i,i,jG[i]-2*w,pre[i][jG[i]-2*w])*/;}}}dfs(n,c);
} View Code 转载于:https://www.cnblogs.com/znsbc-13/p/11361565.html
