什么软件能看网站?,江苏已经宣布封城的城市,静态网站后台管理系统,项目管理证书 pmpBeautiful Sequence 贪心#xff0c;二进制#xff0c;构造 Cyperation 模拟 #xff0c;数学 We Love Strings 分块#xff0c;二进制枚举#xff0c;二进制容斥dp Writing Books 签到 根据相邻两个异或值B#xff0c;因为前小于等于后#xff0c;故从高到低遍历B的每一… Beautiful Sequence 贪心二进制构造 Cyperation 模拟 数学 We Love Strings 分块二进制枚举二进制容斥dp Writing Books 签到 根据相邻两个异或值B因为前小于等于后故从高到低遍历B的每一位时第一个是1的位置一定决定了前者与后者的大小关系。且前者这一位必定是0后者这一位必定是1。有根据B的前缀异或和是A1^Ai,如果A1^Ai这一位是0那么A1这一位必定填1否则必定填0。 这样处理之后A1会形成若干确定的填法。而对于剩余没能确定的也就是字典序产生的由来。继续从高到低遍历每一位当前位置i若没有确定如果位置i之前(所有小于位置i)的有x的没有确定的那么当前填0的贡献为(1x),这一贡献如果大于等于k,这一位就必定是0否则这一位必定是1。 #includebits/stdc.h
using namespace std;
typedef long long int ll;
const int N1e65;
long long n,k,b[N],T,c[N],d[50];
ll qp(ll base,ll pow)
{ll ans1;while(pow){if(pow1)ansans*base;pow1;basebase*base;}return ans;
}
int main()
{cinT;while(T--){cinnk;int f1;for(int i1; in; i)cinb[i],c[i]c[i-1]^b[i];int t0;memset(d,-1,sizeof(d));for(int i1; inf; i){for(int j29; j0; j--){if(b[i]j) {if(d[j]!-1d[j]!1^((c[i]j)1)){f0;break;}d[j]1^((c[i]j)1);break;}}}int pre[50];memset(pre,0,sizeof(pre));pre[0](d[0]-1);for(int i1; i29; i){pre[i]pre[i-1];if(d[i]-1)pre[i];}for(int i29; i1; i--){if(d[i]-1){ll tempqp(2ll,pre[i-1]);if(ktemp){d[i]0;}else{d[i]1;k-(temp);}}}if(d[0]-1){if(k1){d[0]0;}else if(k2){d[0]1;k1;}}if(k1||f0)puts(-1);else{int p0;for(int i29; i0; i--){pp1|d[i];}for(int i0; in; i){printf(%d ,(p^c[i]));}puts();}}
}首先一个大环可以拆成若干互不影响的小环。先拆环为链即设a1和ak共同减去了x,则接下来的删除是固定方向的由a1开始到ak结束。上图为偶数情况一个合法的x要满足每一轮相减的剩余量都大于等于0最后的a4剩余量为0.这一过程维护x的取值范围判断合法即可。 对于奇数同理只是多了一个判断剩余量是否能够整除2和整除解出来的x是否合法。 #includebits/stdc.h
using namespace std;
typedef long long int ll;
int vis[100000010],a[100000010];
int main()
{cin.tie(0);ios::sync_with_stdio(0);int t;cint;while(t--){int n,k;cinnk;int zero0;for(int i1; in; i){cina[i];if(a[i])zero1;vis[i]0;}if(kn/2){if(zero){coutNO\n;}elsecoutYES\n;continue;}int flag1;for(int i1; in; i){if(vis[i])continue;int nowi;ll temp0;int op1;ll L-1e18,R1e18;//cout endl;while(!vis[now]){vis[now]1;// coutnow ;if(op1){Rmin(R,a[now]-temp);}else{Lmax(L,temp-a[now]);}op^1;tempa[now]-temp;nowk;now%n;if(now0)nown;}if(LR){flag0;break;}if(op1){if(temp0)continue;flag0;}if(op0){if(temp%2){flag0;continue;}temp/2;if(tempL||tempR){flag0;continue;}}}if(flag0){coutNO\n;}else{coutYES\n;}}return 0;
}这题可以分块做400给的很巧妙这就意味这长度小于20的可以暴力枚举长度大于20的不会超过20个仍然可以暴力枚举。 对于前者相同长度的可以暴力枚举每一位01情况然后进行检查一旦检查出可以的就答案 对于后者也是相同长度的暴力枚举但枚举方式变为这x个字符串哪个参与匹配哪个不参与。对于一个枚举出的方案若合法(已知位置不冲突)则这一方案的方案数为其不确定位置的个数的2次幂。但直接统计肯定会有重复。因为如2 3 4组成的集合方案数就包含了2 3 4 5的方案数。这种重复出现在2 3 4组成集合的问号区域乘了2这个2就包含了2 3 4 5的部分。故需要从2 3 4方案数里面减去。按照二进制容斥原理来说就是满足小集合的方案数里面包含了满足大集合的需要从小集合里面容斥掉大集合的。 #include bits/stdc.h
using namespace std;
typedef long long int ll;
vectorstringv[410];
int n;
ll ans;
# define mod 998244353
void workxiao(int len)
{if(v[len].size()0)return ;for(int i0;i(1len);i){for(auto it:v[len]){int flag0;for(int j0;jlen;j){if((i(1j))){if(it[j]0)flag1;}else{if(it[j]1)flag1;}}if(flag0){ans;ans%mod;break;}}}
}
ll dp[(122)],pre[410];
void init()
{pre[0]1;for(int i1;i400;i){pre[i]pre[i-1]*2ll%mod;}
}
int check(string now)
{int ans0;for(int i0;inow.length();i){ans(now[i]?);}return ans;
}
void workda(int len)
{if(v[len].size()0)return ;int nownv[len].size();string temp;for(int i0;ilen;i){temp?;}for(int i1;i(1nown);i){dp[i]0;string nowtemp;int flag0;for(int j0;jnown;j){if((i(1j))){for(int k0;klen;k){if(v[len][j][k]!?){if(now[k]?){now[k]v[len][j][k];}else{if(now[k]!v[len][j][k]){flag1;break;}}}}}if(flag)break;}if(flag0)dp[i]pre[check(now)];}for(int i1;i(1nown);i){for(int j0;jnown;j){if((i(1j))){dp[(i^(1j))]((dp[(i^(1j))]-dp[i])%modmod)%mod;}}}for(int i1;i(1nown);i){ansdp[i];ans%mod;}}
int main()
{init();cinn;for(int i1;in;i){string s;cins;v[(int)(s.length())].push_back(s);}for(int i1;i20;i){workxiao(i);}for(int i21;i400;i){workda(i);}coutans;return 0;
}签到题不赘述
