官方网站建设ppt,免费制作ppt,有没有专门做中考卷子的网站,如何做ptp刷流量的网站目录
C.Beautiful Sequence
I.We Love Strings
M.Writing Books C.Beautiful Sequence
思路#xff1a;显然若得到了a[1]#xff0c;则整个序列a我们都知道了。所以我们要求出第k大的a[1]#xff0c;这个可以利用序列a为不递减序列的性质来得出。
首先#xff0c;由题…目录
C.Beautiful Sequence
I.We Love Strings
M.Writing Books C.Beautiful Sequence
思路显然若得到了a[1]则整个序列a我们都知道了。所以我们要求出第k大的a[1]这个可以利用序列a为不递减序列的性质来得出。
首先由题意可得
a[2]a[1]^b[1]
a[3]a[2]^b[2](a[1]^b[1])^b[2]
a[4]a[3]^b[3]((a[1]^b[1])^b[2])^b[3]
......
得出a[i]a[1]^(序列b的前缀i异或和
我们把序列b的前缀i异或和定义为f[i]因为序列a不递减所以
a[i]a[i1] a[1]^f[i-1] a[1]^f[i]
首先我们先初始化a[1]二进制位为-1这代表a[1]的这个位可以是0也可以是1。然后我们再根据a[1]^f[i-1] a[1]^f[i] 这个公式来得出a[1]的哪些位它是确定的不能是-1。
我们需要从高位往低位贪心因为如果a[1]^f[i-1]的一个高位如果是1而a[1]^f[i]的这个位是0那么低位再怎么变a[1]^f[i-1]也必然小于a[1]^f[i]。比如两个二进制数1????和0????就算左边的低位全是1右边的高位全是0也就是变成10000和01111左边依然大于右边。
然后我们从高位到低位怎么贪心呢找f[i]的f[i-1]的从高位到低位第一个不同的位即可我们设这个是第k位。此时a[1]的第k位必须和f[i]第k位的值相同这样子就能让f[i]^a[1]的第k位是0f[i1]^a[1]第k位是1保证了前者小于后者。在此之前a[i]的第k位必须等于-1或者等于f[i]的第k位否则输出-1。
此时我们得到了n个-1的值我们我们最多能表示第2的n次方大的值此时我们只需将k-1拆分成二进制依次填入-1的位置即可。具体实现见代码。
代码
void solve() {a[1]0;mem(now,-1);int n,k;cinnk;for(int i1; in; i) {cinb[i];f[i](f[i-1]^b[i]);}for(int i0; in-1; i) {for(int j29; j0; j--) {if((f[i]j1ll)!(f[i1]j1ll)) {//找到高位第一个不相等的二进制位if(now[j]-1)now[j](f[i]j1ll);else if(now[j](f[i1]j1ll)) {//如果该位已经确定并且与想要填的数相反则输出-1cout-1endl;return;}break;//高位比上一个大了之后就不用再管低位了}}}k--;//去掉初始不变的情况方便替换-1int maxx0;for(int i0; i30; i) {if(now[i]-1)maxxmaxx*21;}if(maxxk) {cout-1endl;return;}vectorintv;while(k) {//将k转换为二进制填入v.push_back({k%2});k/2;}reverse(v.begin(),v.end());for(int i0; i30; i) {if(!v.size())break;//填完了就退出if(now[i]-1) {//依次填入now[i]v.back(),v.pop_back();}}for(int i0; i30; i)now[i]max(now[i],0ll);//把没填的-1变成0for(int i29; i0; i--) a[1]a[1]*2now[i];;//得出a[1]的值couta[1] ;for(int i2; in; i)cout(b[i-1]^a[i-1]) ,a[i](b[i-1]^a[i-1]);//根据a[1]得出整个序列acoutendl;
}
I.We Love Strings
思路因为字符串长度不相同的字符串两两之间肯定不能匹配所以我们根据字符串长度大小来求解。在lenth20时我们暴力枚举字符串所有情况进行求解而在lenth20的时候我们暴力容斥来求解。
那么为什么这个临界值为20呢
我们设临界值为N暴力枚举所有情况的复杂度主要由字符串长度决定复杂度为 而容斥的复杂度主要由容斥的集合大小决定而这个集合的最大大小又由n的最大值和N共同决定它的复杂度为 总的复杂度为他们两个相加。
此时N取太大或者取太小都会使得一方的复杂度过大此时取400的根号也就是N20是最好的。
具体实现见代码。
代码
int pp(vectorintv,string s,int n) {for(int i0; in; i) {if(s[i]!?v[i]!s[i]-0)return 0;//如果两个串确定有位置不同了则匹配失败 }return 1;//匹配成功
}
int f1(int n) {int sum0;for(int i0; i(1n); i) {//枚举这个长度01串的所有可能。 vectorints;for(int j0; jn; j) {s.push_back((ij1ll));} //将枚举的串存入vector for(int i0; iv[n].size(); i) {if(pp(s,v[n][i],n)) {//如果有一个串能和这个枚举的串匹配答案1 sum;break;}}}return sum;
}
int f2(int n) {int mv[n].size(),ans0;//注意i要从1开始若从0开始则会使答案增加 for(int i1; i(1llm); i) {//枚举集合内的串int sum1;for(int j0; jn; j) {//枚举串的每个位 int cnt00,cnt10;for(int k0; km; k) {//表示这是集合内第几个串 if((ik1ll)) {if(v[n][k][j]0)cnt0;if(v[n][k][j]1)cnt1;}}if(cnt0cnt1) {//若该位上确定的数不一致则不能进行容斥 sum0;break;}if(!cnt0!cnt1)sumsum*2%mod;//该位上全是贡献*2 }int now__builtin_popcount(i); if(now%2)ans(anssum)%mod; //进行容斥 else ans(ans-summod)%mod;}return ans;
}
void solve() {int n,ans0;cinn;for(int i1; in; i) {string s;cins;v[(int)s.size()].push_back(s);//将字符串根据长度分类 }for(int i1; i400; i) {if(!v[i].size())continue;if(i20)ans(ansf1(i))%mod;//若长度20则暴力求解 else ans(ansf2(i))%mod;//否则暴力容斥 }coutansendl;
}
M.Writing Books
思路显然1~9对于答案的贡献为1*9,10~99对于答案的贡献为2*90,100~999对于答案的贡献为3*900......。分块求出贡献即可。
代码
void solve() {int n,l1,r10,now1,ans0;cinn;while(ln){if(nr-1)ans(r-l)*now;else ans(n-l1)*now;now,lr,r*10;}coutansendl;
}
