题解 [eJOI 2022] Adjacent Pairs前言题目跳转 : QOJ4925 和 洛谷P13781。本人在 NOIP 模拟上遇到此题作为 T1。题面给一个长为n nn的序列求至少单点赋值多少次后使过程中任何操作后使相邻两数不同且最后的序列仅有两个不同的值求最少操作次数。题解首先因为结束时相邻两数不同且最后的序列仅有两个值所以一定是形如a b a b a b a\text{ }b\text{ }a\text{ }b\text{ }a\text{ }bababab这样的交替出现的序列。然后我们可以枚举a aa和b bb并快速求出所需的次数具体地如果奇数位上已经是a aa那么不用直接修改偶数位同理其它的位置会花费至少一次代价为什么是至少呢首先到达对应的值需要一次然后如b a b b\text{ }a\text{ }bbab这样的情况直接修改中间的a aa成为b bb是错误的要先将中间的a aa修改成为c ( c ≠ a , c ≠ b ) c(c\ne a,c\ne b)c(ca,cb)就是b c b b\text{ }c\text{ }bbcb然后修改b bb成为a aa再修改c cc成为b bb才行。所以说对于连续交替出现的b a b a b b\text{ }a\text{ }b\text{ }a\text{ }bbabab其中第一位应当出现a aa或者a b a b a a\text{ }b\text{ }a\text{ }b\text{ }aababa其中第一位应当出现b bb所多花的代价为a aa和b bb出现次数的最小值显然故答案为( n − c n t 1 , a − c n t 0 , b − f ( b , a ) ) f ( b , a ) × 2 n − c n t 1 , a − c n t 0 , b f ( b , a ) (n-cnt_{1,a}-cnt_{0,b}-f(b,a))f(b,a)\times 2n-cnt_{1,a}-cnt_{0,b}f(b,a)(n−cnt1,a​−cnt0,b​−f(b,a))f(b,a)×2n−cnt1,a​−cnt0,b​f(b,a)其中c n t 0 , x cnt_{0,x}cnt0,x​表示偶数位上x xx的出现次数c n t 1 , x cnt_{1,x}cnt1,x​表示奇数位上x xx的出现次数f ( a , b ) f(a,b)f(a,b)为上述情况的答案注意f ( a , b ) f(a,b)f(a,b)不一定等于f ( b , a ) f(b,a)f(b,a)因为它们意义不同可以发现有f ( a , b ) ∑ l , r ⌊ r − l 1 2 ⌋ f(a,b)\sum\limits_{l,r}\lfloor\frac{r-l1}2\rfloorf(a,b)l,r∑​⌊2r−l1​⌋其中l , r l,rl,r为连续段的左右端点且f ( a , b ) f(a,b)f(a,b)与c n t cntcnt可以预处理f ( a , b ) f(a,b)f(a,b)可以使用mappairint,int,int进行存储详见代码30pts。最后考虑优化发现到f ( a , b ) ≠ 0 f(a,b)\ne 0f(a,b)0的不超过n nn个所以枚举a aa然后枚举满足f ( a , b ) ≠ 0 f(a,b)\ne 0f(a,b)0的b bb这很容易用vector实现然后对于剩下的情况直接考虑最大的c n t 0 , c cnt_{0,c}cnt0,c​且f ( a , c ) 0 f(a,c)0f(a,c)0直接按c n t 0 , c cnt_{0,c}cnt0,c​从大到小枚举第一个不在map中的即可可能看代码100pts比较好理解。代码30pts#includeiostream#includevector#includealgorithm#includemapusingnamespacestd;chars[120],*p,*q;#definegc()(((pq(p(qs)fread(s,1,120,stdin))),pq)?EOF:*q)inlineintread(){intres0;boolsignfalse;charcgc();for(;!isdigit(c);cgc())if(c-)signtrue;for(;isdigit(c);cgc())resres*10c-0;returnsign?-res:res;}intt,n;vectorinta[2],c;mappairint,int,intb;voiddoes(){nread(),a[0].clear(),a[1].clear(),a[0].resize(n1),a[1].resize(n1),c.clear(),c.resize(n1),b.clear();for(inti1;in;i)a[i1][c[i]read()];for(inti1;in;)if(in){intac[i],aac[i1],lasi1;for(intposi2,j0;posn;pos,j!j)if((!jc[pos]!a)||(jc[pos]!aa))break;elselas;if((i1)1)b[{a,aa}](las-i1)/2;elseb[{aa,a}](las-i1)/2;ilas;}intansn;for(inti1;in;i){for(intj1;jn;j)if(i!j)ansmin(ans,n-a[1][i]-a[0][j]b[{j,i}]);}coutans\n;}signedmain(void){ios::sync_with_stdio(0),cin.tie(0);tread();while(t--)does();return0;}100pts#includeiostream#includevector#includealgorithm#includemapusingnamespacestd;chars[120],*p,*q;#definegc()(((pq(p(qs)fread(s,1,120,stdin))),pq)?EOF:*q)inlineintread(){intres0;boolsignfalse;charcgc();for(;!isdigit(c);cgc())if(c-)signtrue;for(;isdigit(c);cgc())resres*10c-0;returnsign?-res:res;}intt,n;vectorinta[2],c;mappairint,int,intb;voiddoes(){nread(),a[0].clear(),a[1].clear(),a[0].resize(n1),a[1].resize(n1),c.clear(),c.resize(n1),b.clear();for(inti1;in;i)a[i1][c[i]read()];vectorvectorintnum(n1);vectorpairint,intcop;for(inti1;in;i)cop.push_back({-a[0][i],i});sort(cop.begin(),cop.end());for(inti1;in;)if(in){intac[i],aac[i1],lasi1;for(intposi2,j0;posn;pos,j!j)if((!jc[pos]!a)||(jc[pos]!aa))break;elselas;if((i1)1)b[{a,aa}](las-i1)/2,num[aa].push_back(a);elseb[{aa,a}](las-i1)/2,num[a].push_back(aa);ilas;}intansn;for(inti1;in;i){for(intj:num[i])ansmin(ans,n-a[1][i]-a[0][j]b[{j,i}]);for(intj0;jn;j)if(b.find({cop[j].second,i})b.end()cop[j].second!i){ansmin(ans,n-a[1][i]cop[j].first);break;}}coutans\n;}signedmain(void){ios::sync_with_stdio(0),cin.tie(0);tread();while(t--)does();return0;}注关于for(int i1;in;i) cop.push_back({-a[0][i],i});一行因为要从大到小排序所以取负最后本来应为n-a[1][i]-cop[j].first但是因为前面已经取负所以是n-a[1][i]cop[j].first。后记同步发表于个人 洛谷专栏 作为 题解仅供参考。