P7853 「EZEC-9」进位
题目背景
规定popcount ( x ) \text{popcount}(x)popcount(x)表示x xx在二进制表示下所含1 11的个数。
题目描述
您有一个二进制数B BB（以一个长为n nn的01 0101字符串形式给出）和长为m mm的序列a aa。
同时，您还需要对B BB进行m mm次操作。
其中，第i ii个操作为B ← B + 2 a i B \gets B + 2^{a_i}B←B+2ai，其价值v i v_ivi为B BB在操作前后变化的位置数量，即v i = popcount ( B x o r ( B + 2 a i ) ) v_i = \operatorname{popcount}(B \mathbin{\mathrm{xor}} (B + 2^{a_i}))vi=popcount(Bxor(B+2ai))。
您需要解决两个问题：
您可以任意安排操作顺序，问在执行所有操作后，∑ i = 1 m v i \displaystyle \sum_{i=1}^mv_ii=1∑mvi最大为多少？
您可以任意安排操作顺序，问在执行所有操作后，max i = 1 m v i \displaystyle \max_{i=1}^mv_ii=1maxmvi最大为多少？
输入格式
第一行两个整数n , m n,mn,m。
第二行一个长为n nn的01 0101字符串，表示二进制数B BB，从低位到高位依次给出。
第三行m mm个整数a 1 , a 2 , … , a m a_1,a_2,\dots,a_ma1,a2,…,am。
输出格式
第一行一个整数，表示第一问的答案。
第二行一个整数，表示第二问的答案。
本题使用 Special Judge，若您的第一问答案正确，可以获得该测试点30 % 30\%30%的分数，若您的第二问答案正确，可以获得该测试点另外70 % 70\%70%的分数。
若您只回答了两问中的一问，请在另一个位置输出一个非负整数。
输入输出样例 #1
输入 #1
5 6 10110 1 0 2 2 2 2输出 #1
14 6输入输出样例 #2
输入 #2
10 10 0101010110 0 1 2 3 4 5 5 4 3 2输出 #2
21 9输入输出样例 #3
输入 #3
10 3 1111101111 5 5 0输出 #3
13 11说明/提示
【样例解释 #1】
对于第一问，依次执行第1 , 2 , 6 , 5 , 4 , 3 1,2,6,5,4,31,2,6,5,4,3个操作可得到∑ i = 1 m v i = 14 \displaystyle \sum\limits_{i=1}^mv_i=14i=1∑mvi=14。
对于第二问，依次执行第6 , 5 , 4 , 3 , 1 , 2 6,5,4,3,1,26,5,4,3,1,2个操作可得到max i = 1 m v i = 6 \displaystyle \max\limits_{i=1}^mv_i=6i=1maxmvi=6。
详细过程
【数据范围】
本题采用捆绑测试。
- Subtask 1（20 points）：n , m ≤ 10 n,m\leq 10n,m≤10。
- Subtask 2（30 points）：n , m ≤ 1000 n,m\leq 1000n,m≤1000。
- Subtask 3（20 points）：B BB中全为0 00，且a 1 = 0 a_1=0a1=0，∀ i > 1 , a i − 1 ≤ a i ≤ a i − 1 + 1 \forall i>1, a_{i-1}\leq a_i\leq a_{i-1}+1∀i>1,ai−1≤ai≤ai−1+1。
- Subtask 4（20 points）：n , m ≤ 10 5 n,m\leq 10^5n,m≤105。
- Subtask 5（10 points）：无特殊限制。
对于100 % 100\%100%的数据，1 ≤ n , m ≤ 10 6 1\leq n,m\leq 10^61≤n,m≤106，0 ≤ a i < n 0\leq a_i< n0≤ai<n。
C++实现
#include<iostream>#include<cstdio>usingnamespacestd;inta[2000010],b[2000010],c[2000010];//b用于计算第一问，c用于计算第二问intmain(){intn,m,maxm=1;scanf("%d %d\n",&n,&m);//maxm设为1而非0registerintans=0;for(registerinti=0;i<n;++i){chargjr=getchar();b[i]=(int)(gjr-'0');c[i]=b[i];}for(registerinti=1;i<=m;++i){scanf("%d",&a[i]);}for(registerinti=1;i<=m;++i){intpt=a[i];++b[pt];//进行操作++c[pt];++ans;//更新价值while(b[pt]==2){//处理进位b[pt++]=0;++b[pt];++ans;}}for(registerinti=0;i<n;++i){if(c[i]>=2){registerintgjr=i,maxl=1;//maxl是当前处理的连续进位的价值while(c[gjr]>=2){++maxl;//能够进位就加1c[gjr+1]+=c[gjr]/2;//处理进位c[gjr++]&=1;}maxm=max(maxl,maxm);}}printf("%d\n%d",ans,maxm);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
