Codeforces Round 865 (Div. 2) A.Ian Visits Mary算法本质思维题目大意已知a b从(0,0)最多跳2次到(a,b)点，要求每次跳跃的dx dy互质。思路推演1与所有数互质，只需要先填x轴再跳y轴就可以了。B.Grid Reconstruction算法本质思维题目大意给定偶数n，在2*n的地图上，将1~2n的数字填入其中。当走到x+y为偶数的格子会使得成本加上当前格子的数字，反之减去。现在小明要从左上角走到右下角，他会选择成本最小的路。现在需要你构造这个地图，最大化小明的行走成本。思路推演已知有n个格子是增加成本的，有n个格子是减少成本的。自然用大数填充前面的，小数填充后面的。另外起点和终点是必然经过的，其他点都是可能不经过的，所以起点终点需要填2n 2n-1。接下来探讨中间格子填什么，当小明已知地图要求最少成本路径时，是用的dp来求。而我们已经确定格子的数字大小，只能做调换的时候：让每个格子从上面2种可能状态转移过来的成本尽可能相近是显然的正解。观察一下样例蕴含的规律。C.Ian and Array Sorting算法本质思维题目大意给定长度n的数组a[]，你可以进行任意次以下操作，目标是使得a[]非递减排序，检查是否可能：选择a[i] a[i+1]都+1或者-1思路推演稍加模拟扩展，可以发现，对任意差距为偶数的元素，可以做到+1 -1，即元素值的转移。这是一个很好的结论，这意味我们可以把元素分为奇数下标、偶数下标两组。这两组元素内部可以转移值，所以必然可以构造非递减。那现在的情况就是，需要构造两组元素之间的非递减。若元素个数为偶数可行的结果显然是：偶数下标组和 >= 奇数下标组和若元素个数为奇数则奇数组多了一个元素，可操作性就大很多了。模拟一下，必然成立。D.Sum Graph算法本质思维（交互题）题目大意存在一个长度n且未知的排列、一个有n个节点的空图，现在你可以进行至多2n次以下操作之一，最后需要猜测排列2次：建图：输入x，图中编号之和为x的节点连接一条边查询：输入i j，返回图中编号为p[i] p[j]的最短距离（无法抵达输出-1）最后可以猜测排列2次，其中一次正确即为正解。思路推演先拿到这个题还是有点蒙。仔细查看查询操作，其依赖于建立好的图，所以建立好图非常关键。模拟一下建图，显然第一次操作的最有解为x=n+1，每个点都是平等的，这样可以多建边。已当前图为例，我们可以用n-1次操作得到相连的2个点，显然信息不够的。最大的一个问题是，没有利用好距离，只利用了是否可达。于是我们再次尝试，x=n，将所有图连接成一条线。这次很好解决了问题，如果我们随机选择一点让其查询其他所有点，而且对于同一点来说：相同距离表示的点至多有2个点。但是正是这不确定性，让我们没办法用剩下的n-1次查询搞定。为了解决这种不确定性，查询点在线边缘即可解决，我们可以找到距离随机点最远的点，其一定是边缘点。然后通过边缘点，查询其他所有点。但是边缘点本身在左在右不确定后，对应了题目最后允许猜测2次。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], ans1[maxn], ans2[maxn]; int dis[maxn]; inline void solve() { //init int x; cin>>n; int l=1, r=n; cout<<"+ "<<1+n<<endl; // 建图 cin>>x; cout<<"+ "<<2+n<<endl; cin>>x; for (int i=1; i<=n; i++) // 记录建图之后的顺序、节点值 { if (i%2) a[i] = l++; else a[i] = r--; } for (int i=2; i<=n; i++) // 找个随机点p[1]，询问与其他点的距离 { cout<<"? 1 "<<i<<endl; cin>>dis[i]; } int s=2; // s为边缘点 for (int i=2; i<=n; i++) // 距离最远的肯定是边缘点 if (dis[i] > dis[s]) s = i; //cal ans1[s] = a[1]; // 可能是左边缘 ans2[s] = a[n]; // 可能是右边缘 for (int i=1; i<=n; i++) { int w; if (i==s) continue; // 自己和自己不需要询问 else { cout<<"? "<<s<<" "<<i<<endl; // 询问距离，通过距离推断 cin>>w; } ans1[i] = a[1+w]; ans2[i] = a[n-w]; } cout<<"! "; // 猜测答案 for (int i=1; i<=n; i++) cout<<ans1[i]<<" "; for (int i=1; i<=n; i++) cout<<ans2[i]<<" \n"[i==n]; cin>>x; return; }E.Between算法本质思维题目大意给定n m，有编号1~n的节点，需要你构造一个尽可能长的序列（可能是无限），满足以下条件：序列的元素是某个节点节点1只有一个接下来会给出m对i j，表示序列每两个i节点中至少存在一个j节点若序列无限输出“无限”否则输出序列n <= 1.5e3思路推演-数目稍加模拟发现这是一个需要用图来思考的题：i j其实是j-->i的边，点x的最大数目 == min( 所有指向x点节点的最大数目中 ) + 1顺带可以发现，当某个点不受限制时，变存在无限长的情况。结合题目性质，想当然认为这是topo排序。经过模拟，成环情况下，其实也并不影响节点数目的判断，类似于最短路，到节点1的最短路。那么现在节点可行的最大数目都求得，接下来需要考虑怎么排序才能满足其中的“夹”条件。思路推演-构造-1首先肯定得优先用数目多的节点，然后接着用其指向的节点，大致思路是这样的。所以把边反向：即数目多的点 --> 数目少的点。这样更好思考。我们观察节点的连接情况，其指向的其他节点的数目，都是>=当前数目-1的。其中数目少的节点x --> 数目多的节点y其实也可以看作y-->x。（相同数目也可行）通过这个操作，重新改变节点边关系，可以保证无环。然后可以用稍加改造的topo来搞定：入度0的点入队若队头的节点数目还有，输出一次，队头节点数目--弹出队头节点，其指向节点入度--，若入度为0则入队这样重复多次直到所有节点数目为0即可。思路推演-构造-2（超越答案思路）但是之前的做法有些麻烦，需要修改边，然后再度topo，继续思考：对于当前数目多节点 --> 数目少节点的情况，指向一个节点也是指，指向多个也是指（最坏情况就是全部指）让数目多节点 --> 所有数目比其少的节点则可以省略修改边的过程，topo排列也变的简单无比ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int num[maxn]; vector<int> g[maxn]; void cls() { for (int i=1; i<=n; i++) g[i].clear(), num[i]=-1; } inline void solve() { //init cin>>n>>m; cls(); while (m--) { int u, v; cin>>u>>v; g[v].push_back(u); } //cal num[1] = 1; queue<int> q; q.push(1); int cnt=0; // 记录遍历的点数 while (q.size()) // 最短路bfs { int u=q.front(); q.pop(); cnt++; for (int v:g[u]) { if (num[v] == -1) { num[v] = num[u] + 1; q.push(v); } } } if (cnt!=n) // 存在不走到1的节点 { cout<<"INFINITE"<<endl; return; } // 否则一定可行 int len=0; for (int i=1; i<=n; i++) len += num[i]; cout<<"FINITE"<<endl; cout<<len<<endl; vector<int> v; // topo排序输出 rep(i,1,n) v.push_back(i); sort(v.begin(), v.end(), [](int a, int b){return num[a] > num[b];}); while (num[v[0]]) { for (int u:v) { if (num[u]==0) break; cout<<u<<" "; num[u]--; } } cout<<endl; return; }

Codeforces Round 864 (Div. 2) A.Li Hua and Maze算法本质思维题目大意给定n*m的棋盘，点(x1, y1)和(x2, y2)。请在棋盘上放置方块，阻断(x1, y1)到(x2, y2)的所有路线（不可放起点、终点上）。输出最小化的方块数。思路推演首先想到就是：阻断墙、围绕起点终点围一圈等策略。随后手动模拟，发现阻断墙这种方式属于“围点”的一种。所以手动检测起点终点周围的空间是否合法，计算“围点”所需要的代价，然后输出小值。B.Li Hua and Pattern算法本质思维题目大意给定n*n的01矩阵、k值。需要恰好执行k次以下操作，使得矩阵 = 矩阵旋转180°：选择一个方格反转其值判断是否可行。思路推演既然最后矩阵 = 矩阵旋转180°，我们就可以给矩阵的每个格子构建一个对应关系：(x, y) ~ (n-x+1, n-y+1)我们仅需使得所有格子对都相等即可。所以我们统计所有的不等格子对数，然后k值减去他们，剩余的k为多余的操作数。（如果不够减，显然不可行）想要消耗掉剩余的k值，偶数的话显然可行，奇数的话，需要看是否存在自己与自己为一个格子对的情况——即n为奇数。C.Li Hua and Chess算法本质思维题目大意给定n*m的棋盘，棋盘中存在一个位置未知的国王，每轮可移动到周围8格之一。现在你可以进行至多3次询问，每次询问给定一个点(x,y)，返回国王走到(x,y)的最少轮次。（交互题）最后输出国王位置。思路推演3次是一个相对奇怪的数目，但是不管怎样，先手动模拟一下。模拟了一会，发现这个很类似雷达的检测原理。第一次询问的显然最优解为(1,1)，最坏的情况是是国王处于一个类L的格子范围中。然后只需要询问在L的两侧边缘的位置，就可以得到具体位置了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>m; int v1, v2, x, y; cout<<"? 1 1"<<endl; // 第一次询问的最优解 cin>>v1; v1++; x = y = v1; // 初始化x y if (v1 <= n) // 确认y值 { cout<<"? "<<v1<<" 1"<<endl; cin>>v2; y = v2+1; } if (v1 <= m) // 确实x值 { cout<<"? 1 "<<v1<<endl; cin>>v2; x = v2+1; } cout<<"! "<<x<<" "<<y<<endl; return; }D.Li Hua and Tree算法本质思维、模拟题目大意给定n节点的树、每个节点的节点重要值a[]。以x节点为根的子树拥有2个属性：树重要值、树大小：树重要值：子树中所有节点的节点重要值之和（含自己）树大小：子树中所有节点个数（含自己）非叶子节点x有一个属性：最大儿子节点（译为heavy son）：最大儿子节点：其所有儿子节点中，作为子树根节点的树大小最大的 儿子节点（如果有多个值一样的，选下标较小的）接下来有m次询问or修改，给出op x：op==1：询问x节点为根的子树的树重要值op==2：修改设fx是x的父节点，sx是x的最大儿子节点（heavy son）。删去fx x边，新增fx sx边——即x边成sx的儿子节点，sx代替x与父节点连接。思路推演这种模拟题就是典型的“思路清晰，写的超快”。我们列出必备的属性：对于节点x来说，其具备的属性：节点重要值父节点最大儿子节点（heavy son）对于x做根节点的子树来说，其具备的属性：树重要值树大小然后根据属性，赋予不同的数据结构、搭配：节点节点重要值不需要修改，直接用a[]表示即可父节点需要修改，用fu[]表示最大儿子节点（heavy son）得搭配“儿子节点集合”使用，需要排序、修改，set显然是个不错的选择，里面放入<树重要值、下标>子树树重要值需要修改，用importance[]表示树大小需要修改，用weight[]表示对于询问，可以直接输出importance[x]，对于修改，接下来弄清楚其具体的数值转移：（记得画图才清晰可见）假设当前点x，父节点fx，儿子节点sa sb sc，其中sa为最大儿子节点heavy son。首先可以发现，整个影响范围有限，只关于x fx sa三个节点属性、子树属性sa的子树属性完全继承x先前的子树属性（树重要值、树大小）x的子树属性需要减去sa先前的子树属性（树重要值、树大小）sa的儿子节点集合新增关于x修改后的<树重要值, x>x的儿子节点集合删去关于sa的值fx的儿子节点集合删去关于先前的x的值，新增当前关于sa的值x父节点修改为sasa的父节点修改为fxac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> g[maxn]; // 记录题目给出的边，方便初始化图 int weight[maxn], importance[maxn]; // 子树属性 int a[maxn], fu[maxn]; // 节点属性 struct node { int w, id; bool operator < (const node &b) const // weight较大优先，weight相同id较小优先 { if (w == b.w) return id < b.id; return w > b.w; } }; set<node> son[maxn]; // <weight, son_id> void dfs(int u, int fr=0) // 初始化图 { fu[u] = fr; for (int v : g[u]) { if (v == fr) continue; dfs(v, u); weight[u] += weight[v]; importance[u] += importance[v]; son[u].insert({weight[v], v}); } weight[u]++; importance[u]+=a[u]; } void cg(int x) // 修改函数 { if (son[x].size()==0) return; int fx = fu[x]; node sx=*son[x].begin(); // heavy son int new_w_son = weight[x]; // 继承 int new_i_son = importance[x]; int new_w_x = weight[x] - weight[sx.id]; // 减去A树 int new_i_x = importance[x] - importance[sx.id]; weight[x] = new_w_x; // 更新 importance[x] = new_i_x; weight[sx.id] = new_w_son; importance[sx.id] = new_i_son; son[x].erase(sx); // 儿子集合更新 son[sx.id].insert({weight[x], x}); son[fx].erase({weight[sx.id], x}); son[fx].insert({weight[sx.id], sx.id}); fu[sx.id] = fx; // 更新父节点 fu[x] = sx.id; } inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>a[i]; for (int i=1; i<=n-1; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1); // 初始化图 while (m--) { int op, x; cin>>op>>x; if (op==1) // 输出树重要值 cout<<importance[x]<<endl; else if (op==2) // 修改 cg(x); } return; }E.Li Hua and Array算法本质思维、数学（欧拉函数）、数据结构（线段树）题目大意设f()表示欧拉函数：f(x)表示<=x且与x互质的正整数个数。现给长度n的a[]、m，接下来会有m次询问、操作：op==1：给定l r，操作对于i属于[l,r]：a[i] = g(a[i])op==2：给定l r，询问对于a[l~r]最少需要几次a[i]=f(a[i])才能使得区间内值相等。（这个操作仅本轮）前置知识在接下来的思路推演中，默认已知前置知识单个x求欧拉函数复杂度O(sqrt(x))范围欧拉函数有线性筛O(n)的做法。若x为偶数：f(x) = x/2若x为基数：f(x) = 小于x的偶数这意味x值想要通过不断自我欧拉值更新来抵达1，最多需要2logx次思路推演思路清晰看到操作与查询时，第一时间想到的就是——LCA。同时这是区间点LCA，显然需要用线段树去优化。再回过头思考一下欧拉函数，其本身的值可以看作一颗节点数为5e6、高度最大为2*log(5e6)的树。（称之为欧拉树）思路推演-框架建立接下来根据题意，仔细思考线段树需要的数据、优化（思路清晰）查询操作应该首先观察先看查询操作：需要log的复杂度搞定区间点的lca，还需要输出到点lca的操作次数对于两点的lca查询复杂度为2log(5e6)，如果加上维护每个区间的lca值，可以将区间lca值查询复杂度将为：2log(5e6) * log(1e5)。这个复杂度还可以接受。再看修改操作：也需要log的复杂度搞定，同时还需要维护区间的lca值对于基础的加法线段树，这一步是采用了懒标记来优化的。但是因为已知需要维护（实时更新）区间的lca值，所以肯定是无法用懒标记维护的。但是，思考欧拉树的性质，其高度最大为log级别，到根节点后再次操作就无法前进了，所起其实可以暴力更新的。不过此暴力非彼暴力，这需要一个属性，来表示这个区间的值是否都抵达了根节点，若都抵达了，则在更新中忽略这个区间。这样操作，单次修改的均摊复杂度为：2log(5e6) * log(1e5)。再加上区间lca的值、点到lca值的操作次数。到此为止，代码的框架已出：构建2颗树：欧拉树、线段树线段树节点属性：基础的l r布尔值f：标记区间是否全部值为欧拉树根节点zu：区间所有元素的lca节点cnt：区间所有元素到zu的操作数思路推演-细节补充接下来需要补充方法。欧拉树，只是名义上的树而已，实际不用建树，把线性欧拉函数的板子添加到代码中。然后构建树节点node：// l r为节点基础属性 // zu记录区间lca值，cnt记录区间元素都抵达zu需要的操作数 // f记录区间元素是否都抵达了根节点（优化更新指令） struct node { int l, r, zu, cnt, f; }; node tr[maxn*4];随后建树，但是建树的过程发现，我们还没有写区间和区间结合的函数。正好这部分修改、询问操作都需要，就单独写成一个函数：zu：需要暴力求解cnt：通过zu整体计算f：直接判断即可因为是线段树中的区间结合函数，所以可以看作是其大区间的更新函数：void update(node &fu, node &lson, node &rson) // fu区间的属性，通过lson和rson来更新 { fu.l = lson.l; // 初始化l,r fu.r = rson.r; fu.f = lson.f && rson.f; // 更新f fu.cnt = lson.cnt + rson.cnt; // 初始化cnt int x=lson.zu, y=rson.zu; // x,y为区间左右两端的lca值 while (x!=y) // 暴力寻找lca值 { if (x>y) x=phi[x], fu.cnt+=(lson.r-lson.l+1); // 更新cnt else y=phi[y], fu.cnt+=(rson.r-rson.l+1); } fu.zu = x; // 更新zu }然后我们再写建树函数：void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if(l == r) // 结束递归语句 { tr[u].zu = a[l]; // 单个点构成的区间，其lca值就是自己 tr[u].cnt = 0; // 自己到祖先的距离为0 tr[u].f = a[l]==1; // 检查所有元素是否为根节点值1 return; } int mid = (l + r)/2; build(2*u, l, mid), build(2*u+1, mid+1, r); update(tr[u], tr[2*u], tr[2*u+1]); // 更新区间属性 }接着需要修改函数：void modify(int u, int l, int r) { if (tr[u].f) return; // 优化，如果区间元素都抵达了根节点，就不用更新了 if (tr[u].l==tr[u].r) // 单值区间 { tr[u].zu = phi[tr[u].zu]; // 更新lca值（cnt值一直为0不需要改变） tr[u].f = tr[u].zu==1; // 检查是否抵达根节点 return; } int mid=(tr[u].l+tr[u].r)/2; if (l<=mid) modify(2*u, l, r); // 递归左子树 if (r>mid) modify(2*u+1, l, r); // 递归右子树 update(tr[u], tr[2*u], tr[2*u+1]); // 更新区间属性 }再然后是查询函数：查询函数的细节略有不同，核心在于根据需要构建一个新的node，所以用node最为返回值显然更好node query(int u, int l, int r) { if (l<=tr[u].l && tr[u].r<=r) return tr[u]; // 区间完全覆盖，返回这个区间 int mid=(tr[u].l+tr[u].r)/2; if (r<=mid) return query(2*u, l, r); // 仅在左半边，交给左节点处理 if (l>mid) return query(2*u+1, l, r); // 仅在右半边，交给右节点处理 node res, lson=query(2*u, l, r), rson=query(2*u+1, l, r); // 左右节点都有用，分别处理 update(res, lson, rson); // 更新区间属性 return res; }ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 const int maxn=1e5+5; // 如果都开5e6且开longlong会报内存 const int maxm=5e6+5; int a[maxn]; // 初始的欧拉值 vector<int> prime; bool not_prime[maxm]; int phi[maxm]; // phi[x] = x的欧拉函数值 void get_phi(int max_num) { phi[1]=1; for(int i=2; i<=max_num; i++) // 同时i也是枚举的倍数 { if(!not_prime[i]) // i是质数 { prime.push_back(i); // 记录质数 phi[i] = i-1; // phi[]对素数的专程处理 } for(int idx=0; prime[idx]*i<=max_num; idx++) { not_prime[i*prime[idx]] = 1; // i*primes[j]不是质数 if(i%prime[idx]==0) // 情况1 primes[j]是i的最小质因子 { phi[i*prime[idx]] = phi[i]*prime[idx]; break; } phi[i*prime[idx]] = phi[i]*(prime[idx]-1); //情况2 } } } // l r为节点基础属性 // zu记录区间lca值，cnt记录区间元素都抵达zu需要的操作数 // f记录区间元素是否都抵达了根节点（优化更新指令） struct node { int l, r, zu, cnt, f; }; node tr[maxn*4]; void update(node &fu, node &lson, node &rson) // fu区间的属性，通过lson和rson来更新 { fu.l = lson.l; // 初始化l,r fu.r = rson.r; fu.f = lson.f && rson.f; // 更新f fu.cnt = lson.cnt + rson.cnt; // 初始化cnt int x=lson.zu, y=rson.zu; // x,y为区间左右两端的lca值 while (x!=y) // 暴力寻找lca值 { if (x>y) x=phi[x], fu.cnt+=(lson.r-lson.l+1); // 更新cnt else y=phi[y], fu.cnt+=(rson.r-rson.l+1); } fu.zu = x; // 更新zu } void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if(l == r) // 结束递归语句 { tr[u].zu = a[l]; // 单个点构成的区间，其lca值就是自己 tr[u].cnt = 0; // 自己到祖先的距离为0 tr[u].f = a[l]==1; // 检查所有元素是否为根节点值1 return; } int mid = (l + r)/2; build(2*u, l, mid), build(2*u+1, mid+1, r); update(tr[u], tr[2*u], tr[2*u+1]); // 更新区间属性 } void modify(int u, int l, int r) { if (tr[u].f) return; // 优化，如果区间元素都抵达了根节点，就不用更新了 if (tr[u].l==tr[u].r) // 单值区间 { tr[u].zu = phi[tr[u].zu]; // 更新lca值（cnt值一直为0不需要改变） tr[u].f = tr[u].zu==1; // 检查是否抵达根节点 return; } int mid=(tr[u].l+tr[u].r)/2; if (l<=mid) modify(2*u, l, r); // 递归左子树 if (r>mid) modify(2*u+1, l, r); // 递归右子树 update(tr[u], tr[2*u], tr[2*u+1]); // 更新区间属性 } node query(int u, int l, int r) { if (l<=tr[u].l && tr[u].r<=r) return tr[u]; // 区间完全覆盖，返回这个区间 int mid=(tr[u].l+tr[u].r)/2; if (r<=mid) return query(2*u, l, r); // 仅在左半边，交给左节点处理 if (l>mid) return query(2*u+1, l, r); // 仅在右半边，交给右节点处理 node res, lson=query(2*u, l, r), rson=query(2*u+1, l, r); // 左右节点都有用，分别处理 update(res, lson, rson); // 更新区间属性 return res; } inline void solve() { //init get_phi(5e6); // 线性筛欧拉值 cin>>n>>m; rep(i,1,n) cin>>a[i]; build(1, 1, n); // 建树 while (m--) { int op, l, r; cin>>op>>l>>r; if (op==1) // 修改操作 modify(1, l, r); else // 询问操作 cout<<query(1, l, r).cnt<<endl; } return; }

Codeforces Round 863 (Div. 3) A.Insert Digit算法本质思维题目大意给定正整数a和小于10的正整数b，可以选择将b插入a的任意位置。输出最大化a思路推演显然来说（稍微模拟一下），规律即从高位数向低位，找到第一个小于b的数字位置。注意，最坏的情况b也需要插入a的末尾。B.Conveyor Belts算法本质思维题目大意对于n*n（偶数n）的矩阵来说，其由n/2条口型传送带组成（如图）：传送带不停顺时针循环，移动到相邻传送带需要花费1元现在Alice想从位置s移动到位置t，输出最小化成本。思路推演显然，我们只需要计算出s和t所处的传送带层级，然后相减即可得到正解。如何通过位置得到传送带层级呢：观察图像，发现整体非常对称，我们可以将传送带上的位置，都转移到左上方位。然后继续观察，当位置处于左上方位，我们可以用min(x,y)来表示传送带的层级。C.Restore the Array算法本质思维题目大意对于长度n的a[]，存在长度n-1的b[]：b[i]=max(a[i], a[i+1])。现在给定长度n-1的b[]，找出一种可能的a[]。（保证有解）思路推演对于b[i]来说，相关联的只有a[i]和a[i+1]，反之对于a[i]来说，关联的只有b[i-1]和b[i]。（可以画个图更直观）假设对于当前的a[i]来说，取值范围为0 ~ min(b[i-1], b[i])，同时可以理解的是，尽量取大是最优解。既然题目自己保证有解，我们只需要找最优解即可。再考虑边缘情况，a[1]=b[1]和a[n]=b[n-1]为最优解。D.Umka and a Long Fligh算法本质思维题目大意设f()是下标从0开始的斐波那契数列。现在给定一个f(n) * f(n+1)的矩形，和特殊位置(x,y)，询问是否可以切割矩形并满足以下条件：切割为n+1个正方形所有正方形边长必须为斐波那契数最多存在一对正方形的边长相等其中(x,y)必须切割为一个1*1的正方形思路推演这些条件，一看有些懵，还是来看看样例吧。可以发现，样例切割的n+1个正方形的边长为：f(n)、f(n-1)、......、f(1)、f(0)这也恰好符合所谓的最多存在一对正方形的边长相等。同时有闲心还可以证明一下：f(n)*f(n+1) = f(n)^2 + f(n-1)^2 + ... + f(1)^2 + f(0)^2（递归证明）随后只有最后一个条件需要满足了：其中(x,y)必须切割为一个1*1的正方形总体来说，矩形还是先切大正方形好切，我们在切大正方形的同时，就需要考虑如何避免切到(x,y)，以此尽可能留其到最后。比如当前矩形长>高，我们固定切正方形切最左边部分， 则通过水平翻转，让(x,y)尽可能靠右，然后再切割。这是贪心最优解，如果无可避免会切割到(x,y)的话，说明不可行。随后旋转剩下的矩形，继续切割，递归写法。E.Living Sequence算法本质思维题目大意Alice有一个1~1e12数字顺序排列的数组a[]，因为她不喜欢数字4，删去了所有有4的数字。现在给定n，返回a[n]的值。思路推演显然的是，我们通过x计算1~x中不含4的数字个数，比反推容易许多。同时其存在单调性，可以用二分协助。如何计算1~x中不含4的数字个数：九进制其实这本质就是九进制嘛其实还有数位dp的方式，但是实际上是九进制的复杂版本ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 string to_s(int x) // 将x转移到string[]中，同时处理掉4 { bool lim=1; // 没有遇到4前存在限制 string res = to_string(x); // 高位在前（方便处理4） for (int i=0; i<res.length(); i++) { if (lim) { if (res[i]=='4') { res[i]='3'; lim=0; } } else res[i] = '9'; } return res; } int jin_9(string x) // 九进制处理 { int res=0; reverse(x.begin(), x.end()); for (int i=0; i<x.length(); i++) { int num = x[i] - '0' - (x[i]>'4'); res += num * qpow(9, i, 1e18); } return res; } inline void solve() { //init cin>>n; int l=1, r=1e13+5; // r要多开大10倍才够 int ans=r; while (l<=r) { int mid=(l+r)/2; int num=jin_9(to_s(mid)); if (num>=n) { ans=mid; // 可能好几个答案相同，找那个最小的（因为只有最小的才不含4） r=mid-1; } else l=mid+1; } cout<<ans<<endl; return; }F.Is It Flower?算法本质思维、模拟题目大意对于一个无向图，恰好满足以下条件称之为美丽：初始有k个点形成简单环这k个点各自又与k-1个点形成简单环，这部分的简单环之间不相交对于给定的无向图，是否能找到某个k使其满足美丽输出YES，反之输出NO。思路推演对于一个美丽图显然存在：边数：k*k+k点数：k*kk个度数为4的点、k*k-k个度数为2的点这部分条件肯定不足以判断美丽，主要是用于规范一下数据范围。题目需要我们判断简单环，经过思考，对于n点为简单环的充要条件为：（这里的度概念仅限n点之间的边）每点度数为2连通性对于题目的第一个要求：初始有k个点形成简单环相对好解决，因为这k个点即度数为4的点，其边、点都很容易取出来，然后判断。随后对于其第二个要求：这k个点各自又与k-1个点形成简单环，这部分的简单环之间不相交发现只需要删除中心k点的边，即保证剩下的图会形成k个k点组成的简单环。我们只需要：度数都为2——都是简单环每个连通块的元素个数为k——k个长度k的简单环中心点所属的连通块不同——每个简单环有一个中心点ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 省略了并查集板子 inline void solve() { //init vector<pair<int,int>> g; // 边 map<int, int> d, d1, d2; // 度、中心度、边缘度 cin>>n>>m; int k=m-n; rep(i,1,m) { int u, v; cin>>u>>v; if (u > v) swap(u, v); g.push_back({u, v}); d[u]++, d[v]++; } // 规范数据范围 map<int, int>cnt_du; for (auto i : d) cnt_du[i.second]++; if (n==k*k && m==k*k+k && cnt_du[2]==k*k-k && cnt_du[4]==k); else { cout<<"NO"<<endl; return; } // 中心k个点成环 init_set(); vector<int> center; for (auto i:d) // 中心点 if (i.second==4) center.push_back(i.first); for (auto i:g) // 中心边 { if (d[i.first]==4 && d[i.second]==4) { d1[i.first]++, d1[i.second]++; union_set(i.first, i.second); } } for (int u:center) // 判断是否为简单环 { if (d1[u]==2 && find_set(u)==find_set(*center.begin())); // 度数为2，且联通 else { cout<<"NO"<<endl; return; } } // 边缘k个环 init_set(); for (auto i:g) { if (d[i.first]==2 || d[i.second]==2) // 边缘边 { d2[i.first]++, d2[i.second]++; union_set(i.first, i.second); } } for (int i=1; i<=n; i++) // 说明有k个k点环互不相交 { if (d2[i]==2 && len[find_set(i)]==k); // 保证有k个长度k的简单环 else { cout<<"NO"<<endl; return; } } set<int> st; for (int u:center) st.insert(find_set(u)); if (st.size()==k); // 保证每个环中都有1个中心点 else { cout<<"NO"<<endl; return; } //out cout<<"YES"<<endl; return; }G2.Vlad and the Nice Paths (hard version)算法本质思维、dp题目大意给定长度n的a[]和k，满足下列条件的a[]子序列称之为美丽：长度为k*x子序列按序分成x组（每组有k个元素），每组元素相等找到美丽且最长的子序列数目。（%mod）注：空数组记作长度为0的一种情况。思路推演显然，如果对于这样的一个子序列，当想往里加元素，只与最后一个元素的值有关，十分适合dp性质。同时我们对个数有要求，需要表示已选个数的信息，值作为方案数即可。创建一个dp[i][j]表示已选了i个元素，最后一个元素的值为j。随后推理转移方程式子：不选择当前a[i]那就不用转移选择当前a[i]新组第一个元素（j%k==1）dp[j][val] += dp[j-1][1~n]（这里显然需要优化处理）其他元素dp[j][val] += dp[j-1][val]对于dp[j-1][1~n]的优化，我们设dp[][0]表示dp[][1~n]的值，每次更新时也向dp[][0]同步更新一下即可。同时因为最后要输出最长的，所以我们还建立了一个vis[][]与dp[][]同步，表示可以抵达的地方。其实可以使用dp值是否为0判断是否可达，但是因为取模的问题，0值也可能表达是mod。当然还可以继续用魔法对抗，在取模中先-1后+1，这样mod值不会被模成0，此题可用。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn][maxn]; // 已选j个元素、最后一个元素的值 bool vis[maxn][maxn]; int val[maxn]; void cls() { for (int i=0; i<=n; i++) { for (int j=0; j<=n; j++) dp[i][j] = vis[i][j] = 0; } } inline void solve() { //init int k; cin>>n>>k; cls(); rep(i,1,n) cin>>val[i]; //cal dp[0][0] = 1; // 空列表的方案数为1 vis[0][0] = 1; // 空列表默认可行 for (int i=1; i<=n; i++) { for (int j=i; j>=1; j--) // 从大往小数，避免干扰当前轮次 { if (j%k == 1) // 开新组 { vis[j][val[i]] |= vis[j-1][0]; dp[j][val[i]] += dp[j-1][0]; dp[j][val[i]] %= mod; vis[j][0] |= vis[j-1][0]; dp[j][0] += dp[j-1][0]; dp[j][0] %= mod; } else { vis[j][val[i]] |= vis[j-1][val[i]]; dp[j][val[i]] += dp[j-1][val[i]]; dp[j][val[i]] %= mod; vis[j][0] |= vis[j-1][val[i]]; dp[j][0] += dp[j-1][val[i]]; dp[j][0] %= mod; } } } int ans; for (int i=n/k*k; i>=0; i-=k) { if (vis[i][0]) { ans = dp[i][0]; break; } } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 862 (Div. 2) A.We Need the Zero算法本质思维题目大意给长度n的数组a[]，必须进行一次以下操作，使得操作后的a[]的元素异或和为0：选择值x，使得a[i] ^= x输出x（不行输出-1）思路推演异或运算有交换律，所以操作后的a[]元素异或和为：a[1] ^ a[2] ^ ... ^ a[n] ^ x ^ x ^ ... ^ x（n个x）如果n为偶数，则可以消去所有x，反之会留下一个x。根据前面的异或和值调整x的值即可。（n偶数且前面异或和不为0，输出-1）B.The String Has a Target算法本质思维题目大意给长度n的字符串s，必须进行一次以下操作，最小化s字典序：调整某个字符至最前面输出操作后的s思路推演显然，我们需要选择一个最小的字符放到最前面。相同的字符，我们用靠后的字符收益更大。B.Place for a Selfie算法本质思维、数学、模拟题目大意有n条过原点的直线设为y1 = kx有m条开口向上的抛物线设为y2 = ax^2 + bx + c (a>0)对于每条抛物线，找到一条不与其相交的直线，输出其斜率（无则-1）思路推演因为抛物线开口向上，模拟了一会即可发现：抛物线、直线斜率都为k的y值为两者最接近的点，若y2 > y1则两者一定不可交随后带入式子，可以推出以下结论：(k-b)^2 < 4ac则两者一定不可交。所以我们要找到距离b最小的k，用二分找b附近的2个k，挨个试验即可。D.A Wide, Wide Graph算法本质思维题目大意给定n个节点的树，设每两点间的距离为树上距离。现将n个点都隔离出来（初始无边），规定距离>=k的两点建立新边，f(k)为当前情况下连通块数目。k=1~n，输出所有的f(k)。思路推演对于点i，当ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 856 (Div. 2) A.Prefix and Suffix Array算法本质思维题目大意对于字符串S，给你所有的前缀字符串、后缀字符串（除了本身、空字符串）。判断s是否是回文字符串。思路推演所有给出的长度相等的字符串，判断其是否倒置相等。B.Not Dividing算法本质思维题目大意给一数组a[]长度为n，可以给任意元素+1操作，最多操作2n次。保证其a[i+1]%a[i] != 0。输出操作后的数组a[]。思路推演对于一组a[i] 和 a[i+1]：修改a[i]如果遇到了3 3*4*5这样的数字，不止需要改修2次，pass修改a[i+1]如果保证a[i]!=1，则a[i+1]至多修改一次，就上保证前者不为1的一次修改，2n次修改足矣C.Scoring Subsequences算法本质思维、数据结构题目大意给定长度为n的数组a[]，其有收益和成本2个属性：收益所有元素的乘积 除以 长度的阶乘成本其收益最大的子数组（可能为自己或空）的最大长度现在请给出n个前缀a[]的数组成本。思路推演子数组的收益，随着元素个数的增加，有明显的单调性。所以是可以用二分来做的。二分做法相对简单多样，不与介绍。下面说一下此题原本的O(n)做法。仔细观察，会发现其实收益的计算方式很简单——讲所有元素排序，从较小值开始，如果其值小于保留元素的个数，则丢弃较小值。所有完全只有一个优先列队历便即可。另外题目给的a[]是有序的，这代表可以可以只用一个双端队列，达到O(n)做法。不过因为本身有序，好像用优先队列，也不会增加复杂度ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; //cal deque <int> q; for (int i=1; i<=n; i++) { q.push_back(a[i]); if (q.front() < q.size()) q.pop_front(); cout<<q.size()<<" "; } cout<<endl; return; }D.Counting Factorizations算法本质思维、dp题目大意已知任何一个正整数都可以用素数指数幂的形式表示，例如24 = 2^3 * 3^1。则设立一函数，例子：f(24) = {2 3 3 1} = {2 1 3 3} = f(54)。现在给出2n个元素，组成了上述的集合，请输出多少正整数的函数值为当前集合。n <= 2e3思路推演如果随便选n个元素当底数，则有$n!$种情况，如果考虑重复，则还需要除以除去重复数字的阶乘。所以可以发现，此题的重点，就是处理各种重复情况。将集合里只有素数可以当底数（且不能重复）。则把集合里的素数种类列出来，这些是有可能作为底数的存在，设有m类。（其他元素必定为指数）我们定义一个基础值res = n!，然后除以必定为指数的元素的重复部分。接下来根据有m类素数，但是只选择其中n种，意味还需要丢掉m-n个素数，而每丢掉一个素数，得到的值都是res除以其重复的次数（相当于乘以其小球分数）。现阶段的题意，可以转化为：有n个不同的小球，每种小球的分数为a[i]，现在要求选k个小球出来， 得分为所有小球分数相乘，现在输出将所有情况的得分相加值。选择dp优化，dp[x][y]表示前x个数丢掉y个。dp[x][y] = dp[x-1][y] + dp[x-1][y-1]*a[x]ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; int dp[maxn][maxn]; int fac[maxn]; bool is_prime(int x) { if (x==1) return false; for (int i=2; i*i<=x; i++) if (x%i==0) return false; return true; } inline void solve() { //init cin>>n; for (int i=1; i<=2*n; i++) cin>>a[i]; fac[0] = 1; //预处理阶乘，要处理到2n for (int i=1; i<=2*n; i++) fac[i] = fac[i-1]*i%mod; //cal int res=fac[n]; map<int, int> not_prime, prime; //val --> count vector <int> prime_list; prime_list.push_back(0); for (int i=1; i<=2*n; i++) { if (is_prime(a[i])) //是素数 prime[a[i]]++; else not_prime[a[i]]++; } for (auto u:not_prime) //除以非素数的重复部分 { res *= qpow(fac[u.second], mod-2, mod); res %= mod; } for (auto u:prime) //除以素数的重复部分（未彻底处理） { res *= qpow(fac[u.second-1], mod-2, mod); res %= mod; prime_list.push_back(u.first); } m = prime.size(); //m表示素数的“种类”数 if (m < n) //特殊判断s { cout<<0<<endl; return; } //cal 2 dp[1][0] = 1; dp[1][1] = qpow(prime[prime_list[1]], mod-2, mod); for (int x=2; x<=m; x++) { for (int y=0; y<=min(m-n, x); y++) { dp[x][y] = dp[x-1][y]; //dp转移公式 if (y>0) dp[x][y] += dp[x-1][y-1] * qpow(prime[prime_list[x]], mod-2, mod); dp[x][y] %= mod; } } int ans = dp[m][m-n] * res % mod; //output cout<<ans<<endl; return; }