- CF613E Puzzle Lover 题解
Description给定一个\(2\timesn\)的矩阵，每个位置上有一个小写字母。有一个长度为\(k\)的小写字符串\(w\)，询问矩阵中有多少条有向路径满足以下条件：路径上的字母连起来恰好为\(w\)。不多次经过同一个位置。只能向上下左右四个方向走。\(n,k\le2\times10^3\)，答案......
- IOI2022 邮局 加强版 题解
[IOI2000]邮局加强版题解考虑动态规划，设\(f_{i,j}\)为经过了\(i\)个村庄，正在建第\(j\)个邮局的最优距离。以及\(w_{i,j}\)表示区间\([i,j]\)内建一个邮局时的距离总和。\(a\)数组表示每个村庄的坐标编号。朴素版状态转移方程：\[f_{i,j}=\min(f_{i,j},f_{k,j......
- 07-25 题解
07-25题解原题出处（按顺序）：CF1556ECF1234FP9746CF1316EP3651CF17CCF1842HA转化：括号序列如果\(a_i\>b_i\)，则有\(a_i-b_i\)个左括号如果\(a_i\<b_i\)，则有\(b_i-a_i\)个右括号（第一个+1的位置一定在第一个-1的位置的左侧，所以情况一用左括号......
- 第二次测试部分题解 (c,d,g)
c-一个欧拉函数模板题 1#include<iostream>2usingnamespacestd;34intmain()5{6intn;7cin>>n;8intr=n;9for(inti=2;i*i<=n;i++)10{11if(n%i==0)12{13r......
- 第二次测试部分题解
A——暴力枚举计数就好了，可以参考这段代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definemod100003#defineMAN1000100charstr[10];intans;voidok(){ ans=0; intlen=0; for(inti=0;str[i]!='\0';i++) len++; if(l......
- ABC260F 题解
题面根据题目描述，原图为二分图，设两侧点集为\(S,T\)，大小为\(s,t(s\le3\times10^5,t\le3\times10^3)\)。注意到有四元环当且仅当\(T\)中存在一个点对\((a,b)\)同时和\(S\)中的某两个点连边。可以先考虑暴力，一种想法是：考虑枚举\(S\)中的点\(c\)，设和\(c\)连边的点......
- ABC263F 题解
题面注意到把对局在图上表示出来是一颗满二叉树（叶节点为选手，其他点为对局），可以考虑树形dp。设\(x\)为\([l_x,r_x]\)之间选手的比赛，且该节点到叶子结点距离\(d_x\)。设\(f(x,p)\)表示胜者为\(p\)的最大钱数，有转移：\[\begin{aligned}f(x,p)&=f(lson(x),p)+g(rson(x))+a......
- ABC262F 题解
题面把“移动\(a_n\)至数列头”称为rotate，删除一项称为erase。因为要求字典序最小，所以可以逐位贪心。考虑一个数\(a_i\)怎么变成第一个数：使用\(n-i\)次rotate/erase，再rotate一次。删除或移动原来的\(a_{i+1}\sima_n\)，再移动原来的\(a_i\)（逐步移动到数列尾，再ro......
- ABC261F 题解
题面注意到如果两个球\(i,j\)有\(i<j,x_i>x_j\)，那么这两个球一定会交换。所以要交换\(x\)的逆序对数次。但是相同颜色交换没有代价，所以答案是\(x\)的逆序对数减去满足\(c_i=c_j,i<j,x_i>x_j\)的\((i,j)\)对的数量。可以对每个\(j\)都求一遍满足\(c_i=j\)的\(......
- ABC264F 题解
题面注意到操作只对当前行/列有效，所以只要记录当前所在行和列是否有被操作。设\(f(i,j,x,y)\)表示到了位置\((i,j)\)，第\(i\)行是否被操作，第\(j\)列是否被操作的最小代价。转移：设\(col=c(i,j)\oplusx\oplusy\)。\[\begin{aligned}f(i+1,j,x2,y)&\xleftarrow......