Educational Codeforces Round 148 (Rated for Div. 2) A.New Palindrome算法本质思维题目大意给定回文字符串s，是否可以通过对其重排列组合出一个新的回文字符串。思路推演焦点在于“新的”，对于回文我们只需要镜像移动即可。当s的某一半回文（不含中间字符）非单一字符组成，则可行，反之不可行。B.Maximum Sum算法本质思维题目大意给定n个数，需要执行k次操作，每次操作为下面的一种：删除2个最小数删除1个最大数输出最大化剩余数的和。（保证2k < n）思路推演排列数，显然我们是删除左边2x个数和右边y个数，其中x+y = k。我们只需要暴力枚举x y即可，这需要一点前缀和优化。C.Contrast Value算法本质思维题目大意给定长度n的数组a[]，定义其对比值：遍历i = 2~n，求和abs(a[i] - a[i-1])找到一个满足下列条件的数组b[]：b[]为a[]的子序列a[] b[]的对比值相等输出最小化b[]的长度。思路推演又要是子序列，又要对比值相等。显然，只有连续上升的时候才可以省去中间部分元素。同时存在前后相等的情况，所以我们可以定义状态：上升、平缓、下降。状态转换间使得答案++。（具体算法比较简单繁琐，这里略过）D2.Red-Blue Operations (Hard Version)算法本质思维题目大意给定长度n的数组a[]，然后会进行q次独立询问，每次询问会给出一个k值。每次询问的规则如下：初始元素都是红色的，接下来需要进行k回合：第i回合需要选择一个元素，若元素为红色，则+i且变为蓝色；反之则-i变为红色。输出最大化k回合后的最小值。n q <= 2e5 元素大小 <= 1e9思路推演 - 抽象题意这个规则给的比较奇怪，我们对其模拟抽象出数学含义。容易观察到的是，对于某个元素，我们至多给其值+k，即只变一次颜色，（对于单个元素）多次颜色变换的收益小于一次变换。所以很容易想到的是，如果k <= n，那我们肯定让元素至多变色一次，即都做加法，再细细琢磨：大的值给较小元素加是最优解。接着思考k > n情况：通过几轮模拟可知，我们将k-n+1 ~ k用于做加法，剩余的值两两合并为-1做减法（如果k-n为奇数，做再拿一个做加法的值过来合并-1），这是显然的最优解。这个结论是很直观的，也可以数学证明，但是需要用中间值替换，比较繁琐。无法理解的话，结合这句话（对于单个元素）多次颜色变换的收益小于一次变换再思考一下。到此，我们就抽象出其背后数学含义：先排序a[]k <= n将1~k作加法，每个元素至多加一次，最优解为a[1]+k a[2]+k-1 …… a[i]+k-i+1 ... a[k]+1ans即其中的最小值k > n将k-n+1 ~ k或者k-n+2 ~ k作加法，剩余的元素两两合并成-1作减法ans即其中的最小值思路推演 - 最优解在抽象出基本题意之后，思考如何解题。对于每次询问来说，我们的均摊复杂度只有log级别的，怎么才能找到其最小值呢。k <= n：这个情况相对简单，我们可以将数组简单分为前k个和后n-k个。因为后n-k的最小值一定是a[k+1]求解前k个元素的最小值，观察其加法，值是有规律的。所以我们可以维护数组b[] b[i]=a[i]-i+1。b[i]+k可以用来表示a[i]+k-i+1的值，从而预处理时就看出谁是最小值。k > n：我们同样借助b[]来O(1)找到最小值，随后需要先用-1打平差距，若打平后还存在-1则可以用除法O(1)计算最小值。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn], pre_min[maxn]; inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>a[i]; sort(a+1, a+n+1); for (int i=1; i<=n; i++) b[i] = a[i] - i + 1; int sumb = accumulate(b+1, b+n+1, 0ll); //预处理 pre_min[0] = 1e18; // pre_min[x]表示b[1~x]的最小值 for (int i=1; i<=n; i++) pre_min[i] = min(pre_min[i-1], b[i]); while (m--) { int x, ans; cin>>x; if (x<n) ans = min(pre_min[x]+x, a[x+1]); // 前半段的最小值和后半段的最小值 else if ((x-n)%2==0) { int num = (x-n)/2; // -1的个数 int xiao = pre_min[n]+x; // 目前最小值 int wast = sumb + x*n - xiao*n; // 打平的花费 num -= wast; // 打平之后的个数 if (num > 0) // 打平后还剩，则继续打 xiao -= (num + n-1) / n; ans = xiao; } else { int num = (x-n+1)/2; // -1的个数 int xiao = min(pre_min[n-1]+x, a[n]); // 哪部分小用什么 int wast = sumb-b[n]+a[n] + x*(n-1) - xiao*n; // 打平的花费 num -= wast; // 打平之后的个数 if (num > 0) // 打平后还剩，则继续打 xiao -= (num + n-1) / n; ans = xiao; } cout<<ans<<" "; } cout<<endl; return; }E.Combinatorics Problem算法本质思维题目大意给定n a[1] x y m k。这里存在数组a[] b[] c[]，数组的定义如下：a[i] = (a[i-1]*x + y) % mb[i] = 求和j:1~i C(i-j+1, k) * a[j]b[i] %= 998244353c[i] = b[i] * i（注意这里不取模）输出c[]元素的异或和。n <= 1e7 k <= 5思路推演1e7显然这是一个O(n)的做法。最朴素的思路就是O(n)求得c[]再作计算答案。思考是否有其他取巧的方法，但是因为c[i] = b[i]*i最后这个*i明显打破了二进制可能存在的规律。所以大概率是不存在取巧方法的。于是先思考一下朴素做法。a[]可以看作已知，重点在b[]的计算。b[]这种组合数多项式，很容易让人想起组合数公式：C(a, b) = C(a-1, b) + C(a-1, b-1)。简单尝试后就可以发现，b[i]和b[i-1]有着关联，但是单凭一维b[]无法搞定。于是我们给b[]扩展一维，多的维度用来表示k值。（即原来的b[i]=b[i][k]）则可得到转移公式：b[i][j] = b[i-1][j] + b[i-1][j-1] + C(1, J)*a[i]。这是一个简单的二维dp，我们先处理好边界条件即可dp得出b[]，最后求出答案。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn][7]; inline void solve() { //init int x, y; cin>>n>>a[1]>>x>>y>>m>>k; for (int i=2; i<=n; i++) a[i] = (a[i-1]*x + y) % m; int pre=0; for (int i=1; i<=n; i++) // 预处理得到b[][0] { pre += a[i]; pre %= mod; b[i][0] = pre; } for (int i=1; i<=n; i++) { for (int j=1; j<=k; j++) b[i][j] = b[i-1][j]+b[i-1][j-1] + a[i]*(j==1), b[i][j]%=mod; } int ans=0; for (int i=1; i<=n; i++) ans ^= b[i][k]*i; cout<<ans<<endl; return; }

