Educational Codeforces Round 135 (Rated for Div. 2) C. Digital Logarithm算法本质思维（贪心）思路推演显然，为了达到最小操作数的目的，要在数大的时候尽量都给抵消了，实在不行才操作：如果a[]和b[]中有重复元素，则移动到一边不变（也可以看作相互抵消了）。然后我们选择具有部分特征的元素进行操作，然后再比较，一直重复这个过程直到完全抵消。通过手动模拟，抓住了一个简单的性质，给数字划分等级。一级：{1} 二级：{2~9} 三级：{10~1e9-1}可以看到，每次对一个数字操作，其都会变成低一级中的对应数字。我们先对a[] b[]中等级为三级的元素，存在相等情况就抵消。剩余的三级元素则全部进行操作，变为二级元素，然后再检查能否抵消，最后不行的变为一级元素——一定相同可抵消了。这个代码实际上就会有2个操作：相互抵消，可以选择map或者双指针(queue)的方式对更高一级的元素进行操作，随意即可——暴力复杂度也可以承受的在代码写出框架后会发现，好像完全没有必要分为多个阶段的操作，我们可以使用priority_queue<int>来排序剩下的元素，然后选择a[]剩下的元素中最大ai和b[]剩下的元素中最大bi，如果两者相等，则抵消；若不等则选择较大值操作。这样的话，实质是把上面的2个操作合并在一起了，但代码中两者可以同时进行——类似于也被我叫做“边输入边计算”的东西。代码思路priority_queue <int> qa, qb放a[]和b[]的元素。同时取出qa.top()和qb.top()，相等则抵消，不等则取大者操作。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int suan(int x) //返回x的长度 { return log10(x)+1; } inline void solve() { // init cin>>n; priority_queue <int> qa, qb; rep(i,1,n) { int a; cin>>a; qa.push(a); } rep(i,1,n) { int b; cin>>b; qb.push(b); } //cal 2 int cnt=0; while(!qa.empty()) { int a=qa.top(), b=qb.top(); if (a==b) //相等——抵消 { qa.pop(); qb.pop(); } else if (a>b) //不等——取大的操作 { qa.pop(); qa.push( suan(a) ); cnt++; } else { qb.pop(); qb.push( suan(b) ); cnt++; } } //out ans = cnt; cout<<ans<<endl; return; }D. Letter Picking算法本质dp、思维（博弈论）思路推演思维题，特别还是博弈论，就一定得从小规律找起，推导到全局。部分简单的手动模拟： bb 平局 ab alice赢 ba alice赢 abba 平局 abcd alice赢可以看到，当长度大于2时，就没有一个相对简单的规律了。但是这道题有很明显的博弈论的意味，博弈论的精髓就在于，俩人各走一步为一个回合，以回合为单位推进转换——这里就和dp的状态转移对应上了，所以博弈论sg组合数的解决方法是用dp的方式呈现的。同时，通过大量的模拟，我们发现好像并没有bob赢的情况，猜测bob可能最多平局，于是开始推理。定理1：若只剩下2个不同的字符，则一定是alice赢。 定理2：若字符串是由一对一对组成的(aabbbbcc)，那一定是平局。 bob能赢的唯一途径：所以最好能让bob在某次选择中先占得先机，最后剩下2个一样的字符，类似于——bacc，让alice选择b，bob选择a。 基于此，alice可以选择优先破坏成对的字符，使得最后剩下2个不一样的字符，这波坏了bob赢的途径。 所以，bob一定不会赢。推出bob一定不会赢，可以很好的简化代码逻辑。我们现在可以简单的定义，bob一心想着平局，alice一心想着不平局。因为只能从左边or右边拿字符，这个博弈论的可能性很低，将会比较好做。假设原字符串为abxxxxcd（xxxx表示偶数个未知字符）（橘色线条代表alice可以走的，蓝色线条代表bob可以走的）若abxxxxcd为平局，有两个可能：中间的bxxxxc为平局 && a==dxxxxcd平局 && a==b && abxxxx平局 && c==d其他则都是alice赢。上面这推理，其实也就是dp里的状态转移方程。若不推出bob的情况，也是可以做的，只是说逻辑会相对复杂。代码思路dp，从底层开始推理。维护cun[][]cun[l][r]=v表示[l,r]，v=0表示未知，还需要自己去求，v=1表示这个点alice会赢，v=2表示会平局。然后用对长度为2的字符串节，对cun[][]初始化。接着长度依次增加2，通过状态转移方程计算。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int cun[maxn][maxn]; //cun[l][r]=v表示[l,r]，v=0表示未知，还需要自己去求，v=1表示这个点alice会赢，v=2表示会平局，v=3表示bob会赢 inline void solve() { // init scanf("%s", ch+1); n = strlen(ch+1); // cal for (int i=1; i<=n-1; i++) //初始化 cun[i][i+1] = 1 + (ch[i]==ch[i+1]); for (int len=4; len<=n; len+=2) { for (int l=1; l+len-1<=n; l++) { int r = l+len-1; //状态转移方程（逻辑） if (cun[l+1][r-1]==2 && ch[l]==ch[r]) cun[l][r]=2; else if (cun[l][r-2]==2 && cun[l+2][r]==2 && ch[l]==ch[l+1] && ch[r]==ch[r-1]) cun[l][r]=2; else cun[l][r]=1; } } //out flag = cun[1][n]==1; if (flag) cout<<"Alice"<<endl; else cout<<"Draw"<<endl; return; }题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round #832 (Div. 2) D. Yet Another Problem算法本质思维题目大意给定一个长度为n的数组arr[]，下面给出m此询问，每次询问给出l r。需要回答，对于arr[l~r]，我们可以最少进行多少次操作，使得其元素全部为0（无法输出-1）。一次操作定义：选定arr[l~r]内连续的奇数个元素，设x为这些元素异或运算，然后将在arr[]这奇数个元素全部赋为x。思路推演梳理思路，显然我们需要找到一个可以通用的、死板的方法来方便解题。在各种猜测、尝试后，第一个问题映入脑海：某个元素变为0，是否会存在中间过程，还是说一步到位。如果是存在中间步骤，则肯定是会对下一次操作有利的。通过这个点，我们可以很快推出：元素变为0是一步到位的。思维部分最难想到的地方就是这一步了，当推出这个结论后，无数多个结论就蜂拥而至：元素总个数为奇数时，是会被化为奇数个操作搞定的——>奇数个操作，可以直接融合为1次操作元素总个数为奇数时，如果能被操作，是被1次或者2次操作搞定的……进一步分类：元素个数为奇数： 元素和为0（元素全部为0）次数为：0 元素异或运算值不等于0：-1 元素异或运算值等于0：1 元素个数为偶数： 元素和为0（元素全部为0）次数为：0 元素异或运算值不等于0：-1 元素异或运算值等于0： { 若能划分出2个连续的奇数块，且这两个连续的奇数块都必须异或和为0，则：1 或 2 （若其中一个奇数块全为0则选择1） 若无法满足上述要求：-1 }接下来就需要查询复杂度：重点在于，如何O(log~2~n)查询到是否存在这样的奇数块呢？继续推理：若第一个奇数块异或为0，且整体异或为0，则第二个奇数块异或也为0。怎么判断是否存在一个以l为下标的奇数块异或为0呢：异或性质！设xsum[y]表示arr[1~y]的元素异或值设i表示第一个奇数块的末尾下标，若存在i使得xsum[i] == xsum[l-1] && i-l+1为奇数，则说明arr[l~i]元素异或值为0，即第一个奇数块！ac核心代码记得关流！头文件、宏定义、快读模板、常见变量、常见变量等略。 int sum[maxn], xsum[maxn]; //sum[]前缀和，xsum[]异或前缀 int gsum(int l, int r) { return sum[r] - sum[l-1]; } int gxsum(int l, int r) { return xsum[r] ^ xsum[l-1]; } map<int, vector<int>> mp1, mp2; //mp1用来存放奇数下标的异或前缀和，mp2存偶数 //mp[异或前缀]里放的是下标集合 inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>ar[i]; rep(i,1,n) { sum[i] = sum[i-1] + ar[i]; //搞定前缀和、异或前缀和 xsum[i] = xsum[i-1] ^ ar[i]; } for (int i=0; i<=n; i++) { if (i%2==1) mp1[xsum[i]].push_back(i); //奇数下标的异或前缀和 else mp2[xsum[i]].push_back(i); //偶数下标的异或前缀和 } //cal while (m--) { int l, r, len; cin>>l>>r; len = r-l+1; //长度 //cal if (gsum(l, r)==0) //全是0的情况，不需要出手 ans=0; else if (gxsum(l, r)!=0) //如果异或和不为0，直接G ans=-1; else if (len%2==1) //奇数，不全为0，且可以操作得到0，则只需要一次操作 ans=1; else if (ar[l]==0 || ar[r]==0) //偶数区间的特殊情况，可以看作一个奇数区间 ans=1; else //偶数，不全为0，也许可以操作得到0，还需要进一步判断 { vector <int> *pv; //奇数下标的异或前缀和 if (l%2==1) pv=&mp1[xsum[l-1]]; //奇数下标 else pv=&mp2[xsum[l-1]]; //偶数下标 auto it = lower_bound((*pv).begin(), (*pv).end(), l); //找到第一个大于l的下标 if (it!=(*pv).end() && *it<=r) //如果存在，且小于等于r，说明可以操作得到0 ans=2; else ans=-1; } //out cout<<ans<<endl; } return; }

