Educational Codeforces Round 139 (Rated for Div. 2) A.Extremely Round算法本质模拟题目大意给定一个n，求1~n中美丽的数字个数。美丽：数字十进制中，有且仅有1个位数字不为0：如1、7、100、4000。思路推演以十进制的位为单位，第一位、第二位……实际做的时候，为了抢时间，考虑可以打表，写了一个暴力打表预处理。B.Notepad#算法本质模拟题目大意给出一个长度为n的字符串s，现在需要判断能否用至多n-1次操作制造出字符串t，其等于s。每次操作可以：向t末尾加入任意一个字符复制t的某个子字符，在末尾粘贴思路推演至多n-1次，考虑能不能有一次复制粘贴相当于多次加字符。将t中所有长度为2的子字符串放入set，添加新字符的时候检测。C.Hamiltonian Wall算法本质模拟题目大意给出一个2*m的格子，格子只有黑白两种颜色。可否找到一个路径走遍所有的黑色格子（不准重复走）。思路推演因为只有2行，从左向右推进即可。对于每一列，只有数种情况：上下都黑可以通过，方位改变。某一格黑方位是否一致，一致可以通过无黑不可通过D.Lucky Chains算法本质思维题目大意给定一对x y（x<y），对于答案k来说，任意的0 <= val < k，都满足gcd(x+val, y+val)==1的情况。输出最大化k。（无限大请输出-1）思路推演可以发现，x y的差是不变的，而根据基本的数学定理可知，当gcd(x+v, y-x)==1时，x+v y+v也互质。所以说本质上，就是y-x分解的各种素数，会像拦路虎一样拦截逐渐增大的x+val。这个计算是相当简单的，但是可能会T，请用注意下面的优化：先用埃式处理素数，用已经获得的素数集分解质因数用int别用long long（可能是为了卡掉普通的质因数分解方法，时间卡的比较紧）E.Decomposition算法本质思维、状压dp题目大意给出长度为n的数组a[]，所有元素范围在0~3。对于某个a[]的连续子数组依，其中元素次放入分组器使得其分为若干组：（设放入a[i]时已经存在k组）依次讲元素尝试放入前k组，若a[i]与当前组的末尾元素值按位和大于0，则将a[i]放入当前组的末尾若当前k组能无法接受a[i]，则新开编号为++k组，放入a[i]每个a[]的连续子数组对ans的贡献是其最后的组数（k值）。计算所有的a[]连续子数组的k值和——ans。n <= 3e5思路推演按位和、0~3的小大……毫无疑问，需要先找到规则的特征。0值在任意时候都会单独成立一组除去0值，其他元素最多成立3组这是一个想到有效的结论，如果抛去0值，我们的状态数最多存在3*4*4=48种，如果满足前后缀的转移，则毫无疑问，使用状压dp的复杂度是ok的。事实如此。代码思路dp(状态, pos)表示：目前状态经历了a[pos]的值 + 经历了a[pos~pos+1]的值 + 经历了a[pos~n]的值。状态用vector<int>来表示。我们固定左边界l，对于每个左边界，都ans += dp(全0状态, l)。dp(当前状态, i) = dp(经历i后的状态, i+1) + 贡献值(经历i后的状态的元素个数)这里有一些问题的是，对于0，理论上我们也需要开一个新组，但是这样会导致内存爆掉。所以我们可以统一记录当前0值的贡献，假设我们固定的左值下标为l，当前0值下标为i，在r取i~n时都会具有1的贡献，所以直接加上n-i+1的值即可。其实其他值也可以，我们可以针对每一个导致开新组的元素，如果其下标为i，则直接加上n-i+1的值。不过为了便于理解，还是挨个加。思路推演-2（未ac）同时因为状态足够少，我们可以推出新组数变化的特征：（暂时自动忽略0）1组-->2组出现1 2或者2 12组-->3组若前面有1 2，则是3 2 2 ... 2 2 1若前面有2 1，则是3 1 1 ... 1 1 2所以搜索所有特征区间，这4种特征分别放入4个队列，可以叫做q12 q21 q321 q312。保证左边界较小的在前。（顺序历便的话自动就是左边界小的在前）随后枚举l = 1~n。详细看代码，但是WA16，不知道哪错了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; map<vector<int>, int> dp[maxn]; vector<int> go(vector<int> tai, int pos) { int val=a[pos]; if (val==0) return tai; // 默认状态不添加0 else { bool f=0; for (int i=0; i<tai.size() && f==0; i++) if ((tai[i]&val) > 0) { f=1; // f==1表示不需要新加组，更新状态，但是此点贡献为0 tai[i] = val; // 更新状态 } if (f==0) // 说明需要加组 tai.push_back(val); return tai; } } int f(vector<int> tai, int pos) //记录状态、当前pos { if (pos == n+1) return 0; if (dp[pos].count(tai)) return dp[pos][tai]; //记忆化 auto nxt=go(tai, pos); //tai经历a[pos]后的状态 int res = nxt.size() + f(nxt, pos+1); //当前贡献值 + 之后的贡献值 if (a[pos]==0) res+=n-pos+1; //0值的贡献值单独计算 return dp[pos][tai]=res; } inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; //cal int ans=0; for (int l=1; l<=n; l++) //枚举固定左边界 ans += f(vector<int>(0), l); //out cout<<ans<<endl; return; }