Educational Codeforces Round 147 (Rated for Div. 2) A.Matching算法本质思维题目大意给定由数组和?组成的字符串，?可以变为任意数字字符，输出其能表示的不存在前导0的数字个数。思路推演显然?在第一位就有9种可能，其他位置有10种可能。但是需要考虑自带前导0的字符串，这种字符串的答案为0。B.Sort the Subarray算法本质思维题目大意给定长度为n的数组a[] b[]，其中b[]是由a[]对自身某个区间元素升序排序后的结果。（保证a[] b[]有所不同）输出长度最大的区间l r。思路推演显然，未排序的地方元素一定相同，排序的区域不一定相同。且元素不相同的地方一定属于排序区域。所以通过对比元素是否相同，确定最小的排序区域。对于在排序区域，但是位置不变的元素，左边的为最小值，右边的为最大值。按照这个规律扩展即可。C.Tear It Apart算法本质思维题目大意给定由小写字母组成的字符串s，进行尽可能少的以下操作，使得s变成由单一字符组成选择任意互不相邻的下标，删除下标元素，剩余字符按序重连输出最小化的操作次数。思路推演显然，最后的可能情况为26字母中的某个。假设剩下的字符传为c，则需要删除c之间的所有字符，发现十分简单，即其log2函数（向上取整）。同时，不删除任何c显然是最优解。D.Black Cells算法本质思维题目大意在一行无限长的方格地图上，存在n个不相连的区间。你操控一只画笔，想要涂（已知）k个格子，但仅能在区间中涂写，并且遵守以下规则：每个回合只能选择选择一个操作：右移一格、笔尖下放、笔尖提起当完成一次笔尖下方、笔尖提起后，画笔在中间所在的方格会被涂色（意思是最后必须笔尖提起）输出最小化回合数。思路推演显然，这题的矛盾点在于，如果我们考虑少走路，就尽可能地用前面的的区间。但是如果前面的区域比较小，则我们的下放、提起所损耗比较多。我们定性分析一下：对于一个长度x的区间若取收益为x，成本为x+2若不取收益为0，成本为x如果我们想在后面捞x收益回来的话，至少需要x的成本所以可知，若x>=2，则这个区间一定是要取的。对于x=1的区间，则存在取或不取2种可能。于是我们枚举最后走到的区间。前面大于1的区间都必取，先加起来，变量名pre若pre>k则continue若pre<=k先用当前区间补一下，若不够补再用之前的1区间补。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int l[maxn], r[maxn]; inline void solve() { //init cin>>n>>k; rep(i,1,n) cin>>l[i]; rep(i,1,n) cin>>r[i]; //cal int ans=1e18; int sum=0, sum2=0, cnt2=0; // sum表示前面区间的总和，sum2表示前面区间>1的总和，cnt2表示前面区间>1的个数 for (int i=1; i<=n; i++) { sum += r[i]-l[i]+1; if (sum >= k) // 当前存在解决方案 { if (sum2 > k) // 说明当前+之后的方案都不是最优方案 break; int cha = k-sum2; // 还差的格子数 int bu = min(cha, r[i]-l[i]+1); // 当前区间尽可能补格子数 int pos = l[i] + bu - 1; // 最后停留下来的位置 int res = pos + (cnt2 + 1 + cha-bu)*2; // 计算这个方案的成本 ans = min(ans, res); } // 善后 if (r[i]-l[i]+1 > 1) sum2 += r[i]-l[i]+1, cnt2++; } if (ans==1e18) ans=-1; cout<<ans<<endl; return; }E.Rearrange Brackets算法本质思维题目大意题意稍微难懂，细心阅读称括号字符串为规则的，当满足以下条件：其可分割为若干子序列，每个子序列都是()定义规则括号字符串的属性成本值：可以进行任意次以下操作：选择两个相邻的字符组成的()，删去他们，成本为右边括号字符数。多次操作的成本之和的最小值，为成本值现给定规则括号字符串s和整数k，可以进行k次以下操作，得到一个新的规则括号字符串。任意调整某个字符位置（即半个括号）输出最小化得到的规则括号字符串的成本值。思路推演成本值是这题的关键属性，我们先模拟一下，如何求解一个括号字符串的成本值。其最优解显然是从右边开始，有点类似剥洋葱——但是从内部剥开。随后允许调整单个字符，再模拟找最优解。这个也非常显然，（调整单个字符的）最优解为把最大洋葱的外皮剥开。思路和代码相当简单，完全不符合2100的题目难度。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>k>>s; stack<int> st; vector<int> v; for (int i=0; i<s.length(); i++) { if (s[i]=='(') st.push(i); else { int l=st.top(); int r=i; // 找到对应的括号对 st.pop(); v.push_back((r-l-1)/2); // 每个括号对对成本的贡献值 } } sort(v.begin(), v.end()); k = min(k, (int)v.size()); int ans = accumulate(v.begin(), v.end()-k, 0ll); // 丢掉最后k个最大值 cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 145 (Rated for Div. 2) A.Garland算法本质思维题目大意给定长度为4、由数字组成的字符串s，表示有4个灯，不同的数字表示不同的灯。最初灯都是关闭状态，尽量少的进行以下操作，使得灯最后全部为打开状态：（不行输出-1）选择与上次操作选择不同种类的灯，改变其状态思路推演如果全部灯都是同一种类，理所当然不能全部打开。如果有3个灯一样，手动模拟一下发现至少需要6次。其他情况都不需要反复开关，4次就好。B.Points on Plane算法本质思维、二分题目大意给定n，需要我们在一个网格状的无限大棋盘上，需要放置n个棋子：棋子只能放在整数坐标上必须保证所有棋子之间的距离大于1定义最终棋盘的成本为：棋子与(0,0)的曼哈顿距离最大值。输出可以最小化的成本。思路推演很显然的二分答案，所以我们去找成本 --> 最多棋子的函数。手动模拟一下，就可以发现放置棋子有2种方式，一种是(0,0)放棋子的，一种是(0,0)不放棋子的。对于第一种方式：0~1 3~1+8 5~1+8+16……这是一个简单的等差数列（抛开第一个点）对于第二种方式：1~4 3~4+12 5~4+12+20……同样是一个简单的等差数列于是就简单地拿到了方程，二分即可。如果进一步检查的话，其实可以发现，当成本为x时，最多放置的棋子个数是x^2，可以进一步简化函数。但是请注意，自带的sqrt()在数字过大的时候有精度问题，1e18相当大，肯定有精度问题，需要自己手写。C.Sum on Subarrays算法本质题目大意对于长度为n的数组a[]来说，满足下列条件拥有魅力值：元素范围[-1e3 ~ 1e3]任意[l,r]范围内元素之和不等于0对于拥有魅力值的a[]来说，其魅力值的具体计算为：其中[l,r]范围内元素之和 > 0 的数目现在需要你构造出一个长度为n、魅力值为k的数组。n <= 30 t <= 5e3思路推演对于任何区间+个数的题，首先想到的就是固定某一端点。此题也是一样，假如固定左端点l后，能使得所有[l, ?]的元素和都大于0，则可以很轻松的凑出k来。显然这理论上可行。选择固定右端点：先将k分为若干个<=n且各不相同的数字，设为集合Q。历便右端点，当r 属于 Q时，表示[?, r]的元素和都需要大于0——相反不属于时，都需要小于0。对于当前右端点r如果r 属于 Q：找到[?, r-1]元素和的最小值，让a[r] = 最小值+1，保证[?, r]元素和都大于0如果r 不属于 Q：找到[?, r-1]元素和的最大值，让a[r] = 最大值-1，保证[?, r]元素和都小于0同时这个做法，显然是：保证所用元素绝对值尽量小为前提。此题做法很多，可以多看看开拓思路。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 D.Binary String Sorting算法本质思维、dp题目大意给定01字符串s，进行以下操作使得s变成一个非递减字符串：1e12元：交换2个相邻字符1e12+1元：去掉一个字符输出最小化花费。s.length <= 3e5思路推演-1这个价格，表达的意思是：尽可能减少操作次数如果操作次数一致，尽可能使用交换操作手动模拟一下就知道，去掉操作是显然优于交换操作（即交换一定可以用去掉代替、去掉不一定用交换代替）。所以就想到，可以先思考去掉操作，找到最小操作值，然后再琢磨把其中的部分换成交换。历便s最后01的分界线，前导1+后导0，就可以找到最少的去掉操作次数。随后发现，当人为设定[1, l-1]全为0、[l, n]全为1的情况时，只有s[l-1]=1 && s[l]=0的情况，交换替换去掉才可以降低成本。所以我们只需要历便的时候，人为检测一下即可。思路推演-2还可以思考一下dp方向，操作简单+不递减的特点，是可以构成前后区间的联系的。定义dp[x]表示第s[1~x]变成不递减字符串的最少花费。当我们想要扩展到dp[x+1]时：如果s[1~x]末尾没有1很高兴，不用花钱，不管s[x+1]是1还是0，都可以直接放进去如果s[1~x]末尾有1个1如果s[x+1]是0，可以用交换，最省钱如果s[1~x]末尾有多个1如果s[x+1]是0，那还是去掉最省钱。可以看到，我们简化为了3个状态，可行。（具体的状态转变不详述了，看代码）ac核心代码-1头文件、宏定义、快读模板、常见变量、常见变量等略。 int pre[2][maxn]; int que(int l,int r,int x) { return pre[x][r]-pre[x][l-1]; } inline void solve() { //init cin>>s; n=s.length(); s=" "+s+" "; //可能会访问s[0]和s[n+1] //cal 预处理前缀和 for (int i=1; i<=n; i++) { pre[0][i]=pre[0][i-1]; pre[1][i]=pre[1][i-1]; pre[s[i]-'0'][i]++; } //cal 2 int qu=INF, huan=INF; for (int i=1; i<=n+1; i++) //[1, i-1]为0，[i, n]为1 { int n_qu = que(1, i-1, 1) + que(i, n, 0); //全去掉操作 if (qu + huan > n_qu) // 更新答案 { qu = n_qu; huan = 0; } if (s[i]=='0' && s[i-1]=='1') // 如果可以用1个交换替换2个去掉 { n_qu-=2; int n_huan=1; if (qu+huan > n_qu+n_huan) //重新更新答案 { qu = n_qu; huan = n_huan; } else if (qu+huan==n_qu+n_huan && huan<n_huan) { qu = n_qu; huan = n_huan; } } } //out int ans = qu*((int)1e12+1) + huan*(int)1e12; // 奇葩错误：double前12位准的，这里超了，最后的那个+1在转int的时候会被舍弃 cout<<ans<<endl; return; }ac核心代码-2int dp[3][maxn]; //dp[i][j]：i表示状态，j表示s[1~j]的最小成本 inline void solve() { //init cin>>s; n=s.length(); s=" "+s; //cal int price[2]; price[0] = 1000000000000 + 1; // 去掉的花费 price[1] = 1000000000000; // 交换的花费 for (int i=1; i<=n; i++) { if (s[i]=='1') { dp[0][i] = dp[0][i-1] + price[0]; dp[1][i] = min(dp[0][i-1], dp[1][i-1]+price[0]); dp[2][i] = min(dp[1][i-1], dp[2][i-1]); } else if (s[i]=='0') { dp[0][i] = dp[0][i-1]; dp[1][i] = dp[1][i-1]+price[1]; //dp[1][i]有可能由dp[2][i-1]去掉操作转化而来，但是保证那个不是最优解，且会破坏状态，所以不写 dp[2][i] = dp[2][i-1] + price[0]; } } //out int ans = min(dp[0][n], min(dp[1][n], dp[2][n])); cout<<ans<<endl; return; }

Educational Codeforces Round 144 (Div. 2) A.Typical Interview Problem算法本质思维题目大意使i顺序历遍[l, r]如果i%3==0则输出F（先判断）如果i%5==0则输出B现在给出一个string，判断是否存在如此的[l r]。思路推演模3模5，直接就想到循环节。找最小公倍数15，可知肯定15个数字为一个循环节。手动模拟1~15：FBFFBFFB因为担心首尾相连的情况和考虑到string的长度，将FBFFBFFB乘3，然后用自带的find方法判断是否可行。B.Asterisk-Minor Template算法本质思维、模拟题目大意（改）*可以表示任意长度的任意字符串（包括空字符串）。现在给出a b两个字母组成字符串，请设计一个字符串满足以下：可以使用*包含a b两种情况*的个数小于等于字符串长度的一半可以请输出此字符串，不行则输出No。思路推演需要尽量找到a b相同的字母来平衡*的数目。手动模拟一下即可发现，首尾其一字母相同即可。其他则需要中间有2个字母连着相同。重点在于要上手模拟一下，规律就很容易看出。C.Maximum Set算法本质思维题目大意给定一对l r，用[l, r]范围的数字建立一个集合（数字不重复）。若集合内数字两两为可整除关系，则称之为美丽集合（只有一个数字的集合也美丽）。集合的数字个数为集合的长度。找到所有美丽集合最长的集合，输出其长度，并且求出有多少个同样长度的美丽集合（%mod）。思路推演这类题乍一看比较唬人，都是些新鲜玩意。实际做题的时候不要怕，都是纸老虎！既然没怎么见过，就按照其要求先模拟一下。要求最长和美丽，首先可以想到的就是从l出发，每次*2计算。如此很快就可以得到最大长度。此时思考其他同长的美丽集合。有2个方向：从l+i出发最远的可行地方，可以用r向下除2来获得，这里称之为l_max将其中的*2改成*3 *4...可以很容易发现，最多将其中一个*2改为*3已知[l, l_max]都是可以通过*2来完成美丽集合的。其中能否将*2换成*3需要判断，因为单调性，所以可以二分判断。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init int l, r; cin>>l>>r; int len=0, x=l; while (x<=r) { x*=2; len++; } int ci=len-1, l_max = r; while (ci--) l_max/=2; //cal int ans=l_max-l+1; //全部都可以*2变成美丽集合 int ll=l, rr=l_max; int res=l-1; //最后res-ll+1表示有这么多个数字可以将*2替换成*3 while (ll<=rr) { int mid=(ll+rr)/2, max_val=mid; if (len-2>0) //len个数字就应该有len-1个*2，换一个*3，还有len-2个 max_val = mid*qpow(2, len-2); max_val *= 3; if (max_val > r) //说明不行 rr = mid-1; else { res = mid; ll = mid+1; } } ans += (res-l+1) * (len-1) % mod; //加上可以替换*3变成美丽集合的 ans %= mod; //out cout<<len<<" "<<ans<<endl; return; }D.Maximum Subarray *算法本质思维题目大意给定数组a[]，你需要选择其中k个不同下标使其+val，其他下标都会-val。完成操作后选择最大子段和，报告其最大值。注：val可能是负值。n <= 2e5 k <= 20思路推演此题很容易让人想到最大子段和。最大字段和的复杂度是O(n)，此题的k也相对小，感觉上是最大字段和的变种。观察其中的规律，当val>0可以很明显的发现其+val的下标要在子段内。同时将val<0情况转化为val=-val, k=n-k，方便统一思考。发现+val有聚集的倾向，直接人为规定所有的+val都必须要贴在一起。并且规定子段一定贴在+val的边缘当+val的长度为n-k时，其存在的可能就及其有限（k种）：枚举所有的n-k长度的+val情况，人为设定子段贴边，用前缀和可以快速暴力出答案当+val的长度为n时同样枚举所有的k长度的+val的情况，但是两边采用最大子段和预处理，同样nk暴力出答案。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 140 (Rated for Div. 2) A.Cut the Triangle算法本质模拟题目大意给定一个面积不为0的三角形，需要你判断是否可以通过竖切or横切分成2个面积不为0的三角形。思路推演只要保证不是水平+竖直方向的直角就好了。B.Block Towers算法本质思维题目大意有n个“塔”，每个塔由a[]的积木堆成，只有积木严格多余的塔之间可以传递积木（每次传递一块）。请问第一个塔最多可以有多少个积木。思路推演优先用较少的积木，贪心处理。title算法本质题目大意思路推演$i + 1\sim j $ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 D.Playoff算法本质思维题目大意有2^n个人，其id各不相同，并且集合是一个排列。现在任意调整他们的位置，其每天会两两战斗，淘汰一半的人，总共战斗n天决出胜者。现在给出一个字符串S，其s[i]=1表示第i天，id值更大的人会获胜，反之亦然。请输出：可以通过调整位置最后胜出的id。思路推演假设当前人id为x。如果当前轮id大的胜就需要制造一个和x一模一样境遇的点，然后放在x下面，假设为y。小于y的值一定小于x，大于y的值无法判断。所以小于x的值的个数*2+1了如果当前轮id小的胜同理，大于y的值的个数*2+1了ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>s; s = " " + s; //cal int da=0, xiao=0; for (int i=1; i<=n; i++) { if (s[i]=='1') xiao = xiao*2+1; else if (s[i]=='0') da = da*2+1; } //out for (int i=xiao+1; i<=qpow(2,n)-da; i++) cout<<i<<" "; cout<<endl; return; }