Codeforces Round #822 (Div. 2) C. Removing Smallest Multiples算法本质思维（贪心）思路推演对于每个缺失的值，我们肯定是希望它用尽可能小的因数来去掉。但是举例12，12的因数2。要想12用因数2来去掉，就需要保证2、4、6、8、10、12都是缺失的。显然，如果我们先找值，再找值的因数，选取最小的，这样复杂度是一定过不了的。所以得先找因数。历遍每个因数，我们寻找其能达到的值，一旦这个某个值并非丢失，则继续。这样复杂度大约是O(nlog~2~n)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 char ch2[maxn]; inline void solve() { cin>>n; scanf("%s", ch+1); //ch[]来表示值是否缺失 rep(i,1,n) ch2[i]=ch[i]; //ch2[]来表示值是否已经被填充，避免重复 ans=0; for (int i=1; i<=n; i++) { for (int pos=i; pos<=n; pos+=i) { if (ch[pos]=='1') break; //遇到不缺失的值了 if (ch2[pos]=='0') //填充 { ch2[pos]='1'; ans+=i; } } } cout<<ans<<endl; return; }D. Slime Escape算法本质思维思路推演这道题跟多校的一个题，思路和模型都很类似，算是那个题的简单版本。题目稍加推理可知，走出去的方法可以归纳为：先走x方向，再走y方向，……，吸纳足够的能量，然后向另一方向冲出去。关键就在于，每次走的时候，应该走到什么地方停下。基础操作围绕核心的点——能量，只要能保证能量收益是正的即可。所以我们假装向某个方向前进，设定走到停下来的条件：收益是大于等于0（那就真的走过去）整体能量为负（那就换个方向）触边（说明成功走出去了）同时，再加一个触发机制——要是连续左右没有更新则表明不能走通。ac核心代码PS：代码看起来多，主要是有大循环里有左右两个方向的代码，重复了许多。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>k; rep(i,1,n) cin>>arr[i]; //cal int l=k-1, r=k+1; //l r表示边界，表示还没走到的地方 ans=arr[k]; flag=0; while (1) { //cal1 计算向左走 int da=ans; //模拟整体能量值——要是能走，就赋值，不能就不动 int yuan_l = l; //记录原来的l位置 int cnt=0; //cnt表示连续不更新的次数，要是cnt==2说明走不通 while (1) //向左边挖洞 { if (da>ans && arr[l]<0) break; //整体收益大于等于0 if (l==0) break; //触碰到边界 if (da+arr[l]<0) break; //保证整体能量大于等于0 da += arr[l]; l--; } if (l==0 || r==n+1) //先判断是否走出来 { flag=1; break; } if (da>=ans) //有收益，则走 ans=da; else //负收益，不走 l=yuan_l; if (yuan_l != l) cnt++; //说明没有更新 //cal 2 计算向右走 da=ans; int yuan_r = r; while (1) //向右边挖洞 { if (da>ans && arr[r]<0) break; //整体收益大于等于0 if (r==n+1) break; //触碰到边界 if (da+arr[r]<0) break; //保证整体能量大于等于0 da += arr[r]; r++; } if (l==0 || r==n+1) //先判断是否走出来 { flag=1; break; } if (da>=ans) ans=da; else r=yuan_r; if (yuan_r != r) cnt++; //计算是否走不通 if (cnt==0) //说明左右目前都走不通，那就算了呗 break; } //out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }E. Rectangular Congruence算法本质思维、（一点）数学思路推演这种题目好像被称之为构造题，叫做数学题也可以吧。不管叫做什么名称，存在这样明确的数学条件（素数、方阵、算式），就一定需要使用数学方法推导出结论，来帮助更好地用代码去解决。a(x,x)+a(y,y) != a(x,y)+a(y,x) --> a(x,x)-a(y,x) != a(x,y)-a(y,y)第二个式子明显有强烈的视觉规律——这4个点，两列，每列的上点减下点的差，不允许相等。（结合方阵中只有主对角线有确定值，可以推断出整个方阵的规律只有相对差值有关系）这个时候，就很容易想到一个思路：各列相邻两点的差值分别固定0 1 2 ... n-1。用具体的数据验证一下，果然是可行的。再结合式子简单分析，发现也是可行的。思路回顾数学题实际推出式子后就十分简单了。作为编程题，大多时候所谓的数学题也不会是枯燥单纯的证明，比如此题是与图形方阵结合，还有的题与位运算结合。也许一些条件、式子看起来毫无章法，但是对其演化，尝尝能得到不错的结果。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void mo(int &x) //方便取余 { x %= n; if (x < 0) x += n; } int mp[maxn][maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>mp[i][i]; //cal for (int c=1; c<=n; c++) //c：列下标 { int add=c-1; //每列的相邻相差值 for (int r=c-1; r>=1; r--) //向上填充 { mp[r][c] = mp[r+1][c]-add; mo(mp[r][c]); } for (int r=c+1; r<=n; r++) //向下填充 { mp[r][c] = mp[r-1][c]+add; mo(mp[r][c]); } } //out rep(i,1,n) { rep(j,1,n) cout<<mp[i][j]<<" "; cout<<endl; } return; }题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round #819 (Div. 1 + Div. 2) D. Edge Split算法本质思维思路推演找规律，要从小规律开找，然后推广。自己拿张纸，任意画个小图，然后其中的边变化颜色：比如全涂红、随机涂等等。就会发现了规律：涂边时，相同颜色边不成环收益 > 成环收益。多试几个图，再根据这个规律总结数学公式，会发现果真如此。题目表示，边数m最多为n+2。所以选择首先先弄一棵树出来，数全为红色，剩下的为蓝色。现在唯一需要担心的是，蓝色部分最多有3条边，可能构成环，那得替换一条边，那应该怎么样替换才能使得替换后大家都没有环呢？又拿出一张纸，开始画图，自己动手……然后发现，替换任意一蓝边都是可行的。随机找一条边，设其中的两个点为u v，红边的选择必须是u v到其最近公共组先的路径上的边。因为这题的性质，特别是只找路径中一个边即可，所以并不用搞一套最近公共组先模板，设u v两点其中深度更大的点是v，那红边设定位v--fu[v]即可。注意，因为最后的输出结构，所以需要记录所有边的下标。代码思路建树，同时维护dep[]、fu[]ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round #818 (Div. 2) A. Madoka and Strange Thoughts算法本质思维思路推演这个题值得注意的一个点就是，在考虑2个数的gcd()、lcm()类似的函数时，可以把这两个数设为ak和bk，保证gcd(a, b)==1。如果使用这个思路，则这个题能够秒解出来。按照题目的要求则把式子化简为：a*b<=3，那就只有数种情况。比如当n=10时，我们把k分为三段。第一段是k为1~3。a b则有5种情况：1 1、1 2、2 1、1 3、3 1。第二段是k为4~5。a b若取3则会超出n，所以只有3种情况：1 1、1 2、2 1。第三段是k为6~10。a b若取2、3则会超出n，所以只有1种情况：1 1。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 ans = 5*(n/3) + 3*(n/2-n/3) + 1*(n-n/2);B. Madoka and Underground Competitions算法本质思维、模拟思路推演最基础的性质就是，同一行、列X之间的距离为k。所以最能第一时间想到的方法是，通过(r, c)把周围必须填的点填上，同时记录哪些行和列已经被填写。然后找到没有填写的行和列，一行+一列为一组，这组把中间交叉的点填上，然后把周围的点天上，记录填写上的行和列。数学上可以证明，不会有重合的部分。但是这样做显得有点过头。题目只会给出一个固定的点，实际完全没有必要采用这样的饱和式攻击。看样例1的第三个情况，就很容发现一种填法，那就是斜着填写。这种填写方法只是正确答案中的一种，但是足够覆盖题目的要求了。（如果题目会给出多个点，这个方法就不能行了）以斜着填写思路为主，稍加思索可知：对于(r, c)，我们先把这一列所有应该填写的点找出来（包括(r,c)），放入集合s，然后集合s里的点，都固定向斜着填写（4个斜着的方向都行），直到再次回来这一列停止。思路回顾简单的一个通过性质写模拟的题目，这种就要留心观察，是否能有一个更加简洁的式子。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int mp[maxn][maxn]; int k, sx, sy; void dfs(int x, int y) { if (x>n) x-=n; if (x<1) x+=n; if (y>n) y-=n; if (y<1) y+=n; if (y==sy) return; mp[x][y]=1; dfs(x+1, y+1); } inline void solve() { // init cin>>n>>k>>sx>>sy; mem(mp, 0); //cal vector <int> row; for (int xx=(sx-1)%k+1; xx<=n; xx+=k) { row.push_back(xx); //记录这一列都应该填写的点的行坐标 mp[xx][sy]=1; } for (int x:row) dfs(x+1, sy+1); //out rep(i,1,n) { rep(j,1,n) { if (mp[i][j]==1) cout<<"X"; else cout<<"."; } cout<<endl; } return; }C. Madoka and Formal Statement算法本质思维思路推演典型的找题目规律（本质）的题目。性质1：存在b[i]<a[i]则无解。性质1是题目中已经给出，更重要的是另一个初始条件：若a[i]<=a[i+1]，则可以a[i]++。可知：在a[i]<=a[i+1]的情况下，最多可以使得a[i]=a[i+1]+1。同时会发现，这个条件，是相邻2个数的关系。于是我们先缩小范围，研究不同情况下a[i] a[i+1] b[i] b[i+1]能否有解。根据条件，我们简单得分为4种情况：a[i] <= a[i+1]+1 && b[i] <= b[i+1]+1a[i] <= a[i+1]+1 && b[i] > b[i+1]+1a[i] > a[i+1]+1 && b[i] <= b[i+1]+1a[i] > a[i+1]+1 && b[i] > b[i+1]+1经过简单思考，发现如果存在b[i]-b[i+1]>=2，则必须保证a[i]==b[i]，否则无解。（性质2）2个元素的关系推理出来了，接着看扩大范围。发现性质相互补充，无缝连接。思路回顾这类题，已经把”找规律“写在脸上了，过程就是通过初始的条件，推出一些规律。但是具体要怎么推，就需要逻辑和思维。代码思路先检查是否存在b[i]<a[i]的情况（性质1）。若存在，无解。再看，如果出现了这样的情况b[i]-b[i+1]>=2，是否能保证a[i]==b[i]。（性质2）若不能做到，无解。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal flag=1; rep(i,1,n) if (a[i]>b[i]) flag=0; //性质1 if (!flag) { cout<<"NO"<<endl; return; } //cal 2 b[n+1] = b[1]; for (int i=1; i<=n; i++) //性质2 { if (b[i]-b[i+1] >= 2) //有沟壑 { if (b[i] != a[i]) flag=0; } } //out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }D. Madoka and The Corruption Scheme算法本质思维、思维（二进制）、一点博弈论思路推演此题最大的提示地方在于：有pow(2,n)个选手，n最大范围1e5。这个数据范围，稍微脑子一转就明白，必须得向二进制方向思考，这是大前提。随后我们简化初始条件，Madoka可以随意变化选手初始位置和每场比赛的胜负边，这里其中有2个“随意”，但实际要做到任意更变，只需要1个“随意”就好了。于是我们改成：每场比赛初始设置永远是左边获胜，Madoka可以随意变化选手初始位置。同时对赞助商的行为简化：希望使得最后胜者编号最大。此时，单纯根据文本推到比较困难，于是举一个例子。n=3，k=0~7。可以很明显的想到，如果要推选任意一个选手为胜者，其付出的代价等价于n。所以n=3 k>=3时，赞助商就可以推编号最大的选手获胜，作特殊处理。接下来思考n=3, k=0~2。以下图为例，红色代表胜利。当k=0时，只能采纳pos=1的点。此时Madoka肯定在pos=1的地方放上编号为1的选手。当k=1时，通过改变胜负边，能采纳pos=1、2、3、5的点。Madoka肯定会在这4个点，放上编号为1~4的选手，最后赞助商肯定会选择编号为4的选手。当k=2时，能采纳pos=1~7的点。Madoka同上操作，赞助商会选择编号为15的选手。接下来就是更简单的事了，根据目前发现的东西，找出规律。（思考类似这样的问题：问什么pos=1点在k=0的时候都能被采纳，而pos=3的店只能在k>=1被采纳？）很明显，一个点的位置是否能被采纳跟原本设定的胜利路径有关系。我们用0表示红色代表胜利的线，1表示黑色代表失败的线，从上往下表示。其二进制表示中，有多少个1则代表其胜利所需要的代价。我们要找的就是：长度为n的二进制数，条件：拥有数字1数目小于等于k，符合条件的二进制数有多少个。代码思路组合数相加。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 //组合数板子略 int C(int a,int b); //C(下，上) inline void solve() { // init init_c(); cin>>n>>m; //m代替题目中的k //cal if (m>=n) ans = qpow(2, n, mod); else { ans=0; rep(i, 0, m) { ans += C(n, i); ans %= mod; } } //out cout<<ans<<endl; return; }