CodeTON Round 4 (Div. 1 + Div. 2) A.Beautiful Sequence算法本质思维题目大意对于长度n的数组a[]，定义其美丽的：至少存在一个a[i]=i定义其帅气的：其子序列至少一个是美丽的现在检查长度为n的a[]是否帅气。思路推演题目转化为，我们找到一个子序列，其中的一个元素等于其下标，这个元素称为奇点。假设a[1]为奇点，则必须保证a[1]=1，若a[2]为奇点，则必须保证a[2]<=2。随后验证a[i]<=n时可以称为奇点。检测一遍即可。B.Candies算法本质思维题目大意初始时有一颗糖，可以进行以下两种操作（操作数之和最多40）：糖数 = 原糖数*2 - 1糖数 = 原糖数*2 + 1最终需要得到n颗糖，复述操作步骤。（不能输出-1）思路推演显然，偶数是不可行的。倒推可以发现，设当前有y颗糖，操作后为x颗糖。若已知y，想保证x为奇数，则只有其中一个操作可以做到。选择可行的操作，然后循环这个逻辑即可。C.Make It Permutation算法本质思维题目大意给定长度n的a[]，进行以下操作，使a[]变为非空排列（下标1开始）：c元：删除一个元素d元：在任意地方插入一个任意元素思路推演有一种方法肯定可行：删除所有元素再加个1。不过这个结论用处有限，继续思考。既然最后是排列，则重复的元素一定需要删除。对于a[]，先排序再去重。设a[i]为最后排列的最大值。遍历所有情况的成本，选最小即可。（包括全删加1的情况）D.Climbing the Tree算法本质思维、模拟题目大意对于一只蜗牛和树，树高h，蜗牛白天爬a，晚上下降b。现在给你一颗高度暂时不知的树，接下来有q只蜗牛会来和你交流，有以下两种交流：爬过树的蜗牛：会告诉你关于它的a b数值，和其所用时间d。如果你目前收集到的情况能证明它说谎，不用理会它；否则当作真实信息接受。没爬过树的蜗牛：告诉你关于它的a b数值，希望你计算出一个切确的爬树时间。若无法切确到多少天，则输出-1。思路推演我们设定树可能最大高度、可能最小高度。爬过树的蜗牛：通过a b d计算出其爬树的最大可能高度、最小可能高度，与原范围取交集。（若无交集说明其说谎）没爬过树的蜗牛：用当前树的最大可能高度、最小可能高度与a b计算出最长、最短的爬树时间，若一致则输出，否则-1。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int f(int a, int b, int h) // 给定属性，看需要爬多少天 { if (a>=h) return 1; int res=1; h -= a; res += (h+a-b-1)/(a-b); return res; } inline void solve() { //init int q; cin>>q; int mm=1e18, mi=-1e18; while (q--) { int op, a, b, d; cin>>op; if (op==1) // 爬过树的蜗牛 { cin>>a>>b>>d; int da = (a-b)*(d-1) + a; // 当前蜗牛爬树的最大可能高度 int xiao = (a-b)*(d-2) + a + 1; // 最小可能高度 if (d==1) // 如果d==1的话，xiao需要特殊处理一下 xiao = 1; if (da>=mi && xiao<=mm) // 与原数据有交集，说的是大实话 { mi = max(mi, xiao); // 更新 mm = min(mm, da); cout<<1<<" "; } else // 在说谎 cout<<0<<" "; } else if (op==2) // 没爬树的蜗牛 { cin>>a>>b; int d1 = f(a, b, mm); // 最长时间 int d2 = f(a, b, mi); // 最短时间 if (d1==d2) cout<<d1<<" "; else cout<<-1<<" "; } } cout<<endl; return; }E.Monsters算法本质思维题目大意给定一个无向图，每个节点存在一个防御力为a[i]的怪物（需要主角的攻击力>=a[i]才能击杀），只有当前节点的怪物被消灭了才可以随意通行。主角初始攻击力为0，每击杀一个怪物攻击力+1。主角可以选择某个节点开始，问是否可以击杀所有的怪物。思路推演显然，起点只能是a[i]=0的点。对于一个起点来说，判断是否可行相对简单，类似prime最小生成树的模型即可。还需要解决的一个问题是：多个起点怎么降低复杂度：当我们跑某个起点时，遇到其他起点可以顺路标记了（不用重复跑了），这个优化使得最多跑2n个节点。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; vector<int> g[maxn]; set<int> v0_used; // 记录已经使用过的0值下标 struct node { int val, pos; // bool operator < (const node &b) const { return val > b.val; } }; int f(int s) { // v0_used.insert(s); vector<bool> vis(n+5, 0); priority_queue<node> q; int power=0; q.push({a[s], s}); while (q.size()) { if (power < q.top().val) return -1; node u=q.top(); q.pop(); if (vis[u.pos]==1) continue; // 检测是否用过了 vis[u.pos] = 1; if (u.val==0) v0_used.insert(u.pos); // 优化复杂度 power++; for (int nxt:g[u.pos]) { if (vis[nxt]==0) q.push({a[nxt], nxt}); } } return power==n; } void clear() { for (int i=1; i<=n; i++) g[i].clear(); v0_used.clear(); } inline void solve() { //init cin>>n>>m; clear(); vector<int> v0; // 记录0值下标 for (int i=1; i<=n; i++) { cin>>a[i]; if (a[i]==0) v0.push_back(i); } while (m--) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } //cal flag=0; for (int s:v0) { if (v0_used.count(s)) continue; // 已经遍历过了 if (f(s)==1) { flag=1; break; } } // out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }

Codeforces Round 882 (Div. 2) A.The Man who became a God算法本质思维题目大意给定a[]信息，在不改变相对顺序条件下，把a[]分成k个组，每个组的成本为：（总成本为每组成本之和）相邻2个数绝对值差之和输出最小化的所有组成本和。思路推演分组的实际意义是，切断了a[i]和a[i+1]之间的连续，使得成本下降了abs(a[i]-a[i+1])。所以记录n-1个绝对值差，减去前k-1个值，即得到剩余的最小化组成本和。B.Hamon Odyssey算法本质思维题目大意给定a[]信息，在不改变相对顺序条件下，把a[]分成若干组，每组的成本为：（总成本为每组成本之和）a[l] & a[l+1] & ... & a[r]输出保证最后成本最小能分的最大组数。思路推演首先可知，若a[1] & a[2] & .. a[n]不为0，则一定不可分割，因为必然会导致值增加。若其全部与运算后为0，则需要保证分割前后都是0才行——即a[l~r]中，每个二进制位都存在某个数此位0。我们选择从左往右遍历，一旦满足这个条件，则记录重置条件。（用贪心思想看，显然正确）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn][40]; // 数组、数组二进制 inline void solve() { cin>>n; for (int i=1; i<=n; i++) { cin>>a[i]; for (int j=0, x=a[i]; j<=30; j++, x/=2) b[i][j] = x%2; } int ans=0; set<int> st; for (int i=1; i<=n; i++) { for (int j=0; j<=30; j++) { if (b[i][j]==0) st.insert(j); } if (st.size()==31) // 重置 { ans++; st.clear(); } } ans = max(ans, 1ll); // 担心整体与运算>0导致ans=0 cout<<ans<<endl; return; }C.Vampiric Powers, anyone?算法本质思维、数据结构题目大意给定长度n的a[]信息，现在可以对其进行若干次操作：选择l使得x = a[l] ^ a[l+1] ^ ... a[n]将x放入a[]末尾，使得其长度+1输出最大化操作后a[]的最大值。n <= 1e5 a[i] <= 2^8思路推演首先抽象操作，设前两次操作分别选择了l1 l2，可以发现，a[n+1]的范围是l1~n，a[n+2]的范围是l1~l2（或l2~l1）。以此类推，a[n+1]和a[n+2]可以看作一起，范围是l2~n。所以后面制造出来的数的实质是：区间异或和。其题目的本质是最大区间异或和。但是数据范围给的耐人寻味，显然存在某种暴力之法。思路推演 - 暴力最基本的暴力是O(n^2^)的，即每次遍历时确定r，然后遍历l去获取不同区间的值。但是由于其值上限只有256，所以其至多有256种情况，可以用256*n的复杂度搞定。思路推演 -ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; set<int> st; int res=0, ans=0; st.insert(0); // 0下标的异或值 for (int i=1; i<=n; i++) { res ^= a[i]; // res表示[1~i]的异或和 for (int x:st) // 遍历前面区间的可能性——至多256种情况 ans = max(ans, res^x); st.insert(res); } cout<<ans<<endl; return; }D.Professor Higashikata算法本质思维题目大意给定01字符串s，指定了m个区间，接下来会有q次询问，每次询问会翻转某位字符信息，玩家可以执行若干次操作：（并不赋值给下一次s，假设性操作）交换某2个字符位置操作后需要保证：根据指定的m个区间截取s生成子串t(1) t(2) ... t(m)，再顺序连接组成新01子串t，使得t的字典序尽可能大输出每次询问的最小操作数。思路推演既然是使得t的字典序大，观察给出m个区间，可以对s的下标进行权重的排序，即先给出的下标权重更大。这里就涉及一个多区间修改的问题，设立R[]来表示右侧未被权重赋值的下标，配合类似并查集find()，能够较好应对。能被赋予权重的下标数目可能达不到n，这里设为len表示，用num1表示当前s中1的数目，会有2种情况：num1 >= len则赋权下标可以全修改为1，计算赋权下标中为0的数目即可。num1 < len记录赋权下标中前s前num1下标为0的数目即可。可以看到的是，这部分是单点修改，区间查询，暴力一点的话，用树状数组可以直接搞定，复杂度为log。当然，这里的区间查询之间的变化至多为1，所以也可以通过一些技巧避开树状数组，但是想要降低复杂度还是比较难。（也能降低，但是写起来比较麻烦）这里选择用树状数组，检查一下，需要原下标到新下标的映射。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 差分树状数组忽略 int R[maxn], vis[maxn]; // R[i]需要赋值为i+1 int find(int x) // 找到右边（含自己）第一个未被遍历的 { if (vis[x]==0) return x; return R[x] = find(R[x]); } inline void solve() { int q, num1=0, len=0; // num1表示s中1的数目，len表示赋权的下标数目 cin>>n>>m>>q>>s; s = " " + s; for (int i=1; i<=n; i++) { R[i] = i+1; num1 += s[i]=='1'; } map<int, int> mp; // 旧id-->新id（新id越小，说明权重越高） while (m--) { int l, r; cin>>l>>r; for (int p=find(l); p<=r; p=find(p)) { vis[p] = 1; mp[p] = ++len; // 更新mp add(len, len, s[p]=='1'); // 树状数组依照新id建立，因为len<=n，所以长度给n没问题 } } while (q--) { int x, val; cin>>x; if (s[x]=='1') s[x]='0', val=-1; else s[x]='1', val=1; num1 += val; if (mp.count(x)) // 说明有对应的新id add(mp[x], mp[x], val); int r=min(len, num1); // 检查树的范围[1~r]中0的个数 int ans = r - getsum(1, r); cout<<ans<<endl; } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 F.The Boss's Identity算法本质思维题目大意给定无限长数组a[]前n个元素信息，其后面元素的大小定义：a[i] = a[i-n] | a[i-n+1]（i>n）接下来有q次询问，每次询问给出x，找到大于x的a[]种的最小下标。（无则返回-1）前缀知识以或运算为例，长度n、大小范围0~2^m-1的a[]的区间异或和至多存在n*m个值。先确定r，遍历l，这是个以r为右端点后缀异或和，显然至多有m个不同值。 存在n个这样的r，至多为n*m个值。（实际严格小于这个值）不仅或运算，与运算（看作0的或运算）、gcd（看作未取素数的或运算）同理。思路推演手动模拟n=5情况：（a1隐藏）长度a2结尾a3结尾a4结尾a5结尾1a2a3a4a52a1~a2a2~a3a3~a4a4~a53a5~a2a1~a3a2~a4a3~a54a4~a2a5~a3a1~a4a2~a55a3~a2（全部）a4~a3（全部）a5~a4（全部）a1~a5（全部）可以发现的是，后面的元素实际上是前面元素的区间或结果，所以从区间的角度思考。结合前缀知识，一个显然的想法是，将这所有区间或至多nlog(1e9)个值取出来，按编号排序，再删去某些点保证其严格递增（删除的点总是存在更优解替代）。那应该如何取出来呢，思考单个元素的贡献，考虑这是位运算，思考单个元素的单个二进制的贡献。我们假设确立a[i]为左端点，其二进制第一位是1，r不断向右延申（注意这里相当于是环形的），首先当r=l时，其对自身的[l,l]区间二进制第一位做出了贡献，接着当r>l时，其对[l, r]二进制第一位做出贡献。当然，前提是[l+1, r]的所有数都没有对其二进制第一位做出贡献。如果发现了在此之前有其他元素先于其做出贡献了，则停止（因为后面做出贡献的时间都是更晚的，存在更优解替代）。在记录这些贡献时，以r为key值来记录，这样就可以得到了r --> 每个二进制位为1的时间点，大概是这样的数据：tim[r][j]=len所有右端点为r的区间，第j位二进制数为1的贡献，最早记录来自于长度为len时（即由r-len+1这个左端点贡献）。我们可以据此每个右端点写出31个{出现id + 异或和值}，共计n * 31个值，排升序，然后遍历删去某些点保证id和值都严格升序，将值作为检索，之后对q次询问二分查找。注意看模拟的图，a1结尾的只有其自身一个，写下标的时候请注意ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn][40]; // b[i][j]:a[i]的第j为二进制数 int tim[maxn][40]; // tim[r][j]=len：以r为右端点的区间，第j位二进制为1的首先贡献是r-len+1的左端点 int er[40]; // 记录二进制值，方便用 inline void solve() { cin>>n>>m; for (int i=1; i<=n; i++) { int x; cin>>x; a[i] = x; for (int j=0; j<=30; j++) { b[i][j] = x%2; // 二进制位记录 x /= 2; tim[i][j] = 0; // 顺便清洗一下tim[][] } } for (int l=1; l<=n; l++) { for (int j=0; j<=30; j++) { if (b[l][j]==0) continue; int len=1; tim[l][j] = len; // 自己对自己的贡献 for (int r=l%n+1; r!=l; r=r%n+1) // 数学推论，这里不会T { // 这里注意别让r>n了 if (b[r][j]==1) break; // 之后的地方，用r做左端点是更优解，所以break tim[r][j] = ++len; } } } vector<pair<int, int>> v1, v2; // {id， 值} v1记录n*m个，只能保证id递增，v2清洗v1，保证id、值都递增 v1.push_back({1, a[1]}); // a[1]特殊处理 for (int i=2; i<=n; i++) { map<int, vector<int>> cod; // cod[len]={a, b, c}：r-len+1的左端点首先贡献了第a b c二进制位的值 for (int j=0; j<=30; j++) { if (tim[i][j]==0) continue; // 说明第j位二进制都没有，忽略 cod[tim[i][j]].push_back(j); } int val=0; for (auto it:cod) { for (int x:it.second) // 遍历这些二进制位，把值加入val val += er[x]; int len=it.first, idx=(len-1)*(n-1)+i; // 计算id v1.push_back({idx, val}); } } sort(v1.begin(), v1.end()); // 以idx排序 // 清洗v1，保证id、值都递增，放置v2 for (auto [idx, val]:v1) { if (v2.size()==0 || val>v2.back().second) v2.push_back({idx, val}); } // v2放到mp中，以值为key值方便二分查找 map<int, int> mp; for (auto [idx, val]:v2) mp[val] = idx; // 正式开始询问 while (m--) { int x; cin>>x; auto it = mp.upper_bound(x); // 第一个>x的下标 int ans=-1; if (it!=mp.end()) // 说明没有比x大的值，输出最后一个 ans = it->second; cout<<ans<<endl; } return; } inline void solve_init() { er[0] = 1; for (int i=1; i<=30; i++) er[i] = er[i-1]*2; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 870 (Div. 2) A.Trust Nobody算法本质思维题目大意给定长n的数组a[]，其a[x]表示第x个人说：这里有至少a[x]个说谎者。一共n个人，每个人只有说谎者和非说谎者身份。若存在满足条件的情况，输出说谎者数目反之输出-1思路推演很显然，我们只需要暴力假设说谎者数目，然后检查当前假设的数目是否符合条件（通过前缀和、桶排序、sort处理等等其中一种方法，可以使得单次查询复杂度O(1)），所以整体是O(n)的复杂度。B.Lunatic Never Content算法本质思维题目大意给定长度n的数组a[]，对齐进行一次以下操作：选择整数x，使得a[]中所有元素都对x取余保证最后a[]成为一个回文数组，输出最大化x。（若x无限大输出0）思路推演最后的目的是让a[]形成回文，则将a[]的元素一对一对拿出来，有n/2对：现在目的是找到一个x，使得这些对元素对x同余。这一步，更换题意，进一步抽象题目的意思，找到算法本质两数对x同余，很快可以写成两数之差对x取余为0。显然，这里有n/2个条件，要使得x尽可能大，我们取差的最大公因数即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; int ans=0; for (int l=1, r=n; l<=r; l++, r--) ans = gcd(ans, abs(a[l]-a[r])); // gcd对于0的一些特性 cout<<ans<<endl; return; }C.Dreaming of Freedom算法本质思维题目大意给定n m，现在有n个人，m个选项。会经历若干次投票，直到选项个数为1，规则如下：每个投票某个选项票数最多的选项保留，其余丢弃询问，是否存在一直投票的可能。思路推演”可能“一词，表示我们的思考方向应该是尽可能让人们平票，贴近无限投票情况。显然当选项>=人数时，肯定是存在无限情况——因为每个人可以分别投票给某个选项。既然如此，进一步思考：两人投一个选项、三人投一个选项……然后会发现，这于因子有关。当选项数>=人数的某个非1因数时，就可以一直保留某几个选项。D.Running Miles算法本质思维题目大意给定长度n的数组b[]。有n种草药，每种草药的价值为b[]，现在小明可以选择一对l r，带走下标属于[l, r]的三种草药，同时消耗r-l的价值。输出最大化带走草药的价值。n <= 1e5思路推演观察题目：n为1e5范围，显然此题需要信息复用——贪心、dp、二分等等同时这个“三种”也让人心生疑惑：为什么刚好是三种，不是两种，不是四种价值的消耗，与范围线性相关（可以联想类似的题目解法）这些都是题目的疑点，在不能看题就想到思路的时候，从疑点入手。为了快速解题，先尝试了从n范围入手：但是思路寥寥，暂无解法。随后选择从“三种”疑点切入：“一种”，显然可解。“两种”，我们可以在确定某个值后，贪心计算出另外一个值的信息。显然，想到了“两种”的解法，就知道了“三种”的解法：我们假设第二个元素下标为x，贪心计算出左右边元素价值，加上即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], pre[maxn], suf[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; for (int i=1; i<=n; i++) { pre[i] = a[i]+i; // 这个值设计的很巧，十分方便后面的r-l代价计算 suf[i] = a[i]-i; } //cal pre[0] = pre[n+1] = suf[0] = suf[n+1] = -1e18; // 注意这里是负数，因为pre和suf可能是负数，最大-n左右 for (int i=1; i<=n; i++) pre[i] = max(pre[i], pre[i-1]); for (int i=n; i>=1; i--) suf[i] = max(suf[i], suf[i+1]); int ans = 0; for (int i=2; i<=n-1; i++) ans = max(ans, pre[i-1]+suf[i+1]+a[i]); cout<<ans<<endl; return; }E.Walk the Runway算法本质思维、bitset题目大意有n个模特，每个模特有自己的出场费a[]。（走m场秀的出场费）有m场秀，每场秀的每个模特的评分为b[][]。对于每场秀，有以下规定：所有秀出现的模特集合相等所有秀模特的出场顺序相同所有秀出场的模特所得评分必须严格单增输出最大化的模特出场费之和。思路推演所有秀中，模特出场集合、顺序都是一致的，所以我们可以把每个模特看成一个node，第i场秀的评分为这个node的第i个属性。（抽象题意）在编排模特出场顺序时，发现模特之间有大小关系（大于、小于、不相等三种关系），且这种关系具备一定传递性。这导致其n个node会组合成一个DAG（无环有向图）最后要最大化的出场费，实际是找一条路径的最大和，显然可以在建图后使用dp搞定。目前的核心问题在于建图（二维直达图）的朴素做法是n^2^m——每2个node之间的关系需要通过m个属性来判断，即使其有传递性，但是传递性并无法降低如此大的复杂度。当时的希望是从评分<=n这点入手的，但是思路寥寥。思路推演 - 正解正解做法是：利用bitset加速处理。因为最终要建的图，可以用临边矩阵表示，用1表示可达，用0表示不可达。通过调整代码，使代码符合bitset的处理方式，从而使得复杂度降低为n^2^m/w（这里w通常为32或64）。ac核心代码因为后面缺乏思维性理解，所以使用别人代码，添加自己注释作为代码。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>m>>n; vector<vector<int>> a(n, vector<int>(m+1)); rep(i,0,n-1) cin >> a[i][m]; // 价格放入a中，方便一会排序带着走 for (int i=0; i<m; i++) for (int j=0; j<n; j++) cin>>a[j][i]; // 评分表：[模特][走秀] sort(a.begin(), a.end()); // 评分表根据模特的第一场秀评分重新排序（偏序），方便后面计算 //cal vector<bitset<maxn>> lower(n); for (int i=0; i<n; i++) lower[i].set(); // 全部设置为1 vector<int> inds(n); iota(inds.begin(), inds.end(), 0); // inds[i]=i for (int i=0; i<m; i++) { sort(inds.begin(), inds.end(), [&] (int x, int y){ return a[x][i] < a[y][i]; }); // inds表示第i场秀评分从小到大的模特编号 bitset<maxn> cur=0; // cur[i]=1表示模特i在第i场秀的评分比当前模特小 int p=0; for (int j=0; j<n; j++) { while (a[inds[p]][i] < a[inds[j]][i]) // 避免相等但是仍然不可达的情况 cur.set(inds[p++], 1); lower[inds[j]] &= cur; // 利用bitset加速 } } vector<long long> dp(n); // dp[i]表示走到i点所获得的最大值 for (int i = 0; i < n; i++) { dp[i] = a[i][m]; // 初始赋值 for (int j = 0; j < i; j++) { if (lower[i][j]) // 可达 dp[i] = max(dp[i], dp[j]+a[i][m]); // 更新 } } cout << *max_element(dp.begin(), dp.end()) << '\n'; // 输出最大值 return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 866 (Div. 2) A.Yura's New Name算法本质思维、读题题目大意给定一串由^和_组成的字符串，现在要求你向其中添加字符，使其合法。合法字符串的定义：对于任意字符，其可以和相邻的若干个字符组成^_^或^^字符串输出最小化添加字符数。思路推演分类讨论，文字详述略微复杂。B.JoJo's Incredible Adventures算法本质思维题目大意给定长度n的01字符串s，复制n个s分别称作s[1]、 s[2]、...、s[n]，组成一个n*n的01矩阵。随后将s[i]字符循环左移i位。对变化后的01矩阵，输出其中最大全1矩形面积。n <= 2e5思路推演稍加模拟可以发现，1的出现都是成片的，其源头是s中连续的1。若s全为1，显然面积为n*n否则：对于s连续的x个1，一定会形成一个倾斜角为45度的x*x的平行四边形。其中可以选中的矩形，长边之和固定为x+1，所以最大面积为(x+1)/2 * (x-(x+1)/2)C.Constructive Problem算法本质思维题目大意给定长度n的数组a[]，现在选择一对l r，使a[l~r]元素变成同样的任意正整数。能否使得改变后的a[]的MEX值恰好为改变前a[]的MEX值+1。输出Yes或No。思路推演设改变前的MEX值为x。我们想要使得改变后MEX为x+1，需要3个条件：创造出x消灭x+1保留0~x-1为了满足创造x的条件，则我们这个任意正整数的值，必须是x。为了满足消灭x+1的条件，则x+1出现的区间，我们一定需要选中。至于能不能保留0~x-1，尽可能使选中的区间较小即可。当然，这里需要讨论一个额外的可能：不存在x+1，那只需要看改变前的MEX是否为n值即可。D.The Butcher算法本质思维、模拟题目大意原有数据不详的大矩形a*b，现在对其切割n-1刀（横切or竖切），分割成n个矩形，切割规则如下：每次切割后的矩形，其中一块放入盒子里，另外一块留在案板上继续等待切割矩形无法旋转现给出这n个打乱顺序后的矩形，请计算其可能的初始形状。思路推演现在，这种题要么从最先切的块的矩形开始猜，要么从最后切的块的开始猜。最后切的块不太好找，最先切的块可以把范围缩小，分别是长最长，宽最长。因为其独特的切割规则，所以初始矩形必然存在长or宽可以被找到。所以我们可以假设其第一次是横切、第一次是竖切。然后依次用长宽还原其切割方式，若能还原则说明可行，不能说明不可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int l[maxn], r[maxn]; map<int, vector<int>> a2b, b2a; bool vis[maxn]; bool qie(int &a, int &b, char c) { bool f=0; if (c=='a') { for (int idx:b2a[b]) { if (vis[idx]) continue; a -= l[idx]; f = 1; vis[idx] = 1; } } else if (c=='b') { for (int idx:a2b[a]) { if (vis[idx]) continue; b -= r[idx]; f = 1; vis[idx] = 1; } } return f; } // 还原，返回1表示可行，返回0表示不可行 bool dfs(int a, int b, int ct=0) { if (a==0 || b==0) return 1; if (ct%2) { if (!qie(a, b, 'a')) return 0; } else { if (!qie(a, b, 'b')) return 0; } return dfs(a, b, ct+1); } inline void solve() { //init cin>>n; int ma=0, mb=0, sum=0; a2b.clear(), b2a.clear(); for (int i=1; i<=n; i++) { cin>>l[i]>>r[i]; sum += l[i]*r[i]; // 拿到总面积 ma=max(ma, l[i]); mb=max(mb, r[i]); a2b[l[i]].push_back(i); b2a[r[i]].push_back(i); } set<pair<int, int> > ans; if (sum%ma==0) // 初步判断是否第一次为竖切 { rep(i,1,n) vis[i]=0; if (dfs(ma, sum/ma, 0)) // 进一步判断，第一次竖切能否切割成功 ans.insert({ma, sum/ma}); // 可行加入答案 } if (sum%mb==0) { rep(i,1,n) vis[i]=0; if (dfs(sum/mb, mb, 1)) ans.insert({sum/mb, mb}); } cout<<ans.size()<<endl; for (auto i:ans) cout<<i.first<<" "<<i.second<<endl; return; }